= 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 '''''A'''x = b'' into a solvable '''''U'''x = c''.

<<TableOfContents>>

-----



== 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 '''''A'''x = 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 [[LinearAlgebra/SpecialMatrices#Permutation_Matrices|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 [[LinearAlgebra/SpecialMatrices#Upper_Triangular_Matrices|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 '''''U'''x = 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 [[LinearAlgebra/SpecialMatrices#Lower_Triangular_Matrices|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 [[LinearAlgebra/SpecialMatrices#Permutation_Matrices|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 [[LinearAlgebra/MatrixProperties#Invertible|non-invertible]].



----
CategoryRicottone