**for**

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