Gaussian Elimination and Row Reduction

It suffices to prove the claim for each of the three operation types, since a general row operation applied to the augmented matrix is one of these three, and the solution set of a system is precisely the solution set determined by its augmented matrix (each row of $[A\mid b]$ is one linear equation).

(Swap.) Interchanging two rows of $[A \mid b]$ merely reorders the list of equations; the set of $x \in F^n$ satisfying all the equations is unaffected by the order in which we list them. So the solution sets are identical.

(Scale.) Suppose row $i$ of $[A \mid b]$, i.e. the equation

is replaced by $c$ times itself, $c \neq 0$, giving

If $x$ satisfies the original equation, multiplying both sides by $c$ shows $x$ satisfies the new equation. Conversely if $x$ satisfies the new equation, multiplying both sides by $c^{-1}$ (which exists since $F$ is a field and $c \neq 0$) recovers the original equation. All other equations in the system are untouched. Hence a vector $x$ satisfies every equation of the new system if and only if it satisfies every equation of the old system, so the solution sets coincide.

(Replacement.) Suppose row $i$ is replaced by $R_i + c R_j$ where $j \neq i$. Write the $i$-th and $j$-th equations of the original system as

The new $i$-th equation is $E_i + c E_j$, meaning

If $x$ satisfies $E_i$ and $E_j$, then adding $c$ times the second to the first shows $x$ satisfies the new equation; combined with the unchanged equations (including $E_j$ itself, which is still present), $x$ satisfies the whole new system. Conversely, if $x$ satisfies the new system, then in particular $x$ satisfies $E_j$ (unchanged) and the new $i$-th equation $E_i + cE_j$. Subtracting $c$ times $E_j$ from the new $i$-th equation recovers exactly $E_i$. So $x$ also satisfies $E_i$, and hence satisfies the entire original system. In all three cases the solution set is unchanged. $\blacksquare$

Induct on the number of elementary row operations used to pass from $[A\mid b]$ to $[A' \mid b']$. If zero operations are used the two matrices are equal and the claim is trivial. If $[A \mid b] \to M_1 \to M_2 \to \cdots \to M_k = [A' \mid b']$ is a chain of $k$ elementary operations, then by the Theorem: Elementary row operations preserve the solution set each consecutive pair in the chain has systems with identical solution sets. Since "having the same solution set" is transitive (if $S(X) = S(Y)$ and $S(Y) = S(Z)$ then $S(X) = S(Z)$, immediate from set equality), the solution set of $[A \mid b]$ equals the solution set of $M_1$, which equals that of $M_2$, and so on, up through $[A' \mid b']$. $\blacksquare$

We give the Gaussian elimination algorithm explicitly and prove by strong induction on $m$ (the number of rows) that it terminates with a matrix in REF. Base case $m = 1$. A single row is trivially in echelon form (conditions (a) and (b) of the definition are vacuous), so no operations are needed. Inductive step. Assume the claim holds for all matrices with fewer than $m$ rows (over any field, any number of columns), and let $A$ be $m \times n$. If $A$ is the zero matrix, it is already in REF (all rows are zero, at the "bottom"); stop. Otherwise, let $c_1$ be the smallest column index such that column $c_1$ of $A$ has some nonzero entry. Among the rows, choose a row with a nonzero entry in column $c_1$ and, if it is not already row $1$, swap it into the first row position (a swap operation). Now $A$'s first row has a nonzero entry $a$ in column $c_1$, and columns $1, \dots, c_1 - 1$ are entirely zero (since $c_1$ was minimal). For each row $i = 2, \dots, m$ with entry $a_{i,c_1}$ in column $c_1$, perform the replacement operation

