Gaussian elimination

Gaussian elimination is the reference algorithm for solving a system of any size. It is mechanical, it never goes wrong, and it is what every computer applies.

The idea: simplify without changing the solutions

Three operations, called elementary, turn a system into another one with exactly the same solutions:

1. swap two rows                            R2 <-> R3
2. multiply a row by a non-zero number      R2 <- 3 R2
3. add a multiple of one row to another     R3 <- R3 - 2 R1

Each is reversible: you can go back, so nothing is lost or added. The goal is to reach row echelon form — a staircase of zeros — where the solutions can be read off immediately.

The table of coefficients

We no longer write the unknowns, only the numbers, in a table called the augmented matrix:

{ x + 2y +  z =  8            [ 1   2   1 |  8 ]
{ 2x + 5y + 3z = 21    -->    [ 2   5   3 | 21 ]
{ -x +  y + 2z =  3           [-1   1   2 |  3 ]
                                ^   ^   ^    ^
                                x   y   z   right-hand side

Going down: creating the zeros

We pick the pivot — the first non-zero coefficient of the row, here the 1 in the top left corner — and use it to cancel everything below it in its column.

[ 1   2   1 |  8 ]                    [ 1   2   1 |  8 ]
[ 2   5   3 | 21 ]  R2 <- R2 - 2R1    [ 0   1   1 |  5 ]
[-1   1   2 |  3 ]  R3 <- R3 + R1     [ 0   3   3 | 11 ]

then with the pivot 1 of the second row:

                                      [ 1   2   1 |  8 ]
                    R3 <- R3 - 3R2    [ 0   1   1 |  5 ]
                                      [ 0   0   0 | -4 ]

The staircase is complete. Read the last row: 0x + 0y + 0z = -4, that is 0 = -4. Impossible. This system has no solution: the planes have no common point.

A case that works out

Take the same system, but with a different third equation: -x + y + 4z = 13.

[ 1   2   1 |  8 ]                    [ 1   2   1 |  8 ]
[ 2   5   3 | 21 ]  R2 <- R2 - 2R1    [ 0   1   1 |  5 ]
[-1   1   4 | 13 ]  R3 <- R3 + R1     [ 0   3   5 | 21 ]

                    R3 <- R3 - 3R2    [ 0   0   2 |  6 ]

Here the last row says 2z = 6, so z = 3. We then climb back up the staircase:

row 3 :  z = 3
row 2 :  y + z = 5      ->  y = 5 - 3 = 2
row 1 :  x + 2y + z = 8 ->  x = 8 - 4 - 3 = 1

Unique solution: (x ; y ; z) = (1 ; 2 ; 3)

This second phase is called back substitution.

Why this is the right method

Gaussian elimination is systematic: there is no clever choice to make, you just follow the procedure. Its computational cost grows like n^3 for n unknowns, which stays reasonable; it is still the basis of scientific computing libraries today.

In practice the pivot chosen is often the coefficient of largest absolute value in the column (partial pivoting): dividing by a very small number amplifies the computer's rounding errors.

Summary

• Three elementary operations preserve the solution set.
• We work on the augmented matrix, without rewriting the unknowns.
• Forward phase: create zeros below each pivot until row echelon form.
• Back substitution: read the unknowns from bottom to top.
• A row 0 = c with c non-zero signals a system with no solution.
• Partial pivoting (largest coefficient) limits numerical errors.