§ 01The Augmented Matrix
A system of linear equations carries all of its information in its coefficients and constants. The augmented matrix strips away the variable names and stores just those numbers, making systematic manipulation fast and clean.
Consider the system of three equations in three unknowns:
We form the augmented matrix [A | b] by writing the coefficients of x, y, z in the first three columns, then a vertical bar, then the right-hand-side constants in the final column:
| 2 | 3 | −1 | 7 |
| −1 | 1 | 2 | 1 |
| 3 | −2 | 1 | 4 |
Every row of the augmented matrix corresponds to one equation. Every column (except the last) corresponds to one variable. The vertical bar represents the equals signs. The goal of row reduction is to transform this matrix into a form where the solution is obvious by inspection.
§ 02The Three Elementary Row Operations
There are exactly three operations we are permitted to perform on the rows of a matrix. Each one corresponds to a legal manipulation of the underlying system of equations and leaves the solution set unchanged.
In practice, Operation R3 is used constantly. The standard notation for "replace row 2 with row 2 minus 3 times row 1" is written: R₂ → R₂ − 3R₁. This notation appears above each arrow between matrices in the worked examples below.
§ 03Row Echelon Form (REF)
A matrix is in Row Echelon Form when it satisfies three conditions:
A matrix in REF looks like a staircase descending from top-left to bottom-right. The pivots are the leading (leftmost) non-zero entries in each row and can be any non-zero value: they do not have to be 1.
| 2 | 5 | 1 | 8 |
| 0 | 3 | -4 | 2 |
| 0 | 0 | 7 | 5 |
Notice the staircase pattern: the first non-zero entry in row 2 is one column to the right of the one in row 1, and similarly for row 3. All entries below each teal pivot are zero.
Gaussian Elimination — The Algorithm to Reach REF
Gaussian elimination is the systematic procedure for reducing any augmented matrix to REF:
§ 04Reduced Row Echelon Form (RREF)
RREF is a stricter version of REF. A matrix is in Reduced Row Echelon Form when it satisfies all three REF conditions plus two additional ones:
A matrix in RREF is unique, every matrix has exactly one RREF. This makes it ideal: reading the solution directly from the RREF requires no further arithmetic.
| 1 | 0 | 0 | 3 |
| 0 | 1 | 0 | −1 |
| 0 | 0 | 1 | 2 |
From this RREF, the solution is immediate: x = 3, y = −1, z = 2. No algebra required, just read off the right-hand column.
The process of reducing all the way to RREF (eliminating both above and below each pivot, then scaling pivots to 1) is called Gauss–Jordan elimination, named after Carl Friedrich Gauss and Wilhelm Jordan. The partial process that stops at REF is called plain Gaussian elimination.
§ 05Pivot Positions and Free Variables
The structure of the RREF tells you everything about the solution of the system. The key vocabulary: pivot columns, non-pivot columns, and free variables.
Counting Free Variables
If a system has n variables and the RREF has r pivot positions (one per non-zero row), then:
where n is the total number of variables and r is the rank (number of pivot positions).
If there are zero free variables, the system has exactly one solution. If there is at least one free variable, the system has infinitely many solutions (a line, plane, or higher-dimensional solution set). If the system is inconsistent, there is no solution regardless of free variables.
| 1 | 0 | 2 | 5 |
| 0 | 1 | −3 | 1 |
| 0 | 0 | 0 | 0 |
Here columns 1 and 2 are pivot columns. Column 3 has no pivot: x₃ is a free variable. Reading: x₁ = 5 − 2x₃ and x₂ = 1 + 3x₃, with x₃ ∈ ℝ.
§ 06The Three Possible Solution Types
After reducing to REF or RREF, a linear system falls into exactly one of three categories. You can always diagnose which case you are in by inspecting the final matrix.
| Type | How to Recognise It in REF/RREF | Number of Solutions |
|---|---|---|
| Unique solution | No zero rows, no free variables — each column has a pivot. The system is consistent and determined. | Exactly one |
| Infinitely many solutions | No contradiction row [0 0 … 0 | c ≠ 0], but at least one non-pivot column exists. Each free variable generates a family of solutions. | Infinitely many (parameterised) |
| No solution (inconsistent) | A row of the form [0 0 … 0 | c] where c ≠ 0 appears. This encodes the impossible equation 0 = c. | Zero |
§ 07Back Substitution
When you stop at REF rather than going all the way to RREF, you recover the solution by back substitution: you read the last (simplest) equation first and substitute upwards.
Suppose your REF is:
| 1 | 2 | 3 | 14 |
| 0 | 4 | 5 | 13 |
| 0 | 0 | 2 | 4 |
Back substitution proceeds:
2z = 4 → z = 2.
4y + 5z = 13 → 4y + 10 = 13 → 4y = 3 → y = 3/4.
x + 2y + 3z = 14 → x + 3/2 + 6 = 14 → x = 14 − 7.5 = 6.5.
Back substitution is faster than completing to RREF when you only need the numerical answer and aren't working symbolically. RREF is preferred when free variables are involved, because it makes the parameterised solution immediately visible.
§ 0812 Fully Worked Examples
System: x + 2y = 5, 3x − y = 1.
| 1 | 2 | 5 |
| 3 | −1 | 1 |
| 1 | 2 | 5 |
| 0 | −7 | −14 |
This is REF. Now scale R₂: R₂ → (−1/7)R₂.
R₁ → R₁ − 2R₂: row 1 becomes [1, 0 | 1].
| 1 | 0 | 1 |
| 0 | 1 | 2 |
System: x + y + z = 6, 2x + y − z = 1, x − y + 2z = 5.
| 1 | 1 | 1 | 6 |
| 2 | 1 | −1 | 1 |
| 1 | −1 | 2 | 5 |
| 1 | 1 | 1 | 6 |
| 0 | −1 | −3 | −11 |
| 0 | −2 | 1 | −1 |
| 1 | 1 | 1 | 6 |
| 0 | −1 | −3 | −11 |
| 0 | 0 | 7 | 21 |
REF achieved. R₃ → (1/7)R₃ → z = 3. R₂ → (−1)R₂ → y + 3z = 11 → y = 2. R₁ → R₁ − R₂ − R₃ → x = 1.
System: x + y = 3, 2x + 2y = 9.
| 1 | 1 | 3 |
| 2 | 2 | 9 |
| 1 | 1 | 3 |
| 0 | 0 | 3 |
Row 2 reads 0·x + 0·y = 3, i.e. 0 = 3. Contradiction.
System: x + 2y + 3z = 9, 2x − y + z = 4, 3x + y + 4z = 13.
After R₂ → R₂ − 2R₁ and R₃ → R₃ − 3R₁:
| 1 | 2 | 3 | 9 |
| 0 | −5 | −5 | −14 |
| 0 | −5 | −5 | −14 |
R₃ → R₃ − R₂ gives a zero row. Scale R₂ by −1/5:
| 1 | 2 | 3 | 9 |
| 0 | 1 | 1 | 14/5 |
| 0 | 0 | 0 | 0 |
Column 3 has no pivot → z is free, z = t. From row 2: y = 14/5 − t. From row 1: x = 9 − 2(14/5 − t) − 3t = 9 − 28/5 + 2t − 3t = 17/5 − t.
System: 0·x + 2y = 4, 3x + y = 5.
| 0 | 2 | 4 |
| 3 | 1 | 5 |
Column 1 of row 1 is zero. We cannot use it as a pivot. Swap: R₁ ↔ R₂.
| 3 | 1 | 5 |
| 0 | 2 | 4 |
Now in REF. Scale: R₁ → (1/3)R₁, R₂ → (1/2)R₂. Then R₁ → R₁ − (1/3)R₂.
System: x₁ + x₂ + x₃ = 4, 2x₁ + x₂ + 3x₃ = 7, x₁ + 2x₂ − x₃ = 5, 3x₁ + 2x₂ + 4x₃ = 11.
After full reduction the RREF is:
| 1 | 0 | 2 | 3 |
| 0 | 1 | −1 | 1 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
Two pivot columns (x₁, x₂); one free variable (x₃ = t).
A homogeneous system has the form Ax = 0 (all right-hand sides are zero). It always has at least the trivial solution x = 0. Non-trivial solutions exist exactly when there are free variables.
System: x − 2y + z = 0, 2x + y − z = 0.
| 1 | −2 | 1 | 0 |
| 2 | 1 | −1 | 0 |
| 1 | −2 | 1 | 0 |
| 0 | 5 | −3 | 0 |
2 pivots, 3 unknowns → 1 free variable (z = t). Row 2: y = 3t/5. Row 1: x = 2(3t/5) − t = t/5.
Row reduction on [A | I] → [I | A⁻¹] lets us compute inverses. Find A⁻¹ where A = [[2, 1], [5, 3]].
| 2 | 1 | 1 | 0 |
| 5 | 3 | 0 | 1 |
| 2 | 1 | 1 | 0 |
| 0 | 1 | −5 | 2 |
R₁→R₁−R₂: [2, 0 | 6, −2]. R₁→(1/2)R₁: [1, 0 | 3, −1].
Verify: AA⁻¹ = [[2·3+1·(−5), 2·(−1)+1·2], [5·3+3·(−5), 5·(−1)+3·2]] = [[1,0],[0,1]] ✓
Determine whether each matrix is in REF, RREF, both, or neither.
| 1 | 3 | 0 |
| 0 | 2 | 5 |
| 0 | 0 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 1 |
| 2 | 1 | 0 |
| 0 | 1 | 3 |
| 0 | 0 | 0 |
(a) REF only. Pivots are 1, 2, 1 (staircase ✓, zeros below ✓), but the pivot in row 2 is 2 (not 1) and there's a non-zero entry above the third pivot. Fails RREF conditions 4 and 5.
(b) RREF (and hence also REF). All pivots = 1, staircase pattern, zeros everywhere else in pivot columns.
(c) Neither. The first pivot is 2 (not 1), so it's not RREF. But also: the entry above the second pivot in row 1 is 1, which is non-zero: however that alone doesn't disqualify REF. The real issue is the pivot in row 1 is 2, not in RREF; and there's no non-zero below it (zeros below is fine), so it is actually REF. Answer: (c) is REF but not RREF because the pivot in row 1 is 2 ≠ 1.
System: x + 2y = 3, 2x + 4y = k. For what value(s) of k does this system have a solution?
| 1 | 2 | 3 |
| 2 | 4 | k |
| 1 | 2 | 3 |
| 0 | 0 | k−6 |
Row 2 reads 0 = k − 6. This is only consistent if k − 6 = 0.
A system of 2 equations in 4 unknowns has been reduced to the RREF below. Write the general solution.
| 1 | 2 | 0 | −1 | 3 |
| 0 | 0 | 1 | 4 | −2 |
Pivot columns: 1 and 3 (variables x₁ and x₃). Free columns: 2 and 4 (variables x₂ = s, x₄ = t).
Row 1: x₁ + 2s − t = 3 → x₁ = 3 − 2s + t.
Row 2: x₃ + 4t = −2 → x₃ = −2 − 4t.
This is a 2-dimensional plane (affine subspace) in ℝ⁴.
System: 2x − y + z = 8, −3x + y − 2z = −11, −2x + y + 2z = −3.
| 2 | −1 | 1 | 8 |
| −3 | 1 | −2 | −11 |
| −2 | 1 | 2 | −3 |
| 1 | −1/2 | 1/2 | 4 |
| −3 | 1 | −2 | −11 |
| −2 | 1 | 2 | −3 |
| 1 | −1/2 | 1/2 | 4 |
| 0 | −1/2 | −1/2 | 1 |
| 0 | 0 | 3 | 5 |
R₂ → −2R₂: [0, 1, 1 | −2]. R₃ → (1/3)R₃: [0, 0, 1 | 5/3].
R₂ → R₂ − R₃: [0, 1, 0 | −2 − 5/3 = −11/3]. R₁ → R₁ + (1/2)R₂ − (1/2)R₃.
x = 4 + (1/2)(−11/3) − (1/2)(5/3) = 4 − 11/6 − 5/6 = 4 − 16/6 = 4 − 8/3 = 4/3.
§ 09Common Mistakes
§ 10Practice Quiz
Test your understanding of row reduction, echelon forms, pivot positions, and solution types. Immediate feedback on every question.