1. Why we need an algorithm
Substitution and elimination work fine for a two-variable system and tolerably for three. Push to four variables and the ad-hoc juggling collapses: which equation do you solve for which variable? In what order? Did you already use that one? An algorithm replaces judgment with a recipe.
Gaussian elimination is that recipe. It takes any system of $m$ equations in $n$ unknowns and grinds through a fixed sequence of moves until the answer is plain. You don't have to be clever — you have to follow the rules.
The trick is to strip away everything that isn't a number. The variable names $x, y, z$ are just labels; only the coefficients matter. So we set them aside in a grid and operate on the grid directly.
2. Augmented matrices
A rectangular array of numbers that encodes a linear system: each row is one equation, the columns on the left hold the coefficients of the unknowns, and the column on the right holds the constants. A vertical bar separates the two regions to remind you that the right column is special.
Take the system
$$ \begin{aligned} \phantom{-}2x + 3y - \phantom{1}z &= \phantom{-1}5 \\ \phantom{-2}x - \phantom{3}y + 2z &= \phantom{-1}3 \\ \phantom{-}3x + \phantom{3}y + \phantom{2}z &= 10 \end{aligned} $$Its augmented matrix is
$$ \left[\begin{array}{rrr|r} 2 & 3 & -1 & 5 \\ 1 & -1 & 2 & 3 \\ 3 & 1 & 1 & 10 \end{array}\right] $$That bar is structural, not decorative. Coefficients on the left, constants on the right; if you mix them up the whole calculation is meaningless.
Before writing the matrix, line up every equation so that like variables stack in the same column and constants sit alone on the right. Missing terms become zeros — $x + z = 4$ has a $0$ in the $y$-column. Get this wrong and every subsequent step is wrong.
3. The three elementary row operations
The only moves allowed on an augmented matrix are three. Each one preserves the solution set — the system represented by the new matrix has exactly the same solutions as the old one.
| Operation | Notation | What it really is |
|---|---|---|
| Swap two rows | $R_i \leftrightarrow R_j$ | Reorder the equations. |
| Multiply a row by a nonzero constant | $R_i \to c R_i$ | Multiply both sides of an equation by $c$. |
| Add a multiple of one row to another | $R_i \to R_i + c R_j$ | Add a multiple of one equation to another. |
That's it. The whole algorithm is just stringing these three moves together to chase the matrix toward a target shape.
$R_i \to 0 \cdot R_i$ would erase an equation and destroy information. Only nonzero constants count.
4. Row-echelon form
A matrix is in row-echelon form when (i) any all-zero rows sit at the bottom, and (ii) in every nonzero row, the first nonzero entry — called the pivot — appears strictly to the right of the pivot in the row above it. The shape is a staircase descending to the right.
Example of REF:
$$ \left[\begin{array}{rrr|r} 1 & 2 & -1 & 3 \\ 0 & 1 & 4 & 2 \\ 0 & 0 & 1 & 5 \end{array}\right] $$To put a matrix in REF, work column by column from left to right: pick a pivot, zero out every entry below it, then move to the next column down and to the right. The pivot doesn't have to be $1$ — only nonzero.
The mechanical recipe, applied to column $k$:
- Find a row at or below row $k$ whose entry in column $k$ is nonzero. Swap it up into row $k$ if needed.
- For every row $i > k$ below the pivot, do $R_i \to R_i - \dfrac{a_{ik}}{a_{kk}} R_k$ to kill the entry in column $k$.
- Move to column $k+1$ and row $k+1$ and repeat.
5. Reduced row-echelon form
Row-echelon form with two extra conditions: every pivot equals $1$, and every entry above a pivot is zero (not just below). Each column with a pivot is a clean column of zeros with a single $1$.
The same matrix, now in RREF:
$$ \left[\begin{array}{rrr|r} 1 & 0 & 0 & \phantom{-1}1 \\ 0 & 1 & 0 & -18 \\ 0 & 0 & 1 & \phantom{-1}5 \end{array}\right] $$This is as far as the algorithm can take you. Read across each row: $x = 1$, $y = -18$, $z = 5$. The solution falls out without any further work.
Pushing REF to RREF is sometimes called Gauss–Jordan elimination. The first half (REF + back-substitution) is the original Gaussian elimination; doing all the work in the matrix and stopping at RREF is the Gauss–Jordan variant. Either gets you the same answer.
For a given matrix, the RREF is unique. Two people doing the row operations in different orders end up with the same RREF. This is what makes it a canonical form — and what makes it useful as a theoretical tool beyond just solving systems.
6. Back-substitution
If you stop at REF rather than push to RREF, you finish the job by back-substitution. The bottom row gives the last variable directly. Plug it into the second-to-last row to get the next variable. Keep climbing.
From the REF example above:
- Bottom row: $z = 5$.
- Middle row: $y + 4z = 2 \Rightarrow y = 2 - 4(5) = -18$.
- Top row: $x + 2y - z = 3 \Rightarrow x = 3 - 2(-18) + 5 = 44$.
Wait — that doesn't match the RREF answer above. Good. It shouldn't: I used a different example in the REF box than the one we drove to RREF. The point of the exercise is the method, not the numbers. In a real problem, the same matrix taken to REF + back-sub and to RREF directly will give identical answers.
RREF means more arithmetic up front but no back-substitution. REF means less arithmetic in the matrix but you have to substitute at the end. For 3×3 systems by hand, REF + back-substitution is usually faster. For computer implementations and theoretical work, RREF is the standard target.
7. Pivots and free variables
After reduction, every column either has a pivot or it doesn't. A column with a pivot corresponds to a basic variable — its value is determined. A column without a pivot corresponds to a free variable — you can pick anything for it, and the basic variables adjust accordingly.
Free variables show up exactly when the system is underdetermined: more unknowns than independent equations. They're how an infinite family of solutions gets encoded.
Suppose the RREF of a 2-equation, 3-unknown system is
$$ \left[\begin{array}{rrr|r} 1 & 0 & 2 & 5 \\ 0 & 1 & -3 & 4 \end{array}\right] $$Columns 1 and 2 have pivots ($x$ and $y$ are basic), column 3 doesn't ($z$ is free). The general solution is
$$ \begin{aligned} x &= 5 - 2t \\ y &= 4 + 3t \\ z &= t \qquad (t \in \mathbb{R}) \end{aligned} $$One free variable means a line of solutions; two would mean a plane; in general, the number of free variables is the dimension of the solution set.
8. No, one, or infinitely many solutions
Every linear system, no matter how big, ends in exactly one of three outcomes. The augmented matrix in REF or RREF tells you which.
| What the matrix looks like | What it means |
|---|---|
| Every column on the left has a pivot, no contradictory row. | Unique solution. One point. |
| A row of the form $[\,0\;\;0\;\cdots\;0\,|\,c\,]$ with $c \neq 0$. | No solution. The system is inconsistent — $0 = c$ can never hold. |
| No contradictory row, but at least one column on the left has no pivot. | Infinitely many solutions. Parameterize by the free variables. |
A row of all zeros — including the constants column, $[\,0\;\;0\;\cdots\;0\,|\,0\,]$ — is not a contradiction. It's a redundant equation ("$0 = 0$") that just got absorbed. The contradictory row has zeros on the left and a nonzero on the right. Train your eye to spot the difference.
9. Common pitfalls
Every row operation feeds into the next. A single sign error in row 2 ruins everything below it. Show your work, keep fractions exact (don't decimalize unless asked), and double-check pivot rows before using them to eliminate.
If you scale a row, scale the right column too. If you add $R_2$ to $R_1$, the constants in both rows move. The right column is part of the matrix; it's just bookkept separately so you remember which side of the equation it lived on.
In RREF, columns 1, 2, 3 correspond to $x, y, z$ — left to right, always. If you let yourself swap columns (which is not an allowed row operation, but tempting), the variable order changes and the answers come out scrambled. Don't swap columns.
If the candidate pivot entry is $0$, you can't divide by it. Swap in a row below that has a nonzero entry in that column. If no row below has a nonzero entry either, that column doesn't get a pivot — move on to the next column.
10. Worked examples
Open each one only after you've tried it.
Example 1 · A 3×3 system with a unique solution
Solve
$$ \begin{aligned} \phantom{-}x + \phantom{2}y + \phantom{2}z &= 6 \\ \phantom{-}2x - \phantom{1}y + \phantom{2}z &= 3 \\ \phantom{-}x + 2y - \phantom{2}z &= 2 \end{aligned} $$Step 1. Write the augmented matrix.
$$ \left[\begin{array}{rrr|r} 1 & \phantom{-}1 & \phantom{-}1 & 6 \\ 2 & -1 & 1 & 3 \\ 1 & \phantom{-}2 & -1 & 2 \end{array}\right] $$Step 2. Eliminate below the first pivot. $R_2 \to R_2 - 2R_1$, $R_3 \to R_3 - R_1$:
$$ \left[\begin{array}{rrr|r} 1 & \phantom{-}1 & \phantom{-}1 & \phantom{-1}6 \\ 0 & -3 & -1 & -9 \\ 0 & \phantom{-}1 & -2 & -4 \end{array}\right] $$Step 3. Eliminate below the second pivot. Easier to use $R_3$'s pivot first: swap $R_2 \leftrightarrow R_3$, then $R_3 \to R_3 + 3R_2$:
$$ \left[\begin{array}{rrr|r} 1 & 1 & \phantom{-}1 & \phantom{-1}6 \\ 0 & 1 & -2 & -4 \\ 0 & 0 & -7 & -21 \end{array}\right] $$Step 4. Back-substitute:
- $-7z = -21 \Rightarrow z = 3$.
- $y - 2(3) = -4 \Rightarrow y = 2$.
- $x + 2 + 3 = 6 \Rightarrow x = 1$.
Check. $(1, 2, 3)$ satisfies all three original equations.
Example 2 · A system with no solution
Solve
$$ \begin{aligned} \phantom{-}x + 2y &= 3 \\ 2x + 4y &= 7 \end{aligned} $$Augment and eliminate:
$$ \left[\begin{array}{rr|r} 1 & 2 & 3 \\ 2 & 4 & 7 \end{array}\right] \xrightarrow{R_2 \to R_2 - 2R_1} \left[\begin{array}{rr|r} 1 & 2 & 3 \\ 0 & 0 & 1 \end{array}\right] $$Row 2 reads $0x + 0y = 1$ — false for every $(x,y)$. The system has no solution. Geometrically: two parallel lines that never meet.
Example 3 · A system with one free variable
Solve
$$ \begin{aligned} \phantom{-}x + \phantom{1}y + \phantom{1}z &= 6 \\ \phantom{-}x - \phantom{1}y + 2z &= 5 \\ \phantom{-}3x + \phantom{1}y + 4z &= 17 \end{aligned} $$Augment and eliminate. $R_2 \to R_2 - R_1$, $R_3 \to R_3 - 3R_1$:
$$ \left[\begin{array}{rrr|r} 1 & \phantom{-}1 & \phantom{-}1 & 6 \\ 0 & -2 & \phantom{-}1 & -1 \\ 0 & -2 & \phantom{-}1 & -1 \end{array}\right] $$$R_3 \to R_3 - R_2$:
$$ \left[\begin{array}{rrr|r} 1 & \phantom{-}1 & 1 & \phantom{-1}6 \\ 0 & -2 & 1 & -1 \\ 0 & \phantom{-}0 & 0 & \phantom{-1}0 \end{array}\right] $$The bottom row is $0=0$ — redundant, not contradictory. Two pivots (columns 1 and 2), three unknowns. Column 3 has no pivot, so $z$ is free.
Let $z = t$. From row 2: $-2y + t = -1 \Rightarrow y = \tfrac{1+t}{2}$. From row 1: $x + \tfrac{1+t}{2} + t = 6 \Rightarrow x = \tfrac{11 - 3t}{2}$.
The solution set is the line $\bigl(\tfrac{11-3t}{2},\;\tfrac{1+t}{2},\;t\bigr)$ for any $t \in \mathbb{R}$.