Module for Gauss-Jordan Elimination

Check out the new Numerical Analysis Projects page.

    In this module we develop a algorithm for solving a general linear system of equations consisting of n equations and n unknowns where it is assumed that the system has a unique solution.  The method is attributed Johann Carl Friedrich Gauss (1777-1855) and Marie Ennemond Camille Jordan (1838-1922).  The following theorem states the sufficient conditions for the existence and uniqueness of solutions of a linear system .  

Theorem (Unique Solutions) Assume that is an matrix.  The following statements are equivalent.

     (i) Given any matrix , the linear system has a unique solution.
     
    (ii) The matrix is nonsingular (i.e., exists).
    
   (iii) The system of equations has the unique solution .  
   
   (iv) The determinant of is nonzero, i.e. .  

    It is convenient to store all the coefficients of the linear system in one array of dimension .  The coefficients of are stored in column of the array (i.e. ).  Row contains all the coefficients necessary to represent the equation in the linear system. The augmented matrix is denoted and the linear system is represented as follows:

           

    The system , with augmented matrix , can be solved by performing row operations on .  The variables  are placeholders for the coefficients and cam be omitted until the end of the computation.

Theorem (Elementary Row Operations). The following operations applied to the augmented matrix yield an equivalent linear system.

     (i) Interchanges:    The order of two rows can be interchanged.  
     
    (ii) Scaling:       Multiplying a row by a nonzero constant.
    
   (iii) Replacement:    Row r can be replaced by the sum of that tow and a nonzero multiple of any other row;
                               that is:  .      

    It is common practice to implement (iii) by replacing a row with the difference of that row and a multiple of another row.  

Definition (Pivot Element). The number in the coefficient matrix that is used to eliminate where , is called the pivot element, and the row is called the pivot row.      

Theorem (Gaussian Elimination with Back Substitution). Assume that is an nonsingular matrix. There exists a unique system that is equivalent to the given system , where is an upper-triangular matrix with for .  After   are constructed, back substitution can be used to solve for .  

Algorithm I. (Limited Gauss-Jordan Elimination).  Construct the solution to the linear system    by using Gauss-Jordan elimination under the assumption that row interchanges are not needed.  The following subroutine uses row operations to eliminate    in column  p  for  .

Mathematica Subroutine (Limited Gauss-Jordan Elimination).

Example 1. Use the Gauss-Jordan elimination method to solve the linear system  .  
Use the menu "Input" then submenu "Create Table/Matrix/Palette" to enter matrices A and M and vector B.
Solution 1.

Example 2. Interchange rows 2 and 3 and try to use the Gauss-Jordan elimination subroutine to solve the linear system  .  
Use lists in the subscript to select rows 2 and 3 and perform the row interchange.
Solution 2.

Provide for row interchanges in the Gauss-Jordan subroutine.

Add the following loop that will interchange rows and perform partial pivoting.

To make these changes, copy your subroutine GaussJordan and place a copy below. Then you can copy the above lines by selecting them and then use the "Edit" and "Copy" menus. The improved Gauss-Jordan subroutine should look like this (blue is for placement information only).  Or just use the active Mathematica code given below.

Algorithm II. (Complete Gauss-Jordan Elimination).  Construct the solution to the linear system    by using Gauss-Jordan elimination.  Provision is made for row interchanges if they are needed.  

Mathematica Subroutine (Complete Gauss-Jordan Elimination).

Example 3. Use the improved Gauss-Jordan elimination subroutine with row interchanges to solve the linear system  .  
Use the matrix A and vector B in example 2.
Solution 3.

Example 4. Use the Gauss-Jordan elimination method to solve the linear system  .  
Solution 4.

Use the subroutine "GaussJordan" to find the inverse of a matrix.

Theorem (Inverse Matrix) Assume that is an nonsingular matrix. Form the augmented matrix of dimension  .  Use Gauss-Jordan elimination to reduce the matrix so that the identity is in the first columns.  Then the inverse is located in columns .      
 

Example 5. Use Gauss-Jordan elimination to find the inverse of the matrix  A.
Enter the matrix  A  and create a 4 by 4 identity matrix and store it in the variable Iden.
Solution 5.

Algorithm III. (Concise Gauss-Jordan Elimination).  Construct the solution to the linear system    by using Gauss-Jordan elimination.  The print statements are for pedagogical purposes and are not needed.  

Mathematica Subroutine (Concise Gauss-Jordan Elimination).

Remark. The Gauss-Jordan elimination method is the "heuristic" scheme found in most linear algebra textbooks.  The line of code
        
divides each entry in the pivot row by its leading coefficient .  Is this step necessary?  A more computationally efficient algorithm will be studied which uses upper-triangularization followed by back substitution.  The partial pivoting strategy will also be employed, which reduces propagated error and instability.

Old Lab Project (Gauss-Jordan Elimination  Gauss-Jordan Elimination).  Internet hyperlinks to an old lab project.  

Research Experience for Undergraduates

Gauss-Jordan Elimination and Pivoting  Gauss-Jordan Elimination and Pivoting  
Internet hyperlinks to web sites and a bibliography of articles.  
 

Downloads (Gauss Jordan Elimination Gauss Jordan Elimination).  
Download this Mathematica notebook.  

(c) John H. Mathews 2003