Module

for

Row Reduced Echelon Form

     

Background

    An important technique for solving a system of linear equations  [Graphics:Images/EchelonFormMod_gr_1.gif]  is to form the augmented matrix  [Graphics:Images/EchelonFormMod_gr_2.gif]and reduce  [Graphics:Images/EchelonFormMod_gr_3.gif]  to reduced row echelon form.  

Definition (Reduced Row Echelon Form).  A matrix is said to be in row-reduced echelon form provided that

(i)    In each row that does not consist of all zero elements, the first non-zero element in this row is a 1.  (called. a "leading 1).  

(ii)    In each column that contains a leading 1 of some row, all other elements of this column are zeros.

(iii)    In any two successive rows with non-zero elements, the leading 1 of the the lower row occurs farther to the right than the leading 1 of the higher row.

(iv)    If there are any rows contains only zero elements then they are grouped together at the bottom.

 

Theorem (Reduced Row Echelon Form).   The reduced row echelon form of a matrix is unique.  

 

Definition (Rank).   The number of nonzero rows in the reduced row echelon form of a matrix  [Graphics:Images/EchelonFormMod_gr_4.gif]  is called the rank of   [Graphics:Images/EchelonFormMod_gr_5.gif] and is denoted by   [Graphics:Images/EchelonFormMod_gr_6.gif].   

 

Theorem.   Consider the  m × n  linear system  [Graphics:Images/EchelonFormMod_gr_7.gif],  where [Graphics:Images/EchelonFormMod_gr_8.gif] is the augmented matrix.  

(i)    If   [Graphics:Images/EchelonFormMod_gr_9.gif]  then the system has a unique solution.  

(ii)    If   [Graphics:Images/EchelonFormMod_gr_10.gif]  then the system has an infinite number of solution.  

(iii)    If   [Graphics:Images/EchelonFormMod_gr_11.gif]  then the system is inconsistent and has no solution.  

Proof  Row Reduced Echelon Form  Row Reduced Echelon Form  

 

Computer Programs  Row Reduced Echelon Form  Row Reduced Echelon Form  

Mathematica Subroutine (Complete Gauss-Jordan Elimination).

[Graphics:Images/EchelonFormMod_gr_12.gif]

Example 1.  Solve the linear system of equations  
        [Graphics:Images/EchelonFormMod_gr_13.gif]    
Solution 1.

 

Example 2.  Solve the linear system of equations  
        [Graphics:Images/EchelonFormMod_gr_78.gif]    
Solution 2.

 

Example 3.  Solve the linear system  
        [Graphics:Images/EchelonFormMod_gr_133.gif]  
Solution 3.

 

Example 4.  Solve the linear system  
        [Graphics:Images/EchelonFormMod_gr_252.gif]  
Solution 4.

 

 

Free Variables

    When the linear system is underdetermined, we needed to introduce free variables in the proper location. The following subroutine will rearrange the equations and introduce free variables in the location they are needed.  Then all that is needed to do is find the row reduced echelon form a second time.  This is done at the end of the next example.

Mathematica Subroutine (Under Determined Equations).

[Graphics:Images/EchelonFormMod_gr_336.gif]

Example 5.  Solve the linear system  
        [Graphics:Images/EchelonFormMod_gr_337.gif]    
Solution 5.

 

Research Experience for Undergraduates

Row Reduced Echelon Form  Row Reduced Echelon Form  Internet hyperlinks to web sites and a bibliography of articles.  

 

Download this Mathematica Notebook Row Reduced Echelon Form

 

Return to Numerical Methods - Numerical Analysis

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(c) John H. Mathews 2004