Elementary Matrices and Row Operations

We use the fact that for matrices $E \in F^{m\times m}$ and $A \in F^{m \times n}$, the $i$-th row of $EA$ equals

i.e., the $i$-th row of the product is the linear combination of the rows of $A$ whose coefficients are the entries of row $i$ of $E$. This is immediate from the definition of matrix multiplication: entry $(i,j)$ of $EA$ is $\sum_k E_{ik}A_{kj}$, and collecting this over all $j$ for fixed $i$ gives exactly the stated linear combination of the row vectors $A_{k,\bullet}$. We check each type.

Type I. Let $E = P_{ij}$, obtained from $I_m$ by swapping rows $i$ and $j$ ($i \ne j$). Then row $i$ of $P_{ij}$ is $e_j^T$ (the standard basis row with a $1$ in position $j$) and row $j$ of $P_{ij}$ is $e_i^T$; every other row $k \ne i,j$ of $P_{ij}$ equals $e_k^T$. By the row-combination formula above:

• row $i$ of $P_{ij}A$ equals $e_j^T \cdot [\text{rows of } A] = A_{j,\bullet}$,
• row $j$ of $P_{ij}A$ equals $e_i^T \cdot [\text{rows of } A] = A_{i,\bullet}$,
• row $k$ of $P_{ij}A$ equals $A_{k,\bullet}$ for $k \ne i,j$.

Hence $P_{ij}A$ is exactly $A$ with rows $i$ and $j$ swapped, which is the Type I operation applied to $A$.

Type II. Let $E = D_i(c)$ ($c \ne 0$), obtained from $I_m$ by replacing row $i$ with $c\, e_i^T$; every other row $k \ne i$ of $D_i(c)$ equals $e_k^T$. Then row $i$ of $D_i(c)A$ equals $c\, e_i^T \cdot [\text{rows of }A] = cA_{i,\bullet}$, and row $k$ of $D_i(c)A$ equals $A_{k,\bullet}$ for $k \ne i$. Hence $D_i(c)A$ is $A$ with row $i$ scaled by $c$, which is the Type II operation applied to $A$.

Type III. Let $E = T_{ij}(c)$ ($i \ne j$), obtained from $I_m$ by adding $c$ times row $j$ to row $i$: explicitly row $i$ of $T_{ij}(c)$ is $e_i^T + c\, e_j^T$, and every other row $k \ne i$ equals $e_k^T$. Then row $i$ of $T_{ij}(c)A$ equals $(e_i^T + c\,e_j^T)\cdot[\text{rows of }A] = A_{i,\bullet} + cA_{j,\bullet}$, and row $k$ of $T_{ij}(c)A$ equals $A_{k,\bullet}$ for $k \ne i$. Hence $T_{ij}(c)A$ is $A$ with row $i$ replaced by $R_i + cR_j$, which is the Type III operation applied to $A$. In all three cases $EA$ equals $A$ with the corresponding elementary row operation applied. $\blacksquare$

By the previous theorem (row operations are left multiplication by elementary matrices), left-multiplying by $E$ performs an elementary row operation, and every elementary row operation is reversible by another elementary row operation of the same type:

• Swapping rows $i,j$ twice returns $A$ to itself: applying Type I with the same $(i,j)$ undoes Type I.
• Scaling row $i$ by $c \ne 0$ then by $c^{-1}$ (valid since $c \ne 0$ in the field $F$) returns row $i$ to its original value.
• Replacing $R_i$ by $R_i + cR_j$ and then replacing the new $R_i$ by $R_i + (-c)R_j$ returns row $i$ to its original value, since row $j$ is untouched throughout.

Apply this reasoning with $A = I_m$. Applying the Type I operation for indices $(i,j)$ to $I_m$ gives $P_{ij}$; applying it again to $P_{ij}$ returns $I_m$. By the theorem, applying an operation to a matrix $A$ equals left-multiplying by the corresponding elementary matrix, so applying Type I twice to $I_m$ equals $P_{ij}(P_{ij} I_m) = P_{ij}P_{ij}$. Since this returns $I_m$, we get $P_{ij}P_{ij} = I_m$, so $P_{ij}$ is its own inverse. Similarly, applying $D_i(c)$ to $I_m$ gives $D_i(c)$, and then applying the reverse scaling operation (scale row $i$ by $c^{-1}$) to $D_i(c)$ gives $I_m$; the reverse operation is left multiplication by $D_i(c^{-1})$, so $D_i(c^{-1})D_i(c) = I_m$. Since $D_i(c)D_i(c^{-1}) = I_m$ as well (scaling by $c$ then $c^{-1}$ in either order returns to the start, by direct entrywise computation on the diagonal matrix), $D_i(c)$ is invertible with inverse $D_i(c^{-1})$. Finally, applying $T_{ij}(c)$ to $I_m$ gives $T_{ij}(c)$, and applying the reverse addition operation (add $-c$ times row $j$ to row $i$) undoes it, giving $I_m$; this reverse operation is left multiplication by $T_{ij}(-c)$. Hence $T_{ij}(-c)T_{ij}(c) = I_m$. A direct computation confirms $T_{ij}(c)T_{ij}(-c) = I_m$ as well: both are $I_m + cE_{ij}$ and $I_m - cE_{ij}$ types (using matrix units $E_{ij}$ satisfying $E_{ij}E_{ij} = 0$ since $i \ne j$), so

