Simon Willison’s Weblog

Gauss Jordan Elimination

Gauss-Jordan Elimination

The steps of the Gauss-Jordan elimination process are as follows:

1. Input augmented matrix A
2. Get the reduced echelon form for A using elementary row operations. This is done by first creating leading 1s, then ensuring that columns containing leading 1s have only 0s above and below the leading 1, column by column starting with the first column.
3. The matrix in reduced echelon form will either give the solution or demonstrate that there is no solution.

Two matrices A and B are row equivalent if A =>* B by elementary row operations. During the process of Gauss-Jordan elimination all matrices are row equivalent to the original and each other.

Example

 x1 + 2x2 + x3 =  1
2x1 + 4x2 - x3 = -1

[ 1   2   1   1 ]    [ 1   2   1   1 ]
[ 2   4  -1  -1 ] => [ 0   0  -3  -3 ] R2 := R2 - 2R1

[ 1   2   1   1 ]
[ 0   0   1   1 ] R2 := R2 / -3

To fix column 3:

[ 1   2   0   0 ] R1 := R1 - R2
[ 0   0   1   1 ] (this is in reduced echelon form)

So...

x1 = -2x2
x2 = anything
x3 = 1

The system has many solutions.

In general, any columns without a leading one of them correspond to a variable that can be any value.

The difficult part of Gauss-Jordan elimination is the bit in the middle—deciding which columns to manipulate and how to convert them in to leading 1s. Consider a matrix A_{n x m} in the middle of the computation. Some number i_l of rows have leading 1s in them and some number j of columns have been processed. j ≥ i_l

    [ a1 ... a1m   b1 ]
A = [ ...            ]
    [ an ... anm   bn ]

The matrix now looks like this:

                               j
   0   0  ...  0   1   0  ...  0  ...  
    ...
il 0   0  ...  0   0   0  ...  1  ...
    ...
   0   0  ...  0   0   0  ...

Next step: Increment j. Look in column j for a_oj ≠ 0, with i > i_l—now interchange row i and row i_l + 1 (if nothing found, move on to next columns. Create a leading 1, then reduce column j.

Pseudo code for Gauss-Jordan elimination

il = 0 (number of leading 1s created)
for j = 1 ... m do:
    if ∃ i > il such that aij ≠ 0 then:
        il = il + 1
        interchange row i and row il (this brings the new row
          just below the row you have just done)
        divide row i by ailj creating a leading 1
        Reduce all other entries in the column to 0

Complexity

Suppose A is n x m. We can measure complexity by the number of +, -, *, / operations that are carried out. To do this we look at the pseudo code. If we run the main loop m times:

• The interchange operation takes 2m operations
• Dividing row i by a_ilj takes m-j operations
• The reduce other entries bit takes nm operations

So the complexity of the operation is O(mnm) or O(nm²)

Additional Resources

• Wikipedia has an excellent explanation of Gauss-Jordan Elimination
• The Gauss-Jordan elimination game is a javascript puzzle
• This page explains the Gauss-Jordan algorithm in a bit more depth

Homogeneous Systems

A system of linera equations is homogeneous if all of the constant terms are 0. For example:

3x1 + 2x2 = 0
 x1 -  x2 = 0

A homogeneous system in n variables always has the trivial solution x₁ = x₂ = ... = 0—so there is no chance that the system will have no solutions, reducing the possible outcomes from three to two.

Theorem

A homogeneous system with more unknowns than equations always has many solutions

Proof

Suppose the system has n equations with m unknowns, and m > n.

Let A = the augmented matrix

Find R = reduced echelon form of A using Gauss-Jordan elimination.

         m
  1 . . . . . . .
  0 1 . . . . . .
n 0 0 1 . . . . .
  0 0 0 1 . . . .
  0 0 0 0 1 . . .

R has ≤ n leading 1s, so at least m-n of the variables can take any value. This shows that there are many solutions.

Example

x1 + 2x2 + x3 = 0
      x2 - x3 = 0

This is the intersection of two planes through the origin in 3D space.

Matrix notation for a system of equations

[ a11x1 + ... + a1mxm = b1 ]
[  ...                   ] can be written as AX = B
[ an1x1 + ... + anmxm = bn ]

    [ a1  ... a1m ]
A = [  ...       ]
    [ an1 ... anm ]

    [ x1 ]      [ b1 ]
X = [ .  ]  B = [    ]
    [ xn ]      [ bn ]