Elimination

Gaussian elimination or Gauss-Jordan elimination is a foundational process for solving systems of linear equations.

Elimination can be generalized as the process of transforming an unsolvable Ax = b into a solvable Ux = c.

Introduction

Consider the below system of equations.

x + 2y + z = 2
3x + 8y + z = 12
4y + z = 2

The first step to solving this system with traditional algebra is eliminating x.

Trivially rewrite the first equation:

x + 2y + z = 2
x = 2 - 2y - z

Substitute this into the second equation:

3x + 8y + z = 12
3(2 - 2y - z) + 8y + z = 12
6 - 6y - 3z + 8y + z = 12
2y - 2z = 6

Now x has been eliminated. But can either y or z be eliminated the same way?

Linear Algebra

This system can be expressed in the form Ax = b:

    A      x  =   b

┌      ┐ ┌  ┐   ┌  ┐
│ 1 2 1│ │ x│   │ 2│
│ 3 8 1│ │ y│ = │12│
│ 0 4 1│ │ z│   │ 2│
└      ┘ └  ┘   └  ┘

Eliminating A

The solution lies in the elimination of A.

The first step is identifying pivots. By reducing the entire column to zeros and the pivot, it is eliminated into a pivot column.

Pivots are noted with boxes or circles in the matrix, as in:

┌        ┐
│ [1] 2 1│
│  3  8 1│
│  0  4 1│
└        ┘

Algebraically, a value is being zeroed out by expressing that variable in terms of the other equations.

Literally, we are subtracting a multiple of the pivot row from the targeted row to create a zero below the pivot. That multiple is discovered by solving part of the equation.

┌  ┐    ┌  ┐   ┌  ┐
│ 3│    │ 1│   │ 0│
│ 8│ - m│ 2│ = │ ?│
│ 1│    │ 1│   │ ?│
└  ┘    └  ┘   └  ┘

3 - 1m = 0
     m = 3

┌  ┐    ┌  ┐   ┌   ┐
│ 3│    │ 1│   │  0│
│ 8│ - 3│ 2│ = │  2│
│ 1│    │ 1│   │ -2│
└  ┘    └  ┘   └   ┘

This process is then repeated for every row below. In this specific problem the multiple is zero as there is already a zero in place.

┌  ┐    ┌  ┐   ┌  ┐
│ 0│    │ 1│   │ 0│
│ 4│ - m│ 2│ = │ ?│
│ 1│    │ 1│   │ ?│
└  ┘    └  ┘   └  ┘

0 - 1m = 0
     m = 0

┌  ┐    ┌  ┐   ┌  ┐
│ 0│    │ 1│   │ 0│
│ 4│ - 0│ 2│ = │ 4│
│ 1│    │ 1│   │ 1│
└  ┘    └  ┘   └  ┘

The matrix is reconstructed:

┌         ┐
│ [1] 2  1│
│  0  2 -2│
│  0  4  1│
└         ┘

The process is then repeated with a new pivot.

If a pivot is zero, rows should be swapped using permutation matrices. If all rows are zero, then this is a free column (as opposed to a pivot column) and should be skipped.

In this specific problem we do have another pivot.

┌           ┐
│ [1]  2   1│
│  0  [2] -2│
│  0   4   1│
└           ┘

Another iteration of elimination yields this matrix, U.

┌           ┐
│[1]  2   1 │
│ 0  [2] -2 │
│ 0   0  [5]│
└           ┘

U is the row echelon form of A. It may also be a upper triangular matrix.

Balancing the Right Hand Side

To re-balance the original equation, replicate the subtractions on b. Recall that the (non-zero) multipliers were 3 and 2:

┌  ┐
│ 2│
│12│
│ 2│
└  ┘

12 - 2m
12 - 2(3)
6

┌  ┐
│ 2│
│ 6│
│ 2│
└  ┘

2 - 6m
2 - 6(2)
-10

┌   ┐
│  2│
│  6│
│-10│
└   ┘

Result of Elimination

The system has been reduced to Ux = c:

┌           ┐ ┌  ┐   ┌   ┐
│[1]  2   1 │ │ x│   │  2│
│ 0  [2] -2 │ │ y│ = │  6│
│ 0   0  [5]│ │ z│   │-10│
└           ┘ └  ┘   └   ┘

x + 2y + z = 2
2y + 2z = 6
5x = -10

Algebraic substitution can now be used to solve; x=2, y=1, z=-2.

Simplification with Augmented Matrices

Instead of eliminating A then re-balancing b, eliminate the augmented matrix in a single step.

Augmented matrix = [   A    b]

                   ┌         ┐
                   │ 1 2 1  2│
Augmented matrix = │ 3 8 1 12│
                   │ 0 4 1  2│
                   └         ┘

Elimination proceeds the exact same way.

┌          ┐
│[1] 2 1  2│
│ 3  8 1 12│
│ 0  4 1  2│
└          ┘
┌            ┐
│[1]  2   1 2│
│ 0  [2] -2 6│
│ 0   4   1 2│
└            ┘
┌               ┐
│[1]  2   1    2│
│ 0  [2] -2    6│
│ 0   0  [5] -10│
└               ┘

Which can be re-expressed as:

┌           ┐ ┌  ┐   ┌   ┐
│[1]  2   1 │ │ x│   │  2│
│ 0  [2] -2 │ │ y│ = │  6│
│ 0   0  [5]│ │ z│   │-10│
└           ┘ └  ┘   └   ┘

Note that this matches the reduced system that was achieved above.

Reduced Row Echelon Form

U can be further reduced with backwards elimination. Repeat the process in the opposite direction until all numbers above and below the pivots are zero, yielding the matrix R.

R is the reduced row echelon form of A. It may also be a lower triangular matrix.

Failure of Elimination

U must have n non-zero pivots for n unknowns.

As noted above, if a pivot is zero, rows should be swapped using permutation matrices. This is a temporary failure.

If rows cannot be swapped to complete elimination, the system has permanent failure. The matrix must then be non-invertible.

CategoryRicottone