1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proving homogeneous systems of linear equations have infinite solutions

  1. Sep 2, 2010 #1
    Proving a linear system of equations cannot have more than one finite solutions

    1. The problem statement, all variables and given/known data

    Prove that the number of solutions to a linear system can not be a finite number larger than one. Provide either a general proof or for a system with two equations and two unknowns.

    2. Relevant equations

    It is mostly simple algebra.

    3. The attempt at a solution

    Assume the following:
    [tex]a_{11}x_{1}+a_{12}x_{2}=b_{1}[/tex] NOTE: If the tex messed up, this reads a11 * x1 + a12 * x2 = b1
    [tex]a_{21}x_{1}+a_{22}x_{2}=b_{2}[/tex] and a21 * x1 + a22 * x2 = b2

    There exists two unique solution sets to the system: {[tex]c_{1}[/tex], [tex]c_{2}[/tex]} (NOTE: this reads {c1, c2}) and {[tex]d_{1}[/tex], [tex]d_{2}[/tex]} are solutions, and [tex]c_{1} \neq d_{1}[/tex], [tex]c_{2} \neq d_{2}[/tex].

    .:.

    [tex]a_{11}c_{1}+a_{12}c_2}=b_{1}=a_{11}d_{1}+a_{12}d_2}[/tex]
    [tex]a_{21}c_{1}+a_{22}c_2}=b_{2}=a_{21}d_{1}+a_{22}d_2}[/tex]

    =>

    [tex]a_{11} \left( c_{1}-d_{1} \right) + a_{12} \left( c_{2}-d_{2} \right) =0[/tex]
    [tex]a_{21} \left( c_{1}-d_{1} \right) + a_{22} \left( c_{2}-d_{2} \right) =0[/tex]

    Therefore, the system is now homogenous. It should be easy enough to generalize to an nxn system of equations. Also, I could generalize it to x number of solutions by showing that any two of the potential solutions subtracted by each other would yield a homogenous system.

    Suppose [tex]f_{1}=c_{1}-d_{1}[/tex], [tex]f_{2}=c_{2}-d_{2}[/tex]

    .:.

    [tex]a_{11}f_{1}+a_{12}f_{2}=0[/tex]
    [tex]a_{21}f_{2}+a_{22}f_{2}=0[/tex]

    [tex]f_{1}=-\frac{a_{12}}{a_{11}}f_{2}[/tex]
    [tex]a_{21} \left( \frac{-a_{12}}{a_{11}} f_{2} \right) + a_{22}f_{2} = \left( a_{22} - \frac{a_{12}a_{21}}{a_{11}} \right) f_{2} = 0[/tex]

    Now, there are two possibilities:

    1.) [tex]f_{2}=f_{1}=0[/tex] ergo [tex]c_{1}=d_{1}[/tex] and [tex]c_{2}=d_{2}[/tex], which is a CONTRADICTION

    2.) [tex]a_{11}a_{22} - a_{21}a_{12} = 0[/tex] ergo det(a)=0

    Now, how should I prove that a homogeneous linear system of equations whose coefficient matrix has a determinant of zero has infinite solutions?

    Furthermore, how should I go about generalizing the problem to an arbitrary number of equations, unknowns and solutions? It should be easy to show that the difference of any two of a given x solutions to an nxn linear system of equations results in a homogeneous system. However, I am unsure of how to state that symbolically. Furthermore, I am a little unclear on how I should generalize the proof that the determinant of the coefficient matrix must be zero.
    1. The problem statement, all variables and given/known data



    2. Relevant equations



    3. The attempt at a solution
     
  2. jcsd
  3. Sep 2, 2010 #2

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You're on the right track but it helps to look at the situation strictly from a linear algebra point of view:

    The idea is that if your coefficient matrix is A, then A if Ax=b has two solutions for x, A must have a non-trivial kernel (Ay=0 is solved by vectors other than 0). This is pretty much what you did here, but can be seen more easily by noting that if x and w are solutions

    Ax=b
    Aw=b
    0=b-b=Ax-Aw=A(x-w)

    and x-w is not zero

    And now the question is why are there infinite vectors y that make Ay=0 if there is one non-zero one?
     
  4. Sep 2, 2010 #3

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    I don't have time to respond to all of this now, so I will leave that to someone else or see if I can reply tomorrow.
    But let me just help you out with this little bit, maybe it will inspire you to solve the rest.

    Suppose that the determinant is indeed zero. Then equation (2) above is automatically satisfied (I'll leave the case where a11 = 0 to you).
    But actually equation (2) is supposed to fix f2, so that is now free to be any number you like. Then from equation (1) there follows a corresponding value for f1. So the number of solutions is equal to the number of real numbers (to be more precise, the cardinality of the solution set equals that of R) which is (uncountably) infinite.

    By the way, what is often done in linear algebra is to write the system of equations in matrix form. Let f = (f1, f2) be the solution vector, b = (b1, b2) the right-hand side, and A the matrix of coefficients. Then the equations can be written as Af = b. The solution is obviously given by getting rid of the matrix, f = A-1b, of course under the condition that A-1 exists (which relates to the determinant how? *wink*)
     
  5. Sep 2, 2010 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    A more general, more abstract, proof is to show that the set of all solutions to Ax= 0 (for A a linear transformation or matrix) forms a subspace of the domain of A.

    Specifically, if u and v both satisfy Au= 0 and Av= 0, then [itex]A(\alpha u+ \beta v)= \alpha Au+ \beta Av= 0[/itex] for all scalars [itex]\alpha[/itex] and [itex]\beta[/itex].

    It then follows that that subspace either
    1) has dimension 0: is only the 0 vector
    2) has dimension greater than 0, in which case it contains an infinite number of vectors.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proving homogeneous systems of linear equations have infinite solutions
Loading...