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 Wilhelm Jordan (1842 to 1899).  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.

Proof  Gauss-Jordan Elimination and Pivoting  Gauss-Jordan Elimination and Pivoting  

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.  

Proof  Gauss-Jordan Elimination and Pivoting  Gauss-Jordan Elimination and Pivoting  

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 .  

Proof  Gauss-Jordan Elimination and Pivoting  Gauss-Jordan Elimination and Pivoting  

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  .

Computer Programs  Gauss-Jordan Elimination and Pivoting  Gauss-Jordan Elimination and Pivoting  

Mathematica Subroutine (Limited Gauss-Jordan Elimination).

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

Example 2. Interchange rows 2 and 3 and try to use the Gauss-Jordan subroutine to solve .  
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.  

Computer Programs  Gauss-Jordan Elimination and Pivoting  Gauss-Jordan Elimination and Pivoting  

Mathematica Subroutine (Complete Gauss-Jordan Elimination).

Example 3. Use the improved Gauss-Jordan elimination subroutine with row interchanges to solve .  
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 .       

Proof  The Inverse Matrix  The Inverse Matrix  

Example 5. Use Gauss-Jordan elimination to find the inverse of the matrix  .
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.  

Computer Programs  Gauss-Jordan Elimination and Pivoting  Gauss-Jordan Elimination and Pivoting  

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.

Application to Polynomial Interpolation

    Consider a polynomial of degree n=5 that passes through the six points ;  

        .

For each point    is used to an equation  ,  which in turn are used to write a system of six equations in six unknowns    

        

						=
						=
						=
						=
						=
						=

The above system can be written in matrix form  MC = B  

        

Solve this linear system for the coefficients     and then construct the interpolating polynomial

        .  

Example 6. Find the polynomial  p[x]  that passes through the six points    using the following steps.
(a). Write down the linear system MC = B to be solved.
(b). Solve the linear system for the coefficients using our Gauss-Jordan subroutine.
(c). Construct the polynomial  p[x].
Solution 6.

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.  

Download this Mathematica Notebook Gauss-Jordan Elimination

Return to Numerical Methods - Numerical Analysis

(c) John H. Mathews 2004