Rank of Matrices and Linear Systems

Author :  Thomas Shores
University of Nebraska
Send comments to :  tshores@math . unl . edu

Matrices, Reduced Forms, and Solutions of Linear Systems

DEFINITION:  A  matrix  R  is said to be in row echelon form  if
   (1)  The nonzero rows of  R  precede the zero rows.
  (2)   The column numbers of  the leading entries of  the nonzero rows of   R  , say rows 1, 2, ... r,  form an increasing sequence of numbers  c1 < c2 < .... < cr .
  (3)   Each leading entry of   R   has only zeros below it.
The matrix   R   is in  reduced row echelon form  if, in addition to the above, 
  (4)  Each leading entry of   R   is 1.
  (5)  Each leading entry of   R  has only zeros above it.
  
Gaussian Elimination has the goal of reaching row echelon form, then backsolving.   But  Gauss -Jordan Elimination has the goal of reaching reduced row echelon form.  One of the differences between the forms is that a matrix can have more than one row reduced form.  But  it is a remarkable fact that every matrix has one and only one row echelon form.  That is the content of the following 
  
KEY FACT:  Every matrix can be reduced by a sequence of elementary row operations to
                      ONE AND ONLY ONE reduced row echelon form.
  
Once we have this  fact, we can define the very useful idea of rank of a matrix:

DEFINITION:   The rank of a matrix is the number of nonzero rows in the Row  Echelon
                           Form of the matrix.  This number is written  as  rank(A).

Here is a simple fact that we can deduce right away from this definition:

FACT:   Let  A  be an  m×n  matrix.   Then  rank(A) ≤  Min[ m, n].

 Mathematica will find the Row Echelon Form for us automatically, from which we can read off the rank of A:

a = {{1,1,2},{2,2,5},{3,3,7}}

MatrixForm[a]

r = RowReduce[a]

MatrixForm[r]

Try substituting some different matrices for the matrix a  in the above cell.  In  particular, build a  5×3 matrix and calcualte its  Row Echelon Form and rank.

Actually, we have seen from earlier discussion that the following key fact  is true:

KEY FACT:  The linear system (LS) with coefficient matrix A and right hand side vector b is 
                         consistent  iff rank A  = rank [A | b], in which case either:
     (1) rank A = n (number of unknowns of (LS)), in which case (LS) has a unique solution, or   
     (2) rank A < n, in which case (LS) has an infinite number of solutions.
	
REMARK:  Note the consistency condition simply says that the system is consistent exactly when no pivot occurs in the last column of the augmented matrix.  Moreover, if the system is consistent,  n - rank A is exactly the number of free variables of the system, so that (1) and (2) say that there is a unique solution when there are no free variables, and infinitely many solutions otherwise.
	Let's see how Mathematica will handle the system with coefficient  matrix and right hand side as follows:

a = {{1,1,1},{2,2,4},{0,0,1}}

b = {2,8,2}

LinearSolve[a,b]

Conclusion?  Get another view of things by doing the Row Echelon Form of the augmented matrix.  Click on the next two cells:

aa={{1,1,1,2},{2,2,4,8},{0,0,1,2}}

MatrixForm[aa]

MatrixForm[RowReduce[aa]]

Try LinearSolve on the following example (also from the lecture):

a = {{1,1,1},{1,1,2},{1,1,0}}

b = {2,4,2}

LinearSolve[a,b]

Exercise

Determine the solvability of the following systems  using (a) the row echelon form and (b) a direct Mathematica function:

1)     5 x + 3 y - 4 z  = 0
           x  -    y  +  z  = 5
         3 x + 2 y + 9 z = -1
         
2)      x + 2 y + 3 z  =  4
       4 x + 5 y + 6 z =  7
       7 x + 8 y  + 9 z = 10
          x  -    y  +   z  = 0       
          
3)     6 a + 5 b -    c   = 5
           a + 2 b + 3 c  = 5 
         3 a -   b  - 10 c = -8