Source

Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree

Gaussian elimination is a systematic way to solve a linear system. It uses row operations to turn the augmented matrix into a triangular (row echelon) form, then solves by back substitution.

Row Echelon Form

The first nonzero entry of each nonzero row is called a pivot.

A matrix is in row echelon (RE) form when:

  • all zero rows are at the bottom
  • each pivot is to the right of the pivot in the row above
  • every entry below a pivot is zero

It is in reduced row echelon (RRE) form if, in addition:

  • every pivot is 1
  • every other entry in a pivot column is 0

The RRE form of a matrix is unique. Reducing all the way to RRE form is called Gauss-Jordan elimination.

Method

Steps:

  1. Write the augmented matrix
  2. Take the leftmost nonzero column as the pivot column. Swap rows if needed so the top entry is nonzero
  3. Use row operations to make every entry below the pivot zero
  4. Cover that row and repeat on the rows below until the matrix is in RE form
  5. Back substitute from the last equation upwards (or keep going to RRE form and read off the answer)

Worked Example

Solve , , .

Back substitution:

So .

What the RE Form Tells You

Once the matrix is in RE form you can read off the type of solution straight away. A row like means no solution, and fewer pivots than unknowns means free variables. This is covered in Consistency and Number of Solutions.

Software

For big systems use software, e.g. rref([A b]) or A\b in MATLAB.