Gaussian Elimination and Echelon Form

Row operations, from the last topic, can change a system as much as we like without changing its solutions. So which shape should we aim for? A staircase.

In each nonzero row, the first nonzero entry is its leading entry. A matrix is in echelon form when (1) all rows of zeros are at the bottom, and (2) each leading entry is in a column to the right of the leading entry in the row above. Then every entry below a leading entry is $0$. The leading entries' positions are called pivot positions, and their columns are pivot columns.

$$\begin{bmatrix} 2 & -1 & 4 & 3 \\ 0 & 0 & 5 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix} \text{ is in echelon form;} \quad \begin{bmatrix} 1 & 2 & 0 \\ 3 & 1 & 1 \\ 0 & 0 & 2 \end{bmatrix} \text{ is not.}$$ In the second matrix, the $3$ sits below the first pivot.

Gaussian elimination

Find the leftmost column that is not all zeros. Its top entry (after a swap, if needed) is the pivot.
Use replacements to make every entry below the pivot $0$.
Cover the pivot row and repeat on the rows below it, until you run out of rows or columns.
Back-substitute: solve the last equation, then work upward.

Why it works

Why does this always work, and why is the result easy? Each round clears one column below a pivot, and later rounds only use rows that already have zeros in the earlier columns, so they never spoil earlier work. At the end, the last nonzero equation has the fewest unknowns, often just one. Each equation above it brings in one new unknown, so back substitution solves for one unknown at a time.

Elimination on the system from the first example.

Worked example: Elimination and back substitution

Solve $x + y - z = 3$, $-x - 3y + 4z = -13$, $-4y + 5z = -18$.

Augmented matrix: $\left[\begin{array}{ccc|c} 1 & 1 & -1 & 3 \\ -1 & -3 & 4 & -13 \\ 0 & -4 & 5 & -18 \end{array}\right]$
Clear below the first pivot. Row 3 already has a $0$ there. $R_{2} \to R_{2} + R_{1}$: $\left[\begin{array}{ccc|c} 1 & 1 & -1 & 3 \\ 0 & -2 & 3 & -10 \\ 0 & -4 & 5 & -18 \end{array}\right]$
Clear below the second pivot, $-2$: $R_{3} \to R_{3} - 2R_{2}$: $\left[\begin{array}{ccc|c} 1 & 1 & -1 & 3 \\ 0 & -2 & 3 & -10 \\ 0 & 0 & -1 & 2 \end{array}\right]$. Echelon form.
Row 3: $-z = 2$, so $z = -2$.
Row 2: $-2y + 3z = -10$, so $-2y - 6 = -10$ and $y = 2$.
Row 1: $x + y - z = 3$, so $x + 2 + 2 = 3$ and $x = -1$.
Check in the original second equation: $-(-1) - 3(2) + 4(-2)$ $= 1 - 6 - 8$ $= -13$. ✓

Answer: $(x, y, z) = (-1, 2, -2)$

Worked example: When fractions appear

Solve $2x + 3y = 8$, $3x - y = 1$.

The pivot is $2$ and the entry below it is $3$, so the multiplier is $\frac{3}{2}$: $R_{2} \to R_{2} - \frac{3}{2}R_{1}$ gives $\left[\begin{array}{cc|c} 2 & 3 & 8 \\ 0 & -\frac{11}{2} & -11 \end{array}\right]$.
Row 2 says $-\frac{11}{2}y = -11$. Multiply both sides by $-\frac{2}{11}$: $y = 2$.
Row 1: $2x + 6 = 8$, so $x = 1$.
Check in both original equations: $2(1) + 3(2) = 8$ ✓ and $3(1) - 2 = 1$ ✓.
To dodge the fractions you could first scale ($R_2 \to 2R_2$), then use $R_2 \to R_2 - 3R_1$. Both routes give the same answer.

Answer: $(x, y) = (1, 2)$

Common mistake

Small slips with signs and fractions are the most common error in elimination, and they are invisible unless you check. Always substitute your answer into every original equation, not the reduced ones: an error made during elimination is built into the reduced system, so it would pass that check.

Key idea

Echelon form is a staircase: zeros below each pivot, each pivot to the right of the one above. Gaussian elimination reaches it with replacements (and swaps when a pivot is $0$), and back substitution then solves from the bottom up.

Gaussian Elimination and Echelon Form

Gaussian elimination

Practice

Builds on

Leads to

Sources and further reading