Row Reduction & Rank

Each move can be undone by another move of the same kind, and any solution of the old equations satisfies the new ones, since every new equation is built from old ones. So nothing is gained or lost. In the row picture, replacing $x - y = 1$ in the system $x + y = 3$, $x - y = 1$ by $(x - y) - (x + y) = 1 - 3$, that is $-2y = -2$, swaps a slanted line for the horizontal line $y = 1$ — a different line through the same crossing point $(2, 1)$. Elimination turns lines into ones that are easier to read without moving the solution.

Why the count works: after elimination, every column either holds a pivot or it does not. Pivot columns correspond to variables that back-substitution determines; the other $n - \text{rank}$ columns correspond to variables you may choose freely. Each free choice is one independent direction of solutions of $A\mathbf x = \mathbf 0$, so the columns split exactly as "determined" plus "free": $n = \text{rank} + \text{nullity}$.

In the row picture the left sides $x + 2y$ and $2x + 4y$ describe parallel lines, since the second is twice the first. Elimination says the same thing: $R_2 \gets R_2 - 2R_1$ turns the second row into $(0, 0 \mid h - 6)$, which reads $0 = h - 6$. At $h = 6$ that row is empty and one line is left (infinitely many solutions); at any other $h$, for instance $h = 2$, it is the false statement $0 = -4$ and the lines never meet.

The shape of the answer follows from linearity. If $A\mathbf x_p = \mathbf b$ and $A\mathbf n = \mathbf 0$, then $A(\mathbf x_p + \mathbf n) = \mathbf b + \mathbf 0 = \mathbf b$; conversely, two solutions of $A\mathbf x = \mathbf b$ differ by a solution of $A\mathbf x = \mathbf 0$. So the full solution set is one solution shifted by the whole null space, and the free variables are exactly the coordinates on that null space — one parameter per pivotless column.

Row 2 now says $3z = 3$, so $z = 1$. Row 1 says $x = 3 - 2y + z = 4 - 2y$. Name the free variable $y = t$:

Check in the original equations: $(4 - 2t) + 2t - 1 = 3$ ✓ and $2(4 - 2t) + 4t + 1 = 9$ ✓ for every $t$. Geometrically, two planes in $\mathbb R^3$ that are not parallel meet in a line, and this is that line: through $(4, 0, 1)$ in the direction $(-2, 1, 0)$.

The RREF is $\left[\begin{array}{cccc|c}1&2&0&1&4\\0&0&1&2&3\\0&0&0&0&0\end{array}\right]$: pivots in columns 1 and 3, so $x_2 = s$ and $x_4 = t$ are free. Read each row as "pivot variable $=$ …": $x_1 = 4 - 2s - t$ and $x_3 = 3 - 2t$. So

The zero row was the third equation repeating information (row 3 $=$ row 2 $-$ row 1 in the original), so it constrains nothing. Audit: rank $2$ and nullity $2$ add to the $4$ columns, as rank–nullity demands.

If $k \ne 5$, the last row has a nonzero pivot $k - 5$, so there are three pivots and a unique solution: $(k - 5)z = 0$ gives $z = 0$, then $y = 1 - 2z = 1$, then $x = 1 - y - z = 0$. Check in the third equation: $0 + 3 + 0 = 3$ ✓. If $k = 5$, the last row is all zeros — $z$ becomes free and there are infinitely many solutions. There is no value of $k$ with no solution, because the right-hand entry of that row is $0$ for every $k$. The case split is not optional: dividing by $k - 5$ without asking whether it is zero would miss the whole line of solutions at $k = 5$.

Each step $R_i \gets R_i - mR_j$ is undone by adding $m R_j$ back, so running the steps in reverse rebuilds $A$ from $U$, and the reverse steps assemble into $L$ with the multipliers sitting in place, signs unchanged. The payoff is reuse: elimination costs about $\tfrac{n^3}{3}$ operations, but once $L$ and $U$ are stored, each new right-hand side costs only two triangular solves, about $n^2$ operations. That is why software factors a matrix once and then solves many systems with it.

Check: $LU = \begin{pmatrix}2&1\\3\cdot2&3\cdot1 + 2\end{pmatrix} = \begin{pmatrix}2&1\\6&5\end{pmatrix}$ ✓. Forward solve $L\mathbf y = (3, 13)$: $y_1 = 3$, then $3y_1 + y_2 = 13$ gives $y_2 = 4$. Back solve $U\mathbf x = (3, 4)$: $2x_2 = 4$ gives $x_2 = 2$, then $2x_1 + 2 = 3$ gives $x_1 = \tfrac12$. Check in the original: $2\cdot\tfrac12 + 2 = 3$ ✓ and $6\cdot\tfrac12 + 5\cdot2 = 13$ ✓. In the row picture, the second equation became $2y = 4$ — a horizontal line through the same point.

Column 2: $R_3 \gets R_3 - 2R_2$ gives $(0, 0, 2)$ — multiplier $2$. So

each multiplier stored where it created a zero. Check the bottom row of $LU$: $(3, 2, 1)$ against the columns of $U$ gives $(3,\ 6 + 2,\ 3 + 4 + 2) = (3, 8, 9)$ ✓. A bonus: $\det A = \det L\cdot\det U = 1\cdot(1\cdot1\cdot2) = 2$, the product of the pivots.

Conversely every homogeneous solution is determined by its free-variable values, so these span: the null space has dimension exactly $n - r$. $\blacksquare$

The result is echelon form: pivots marching down and right, zeros below each. Then read off the verdict: a row $(0\,\cdots\,0\,|\,b)$, $b \ne 0$, means inconsistent; otherwise count pivots — every column with a pivot pins a variable, every column without one donates a free parameter. Back-substitution finishes: solve the last pivot equation, substitute upward. The whole of solvability theory — unique/infinite/none, rank, dimension of the solution space — is a bookkeeping layer on this one procedure.

Step 1 — clear column 1 below the pivot: $R_2 \gets R_2 - 2R_1$: $(0, -1, 1\,|\,1)$; $R_3 \gets R_3 - R_1$: $(0, 1, -2\,|\,-4)$.

Step 2 — clear column 2 below the new pivot: $R_3 \gets R_3 + R_2$: $(0, 0, -1\,|\,-3)$.

Step 3 — echelon form reached with three pivots ($1, -1, -1$): a unique solution exists.

Step 4 — back-substitute: from row 3, $z = 3$; from row 2, $-y + 3 = 1$ so $y = 2$; from row 1, $x = 6 - 2 - 3 = 1$.

Step 5 — verify in the original equations: $1 + 2 + 3 = 6$ ✓, $2 + 2 + 9 = 13$ ✓, $1 + 4 - 3 = 2$ ✓. The verification step costs ten seconds and catches nearly every slip.

Step 1: $R_2 \gets R_2 - 2R_1 = (0,0,0)$ — row 2 was twice row 1, and elimination exposes the dependence as a zero row. Step 2: $R_3 \gets R_3 - R_1 = (0,-1,-2)$. Echelon form: pivots in columns 1 and 2, none in column 3: rank $2$.

Step 3 — the homogeneous solutions: $z$ is free; row 2 gives $y = -2z$; row 1 gives $x = -2y - 3z = 4z - 3z = z$. So the null space is the line of multiples of $(1, -2, 1)$, dimension $1$ — and rank–nullity checks: $3$ columns $= 2$ (rank) $+ 1$ (nullity) ✓. Rank counts surviving information; nullity counts what the matrix destroys.