Module

for

Homogeneous Linear Systems

     

Background

    
We have seen how Gaussian elimination can be used to obtain the reduced row echelon form of a matrix and the solution of a linear system
  [Graphics:Images/HomogenLinSystemMod_gr_1.gif].  Now we consider the special case of solving a homogeneous linear
system where the column vector is
  [Graphics:Images/HomogenLinSystemMod_gr_2.gif].

(1)        [Graphics:Images/HomogenLinSystemMod_gr_3.gif]     

    which can be written in matrix form
  
        
        [Graphics:Images/HomogenLinSystemMod_gr_4.gif].

At first glance it seems that the solution to (1) should be
[Graphics:Images/HomogenLinSystemMod_gr_5.gif],  and certainly this is the case.  Since it was easy to come up with, [Graphics:Images/HomogenLinSystemMod_gr_6.gif], it is called the "trivial solution,"  and if  [Graphics:Images/HomogenLinSystemMod_gr_7.gif], then it is the unique solution.  What makes the solution to (1) interesting is the case when [Graphics:Images/HomogenLinSystemMod_gr_8.gif]  and if this happens there is an infinite number of solutions.  
    

    An important technique for solving a homogeneous system of linear equations  [Graphics:Images/HomogenLinSystemMod_gr_9.gif]  is to form the augmented matrix  [Graphics:Images/HomogenLinSystemMod_gr_10.gif]and reduce  [Graphics:Images/HomogenLinSystemMod_gr_11.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.

 

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

 

Lemma.   Consider the  m × n  homogeneous linear system  [Graphics:Images/HomogenLinSystemMod_gr_15.gif],  where [Graphics:Images/HomogenLinSystemMod_gr_16.gif] is the augmented matrix then  [Graphics:Images/HomogenLinSystemMod_gr_17.gif].

 

Theorem.   Consider the  n × n  homogeneous linear system  [Graphics:Images/HomogenLinSystemMod_gr_18.gif].  

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

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

 

When the matrix  [Graphics:Images/HomogenLinSystemMod_gr_22.gif],  is an  n × n,  square matrix, then the determinant can be used to express these ideas.

 

Theorem.   Consider the  n × n  homogeneous linear system  [Graphics:Images/HomogenLinSystemMod_gr_23.gif].  

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

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

Proof  Homogeneous Linear Systems  Homogeneous Linear Systems  

 

Computer Programs  Homogeneous Linear Systems  Homogeneous Linear Systems  

Mathematica Subroutine (Complete Gauss-Jordan Elimination).

[Graphics:Images/HomogenLinSystemMod_gr_27.gif]

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

 

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

 

Example 3.  Solve the homogeneous linear system of equations  
        [Graphics:Images/HomogenLinSystemMod_gr_200.gif]  
Solution 3.

 

 

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/HomogenLinSystemMod_gr_275.gif]

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

 

 

Application to Chemistry

    
Propane is used to reduce automobile emissions.  Consider the chemical equation which relates how propane molecules (
[Graphics:Images/HomogenLinSystemMod_gr_365.gif])  combine with oxygen atoms ([Graphics:Images/HomogenLinSystemMod_gr_366.gif]) to form carbon dioxide ([Graphics:Images/HomogenLinSystemMod_gr_367.gif]) and water ([Graphics:Images/HomogenLinSystemMod_gr_368.gif]):
    
            
[Graphics:Images/HomogenLinSystemMod_gr_369.gif]  

When a chemist wants to "balance this equation," whole numbers  [Graphics:Images/HomogenLinSystemMod_gr_370.gif]  must be found so that the number of atoms of carbon (C), hydrogen (H) and oxygen (O) on the left match their respective number on the right.  To balance the equation, write three equations which keep track of the number of carbon, hydrogen and oxygen atoms, respectively.

        [Graphics:Images/HomogenLinSystemMod_gr_371.gif]     

The next example shows how to solve this system.

 

Example 5.  Balance the propane-oxygen equation by solve the homogeneous linear system
        [Graphics:Images/HomogenLinSystemMod_gr_372.gif]
Solution 5.

 

Research Experience for Undergraduates

Homogeneous Linear Systems  Homogeneous Linear Systems  Internet hyperlinks to web sites and a bibliography of articles.  

 

Download this Mathematica Notebook Homogeneous Linear Systems

 

Return to Numerical Methods - Numerical Analysis

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(c) John H. Mathews 2004