Thus $T_{ij}(c)$ is invertible with inverse $T_{ij}(-c)$. In every case $E^{-1}$ exists and is elementary of the same type. $\blacksquare$

Reflexivity. $A = I_m A$, and $I_m$ is (vacuously, or by convention) the empty product of elementary matrices; so $A \sim A$.

Symmetry. If $B = E_k \cdots E_1 A$ with each $E_i$ elementary, then since each $E_i$ is invertible with elementary inverse $E_i^{-1}$ by the Lemma above, we have

which exhibits $A$ as obtained from $B$ by a finite sequence of elementary matrices ($E_k^{-1}$ first, ..., $E_1^{-1}$ last). Hence $B \sim A$.

Transitivity. If $B = E_k\cdots E_1 A$ and $C = F_l \cdots F_1 B$ for elementary matrices $E_i, F_j$, then

a product of elementary matrices applied to $A$, so $A \sim C$. All three properties hold, so $\sim$ is an equivalence relation. $\blacksquare$

Existence. We argue by induction on the number of columns $n$. Base case $n = 0$: the unique $m \times 0$ matrix is vacuously in RREF. Inductive step: Suppose every matrix with fewer than $n$ columns can be row-reduced to RREF using elementary row operations. Let $A$ have $n$ columns. Consider the leftmost column of $A$, say column $c_1$, that contains a nonzero entry (if no such column exists, $A$ is the zero matrix, already in RREF). Suppose the nonzero entry is in row $r$, i.e., $A_{r,c_1}\ne0$. Apply a Type I operation (row swap $E = P_{1r}$, or the identity if $r=1$) to move this row to the top: this produces a matrix with nonzero entry in position $(1,c_1)$. Apply a Type II operation $D_1(A_{1,c_1}^{-1})$ to scale row $1$ so its $(1,c_1)$ entry becomes $1$ (valid since $A_{1,c_1} \ne 0$ is invertible in the field $F$). Then, for each row $i \ne 1$ with a nonzero entry $a$ in column $c_1$, apply the Type III operation $T_{i,1}(-a)$ to clear it. After these steps, column $c_1$ has a single $1$ in row $1$ and $0$ elsewhere; call the resulting matrix $A'$, obtained from $A$ by finitely many elementary row operations, hence $A \sim A'$. Let $A''$ be the submatrix of $A'$ formed by rows $2,\dots,m$ and columns $c_1+1,\dots,n$; this has fewer than $n$ columns (indeed $n - c_1 < n$ since $c_1 \ge 1$). By the inductive hypothesis, $A''$ is row-equivalent, via elementary row operations acting on rows $2,\ldots,m$ restricted to those columns, to a matrix $R''$ in RREF. Performing the corresponding row operations on rows $2,\dots,m$ of the full matrix $A'$ (leaving row $1$ and columns $1,\dots,c_1$ untouched, since these operations only add multiples of rows $2,\dots,m$ to each other, scale them, or swap them — never touching row $1$) transforms $A'$ into a matrix $R'$ whose submatrix on rows $2,\ldots,m$, columns $c_1+1,\ldots,n$ is $R''$, and whose columns $1,\ldots,c_1$ are unchanged from $A'$ (in particular column $c_1$ is still the standard basis vector $e_1$, since operations restricted to rows $2,\ldots,m$ leave a column that is already zero in those rows unchanged, and leave row $1$ untouched). It remains to clear any nonzero entries appearing above a pivot introduced in the recursive step, in order to satisfy condition (4) for the newly created pivot columns from $R''$. Each pivot in $R''$, lying in some row $i \ge 2$ and column $c \ge c_1+1$, has entry $1$ there and $0$ in that column for all other rows $2,\ldots,m$ (by $R''$ being in RREF, condition 4, applied within rows $2,\ldots,m$). If row $1$ has a nonzero entry $b$ in that pivot column, apply the Type III operation $T_{1,i}(-b)$ to clear it; this does not disturb column $c_1$ (still $e_1$) nor any other already-cleared pivot column, since row $i$ has zero entries in all columns to the left of $c$ except column $c_1$ where it is already $0$, and zero entries in all other already-processed pivot columns (by induction, $R''$'s pivot columns are cleared amongst rows $2,\ldots,m$, and row $i$'s only nonzero entries in columns $\le c$ are the pivot at $c$ itself, given RREF conditions 3–4 for $R''$). Performing this clearing for each pivot column of $R''$, in order from left to right, yields a matrix $R$ satisfying all four RREF conditions, and $R$ is obtained from $A$ by a finite sequence of elementary row operations, so $A \sim R$. This completes the induction, proving existence of an RREF for every $A$.

