Elimination
A fundamental step to solving systems of equations with linear algebra is elimination. This is also called Gaussian elimination or Gauss–Jordan elimination.
Contents
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 0 as there is already a 0 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 called the upper triangle matrix for square (n by n) matrices, but more generally and formally is called the row echelon form of A.
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
A matrix can be further reduced with backwards elimination. This means to repeat elimination in the opposite direction until all numbers above and below the pivots are zero. This yields the reduced row echelon form of A, called R.
Failure of Elimination
Elimination is the process to transform A -> U, where U must have n non-zero pivots for n unknowns.
If the equations align such that a pivot would be 0, you have temporary failure. Re-align the equations and re-eliminate.
If the equations cannot be re-aligned to solve, you have permanent failure