Lesson 3 of 8 · 18 min

Gaussian elimination

Write a system of linear equations as an augmented matrix, use elementary row operations to reach row-echelon form, and back-substitute to solve it, by hand and with technology.

What you will be able to do

  • Recognise the general form of a system of linear equations in several variables.
  • Write a system as an augmented matrix, and read a system from one.
  • Use the three elementary row operations to reduce an augmented matrix to row-echelon form.
  • Solve the system by back substitution, and with technology.

The inverse method X=A−1B\bm{X} = \bm{A}^{-1}\bm{B} is quick with a calculator, but it has two weaknesses. Without technology a 3×33 \times 3 inverse is slow, and when det⁡(A)=0\det(\bm{A}) = 0 the method simply stops, without telling you whether there are no solutions or infinitely many.

Gaussian elimination fixes both. It is the elimination you used in Year 10 for two equations, organised so it works for any number of equations and unknowns. It is also what computers use to solve systems with millions of unknowns.

Definition

Systems of linear equations

A system of mm linear equations in nn variables x1,x2,…,xnx_1, x_2, \dots, x_n has the general form

a11x1+a12x2+⋯+a1nxn=b1a21x1+a22x2+⋯+a2nxn=b2    ⋮am1x1+am2x2+⋯+amnxn=bm\begin{aligned} a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n &= b_1 \\ a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n &= b_2 \\ &\;\;\vdots \\ a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n &= b_m \end{aligned}

Each variable appears only to the first power, with no products of variables. With three variables we usually write xx, yy and zz.

All the information is in the numbers, so drop the variables and the equals signs and keep the coefficients and constants in an augmented matrix, with a bar where the equals signs were:

x+y+2z=92x−y+z=33x+2y−z=4⟷[11292−11332−14]\begin{aligned} x + y + 2z &= 9 \\ 2x - y + z &= 3 \\ 3x + 2y - z &= 4 \end{aligned} \qquad \longleftrightarrow \qquad \left[\begin{array}{ccc|c} 1 & 1 & 2 & 9 \\ 2 & -1 & 1 & 3 \\ 3 & 2 & -1 & 4 \end{array}\right]

Each row is one equation, and each column before the bar belongs to one variable. A variable missing from an equation has coefficient 00.

Which augmented matrix represents the system 2x−z=52x - z = 5, x+3y=−1x + 3y = -1, y−4z=2y - 4z = 2?

Choose one answer

Key idea

Elementary row operations

These three operations change the equations but never their solutions:

  1. Swap two rows: Ri↔RjR_i \leftrightarrow R_j.
  2. Multiply a row by a non-zero constant: Ri→kRiR_i \to kR_i, k≠0k \neq 0.
  3. Add a multiple of another row: Ri→Ri+kRjR_i \to R_i + kR_j.

Each acts on the whole row, including the constant after the bar.

The goal is row-echelon form: a staircase of zeros in the bottom-left corner, so each row starts further right than the one above.

[∗∗∗∗0∗∗∗00∗∗]\left[\begin{array}{ccc|c} \ast & \ast & \ast & \ast \\ 0 & \ast & \ast & \ast \\ 0 & 0 & \ast & \ast \end{array}\right]

Then the last row is an equation in zz alone, the one above it in yy and zz, and so on. Solving from the bottom up is back substitution.

Gaussian elimination

  1. Write the augmented matrix

    Keep the variables in the same order in every row.

  2. Get a leading entry in row 1

    If the top-left entry is 00, swap in a row that does not start with 00. A leading 11 keeps the arithmetic simple.

  3. Clear the first column below it

    Use R2→R2−kR1R_2 \to R_2 - kR_1 and R3→R3−kR1R_3 \to R_3 - kR_1 to make the entries below the leading entry 00.

  4. Repeat one row down

    Use row 2's leading entry to clear the entry below it in column 2. Never use row 1 again: it would bring back the zeros you made.

  5. Back-substitute

    Solve the last row for zz, then the row above for yy, then the top row for xx.

  6. Check

    Substitute your solution into every original equation.

Interactive

Step through the elimination

Choose "Gaussian elimination" to see each row operation and the back substitution. Then edit a coefficient and watch the operations change.

Worked example

Solve a system by Gaussian elimination

  • Simple familiar
  • Technology free

Use Gaussian elimination to solve

x+y+2z=92x−y+z=33x+2y−z=4\begin{aligned} x + y + 2z &= 9 \\ 2x - y + z &= 3 \\ 3x + 2y - z &= 4 \end{aligned}
6 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Write the augmented matrix.

  2. Use row 1 to clear column 1, then row 2 to clear column 2.

  3. Back-substitute from the last row up.

  4. Check in every original equation.

Watch out for

  • Using R1R_1 again to clear column 2, which brings back a non-zero entry in column 1.

  • Forgetting to apply the operation to the constant after the bar.

Solve the system whose augmented matrix is in row-echelon form:

[1−12101−3−40026]\left[\begin{array}{ccc|c} 1 & -1 & 2 & 1 \\ 0 & 1 & -3 & -4 \\ 0 & 0 & 2 & 6 \end{array}\right]

Which row operation changes the second row of

[12−133125]into[0−55−4]?\left[\begin{array}{ccc|c} 1 & 2 & -1 & 3 \\ 3 & 1 & 2 & 5 \end{array}\right] \quad \text{into} \quad \left[\begin{array}{ccc|c} 0 & -5 & 5 & -4 \end{array}\right]?
Choose one answer

Common mistake

Arithmetic across the whole row

The commonest slip is to change the coefficients and forget the constant after the bar, or to subtract a negative wrongly: 2−3(−1)=52 - 3(-1) = 5, not −1-1. Write the operation beside each new row so you (and the marker) can check it.

Without technology

Show each augmented matrix and the operations that produced it. Choose operations that avoid fractions where you can, such as R3→2R3−3R2R_3 \to 2R_3 - 3R_2 instead of R3→R3−32R2R_3 \to R_3 - \frac{3}{2}R_2.

With technology

The calculator's ref and rref commands row-reduce a matrix. rref (reduced row-echelon form) goes further, giving 11s down the diagonal and 00s above them too, so the solution sits in the last column. Write down the augmented matrix you entered and the rref result.

Exam tip

Show the row operations

"Use Gaussian elimination" questions in Paper 1 award marks for the method. Label every step (R2→R2−2R1R_2 \to R_2 - 2R_1), reach row-echelon form, then back-substitute. A solution found another way, such as substitution, may not earn the method marks.

Summary

  • A system of linear equations becomes an augmented matrix [A∣B][\bm{A} \mid \bm{B}]: one row per equation, one column per variable, constants after the bar.

  • The row operations are: swap two rows, multiply a row by a non-zero constant, add a multiple of one row to another. None changes the solutions.

  • Row-echelon form has a staircase of zeros in the bottom-left corner.

  • Clear column 1 using row 1, then column 2 using row 2, then back-substitute from the bottom up.

  • With technology, rref gives the solution directly; still record the matrix you entered.

Finished the lesson?

Try the 3 quick checks above and the lesson completes itself, or mark it complete now.

Lesson 3 of 80% read

Save your progress with a free account