Elimination
Introduction
Consider the below system of equations.
x + 2y + z = 2 3x + 8y + z = 12 4y + z = 2
Algebra
The first step to solving this system is eliminating x. Note that x = 2 - 2y - z (from the first equation) and substitute 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
Matrix Picture
This system can be expressed in the form Ax = b:
┌ ┐ ┌ ┐ ┌ ┐ │ 1 2 1│ │ x│ │ 2│ │ 3 8 1│ │ y│ = │12│ │ 0 4 1│ │ z│ │ 2│ └ ┘ └ ┘ └ ┘
A -> U
The solution lies in the elimination of A.
The first step is identifying a pivot and reducing all below numbers to 0. The pivot in this case is the boxed 1 in the top-left.
┌ ┐ │ [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.
b -> c
To 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│ └ ┘
Ux = c
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.
U -> R
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