A system of equations is a bunch of equations that all have to be true at the same time. You've solved little ones before, two equations and two unknowns, by adding or subtracting the equations until one unknown drops out. This page turns that trick into a recipe that works on any system at all, however many equations and unknowns it has. The recipe is called row reduction, and almost everything else in linear algebra runs on it.
A system of equations is a bunch of equations that all have to be true at the same time. You've solved little ones before, two equations and two unknowns, by adding or subtracting the equations until one unknown drops out. And on Lines & Planes you saw that an equation like $2x - y + z = 4$ is a plane in space. So three equations in $x$, $y$, and $z$ are three planes, and solving the system means hunting for the points that sit on all three at once. This page turns the add-and-subtract trick into a recipe for that hunt. It's called row reduction, and almost everything else in linear algebra runs on it.
The practice is mixed into the lesson: each question sits right after the idea it needs, and the Mixed Practice at the bottom takes that hint away. Flip the switch on a question to type your answer instead: a list of numbers separated by commas, like 2, -1, 3.
Remember systems from ISEE Section 4? Two equations, two unknowns, and you added the equations together so one unknown cancelled. That move is the whole engine of this page. We're just going to run it on bigger systems, and write down exactly why it's allowed.
First, what kind of equations are we talking about? Only the plainest kind: each unknown appears to the first power, multiplied by a number, and the terms are added up. No $x^2$, no $xy$, no $\sqrt{x}$.
A linear equation in the unknowns $x_1, x_2, \ldots, x_n$ is an equation of the form $$a_1x_1 + a_2x_2 + \cdots + a_nx_n = b,$$ where the coefficients $a_1, \ldots, a_n$ and the constant $b$ are real numbers.
A linear equation in the unknowns $x$ and $y$, or $x$, $y$, and $z$, is an equation of the form $$ax + by = d \quad \text{or} \quad ax + by + cz = d,$$ where the coefficients $a$, $b$, $c$ and the constant $d$ are real numbers.
On Lines & Planes, $ax + by + cz = d$ was a plane (as long as the coefficients aren't all $0$), and $(a, b, c)$ was its normal, the arrow standing perpendicular to it. With only two unknowns, $ax + by = d$ is a line in the plane. Either way, a linear equation is something flat.
With two or three unknowns we'll usually call them $x$, $y$, $z$ instead of $x_1$, $x_2$, $x_3$. The test for "linear" is quick once you know what to look for:
The test for "linear" is quick once you know what to look for:
Which of these equations are linear? $$\text{(a) } 2x - y + z = -1 \qquad \text{(b) } x_1 = 7$$ $$\text{(c) } xy + z = 4 \qquad \text{(d) } 3x + \sqrt{2}\,y = \pi$$
Which of these equations are linear? $$\text{(a) } 2x - y + z = -1 \qquad \text{(b) } z = 7$$ $$\text{(c) } xy + z = 4 \qquad \text{(d) } 3x + \sqrt{2}\,y = \pi$$
(a) is linear, with coefficients $2, -1, 1$. (b) is linear too: every other coefficient is $0$. (c) is not, because $xy$ multiplies two unknowns together. (d) is linear: $\sqrt{2}$ and $\pi$ look scary, but they're just numbers, and the unknowns $x$ and $y$ still appear to the first power, each times a number.
Here's what each one looks like. A straight ruler turns on each surface, and on a flat one it never lifts off:
Now stack a few of them up.
A system of linear equations is a finite list of linear equations in the same unknowns $x_1, \ldots, x_n$.
A system of linear equations is a finite list of linear equations in the same unknowns: $x$ and $y$, or $x$, $y$, and $z$.
The whole point of a system is that every equation has to hold at once. A list of numbers that pulls that off gets a name.
A solution of a system in the unknowns $x_1, \ldots, x_n$ is an $n$-tuple $(s_1, \ldots, s_n)$ of real numbers that makes every equation true when $x_1 = s_1, \ldots, x_n = s_n$. The solution set of the system is the set of all its solutions.
A solution of a system in $x$, $y$, $z$ is a point $(x, y, z)$ that makes every equation true. In pictures, it's a point that sits on every one of the system's planes (with two unknowns, on every one of its lines). The solution set of the system is the set of all its solutions.
Checking a solution is easy: plug it in. Finding them is the hard part, and that's the rest of the page.
Which of $(1, 2, -1)$ and $(0, 3, 2)$ are solutions of the system $$\begin{aligned} 2x - y + z &= -1 \\ x + 3y - 2z &= 9\, ? \end{aligned}$$
Plug in $(1, 2, -1)$: the first equation gives $2 - 2 - 1 = -1$ and the second gives $1 + 6 + 2 = 9$. Both hold, so $(1, 2, -1)$ is a solution.
Plug in $(0, 3, 2)$: the first equation gives $0 - 3 + 2 = -1$, fine, but the second gives $0 + 9 - 4 = 5 \neq 9$. One equation failing is enough: $(0, 3, 2)$ is not a solution.
In space, plugging in is asking "is this point on both planes?"
With two unknowns, each linear equation is a line in the plane, and a solution of the system is a point that sits on every line. Two lines can only do three things:
Try to find a fourth option. You won't, but it's worth the attempt.
You can often call it from the equations alone, with no picture. If the left sides are multiples of each other, the lines are parallel or the same; the right sides decide which. Try it:
Here's the surprise: the same three options hold for every system, not just two lines. Three planes in space, ten equations in fifty unknowns, anything. A linear system can never have exactly two solutions, or exactly seven. The reason fits in one picture:
Three planes in space can sit in many more ways than two lines can. Here's a tour. Keep an eye on the count at the bottom:
Seven arrangements, and only three counts: one, infinitely many, or none. Build some yourself. Two walls stand still; turn, tilt, and slide the third plane:
However you set them, you never get exactly two solutions, or exactly seven. Here's why, with two lines first:
That walk works in any number of unknowns, so it's a theorem.
A plane is flat too, so the same walk works in space. That makes it a theorem.
Every system of linear equations has no solution, exactly one solution, or infinitely many solutions.
Suppose the system has two different solutions $s = (s_1, \ldots, s_n)$ and $s' = (s'_1, \ldots, s'_n)$. We show it has infinitely many. For each real number $t$, let $$\begin{aligned} u &= s + t(s' - s) \\ &= \big(s_1 + t(s'_1 - s_1), \ \ldots, \ s_n + t(s'_n - s_n)\big). \end{aligned}$$ Take any equation $a_1x_1 + \cdots + a_nx_n = b$ of the system. Plugging in $u$ and regrouping, $$\begin{aligned} a_1u_1 + \cdots + a_nu_n &= (a_1s_1 + \cdots + a_ns_n) \\ &\quad + t\big[(a_1s'_1 + \cdots + a_ns'_n) \\ &\qquad\quad - (a_1s_1 + \cdots + a_ns_n)\big] \\ &= b + t(b - b) = b, \end{aligned}$$ because $s$ and $s'$ both satisfy the equation. So $u$ is a solution for every $t$. Since $s' - s$ has a nonzero entry, different values of $t$ give different $u$, so there are infinitely many solutions.
So a system with more than one solution has infinitely many, and the only other options are none or exactly one. $\blacksquare$
This is a visual argument, not a formal proof. It leans on one fact from geometry class: if two points lie on a plane, the whole straight line through them lies on the plane. Suppose a system has two different solutions $s_1$ and $s_2$:
Each of the system's planes holds both points, so each holds the whole line through them. Every point of that line is on every plane, so every one is a solution: infinitely many. With two unknowns it's the same story, since each equation is a line, and the only line through $s_1$ and $s_2$ is the line through $s_1$ and $s_2$. So two solutions always means infinitely many, and the only other options are none or exactly one. The full proof is in the n version.
The "none" case is common enough to have its own word, and so is its opposite.
A system of linear equations is consistent if it has at least one solution, and inconsistent if it has none.
So the parallel lines were an inconsistent system, and the other two pictures were consistent. Next question: given a system, how do we find its solution set without drawing anything?
The plan is to keep swapping the system for a simpler one with exactly the same solutions, until the system is so simple you can read the answer off it. "Exactly the same solutions" deserves a name.
Two systems of linear equations in the same unknowns are equivalent if they have the same solution set.
Now we need moves that always produce an equivalent system. There are exactly three, and you've been using all of them since algebra class. We'll call the equations rows and write $R_i$ for the $i$th one (they'll literally become rows of a matrix in a minute).
An elementary row operation on a system (or on a matrix) is one of the following:
The fine print matters: each move changes one row (or swaps two), and it only ever uses numbers, never unknowns.
Which of these are elementary row operations? (a) $R_2 \to R_2 + 3R_1$ (b) $R_1 \leftrightarrow R_3$ (c) $R_1 \to 0R_1$ (d) $R_2 \to 4R_1$
(a) adds a multiple of row 1 to row 2: yes. (b) swaps two rows: yes. (c) multiplies by $0$, and the scaling has to be by a nonzero number: no. (d) replaces row 2 by a multiple of row 1, which throws row 2 away; the allowed move adds a multiple to row 2 and keeps what was there: no.
Swapping two equations counts as an official operation? I've been doing that by accident since sixth grade. I'd like partial credit, backdated.
Notice the "nonzero" in the second move. That's not fine print.
Why can't I multiply a row by $0$? It would turn the equation into $0 = 0$, which is always true, so it solves the equation instantly by... oh. By deleting it.
Exactly: multiplying by $0$ throws an equation away, and you can't get it back. Every legal move can be undone by another legal move: swap the rows back, multiply by $\frac{1}{c}$, or subtract the multiple you added. That's the whole reason they're safe.
If one system of linear equations is obtained from another by an elementary row operation, then the two systems are equivalent. So any sequence of elementary row operations turns a system into an equivalent one.
We show each operation keeps every old solution, and loses nothing.
Interchange. The new system is the same list of equations in a different order, so it has the same solutions.
Scaling by $c \neq 0$. Only row $i$ changes. If $s$ makes row $i$ true, multiplying both sides by $c$ keeps it true. If $s$ makes the scaled row true, multiplying both sides by $\frac{1}{c}$ (which exists because $c \neq 0$) shows the original row is true too.
Adding $kR_j$ to $R_i$ (with $i \neq j$). Only row $i$ changes. If $s$ satisfies the old system, then rows $i$ and $j$ are both true at $s$, so adding $k$ times row $j$ to row $i$ gives another true equation: $s$ satisfies the new system. Conversely, if $s$ satisfies the new system, row $j$ is still there and unchanged, so subtracting $k$ times row $j$ from the new row $i$ gives back the old row $i$, true at $s$.
For a sequence of operations, each step keeps the solution set the same, so the first and last systems have the same solutions. $\blacksquare$
This is a visual argument, not a formal proof. A swap doesn't move any plane; it only changes the order we list them in. Scaling by $c \neq 0$ doesn't move a plane either: $2x + 2y + 2z = 8$ and $x + y + z = 4$ hold at exactly the same points. The interesting move is adding $kR_j$ to $R_i$. A point on both plane $i$ and plane $j$ makes both equations true, so it makes $R_i + kR_j$ true too. So the new plane $i$ still holds the whole line where planes $i$ and $j$ met: it swings around that line like a door on a hinge. Here it is on the $3 \times 3$ system you'll solve later on this page:
Every solution is on every plane, so in particular it's on the hinge, and the hinge doesn't move. Nothing new sneaks in, either: a point on the new plane $i$ and on plane $j$ is on the old plane $i$ too, because subtracting $kR_j$ brings the old equation back. (If planes $i$ and $j$ are parallel there's no hinge, but then no point is on both, and the system had no solutions to begin with.) The full proof is in the n version.
Here's what that theorem looks like with two unknowns. Each row operation changes an equation, so it moves a line, but it can never move the crossing point.
That's the whole strategy in one picture: swing the lines around the solution until they're horizontal and vertical, and then the equations say $x = $ something and $y = $ something. Your turn to swing one. Pick a row, slide $k$, and try to make the lines flat and upright.
Here's a full solve with equations, using all three moves. Each step is a row operation, so each system is equivalent to the one before it.
Solve the system $$\begin{aligned} 3x + 2y &= 7 \\ x - y &= 4. \end{aligned}$$
Put the equation with a plain $x$ on top ($R_1 \leftrightarrow R_2$), then use it to wipe $x$ out of the other one ($R_2 \to R_2 - 3R_1$): $$\begin{aligned} x - y &= 4 \\ 3x + 2y &= 7 \end{aligned} \qquad \longrightarrow \qquad \begin{aligned} x - y &= 4 \\ 5y &= -5. \end{aligned}$$ Scale the second equation ($R_2 \to \frac{1}{5}R_2$), then add it to the first to clear $y$ out of it ($R_1 \to R_1 + R_2$): $$\begin{aligned} x - y &= 4 \\ y &= -1 \end{aligned} \qquad \longrightarrow \qquad \begin{aligned} x &= 3 \\ y &= -1. \end{aligned}$$ The last system has exactly one solution, so the first one does too: $(x, y) = (3, -1)$. Check: $3(3) + 2(-1) = 7$ and $3 - (-1) = 4$.
Here's that solve as two lines. Watch which of the four moves actually moves a line:
Look at that example again. Every step, we rewrote $x$, $y$, $+$, and $=$, and none of them ever changed. Only the numbers did. So let's stop writing the rest and keep just the numbers, in a grid.
The coefficient matrix of a system of $m$ linear equations in $n$ unknowns is the $m \times n$ matrix $A$ whose entry in row $i$, column $j$ is the coefficient of $x_j$ in equation $i$.
The coefficient matrix of a system is the grid of its coefficients: row $i$ holds the coefficients of equation $i$, and the columns belong to $x$, $y$, and $z$, in that order. Three equations in three unknowns give a $3 \times 3$ matrix $A$.
The coefficient matrix forgets the right-hand sides, and we need those too. So tack them on as one more column, with a bar to remind us where the equals signs were.
The augmented matrix $(A|b)$ of a system is its coefficient matrix $A$ with one more column on the right holding the constants $b_1, \ldots, b_m$ of the equations.
The augmented matrix $(A|b)$ of a system is its coefficient matrix $A$ with one more column on the right, $b$, holding the constants of the equations.
Each row of the augmented matrix is one equation, which is why the moves are called row operations. An unknown that's missing from an equation still gets its spot, with a $0$ in it:
Write the augmented matrix of the system $$\begin{aligned} 2x - z &= 5 \\ x + y + 4z &= 0 \\ 3y - z &= -2. \end{aligned}$$
One row per equation and one column per unknown, in the order $x$, $y$, $z$, with the constants after the bar. The first equation has no $y$ and the third has no $x$, so those spots get $0$: $$\left(\begin{array}{rrr|r} 2 & 0 & -1 & 5 \\ 1 & 1 & 4 & 0 \\ 0 & 3 & -1 & -2 \end{array}\right).$$
Each row is still a plane, and the row keeps everything Lines & Planes needs to draw it: the part before the bar is the normal, and the number after the bar slides the plane off the origin.
A row operation on the matrix is the same move as on the equations. Adding $k$ times row $j$ to row $i$ means adding $k$ times each entry of row $j$ to the entry below it in row $i$, all the way across.
All the way across means the last column too. The single most common row-reduction slip is doing the operation to the coefficients and forgetting the number after the bar. That's changing the equation's left side and not its right side, so the "equivalent" system isn't equivalent anymore.
One more thing before you try it: if you read other textbooks, the notation may look a little different.
Other books write these a little differently. Some put square brackets around the augmented matrix, or write it [A b] with no bar. Some write a row operation the other way around, like R2 − 3R1 → R2, and many call the reduced row echelon form of A "rref(A)". Same ideas, different handwriting.
Try one operation on a matrix. Remember: every entry of the row changes, the one after the bar included.
Loading practice engine...
We know the legal moves. Now: where are we going? In the two-line example the finish line was "$x = 3$, $y = -1$": each equation solved for one unknown. For a matrix, the finish line is a staircase shape. To describe it, we need a name for the first number in each row.
The pivot of a nonzero row of a matrix is its leftmost nonzero entry.
Watch out for rows that start with zeros: the pivot is the first entry that isn't zero.
Find the pivot of each row of $$\begin{pmatrix} 0 & 3 & 1 \\ 0 & 0 & 0 \\ 2 & 0 & 5 \end{pmatrix}.$$
Row 1 starts with a $0$, so its pivot is the $3$ in column 2. Row 2 is all zeros, so it has no pivot. Row 3's pivot is the $2$ in column 1. (This matrix isn't in any nice shape yet: the pivot in row 3 is to the left of the one in row 1.)
The staircase comes in two strengths. The first one is what you get by clearing out everything below each pivot.
A matrix is in row echelon form if every row of zeros sits below every nonzero row, and the pivot of each nonzero row is in a column to the right of the pivot of the row above it.
So the pivots step down and to the right, and everything below a pivot is $0$. The stronger version also cleans up above the pivots and scales each pivot to $1$.
A matrix is in reduced row echelon form if it is in row echelon form, every pivot is $1$, and each pivot is the only nonzero entry in its column.
The rules only talk about the pivot columns. Columns without a pivot can hold any numbers at all, and that will matter a lot later.
Is each matrix in row echelon form? In reduced row echelon form? $$P = \begin{pmatrix} 1 & 5 & 0 & 2 \\ 0 & 0 & 1 & -3 \\ 0 & 0 & 0 & 0 \end{pmatrix},$$ $$Q = \begin{pmatrix} 1 & 5 & 2 & 2 \\ 0 & 0 & 3 & -3 \\ 0 & 0 & 0 & 0 \end{pmatrix},$$ $$S = \begin{pmatrix} 0 & 0 & 1 & 4 \\ 1 & 2 & 0 & 0 \end{pmatrix}.$$
$P$: the pivots are in columns 1 and 3, stepping right, with the zero row at the bottom, so it's in row echelon form. Both pivots are $1$ and alone in their columns, so it's reduced too. The $5$ and the $2$ sit in columns 2 and 4, which have no pivot, so they're allowed.
$Q$: same staircase, so row echelon form. But its second pivot is $3$, not $1$, and there's a $2$ above it, so it is not reduced.
$S$: the first row's pivot is in column 3 and the second row's is in column 1, so the pivots step left. Not even row echelon form. Swapping the rows fixes it.
Sort these and see if the rules have sunk in:
Now without the bins.
Loading practice engine...
Here's the recipe that gets any matrix into reduced row echelon form. It runs in two phases.
This recipe is called Gauss–Jordan elimination. Watch the forward phase first:
Zeros below the pivots: row echelon form. The backward phase picks up right there.
This method is in the Nine Chapters on the Mathematical Art, a Chinese textbook that's around 2,000 years old, done with counting rods on a board. Gauss was born in 1777. Naming it after him is like naming pizza after the last person who ordered one.
The recipe never gets stuck: at each stage either there's a nonzero entry to use as a pivot, or the rest of the column is zeros and we move right. So it always finishes, and that's worth stating.
Every matrix can be carried to a matrix in reduced row echelon form by a finite sequence of elementary row operations.
Run Gauss–Jordan elimination. In the forward phase, each stage looks at the rows not yet set aside. If they are all zero, stop. Otherwise take the leftmost column with a nonzero entry among them, swap a row with a nonzero entry there to the top of those rows, and subtract multiples of it to make the entries below it $0$. That row's pivot is in this column, and every row below it is now zero in this column and in every column to its left. Set the row aside and repeat. Each stage sets aside one row, so the phase ends, and when it does, the pivots step to the right going down and the zero rows are at the bottom: row echelon form.
In the backward phase, take the pivots from the bottom up. Scale the pivot's row so the pivot is $1$, then subtract multiples of that row from each row above it to make the entries above the pivot $0$. The row being subtracted is zero to the left of its pivot, so this only changes entries in the pivot's column and to its right. The rows above have their pivots further left, so their pivots stay put, and the matrix stays in row echelon form. After the last pivot, every pivot is $1$ and alone in its column: reduced row echelon form. $\blacksquare$
This is a visual argument, not a formal proof. Run the forward phase and keep count. Each pass looks at one column, below the rows already set aside, and does one of two things: it finds a nonzero entry, makes it a pivot, clears below it, and sets that row aside; or it finds only zeros and steps one column right. Either way, something gets used up. The augmented matrix of a system in $x$, $y$, $z$ has at most 3 rows and 4 columns, so after at most 7 passes the recipe runs out of rows or columns, and it stops in row echelon form:
The backward phase is shorter still: at most three pivots, each scaled to $1$ and used to clear the entries above it. That only changes entries in the pivot's column and to its right, because the row being subtracted is all zeros to the left of its pivot, so the staircase survives. The full proof, for any number of rows and columns, is in the n version.
Put that together with the theorem about row operations, and solving any system is mechanical: write its augmented matrix, row reduce, and read off the answer. Here's one that needs a couple of swaps along the way.
Solve the system $$\begin{aligned} 2y + z &= 3 \\ x + y + z &= 4 \\ 2x + y - z &= 4. \end{aligned}$$
The top-left entry is $0$, so start with $R_1 \leftrightarrow R_2$, then clear below the first pivot with $R_3 \to R_3 - 2R_1$: $$\left(\begin{array}{rrr|r} 0 & 2 & 1 & 3 \\ 1 & 1 & 1 & 4 \\ 2 & 1 & -1 & 4 \end{array}\right) \to \left(\begin{array}{rrr|r} 1 & 1 & 1 & 4 \\ 0 & 2 & 1 & 3 \\ 2 & 1 & -1 & 4 \end{array}\right)$$ $$\to \left(\begin{array}{rrr|r} 1 & 1 & 1 & 4 \\ 0 & 2 & 1 & 3 \\ 0 & -1 & -3 & -4 \end{array}\right).$$ Fractions are legal, but we can dodge them here: swap rows 2 and 3 ($R_2 \leftrightarrow R_3$), flip the sign of the new row 2 ($R_2 \to -R_2$), and clear below it ($R_3 \to R_3 - 2R_2$): $$\left(\begin{array}{rrr|r} 1 & 1 & 1 & 4 \\ 0 & 1 & 3 & 4 \\ 0 & 2 & 1 & 3 \end{array}\right) \to \left(\begin{array}{rrr|r} 1 & 1 & 1 & 4 \\ 0 & 1 & 3 & 4 \\ 0 & 0 & -5 & -5 \end{array}\right).$$ That's row echelon form. Backward phase: $R_3 \to -\frac{1}{5}R_3$, then $R_2 \to R_2 - 3R_3$ and $R_1 \to R_1 - R_3$, then $R_1 \to R_1 - R_2$: $$\left(\begin{array}{rrr|r} 1 & 1 & 1 & 4 \\ 0 & 1 & 3 & 4 \\ 0 & 0 & 1 & 1 \end{array}\right) \to \left(\begin{array}{rrr|r} 1 & 1 & 0 & 3 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{array}\right)$$ $$\to \left(\begin{array}{rrr|r} 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{array}\right).$$ Each row now names one unknown: $(x, y, z) = (2, 1, 1)$. Check in the original system: $2 + 1 = 3$, $2 + 1 + 1 = 4$, and $4 + 1 - 1 = 4$.
Here's the whole solve in space. Every move either leaves the planes alone or swings one on a hinge, until they stand as two walls and a floor:
Your turn. The question doesn't care how you get there, as long as every step is a row operation.
Loading practice engine...
So far every system had exactly one solution, and the reduced form handed it over directly. But we know two other things can happen. Here's a system with more unknowns than equations.
Find every solution of the system $$\begin{aligned} x_1 + 2x_2 - x_3 &= 3 \\ 2x_1 + 4x_2 + x_3 &= 9. \end{aligned}$$
Row reduce with $R_2 \to R_2 - 2R_1$, then $R_2 \to \frac{1}{3}R_2$, then $R_1 \to R_1 + R_2$: $$\left(\begin{array}{rrr|r} 1 & 2 & -1 & 3 \\ 2 & 4 & 1 & 9 \end{array}\right) \to \left(\begin{array}{rrr|r} 1 & 2 & -1 & 3 \\ 0 & 0 & 3 & 3 \end{array}\right)$$ $$\to \left(\begin{array}{rrr|r} 1 & 2 & 0 & 4 \\ 0 & 0 & 1 & 1 \end{array}\right).$$ The reduced form says $x_1 + 2x_2 = 4$ and $x_3 = 1$. Nothing pins down $x_2$: column 2 has no pivot. So let $x_2 = t$ be any number at all. Then $x_1 = 4 - 2t$ and $x_3 = 1$, and the solutions are $$\begin{aligned} (x_1, x_2, x_3) &= (4 - 2t, \ t, \ 1) \\ &= (4, 0, 1) + t(-2, 1, 0), \end{aligned}$$ one solution for every real number $t$. Check $t = 1$: $(2, 1, 1)$ gives $2 + 2 - 1 = 3$ and $4 + 4 + 1 = 9$.
In space: two planes, one line of solutions. Row reduction swings them into a wall and a floor without moving the line, and then $t$ slides along it:
That $x_2$ was free to be anything, and the other unknowns just followed along. Which unknowns get to be free is decided by the columns of the reduced form.
Suppose the augmented matrix of a system has been carried to reduced row echelon form. An unknown whose column holds a pivot is a basic variable, and an unknown whose column holds no pivot is a free variable.
Free variable. Finally, a variable with no responsibilities. The basic variables do all the work and it just takes whatever value it wants.
The answer $(4, 0, 1) + t(-2, 1, 0)$ is written in parametric vector form: one particular solution, plus a free amount of a direction. Set $t = 0$ and you get the particular solution $(4, 0, 1)$; change $t$ and you slide along a line of solutions. That's the line from the very first picture of two solutions. Now we can read any reduced form, all three cases at once.
Suppose the augmented matrix of a system of linear equations has been carried to reduced row echelon form $R$.
By the theorem on row operations, the system with augmented matrix $R$ has the same solutions as the original system, so we read $R$.
If the last column holds a pivot, that pivot's row is $(0 \ \cdots \ 0 \mid 1)$, the equation $0x_1 + \cdots + 0x_n = 1$, which no choice of $x_1, \ldots, x_n$ satisfies. So the system is inconsistent.
Otherwise every nonzero row has its pivot under some unknown $x_p$. Since $R$ is reduced, that row's equation is $x_p$ plus terms in the free variables only, equal to a constant $d$: no other basic variable appears, because each pivot is alone in its column. Rows of zeros say $0 = 0$, which always holds. So a list $(s_1, \ldots, s_n)$ is a solution exactly when each basic variable equals its row's $d$ minus the free-variable terms, evaluated at the free variables' values. Any values of the free variables are allowed, and then the basic variables are determined. So the choices of free-variable values match up exactly with the solutions.
If there are no free variables, there is exactly one choice (of nothing), so exactly one solution. If there is at least one free variable, its infinitely many possible values give infinitely many different solutions. $\blacksquare$
This is a visual argument, not a formal proof. Row operations never change the solutions, so it's enough to read the reduced system. Here are the three kinds of reduced form for $x$, $y$, $z$:
A pivot in every column of $x$, $y$, $z$ means the rows say $x = $ a number, $y = $ a number, and $z = $ a number: two walls and a floor, one corner. A column with no pivot means that unknown can be anything. Pick its value, and each pivot row says exactly what its own unknown must be, because a reduced row holds only its pivot's unknown and free ones. One point for each choice: a line of them, or a plane with two free unknowns. A pivot after the bar is a row $(0 \ 0 \ 0 \mid 1)$, the equation $0 = 1$, which no point satisfies, whatever the other rows say. The full proof is in the n version.
So the reduced form answers everything: a pivot after the bar means no solutions, and otherwise you count the pivot-free columns. Build a few reduced forms and watch the theorem call each one.
Did you try a "none" row in the middle of the build? It has to sit at the bottom, and it never causes trouble.
A row of all zeros, $(0 \ 0 \ 0 \mid 0)$, is not a contradiction. It says $0 = 0$, which is always true; it just means one equation was redundant. Only a row like $(0 \ 0 \ 0 \mid 5)$, which says $0 = 5$, makes a system inconsistent.
With two free variables, the solutions fill a whole plane instead of a line. Here's the single equation $x + 2y - z = 2$. Its reduced form is just that one row, so $y$ and $z$ are both free. Call them $s$ and $t$ and slide them around:
Look at how $x = 2 - 2s + t$ came out of $x + 2y - z = 2$: the $+2y$ turned into $-2s$, and the $-z$ into $+t$. That flip is where most mistakes happen.
When you move a free variable across the equals sign, its sign flips. The row $(1 \ \ 2 \ \ 0 \mid 4)$ says $x_1 + 2x_2 = 4$, so $x_1 = 4 - 2x_2$, and the direction vector gets a $-2$, not a $2$. And don't forget the free variable's own slot: $x_2 = t$ puts a $1$ in the second spot of the direction.
Now read a few reduced forms on your own. Some of them have a nasty surprise in the last row.
Loading practice engine...
One thing might be bugging you. Gauss–Jordan elimination leaves you lots of choices (which row to swap up, when to scale), and two people solving the same system rarely make the same moves. Do they always land on the same reduced form? They do, and that's why "the" reduced row echelon form makes sense.
A matrix can be carried to only one matrix in reduced row echelon form. That is, if elementary row operations carry $A$ to $B$, and other elementary row operations carry $A$ to $C$, and $B$ and $C$ are both in reduced row echelon form, then $B = C$.
We use induction on the number of columns $n$. If $n = 1$, row operations keep a zero column zero and a nonzero column nonzero, and the only reduced forms of a single column are all zeros and a $1$ on top of zeros. So $B = C$.
Now let $n > 1$, and delete the last column of $A$, $B$, and $C$ to get $A'$, $B'$, $C'$. The same row operations carry $A'$ to $B'$ and to $C'$, and deleting the last column of a matrix in reduced row echelon form leaves one in reduced row echelon form. By induction, $B' = C'$. So $B$ and $C$ agree everywhere except possibly in the last column.
Suppose they differ there, say in row $i$. Think of $A$, $B$, and $C$ as coefficient matrices of homogeneous systems, every constant $0$. Row operations on a coefficient matrix are row operations on that system (the constants stay $0$), so by the theorem on row operations the three systems have the same solutions. Let $u$ be any solution. Row $i$ of the $B$ system and row $i$ of the $C$ system are both true at $u$, and their coefficients agree except in column $n$, so subtracting them gives $(b_{in} - c_{in})u_n = 0$, hence $u_n = 0$. So every solution has $u_n = 0$.
That means column $n$ of $B$ holds a pivot: otherwise $x_n$ would be a free variable of the $B$ system, and the theorem on reading reduced forms would give a solution with $x_n = 1$. In the same way column $n$ of $C$ holds a pivot. In a reduced form, a pivot in the last column is a $1$ sitting in the first row below all the pivots of the earlier columns, with zeros everywhere else in that column. Since $B' = C'$, those earlier pivots are the same for $B$ and $C$, so the last columns of $B$ and $C$ are the same. That contradicts our assumption, so $B = C$. $\blacksquare$
This is a visual argument, not a formal proof, and it only covers part of the theorem. Here's the $3 \times 3$ system from earlier, reduced two different ways at once:
The moves are different, so the planes swing differently. But row operations never change the solutions, so both routes keep the same corner, $(2, 1, 1)$. And once a reduced form has a pivot in every column of $x$, $y$, $z$, there are no choices left in it: its rows must say $x = 2$, $y = 1$, $z = 1$, which makes it the matrix $\left(\begin{array}{rrr|r} 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{array}\right)$. So for a system with exactly one solution, every route ends at the same reduced form. When the solutions make a line or a plane the theorem is still true, but the bookkeeping is longer, and the full proof is in the n version.
So whatever moves you make, the reduced form, and with it the set of pivot columns, is the same. That's what lets us talk about the free variables of a system.
One kind of system deserves special attention, because it shows up all over the rest of the course: the kind where every right-hand side is $0$.
A system of linear equations is homogeneous if every constant $b_1, \ldots, b_m$ is $0$, and nonhomogeneous otherwise.
A homogeneous system is never inconsistent: setting every unknown to $0$ makes every equation say $0 = 0$. That all-zero solution is called the trivial solution. The interesting question is whether there are any others.
In pictures: a right-hand side of $0$ means the plane passes through the origin, so every plane of a homogeneous system goes through $0$, and they all meet there at least.
Find every solution of the homogeneous system $$\begin{aligned} x + y - z &= 0 \\ 2x + 3y + z &= 0. \end{aligned}$$
Row reduce with $R_2 \to R_2 - 2R_1$, then $R_1 \to R_1 - R_2$: $$\left(\begin{array}{rrr|r} 1 & 1 & -1 & 0 \\ 2 & 3 & 1 & 0 \end{array}\right) \to \left(\begin{array}{rrr|r} 1 & 1 & -1 & 0 \\ 0 & 1 & 3 & 0 \end{array}\right)$$ $$\to \left(\begin{array}{rrr|r} 1 & 0 & -4 & 0 \\ 0 & 1 & 3 & 0 \end{array}\right).$$ Column 3 has no pivot, so $z = t$ is free, $x = 4t$, and $y = -3t$: $$(x, y, z) = t(4, -3, 1),$$ one solution for every real number $t$. The trivial solution is $t = 0$, and every other $t$ gives a nontrivial one, like $(4, -3, 1)$: check $4 - 3 - 1 = 0$ and $8 - 9 + 1 = 0$.
That direction $(4, -3, 1)$ has a second meaning in space. Both planes pass through $0$, so they meet in a line through $0$, and that line is perpendicular to both normals. On Dot & Cross Products, the arrow perpendicular to two others was their cross product: $(1, 1, -1) \times (2, 3, 1) = (4, -3, 1)$.
Two equations, three unknowns, and a free variable showed up. That's no accident: there just aren't enough equations to hand every unknown its own pivot.
A homogeneous system with fewer equations than unknowns has infinitely many solutions. In particular, it has a nontrivial solution.
Say there are $m$ equations and $n$ unknowns, with $m < n$. Carry the augmented matrix to reduced row echelon form $R$. The last column starts out all zeros, and row operations keep a zero column zero, so the last column of $R$ holds no pivot. Each pivot sits in its own row, so there are at most $m$ pivots, which is fewer than the $n$ unknowns. So some unknown is free, and by the theorem on reading reduced forms the system has infinitely many solutions. Only one of them is trivial. $\blacksquare$
This is a visual argument, not a formal proof. With at most three unknowns there are only three cases with fewer equations than unknowns, and every line or plane in them passes through $0$:
One equation in two unknowns is a line through $0$. One equation in three unknowns is a plane through $0$. Two equations in three unknowns are two planes through $0$, and two planes that share a point are either the same plane or cross in a whole line through it (a fact from solid geometry, and the one this picture leans on). (An equation whose coefficients are all $0$ says $0 = 0$, and every point satisfies it, which only makes more solutions.) In every case there are infinitely many solutions, and only $0$ is trivial. The full proof is in the n version.
On the next page, Solution Sets, every system gets paired with its homogeneous one: the solutions of the real system are one particular solution plus every homogeneous solution.
On the Linear Combinations & Span page, "is this vector a combination of those?" turns into a system of linear equations in the unknown coefficients. Everything on this page is how you'll answer it.
That theorem looks innocent, but it's the engine behind one of the biggest facts in the course: in $\R^n$, you can never have more than $n$ independent directions. Keep it in your back pocket.
That theorem looks innocent, but it's the engine behind one of the biggest facts in the course: in $\R^3$, you can never have more than $3$ independent directions. Keep it in your back pocket.
The number of pivots in a reduced form gets a name later: the rank. On Rank & Inverses, "a pivot after the bar" becomes "the augmented matrix has bigger rank than the coefficient matrix," and the same row operations compute inverse matrices.
Every question so far came right after its idea, which is a hint a quiz never gives you. Down here the hint is gone. First, true or false: a claim from anywhere on this page, and you decide whether it holds.
Loading practice engine...
Next, a mixed set: every question type on this page, shuffled. Figuring out which idea a question needs is half the work.
Loading practice engine...
Made it this far? Time for something with a little heat. Chemists balance reactions by making sure every atom that goes in comes out. That's one linear equation per element, and the whole thing is a homogeneous system with a free variable. Set it up, row reduce, and find the smallest whole-number solution.
Here's the smallest one, hydrogen burning into water: $a\,\mathrm{H_2} + b\,\mathrm{O_2} \to c\,\mathrm{H_2O}$. Three substances means three unknowns, so you can watch it:
A warning before you start: most reactions below have four substances, so four unknowns, one more than this page draws. That's fine. Row reduction never needed a picture. It runs the same way on four unknowns, and the solutions still form a line through $0$, just in a space with four directions instead of three.
Loading practice engine...