which is a valid elementary row operation since $F$ is a field, so $a^{-1}$ exists and $a_{i,c_1}/a \in F$. After this, every entry in column $c_1$ below row $1$ is zero, and row $1$ is unchanged in columns $1,\dots,c_1$. Now consider the submatrix $A'$ formed by rows $2$ through $m$ and columns $c_1+1$ through $n$; it has $m - 1 < m$ rows. By the induction hypothesis, a finite sequence of elementary row operations reduces $A'$ to a matrix $R'$ in row echelon form. Performing this same sequence of row operations on rows $2,\dots,m$ of the full matrix (restricted to those columns; entries in columns $1,\dots,c_1$ of these rows are already all zero and are unaffected by operations confined to later columns) yields a matrix $R$ whose first row has leading entry $a$ in column $c_1$, and whose rows $2,\dots,m$ (restricted to columns $c_1+1,\dots,n$) form $R'$, in echelon form. We check $R$ is in REF. Condition (a): the zero rows of $R'$ (bottom of rows $2,\ldots,m$) remain at the bottom, since row $1$ is nonzero (it has the pivot $a$). Condition (b): every pivot in rows $2,\dots,m$ lies in a column $> c_1$ (since these pivots come from $R'$, whose columns are $c_1+1,\dots,n$), so in particular strictly right of row $1$'s pivot at $c_1$; and among rows $2,\dots,m$ themselves, the echelon condition holds because $R'$ is in echelon form. Hence $R$ satisfies both conditions and is in row echelon form. This entire procedure used only finitely many elementary row operations (the swap, at most $m-1$ replacements to clear column $c_1$, and the finitely many operations used recursively on the smaller matrix), so by induction the claim holds for all $m$. $\blacksquare$

