Gaussian Elimination is an algorithm to solve systems of system of linear equation.

It first reduces a matrix to a upper-triangular matrix and back substitutes the result.

We can augment a matrix with the right hand side of the equation to create an augmented matrix.

And then we can perform elementary row operations on the augmented matrix. Those row operations will not change the solution of the equation:

elementary row operations

  1. Switch two rows
  2. Scaling row
  3. Linearly combining two rows

We reduces the augmented matrix row-by-row until its left side reaches the upper-triangular form.

when first element is zero

Sometimes it is not possible to eliminate if the first variable in the first row is 0:

In this case, we can reorder the equations:

Gaussian elimination suffers from the problems of numerical instability and redundant computation, and LU factorization is often a preferred numerical algorithm.