Matrix Pattern Tells Solution Set?

Date: 9/4/96 at 1:37:24
From: KATHY H DOAN
Subject: Matrix Pattern Tells Solution Set?

Is there a pattern for reduced row-echelon form matrices that can
differentiate whether the solution set has no solutions, exactly one
solution, or infinitely many solutions?

I want to be able to tell what kind of solution set a reduced row-
echelon matrix has just by looking at it.

For example:  --            --
              |    1 0 0 a   |
              |    0 1 0 b   |
              |    0 0 1 c   |
              --            --

I know that this has infinitely many solutions, but what would 
dependent and inconsistent matrices look like?  Is there a set 
pattern? 

Thanks.
Kathy

Date: 10/18/96 at 18:19:26
From: Doctor Keith
Subject: Re: Matrix Pattern Tells Solution Set?

Hi Kathy,

You are asking some great questions, and yes there is a relation.

I am assuming from your question that you have had some linear 
(matrix) algebra before, so I will give you a quick run-down of what 
and why. For more details I recommend Gilbert Strang, _Linear Algebra 
and its Applications_.  If something I say is confusing or you are not 
sure about it, email your concerns and I will be happy to explain 
further. I am deliberately assuming some knowledge since this is 
usually a semester course in college to deal with this problem and 
methods of solution.  When we are solving a system of linear equations 
of the form of:

Ax=B
   A is a real m by n matrix (m rows and n columns)
   x is a real n by 1 matrix (a column vector with n unknown elements)
   B is a real m by 1 matrix (a column vector with m elements)

for the unknown vector x we need to be concerned with the formulation
of the problem.  That is as you pointed out we could get many 
solutions, one solution or none.

Have you ever heard of the four fundamental spaces?  Knowing what they
are and the relations between them can help you understand and 
remember all the conditions for when you will get a solution, and how 
many you will get.  To answer your question we only need to look at 
two of the spaces (thus saving alot of reading for you and writing for 
me).

  1) Null space of A:  This is basically the set of all vectors z that
     satisfy the equation:
        Az = 0

     Why do we care? Well consider the following:
        Let y = x+z
        then Ay = Ax + Az = Ax = b
        thus if x is a solution then so is y

     In other words we can get infinitely many solutions by adding az 
to x and varying a.  The Null space of A thus controls the possibility 
of infinitely many solutions. For one solution we want no vectors in 
the null space, and for infinitely many solutions we want at least one 
vector in the null space.

     How can you check this using a reduced form as you have?  Well 
you gave me that some matrix say C is:

         C=| 1  0  0  a |
           | 0  1  0  b |
           | 0  0  1  c |

     and that this matrix was reduced from A:

         EA = C  or  A = EinvC  with Einv = inverse of E (which exists
                                  for the elementary matrices used to
                                  calculate C from A)
     thus if Az = 0  and E is invertible then Cz=0

     Now we have a condition based on your reduced matrix.
     So when does Cz=0?  In your example we have 4 columns in C and
     only three rows.  You can verify that there exists one vector
     in the null space, thus there are infinitely many solutions, as
     you mentioned.  Whenever the number of columns exceeds the number
     of rows we will have ambiguity (vectors in the null space), but
     this is not the only condition.  The general condition (which 
     includes this as a special case) is, if the rank of C is less    
     than the number of columns we will have ambiguity.  Well what is 
     rank?  There are a lot of ways of calculating it but in this case 
     here are the three easiest:

        rank(C) = # linearly independant columns of C
                = # linearly independant rows of C
                = # pivots (nonzero elements on the main diagonal)
      the last condition is the easiest in the case you supplied.

      Let's calculate:
        # vectors in the null space of A = # columns - # pivots
                                         = 4 - 3 = 1
      One vector in null space means you  will have infinetly many
      solutions if you have a solution.

   2) The other space you care about is the Range Space of A.  The
      Range of A (as it is often called) is informally a collection
      of all the vectors that can be formed by multiplying a vector
      times A.  What happens when B is not in the Range of A?  Well
      no vector, and that includes x, that multiplies A can produce
      B!  Thus no solution exists.  So in order to get a solution
      we must have B in the Range of A.  So how do we figure this out
      given your reduced matrix C?  Well one relation that is 
      particularly helpful is the Range of A is the space spanned by 
      the linearly independant columns of A.  In english this means 
      that any vector in the Range of A (ie B) can be written as a 
      linear combination of the columns of A.  Thus if you can write 
      it this way you are done. You should be saying about now that 
      while this is cool, it depends on the columns of A, not C.  
      Unfortuneately Range of A is not the Range of C (like we had 
      above with Null of A was the Null of C), but one important 
      relation connects the two.  If the rank of A is equal to the 
      number of rows of A then any B is in the Range of A. Since the 
      rank of A is the rank of C, and we can get the rank of C as 
      described above, we can easily check if any vector B we are  
      given will have a solution by:

          if # rows - # pivots = 0 then a solution exists for any B
      If this does not hold then you are stuck going back to A and
      checking if B can be written as the summ of the columns.  If it 
      can then a solution exists, if not no solution exists.

Summarizing:
    let r= # pivots (non-zero components on main diagonal)
    let m= # rows
    let n= # columns
      r <= m  and r <= n for all matrices

    if r = m (m - r = 0) then a solution exists for all B
    if r < m (m - r > 0)then you must see if B can be written as a 
                               combination of the columns of A
    if r = n (n - r = 0) then any solution is unique
    if r < n (n - r > 0) then if a solution exists then there are
                               infinitely many solutions

I hope this helps. This is fun and a very, very useful area of math
(it is used in engineering, physics, etc all the time) and you will
be well ahead of the game if you understand it.  I know I rushed it
but I was trying to strike a balance between meeting the need with
some understanding of what is going on, and typing you a textbook.
Let me know if you want something further explained, I love to talk
about this field in particular.

-Doctor Keith,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/