Existence. By the Theorem: Every matrix reduces to row echelon form, reduce $A$ to some REF matrix $E$. Process the nonzero rows of $E$ from the bottom row upward. For each nonzero row with pivot entry $p \neq 0$ in column $k$: first scale that row by $p^{-1}$ (valid since $F$ is a field and $p \neq 0$) so the pivot becomes exactly $1$; then, for every other row $i$ with a nonzero entry $q$ in column $k$, replace $R_i \leftarrow R_i - q R_{\text{pivot row}}$ to zero out that entry. We must check this process does not disturb the echelon structure already achieved. Scaling a row by a nonzero constant does not change which entries are zero, so condition (b) (position of pivots) and (a) (zero rows at bottom) are preserved, and the pivot becomes $1$. When we clear column $k$ using the pivot row, we only add multiples of a row whose nonzero entries lie in columns $\geq k$ (by the echelon property, since it's a pivot row with pivot in column $k$) to other rows; this can only change entries in columns $\geq k$ of the target rows, hence cannot alter previously-established pivots in columns $< k$ or disturb already-cleared columns to their left. Since we work from the bottom pivot upward, by the time we clear column $k$, all columns of pivots below row's own pivot have already been made into "unit columns" (a single $1$, rest zero) and remain so, because clearing column $k$ never touches columns $> k$... More carefully: when clearing column $k$ using row $R_p$ (whose only nonzero entries are in columns $\geq k$), the update $R_i \leftarrow R_i - q R_p$ changes entries of $R_i$ only in columns where $R_p$ is nonzero, i.e., columns $\geq k$. In particular it does not change entries of $R_i$ in columns $< k$, so if $R_i$ was already a pivot row with pivot in some column $k' < k$ made into a clean unit column, it stays a clean unit column (its only possible new nonzero entries are in columns $\ge k > k'$, but we specifically zero out its entry in column $k$ itself, and entries in columns strictly between $k'$ and $k$ that are not pivot columns are simply whatever they are — they are not required to be zero for RREF, only pivot columns must be clean). Since we go pivot column by pivot column from right to left (equivalently, bottom row to top row, as pivots increase left-to-right down the rows), each pivot column, once cleared, is never touched again by later steps (which only add multiples of rows with pivots strictly to the right, hence zero in the already-cleared column). After processing every nonzero row, every pivot column has exactly one nonzero entry (a $1$, in its own pivot row), giving conditions (c) and (d). The result $R$ is in RREF, and it was obtained from $A$ by finitely many elementary operations (those used to reach $E$, plus finitely many more here), so $A \sim R$.

Uniqueness. This is the substantial part of the claim. We use the following key fact about row equivalence and linear dependence, proven first. Claim: If $A \sim B$ (both $m\times n$ over $F$), then for every choice of column indices $j_1 < j_2 < \cdots < j_r$, a linear dependence relation

among the corresponding columns of $A$ holds (for scalars $\lambda_i \in F$, not all zero) if and only if the same relation

holds among the corresponding columns of $B$, with the same scalars $\lambda_i$. Proof of claim: It suffices to check this for a single elementary row operation, since row equivalence is a finite chain of these and the property is preserved through each link (transitivity of "same dependence relations hold"). Each elementary row operation corresponds to left-multiplication by an invertible matrix: swapping rows $i,j$ is left-multiplication by a permutation matrix $P$; scaling row $i$ by $c\ne 0$ is left-multiplication by a diagonal matrix $D$ with $c$ in position $(i,i)$ and $1$s elsewhere, which is invertible since $c \ne 0$; replacement $R_i \leftarrow R_i + cR_j$ is left-multiplication by $I + cE_{ij}$ (elementary matrix), whose inverse is $I - cE_{ij}$, confirmed by direct computation $(I+cE_{ij})(I-cE_{ij}) = I - c^2 E_{ij}^2 = I$ when $i \ne j$ (since $E_{ij}E_{ij} = 0$ for $i \neq j$). In every case $B = MA$ for some invertible matrix $M$. Then for any columns, $B_{[:,j_t]} = M A_{[:,j_t]}$, so

If the right-hand relation among the $A$-columns is zero, the left side is $M \cdot 0 = 0$. Conversely if the $B$-relation is zero, since $M$ is invertible, $M^{-1} \cdot 0 = 0$ forces the $A$-relation $\lambda_1 A_{[:,j_1]} + \cdots + \lambda_r A_{[:,j_r]} = 0$ as well (apply $M^{-1}$ to both sides of $M(\cdot) = 0$). This proves the claim for one operation, and hence, by induction on the length of a row-equivalence chain, for row equivalence in general. Now suppose $A \sim R_1$ and $A \sim R_2$, with $R_1, R_2$ in RREF. Since row equivalence is symmetric and transitive (each elementary operation is invertible by another elementary operation of the same type, e.g. a swap undoes a swap, scaling by $c^{-1}$ undoes scaling by $c$, and replacement with $-c$ undoes replacement with $c$; concatenating finite chains gives transitivity), we get $R_1 \sim R_2$. We show the pivot columns of $R_1$ and $R_2$ occur in exactly the same positions, and that $R_1 = R_2$ entirely, by induction on the column index $k = 1, \ldots, n$, maintaining the hypothesis that columns $1,\ldots,k$ of $R_1$ and $R_2$ are identical, and that a column index in $\{1,\ldots,k\}$ is a pivot column of $R_1$ if and only if it is a pivot column of $R_2$. For $k=0$ there is nothing to check. Suppose the hypothesis holds up through column $k-1$; consider column $k$. Case A: column $k$ is a pivot column of $R_1$. Say it is the pivot column for row $p$ of $R_1$ (the $p$-th nonzero row), so among columns $1,\ldots,k$ of $R_1$, exactly the pivot columns of rows $1,\ldots,p$ (all $\le k$, with the one in column $k$ being the newest) are nonzero-supporting, and in particular the columns $1, \ldots, k-1$ contain exactly $p-1$ pivot columns (by the induction hypothesis these are also exactly the pivot columns of $R_2$ among $1,\ldots,k-1$, namely $p - 1$ of them, in identical positions with identical column vectors — since $R_1,R_2$ agree on columns $1,\ldots,k-1$). The columns $j_1 < \cdots < j_{p-1} < k$ of pivot columns before column $k$, together with column $k$ itself, satisfy in $R_1$: column $k$ equals $e_p$ (the $p$-th standard basis vector in $F^m$, using that RREF pivot columns are standard basis vectors and $R_1$'s pivot in column $k$ is in row $p$) which is not a linear combination of the columns $j_1,\ldots,j_{p-1}$ of $R_1$ — those are $e_1,\ldots,e_{p-1}$ respectively (up to relabeling) — no relation $\mu_1 e_1 + \cdots + \mu_{p-1}e_{p-1} = e_p$ can hold since the left side has zero $p$-th coordinate while the right side does not. So there is no linear dependence relation of the form $\mu_1 R_{1[:,j_1]} + \cdots + \mu_{p-1} R_{1[:,j_{p-1}]} - R_{1[:,k]} = 0$. By the Claim, exactly the same absence of relation holds among the corresponding columns of $R_2$: there is no relation $\mu_1 R_{2[:,j_1]} + \cdots + \mu_{p-1}R_{2[:,j_{p-1}]} - R_{2[:,k]} = 0$. Since columns $j_1,\ldots,j_{p-1}$ of $R_2$ are (by the induction hypothesis) the same vectors $e_1,\ldots,e_{p-1}$ as in $R_1$, this means column $k$ of $R_2$, call it $v = R_{2[:,k]}$, is not in the span of $e_1,\ldots,e_{p-1}$; since $R_2$ is in RREF, and its nonzero rows among $1,\ldots,p-1$ already have pivots in columns $j_1,\ldots,j_{p-1}$ (with entries in later columns among rows $1,\ldots,p-1$ possibly nonzero but the columns $j_1,\ldots,j_{p-1}$ are clean unit vectors)... we argue directly: since $v \notin \operatorname{span}(e_1,\dots,e_{p-1})$, some coordinate of $v$ among $\{p, p+1,\ldots,m\}$ is nonzero. If $R_2$ has not yet used a pivot at or before column $k$ beyond row $p-1$, and $R_2$ is in echelon form, the only way column $k$ can have a nonzero entry in row $\ge p$ consistent with the echelon staircase (pivots so far only through row $p-1$, using columns $<k$) is if row $p$ of $R_2$ has its pivot exactly at column $k$ — any nonzero entry in row $p$ or below at column $k$, given no earlier pivot has occurred past row $p - 1$, must itself be a new pivot, and since $R_2$'s columns before $k$ already account for pivots in rows $1,\ldots,p-1$ only, the first available pivot row is $p$, forced to appear in column $k$ (echelon form requires pivots to occur in the earliest available column for each row in sequence, and the argument that $v$ is not in the span of earlier standard basis vectors forces the entry in row $p$, or a still-later row, to be the new leading entry, and REF forces it to be row $p$ exactly since rows are processed top to bottom without skipping). Since $R_2$ is in RREF, this new pivot entry equals $1$ and all other entries of column $k$ are $0$ (conditions (c),(d)), i.e. column $k$ of $R_2$ is exactly $e_p$ — identical to column $k$ of $R_1$. Moreover the pivot for row $p$ occurring at column $k$ in $R_2$, matching $R_1$, extends the induction hypothesis: column $k$ is a pivot column in both, in the same row position, with identical (standard basis) column vector. Case B: column $k$ is not a pivot column of $R_1$. Then, letting $j_1 < \cdots < j_s$ be the pivot columns of $R_1$ among $1,\ldots,k$ (necessarily all $< k$, and by the induction hypothesis identical in $R_2$), column $k$ of $R_1$ is some vector $w$ expressible uniquely as $w = \sum_{t=1}^s \mu_t e_t$ where $\mu_t$ is the entry of $R_1$ in row corresponding to pivot column $j_t$, at column $k$ (this holds because $R_1$ is in RREF: rows below the $s$-th pivot row are entirely zero in columns $\le k$, since column $k$ is not itself a pivot column and no later pivot can occur at or before column $k$; so column $k$'s only possibly-nonzero entries lie in rows $1,\ldots,s$, each such row's nonzero entries besides its own clean pivot column being otherwise free, but restricted to exactly those $s$ coordinates). This gives an explicit dependence relation

By the Claim, the same relation, same scalars $\mu_t$, holds for $R_2$:

using that $R_2$'s pivot columns among $1,\ldots,k-1$ coincide exactly with $R_1$'s (induction hypothesis). Hence column $k$ of $R_2$ equals column $k$ of $R_1$, and since a matrix in RREF has column $k$ a pivot column exactly when it is not in the span of the strictly-earlier pivot columns (standard basis vectors of full support so far), and we've shown $R_{2[:,k]}$ is that specific combination of earlier standard basis vectors, column $k$ is not a pivot column of $R_2$ either. This extends the induction hypothesis to column $k$. By induction, columns $1$ through $n$ of $R_1$ and $R_2$ are all identical, i.e. $R_1 = R_2$. $\blacksquare$