Uniqueness. Suppose $R$ and $S$ are both in RREF and $A \sim R$, $A \sim S$. By the corollary above (row-equivalence is an equivalence relation), $R \sim S$, so there is an invertible matrix $E$ (a product of elementary matrices) with $S = ER$. We show $R = S$ by proving that RRECF is determined by the linear-algebraic data of $A$ alone, which is preserved under left multiplication by an invertible matrix, using the following two facts, each of which we justify. Fact 1: left multiplication by an invertible matrix $E$ preserves the set of solutions $x \in F^n$ to $Mx = 0$. Indeed $Mx = 0 \iff EMx = 0$, since $E$ invertible implies $EMx=0 \Rightarrow Mx = E^{-1}EMx = E^{-1}0=0$, and conversely $Mx=0\Rightarrow EMx=0$. Hence $R$ and $S = ER$ have the same solution set to $Rx=0$ and $Sx=0$ respectively — indeed the same set, since these are the same equation up to left-multiplying by $E$: $\{x : Sx=0\} = \{x: ERx=0\} = \{x: Rx = 0\}$. Fact 2: left multiplication by an invertible matrix $E$ preserves, for every subset of column indices $\{j_1,\dots,j_k\}$, whether the corresponding columns of $M$ are linearly dependent, and preserves the coefficients of any dependence. Indeed if $M_{\bullet j_1},\ldots,M_{\bullet j_k}$ are columns of $M$ with $\sum_t \lambda_t M_{\bullet j_t} = 0$, then multiplying by $E$ gives $\sum_t \lambda_t (EM)_{\bullet j_t} = 0$ with the same coefficients $\lambda_t$ (since $E$ acts on columns of $M$ exactly as it acts on any vector, by linearity: $E\left(\sum_t \lambda_t M_{\bullet j_t}\right) = \sum_t \lambda_t (E M_{\bullet j_t})$, and $EM_{\bullet j_t} = (EM)_{\bullet j_t}$). Since $E$ is invertible this correspondence of dependence relations is exact (reversible using $E^{-1}$). Now we determine the pivot columns of an RRECF matrix $R$ purely from these two data (solution sets and column dependencies), which are shared by $R$ and $S$ since $S = ER$ with $E$ invertible. Claim: column $j$ of $R$ is a pivot column if and only if column $j$ of $R$ is not a linear combination of the columns of $R$ strictly to its left. If column $j$ is a pivot column, it is the standard basis vector $e_i$ for the row $i$ of that pivot (by RREF conditions 2,4), and no column strictly to the left of $j$ has a nonzero entry in row $i$ (by RRECF condition 3: any pivot in a row above $i$ occurs strictly left of $j$'s column only among columns left of $j$, contributing to rows above $i$, and condition 1 makes rows below the last pivot row zero; more directly, since $R$ is in echelon form, the pivot at $(i,j)$ is the first nonzero entry of row $i$, so every column left of $j$ has $0$ in row $i$, hence any combination of them has $0$ in coordinate $i$, whereas column $j$ has $1$ there) — so $e_i$ cannot be written as such a combination. Conversely if column $j$ is not a pivot column, then (by the echelon structure) it lies weakly to the right of some pivot column(s) whose pivot rows cover every nonzero entry appearing in column $j$: precisely, writing column $j$'s nonzero entries as occurring only in rows that are pivot rows for columns $\le j$ (an immediate consequence of the echelon conditions 1–3, since row $i$ can have a nonzero entry in column $j$ only if row $i$'s pivot column is $\le j$, otherwise the leftmost nonzero entry of row $i$ would occur to the right of $j$, contradicting a nonzero entry at column $j<$ pivot column), column $j$ is exactly the linear combination of the pivot columns at or before $j$ with coefficients equal to its own entries in those pivot rows (again since each pivot column is a standard basis vector). This claim characterizes the pivot columns of $R$ via Fact 2's invariant (linear dependence on columns to the left), so $R$ and $S$ have pivot columns in the identical set of positions $j_1 < j_2 < \cdots < j_k$. Next, for each pivot column $j_t$, both $R$ and $S$ restricted to that column equal $e_t$ (the $t$-th standard basis vector), by RRECF condition 2 and 4 together with condition 3 (pivots occur in strictly increasing rows as columns increase, and since $j_1 < \cdots < j_k$ are the pivot columns in order, the pivot rows must be $1,2,\ldots,k$ respectively — the only way to satisfy strict monotonicity starting from row $\ge 1$, using also that rows above the first pivot row cannot exist by condition 1). So $R$ and $S$ agree exactly on all pivot columns. Finally, for a non-pivot column $j$, both $R_{\bullet j}$ and $S_{\bullet j}$ are the unique linear combination of the pivot columns at or before $j$ reproducing that column's entries in the pivot rows (as shown in the Claim's converse direction) — and since $R,S$ agree on all pivot columns and (by Fact 2, applied to the specific set of columns $\{j_1,\ldots,j_t,j\}$ where $j_t$ is the last pivot column $\le j$) the coefficients of the dependence of column $j$ on the earlier pivot columns are shared between $R$ and $S$, the non-pivot columns of $R$ and $S$ coincide as well. Hence $R = S$ column by column, proving uniqueness. $\blacksquare$