Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 62 ยท Linear Systems

Gaussian Elimination

Learn Gaussian elimination: the three row operations, echelon form, back substitution and partial pivoting, then write a working solver from scratch in Python.

Gaussian elimination is the standard recipe for solving Ax = b. The idea is the one you used at school when you subtracted one equation from another to remove a variable, but organized so that it works for any number of equations. You transform the system into an equivalent, much simpler one whose solution can be read off from the bottom up.

This lesson shows the three allowed row operations, what an echelon form looks like, how back substitution finishes the job, why you should swap rows to pick a good pivot, and how to write a complete solver in about twenty lines. Libraries do this for you, but writing it once is the best way to understand what np.linalg.solve does.

The elimination recipe

Pick a pivot Choose a non-zero entry in the current column.
Eliminate Subtract multiples of its row from the rows below.
Move on Repeat with the next column and row.
Back-substitute Solve from the last equation upward.

Elimination makes a triangle; substitution solves it.

1 / 2

Three row operations

You may change a system in three ways without changing its solutions. Applied to the rows of the augmented matrix [A | b], they are:

  1. Swap two rows.
  2. Scale a row by a non-zero number.
  3. Add a multiple of one row to another row.

Each operation is reversible, so the new system has exactly the same solutions as the old one. Elimination uses mostly the third operation, with swaps when needed.

Elimination by example

Solve:

TEXT
 x + 2y +  z =  9
2x +  y -  z =  3
 x -  y + 2z =  8

The augmented matrix is

TEXT
[1  2  1 |  9]
[2  1 -1 |  3]
[1 -1  2 |  8]

Use the 1 in the top-left (the first pivot) to clear the entries below it. Subtract 2 times row 1 from row 2, and 1 times row 1 from row 3:

TEXT
[1  2  1 |  9]
[0 -3 -3 | -15]
[0 -3  1 | -1]

The next pivot is -3. Subtract row 2 from row 3:

TEXT
[1  2  1 |  9]
[0 -3 -3 | -15]
[0  0  4 |  14]

This is row echelon form: the nonzero entries form a staircase, and everything below each pivot is zero.

Back substitution

The last row says 4z = 14, so z = 3.5. The middle row says -3y - 3z = -15, so y = 5 - z = 1.5. The first row gives x = 9 - 2y - z = 9 - 3 - 3.5 = 2.5.

Working upward, each step has only one new unknown. That is why a triangular system is easy: every equation can be solved using the values already found.

Python The hand calculation, checked

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Why pivoting matters

What if the pivot position holds a zero? Then you cannot divide by it. The fix is to swap with a lower row that has a non-zero entry in that column. Even when the pivot is non-zero but tiny, dividing by it makes huge multipliers that amplify rounding errors. Partial pivoting avoids this: before eliminating a column, swap in the row with the largest absolute value in that column.

The following system has an innocent solution x โ‰ˆ 1, y โ‰ˆ 1, but a naive elimination with the tiny pivot 1e-20 loses all accuracy.

Python A tiny pivot causes trouble

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The naive version returns x = 0.0, which is badly wrong, while the pivoted version returns values very close to 1. Library routines always use pivoting, and you will meet it again in LU decomposition.

Writing it from scratch

Here is a complete solver for square systems with a unique solution. It builds the augmented matrix, does forward elimination with partial pivoting, and back-substitutes.

Python A Gaussian elimination solver

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Cost and what can go wrong

For an n by n system the elimination needs about n^3 / 3 multiplications, then only about n^2 for back substitution. That is why factoring once and reusing the work for many right-hand sides is worthwhile (again: LU decomposition).

If you reach a column with no usable pivot, the matrix is singular. Then the system either has no solution (a row like 0 0 0 | 5) or infinitely many (free unknowns). Handling those cases cleanly is the topic of Reduced Row Echelon Form.

Python Spotting a contradiction during elimination

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which of these is NOT an allowed row operation?

    Multiplying by zero destroys information and is not reversible, so it can change the solution set.
  2. 2. What does back substitution do?

    In a triangular system the last equation has one unknown; each earlier equation then needs only one new value.
  3. 3. Why does partial pivoting choose the largest entry in the column?

    Dividing by a tiny pivot creates huge multipliers that amplify floating-point errors.
  4. 4. Roughly how many multiplications does elimination need for an n by n system?

    Forward elimination dominates with about n^3/3 operations; back substitution adds only about n^2.

Summary

  • Gaussian elimination uses row swaps, row scaling and row additions, which never change the solutions.
  • Forward elimination produces row echelon form, a triangular staircase.
  • Back substitution solves the last equation first and works upward.
  • Partial pivoting swaps in the largest available pivot to keep rounding errors small.
  • A column with no usable pivot signals a singular system: no solution or infinitely many.
  • Elimination costs about n^3 / 3 operations; this is what library solvers do internally.

Next: handle every case cleanly with Reduced Row Echelon Form.