3.3 Uniqueness of the Reduced Form

Gauss–Jordan elimination involves choices: which non-zero entry to use as a pivot, and in what order to perform the operations. Different choices give different intermediate matrices, and different row echelon forms. The previous section claimed that they always end at the same reduced row echelon form. This matters more than it seems. Pivot columns, free variables, and later the rank of a matrix are all read off from the reduced form; if two people could reduce the same matrix to two different answers, none of these would be well defined. This section proves the claim.

3.3.1. What row operations remember

Row operations change the columns of a matrix. What do they keep? Take $\mathbf{A} = \begin{pmatrix} 1 & 2 & 1 & 3 \\ 2 & 4 & 0 & 2 \\ 3 & 6 & 2 & 7 \end{pmatrix} \quad \text{and its RREF} \quad \mathbf{R} = \begin{pmatrix} 1 & 2 & 0 & 1 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 \end{pmatrix}$ over $\mathbb{R}$ (the computation is carried out in an example later in this section). The columns of $\mathbf{R}$ look nothing like those of $\mathbf{A}$ . But look at how the columns depend on each other. In $\mathbf{R}$ , column 2 is twice column 1, and column 4 is column 1 plus twice column 3. In $\mathbf{A}$ , with columns $\mathbf{a}_1, \dots, \mathbf{a}_4$ , $\mathbf{a}_2 = (2, 4, 6) = 2\mathbf{a}_1, \qquad \mathbf{a}_4 = (3, 2, 7) = (1, 2, 3) + 2(1, 0, 2) = \mathbf{a}_1 + 2\mathbf{a}_3 .$ The same relations, with the same coefficients. This is no accident. A relation $x_1\mathbf{a}_1 + \dots + x_n\mathbf{a}_n = \mathbf{0}$ among the columns says $\mathbf{A}\mathbf{x} = \mathbf{0}$ (Theorem 0.9.3), and row operations do not change the solutions of a homogeneous system.

Lemma 3.3.1 (Row equivalent matrices have the same homogeneous solutions)

Let $\mathbf{A}, \mathbf{B} \in M_{m \times n}(F)$ be row equivalent. Then for every $\mathbf{x} \in F^n$ , $\mathbf{A}\mathbf{x} = \mathbf{0}$ if and only if $\mathbf{B}\mathbf{x} = \mathbf{0}$ .

Proof. Let a sequence of elementary row operations turn $\mathbf{A}$ into $\mathbf{B}$ . By Lemma 3.2.1, the same sequence turns $[\, \mathbf{A} \mid \mathbf{0} \,]$ into $[\, \mathbf{B} \mid \mathbf{0}' \,]$ , where $\mathbf{0}'$ is obtained from the zero column by row operations and so is again the zero column. Hence $[\, \mathbf{A} \mid \mathbf{0} \,]$ and $[\, \mathbf{B} \mid \mathbf{0} \,]$ are row equivalent, and by Theorem 3.2.2 (c) the systems $\mathbf{A}\mathbf{x} = \mathbf{0}$ and $\mathbf{B}\mathbf{x} = \mathbf{0}$ have the same solution set.

Rewriting $\mathbf{A}\mathbf{x}$ as a combination of columns turns the lemma into the statement we observed.

Lemma 3.3.2 (Row operations preserve column relations)

Let $\mathbf{A}, \mathbf{B} \in M_{m \times n}(F)$ have columns $\mathbf{a}_1, \dots, \mathbf{a}_n$ and $\mathbf{b}_1, \dots, \mathbf{b}_n$ , and suppose that $\mathbf{A}\mathbf{x} = \mathbf{0} \Leftrightarrow \mathbf{B}\mathbf{x} = \mathbf{0}$ for every $\mathbf{x} \in F^n$ . This holds, for instance, if $\mathbf{A}$ and $\mathbf{B}$ are row equivalent (Lemma 3.3.1). Then:

(a) for all $x_1, \dots, x_n \in F$ : $x_1\mathbf{a}_1 + \dots + x_n\mathbf{a}_n = \mathbf{0}$ if and only if $x_1\mathbf{b}_1 + \dots + x_n\mathbf{b}_n = \mathbf{0}$ ;
(b) for every index $l$ and all scalars $d_1, \dots, d_{l-1}$ : $\mathbf{a}_l = d_1\mathbf{a}_1 + \dots + d_{l-1}\mathbf{a}_{l-1}$ if and only if $\mathbf{b}_l = d_1\mathbf{b}_1 + \dots + d_{l-1}\mathbf{b}_{l-1}$ ;
(c) for every index $l$ : $\mathbf{a}_l \in \operatorname{span}(\mathbf{a}_1, \dots, \mathbf{a}_{l-1})$ if and only if $\mathbf{b}_l \in \operatorname{span}(\mathbf{b}_1, \dots, \mathbf{b}_{l-1})$ .

Proof.

(a) By Theorem 0.9.3, $x_1\mathbf{a}_1 + \dots + x_n\mathbf{a}_n = \mathbf{A}\mathbf{x}$ and $x_1\mathbf{b}_1 + \dots + x_n\mathbf{b}_n = \mathbf{B}\mathbf{x}$ , where $\mathbf{x} = (x_1, \dots, x_n)$ . The hypothesis says $\mathbf{A}\mathbf{x} = \mathbf{0} \Leftrightarrow \mathbf{B}\mathbf{x} = \mathbf{0}$ .
(b) The equation $\mathbf{a}_l = d_1\mathbf{a}_1 + \dots + d_{l-1}\mathbf{a}_{l-1}$ holds if and only if $d_1\mathbf{a}_1 + \dots + d_{l-1}\mathbf{a}_{l-1} + (-1)\mathbf{a}_l + 0\mathbf{a}_{l+1} + \dots + 0\mathbf{a}_n = \mathbf{0}$ . By (a), with these coefficients, this holds if and only if the same combination of the $\mathbf{b}_j$ is $\mathbf{0}$ , that is, $\mathbf{b}_l = d_1\mathbf{b}_1 + \dots + d_{l-1}\mathbf{b}_{l-1}$ .
(c) By Definition 1.3.2, $\mathbf{a}_l \in \operatorname{span}(\mathbf{a}_1, \dots, \mathbf{a}_{l-1})$ means that the left side of (b) holds for some scalars $d_1, \dots, d_{l-1}$ . By (b) this happens if and only if the right side holds for some scalars, which means $\mathbf{b}_l \in \operatorname{span}(\mathbf{b}_1, \dots, \mathbf{b}_{l-1})$ .

Warning. Row operations preserve column relations, not columns or their span. For $\mathbf{A} = \begin{pmatrix} 1 & 2 \\ 1 & 2 \end{pmatrix}$ over $\mathbb{R}$ , the operation $R_2 \to R_2 - R_1$ gives $\begin{pmatrix} 1 & 2 \\ 0 & 0 \end{pmatrix}$ . The relation “column 2 $= 2 \cdot$ column 1” holds in both. But every column of $\mathbf{A}$ lies on the line $\operatorname{span}((1, 1))$ , and every column of the new matrix lies on the different line $\operatorname{span}((1, 0))$ . So the span of the columns changed. To answer a question about the columns of $\mathbf{A}$ themselves, find the relations from the reduced form, and then use them on the columns of $\mathbf{A}$ .

3.3.2. The columns of a reduced matrix

In a matrix in RREF, the column relations can be read off at a glance: pivot columns are standard basis vectors, and a non-pivot column displays its own coefficients. We record this precisely, together with a description of the pivot columns that does not mention pivots at all.

Lemma 3.3.3 (Columns of a matrix in RREF)

Let $\mathbf{R} \in M_{m \times n}(F)$ be in reduced row echelon form, with entries $r_{il}$ , columns $\mathbf{u}_1, \dots, \mathbf{u}_n$ , and pivot columns $j_1 < \dots < j_r$ .

(a) For each $i = 1, \dots, r$ , the pivot column $\mathbf{u}_{j_i}$ is $\mathbf{e}_i$ .
(b) If $l$ is not a pivot column, then $\mathbf{u}_l = \sum_{i \,:\, j_i < l} r_{il}\, \mathbf{e}_i = \sum_{i \,:\, j_i < l} r_{il}\, \mathbf{u}_{j_i} .$
(c) Column $l$ is a pivot column if and only if $\mathbf{u}_l \notin \operatorname{span}(\mathbf{u}_1, \dots, \mathbf{u}_{l-1})$ .

Proof.

(a) By (E3) the entry of $\mathbf{u}_{j_i}$ in row $i$ is $1$ , and by (E4) its other entries are $0$ .
(b) Let $l$ be a non-pivot column, and look at the entry $r_{il}$ in each row $i$ . If $i > r$ , row $i$ is zero by (E1), so $r_{il} = 0$ . If $i \le r$ and $j_i > l$ , then $r_{il}$ lies strictly before the leading entry of row $i$ , so $r_{il} = 0$ . The case $j_i = l$ does not occur, since $l$ is not a pivot column. So the only possibly non-zero entries of $\mathbf{u}_l$ are the $r_{il}$ with $j_i < l$ , which gives the first expression; the second follows from (a).
(c) If $l$ is not a pivot column, (b) writes $\mathbf{u}_l$ as a combination of the columns $\mathbf{u}_{j_i}$ with $j_i < l$ , so $\mathbf{u}_l \in \operatorname{span}(\mathbf{u}_1, \dots, \mathbf{u}_{l-1})$ . Conversely, let $l = j_i$ be a pivot column. For each $l' < j_i$ , the entry $r_{il'}$ lies before the leading entry of row $i$ , so it is $0$ . Hence every vector of $\operatorname{span}(\mathbf{u}_1, \dots, \mathbf{u}_{l-1})$ , being a combination of vectors with $i$ -th entry $0$ , has $i$ -th entry $0$ . But $\mathbf{u}_l = \mathbf{e}_i$ has $i$ -th entry $1 \neq 0$ , so $\mathbf{u}_l \notin \operatorname{span}(\mathbf{u}_1, \dots, \mathbf{u}_{l-1})$ .

Part (c) says: reading the columns from left to right, a column gets a pivot exactly when it is new, not a combination of the columns before it. That condition is about column relations only, and column relations survive row operations. This is the whole idea of the uniqueness proof.

3.3.3. The uniqueness theorem

We can now prove that the reduced form depends only on the homogeneous solutions, and hence not on the operations used to reach it.

Theorem 3.3.4 (Uniqueness of the reduced row echelon form)

Let $\mathbf{R}, \mathbf{R}' \in M_{m \times n}(F)$ be in reduced row echelon form, and suppose that $\mathbf{R}\mathbf{x} = \mathbf{0} \Leftrightarrow \mathbf{R}'\mathbf{x} = \mathbf{0}$ for every $\mathbf{x} \in F^n$ . Then $\mathbf{R} = \mathbf{R}'$ .

Consequently, every matrix $\mathbf{A} \in M_{m \times n}(F)$ is row equivalent to exactly one matrix in reduced row echelon form, called the RREF of $\mathbf{A}$ .

Idea. A column dependence $\sum_j x_j \mathbf{u}_j = \mathbf{0}$ is exactly a null vector $\mathbf{x}$ , so $\mathbf{R}$ and $\mathbf{R}'$ have the same column relations. The pivot columns are exactly the columns that are not combinations of earlier columns (Lemma 3.3.3 (c)), so $\mathbf{R}$ and $\mathbf{R}'$ have the same pivot columns. A pivot column is a standard basis vector in both. A non-pivot column of an RREF matrix is determined by how it is built from the pivot columns before it (Lemma 3.3.3 (b)), and that recipe is a column relation, so it is the same in both. Hence every column agrees.

Proof. Let $\mathbf{u}_1, \dots, \mathbf{u}_n$ and $\mathbf{u}'_1, \dots, \mathbf{u}'_n$ be the columns of $\mathbf{R}$ and $\mathbf{R}'$ , and $r_{il}$ the entries of $\mathbf{R}$ . By hypothesis, Lemma 3.3.2 applies to $\mathbf{R}$ and $\mathbf{R}'$ .

Same pivot columns. For each $l$ , by Lemma 3.3.2 (c), $\mathbf{u}_l \in \operatorname{span}(\mathbf{u}_1, \dots, \mathbf{u}_{l-1})$ if and only if $\mathbf{u}'_l \in \operatorname{span}(\mathbf{u}'_1, \dots, \mathbf{u}'_{l-1})$ . By Lemma 3.3.3 (c) applied to $\mathbf{R}$ and to $\mathbf{R}'$ , column $l$ is a pivot column of $\mathbf{R}$ if and only if it is a pivot column of $\mathbf{R}'$ . So both matrices have the same pivot columns $j_1 < \dots < j_r$ .

Pivot columns agree. By Lemma 3.3.3 (a), $\mathbf{u}_{j_i} = \mathbf{e}_i = \mathbf{u}'_{j_i}$ for $i = 1, \dots, r$ .

Same non-pivot columns. Let $l$ be a non-pivot column. By Lemma 3.3.3 (b) for $\mathbf{R}$ , $\mathbf{u}_l = \sum_{i \,:\, j_i < l} r_{il}\, \mathbf{u}_{j_i} .$ This is an equation of the form in Lemma 3.3.2 (b), with coefficient $r_{il}$ on column $j_i$ and $0$ on the other earlier columns. By that lemma, the same equation holds for $\mathbf{R}'$ : $\mathbf{u}'_l = \sum_{i \,:\, j_i < l} r_{il}\, \mathbf{u}'_{j_i} = \sum_{i \,:\, j_i < l} r_{il}\, \mathbf{e}_i = \mathbf{u}_l ,$ where the middle equality uses Lemma 3.3.3 (a) for $\mathbf{R}'$ , and the last uses Lemma 3.3.3 (b) for $\mathbf{R}$ .

Hence $\mathbf{u}_l = \mathbf{u}'_l$ for every $l$ , and $\mathbf{R} = \mathbf{R}'$ .

For the consequence, let $\mathbf{A} \in M_{m \times n}(F)$ . By Theorem 3.2.3, $\mathbf{A}$ is row equivalent to at least one matrix in RREF. Suppose $\mathbf{A}$ is row equivalent to $\mathbf{R}$ and to $\mathbf{R}'$ , both in RREF. Row equivalence is an equivalence relation (Theorem 3.2.2 (b)), so $\mathbf{R}$ is row equivalent to $\mathbf{R}'$ . By Lemma 3.3.1, $\mathbf{R}\mathbf{x} = \mathbf{0} \Leftrightarrow \mathbf{R}'\mathbf{x} = \mathbf{0}$ for every $\mathbf{x}$ , and by the first part $\mathbf{R} = \mathbf{R}'$ . This proves the theorem.

Notice what the proof did not do: it never compared the two sequences of operations. A direct comparison of two runs of the algorithm would have to track every choice, and quickly becomes unmanageable. The proof instead found a description of the RREF, “pivots where a new column appears, and coefficients of the old columns elsewhere”, that refers only to the null space, which the operations cannot change.

The theorem also gives a practical test: two matrices of the same size are row equivalent exactly when their RREFs are equal (you will write out the two-line proof in Exercise (B2: Row equivalence via the RREF)). For example, over $\mathbb{R}$ , $\begin{pmatrix} 1 & 2 \\ 2 & 4 \end{pmatrix}$ and $\begin{pmatrix} 2 & 4 \\ 0 & 0 \end{pmatrix}$ both reduce to $\begin{pmatrix} 1 & 2 \\ 0 & 0 \end{pmatrix}$ , by $R_2 \to R_2 - 2R_1$ and by $R_1 \to \tfrac12 R_1$ respectively, so they are row equivalent. But $\begin{pmatrix} 1 & 3 \\ 2 & 6 \end{pmatrix}$ reduces to $\begin{pmatrix} 1 & 3 \\ 0 & 0 \end{pmatrix} \neq \begin{pmatrix} 1 & 2 \\ 0 & 0 \end{pmatrix}$ , so it is row equivalent to neither, even though all three matrices have the same pivot columns.

Example (Two echelon forms, one reduced form)

Let $\mathbf{A} = \begin{pmatrix} 1 & 2 & 1 & 3 \\ 2 & 4 & 0 & 2 \\ 3 & 6 & 2 & 7 \end{pmatrix}$ over $\mathbb{R}$ .

(a) Reduce $\mathbf{A}$ to a row echelon form in two ways: first using row 1 as the first pivot row, then starting with $R_1 \leftrightarrow R_2$ .
(b) Continue both to reduced row echelon form.
(c) Read the column relations of $\mathbf{A}$ off the RREF.

Solution.

(a) First route: $\begin{aligned} \mathbf{A} \xrightarrow{R_2 \to R_2 - 2R_1} \begin{pmatrix} 1 & 2 & 1 & 3 \\ 0 & 0 & -2 & -4 \\ 3 & 6 & 2 & 7 \end{pmatrix} &\xrightarrow{R_3 \to R_3 - 3R_1} \begin{pmatrix} 1 & 2 & 1 & 3 \\ 0 & 0 & -2 & -4 \\ 0 & 0 & -1 & -2 \end{pmatrix} \\ &\xrightarrow{R_3 \to R_3 - \frac12 R_2} \begin{pmatrix} 1 & 2 & 1 & 3 \\ 0 & 0 & -2 & -4 \\ 0 & 0 & 0 & 0 \end{pmatrix} = \mathbf{E}_1 . \end{aligned}$ Second route: $\begin{aligned} \mathbf{A} \xrightarrow{R_1 \leftrightarrow R_2} \begin{pmatrix} 2 & 4 & 0 & 2 \\ 1 & 2 & 1 & 3 \\ 3 & 6 & 2 & 7 \end{pmatrix} &\xrightarrow{R_2 \to R_2 - \frac12 R_1} \begin{pmatrix} 2 & 4 & 0 & 2 \\ 0 & 0 & 1 & 2 \\ 3 & 6 & 2 & 7 \end{pmatrix} \\ &\xrightarrow{R_3 \to R_3 - \frac32 R_1} \begin{pmatrix} 2 & 4 & 0 & 2 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 2 & 4 \end{pmatrix} \\ &\xrightarrow{R_3 \to R_3 - 2R_2} \begin{pmatrix} 2 & 4 & 0 & 2 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 \end{pmatrix} = \mathbf{E}_2 . \end{aligned}$ Both $\mathbf{E}_1$ and $\mathbf{E}_2$ are in row echelon form, and $\mathbf{E}_1 \neq \mathbf{E}_2$ . Both have pivot columns 1 and 3.
(b) From $\mathbf{E}_1$ : $\mathbf{E}_1 \xrightarrow{R_2 \to -\frac12 R_2} \begin{pmatrix} 1 & 2 & 1 & 3 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 \end{pmatrix} \xrightarrow{R_1 \to R_1 - R_2} \begin{pmatrix} 1 & 2 & 0 & 1 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 \end{pmatrix}.$ From $\mathbf{E}_2$ : $\mathbf{E}_2 \xrightarrow{R_1 \to \frac12 R_1} \begin{pmatrix} 1 & 2 & 0 & 1 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 \end{pmatrix}.$ The two routes end at the same matrix $\mathbf{R}$ , as Theorem 3.3.4 guarantees.
(c) By Lemma 3.3.3 (b), the non-pivot columns of $\mathbf{R}$ are $\mathbf{u}_2 = 2\mathbf{u}_1$ and $\mathbf{u}_4 = 1 \cdot \mathbf{u}_1 + 2\mathbf{u}_3$ , reading the coefficients from the entries of each column. By Lemma 3.3.2 (b), the same relations hold for the columns of $\mathbf{A}$ : $\mathbf{a}_2 = 2\mathbf{a}_1$ and $\mathbf{a}_4 = \mathbf{a}_1 + 2\mathbf{a}_3$ . Check: $2(1, 2, 3) = (2, 4, 6)$ and $(1, 2, 3) + 2(1, 0, 2) = (3, 2, 7)$ .

Both echelon forms in the example had the same pivot columns, although they were different matrices. That is also true in general, and it is the practical version of the theorem.

3.3.4. Pivot columns are well defined

Corollary 3.3.5 (Pivot columns are well defined)

Let $\mathbf{A} \in M_{m \times n}(F)$ have columns $\mathbf{a}_1, \dots, \mathbf{a}_n$ . Define the pivot columns of $\mathbf{A}$ to be the pivot columns of the RREF of $\mathbf{A}$ .

(a) Column $l$ is a pivot column of $\mathbf{A}$ if and only if $\mathbf{a}_l \notin \operatorname{span}(\mathbf{a}_1, \dots, \mathbf{a}_{l-1})$ .
(b) If $\mathbf{E}$ is any matrix in row echelon form that is row equivalent to $\mathbf{A}$ , then the pivot columns of $\mathbf{E}$ are the pivot columns of $\mathbf{A}$ . In particular, every row echelon form of $\mathbf{A}$ has the same number of non-zero rows.

Idea. Part (a) combines Lemma 3.3.3 (c) with the fact that column relations pass from the RREF back to $\mathbf{A}$ . For (b), finish the reduction of $\mathbf{E}$ : scale each pivot to $1$ and clear the entries above the pivots. These operations never move a leading entry, so they produce a matrix in RREF with the same pivot columns as $\mathbf{E}$ , and by uniqueness it is the RREF of $\mathbf{A}$ .

Proof. The RREF of $\mathbf{A}$ is well defined by Theorem 3.3.4; let $\mathbf{u}_1, \dots, \mathbf{u}_n$ be its columns.

(a) $\mathbf{A}$ and its RREF are row equivalent, so by Lemma 3.3.2 (c), $\mathbf{a}_l \in \operatorname{span}(\mathbf{a}_1, \dots, \mathbf{a}_{l-1})$ if and only if $\mathbf{u}_l \in \operatorname{span}(\mathbf{u}_1, \dots, \mathbf{u}_{l-1})$ . By Lemma 3.3.3 (c), the latter fails exactly when $l$ is a pivot column.
(b) Let $\mathbf{E}$ have entries $e_{hl}$ and pivot columns $j_1 < \dots < j_s$ . First perform $R_i \to e_{i j_i}^{-1} R_i$ for $i = 1, \dots, s$ , which is legal since each pivot $e_{i j_i}$ is non-zero. Scaling a row by a non-zero scalar does not change which of its entries are zero (Theorem 0.7.1 (d), (f)), so the result is still in row echelon form with the same pivot columns, and now every pivot is $1$ . Next, for $i = 1, 2, \dots, s$ in turn, and for each $h < i$ , perform $R_h \to R_h - cR_i$ , where $c$ is the current entry of row $h$ in column $j_i$ . Row $i$ is zero in all columns before $j_i$ , so this changes row $h$ only in columns $\ge j_i > j_h$ . Hence the leading entry of row $h$ is still a $1$ in column $j_h$ , no zero row is touched, and the entries below every pivot stay $0$ . The operation makes the entry in position $(h, j_i)$ equal to $0$ , and it does not spoil the entries $(h, j_{i'})$ with $i' < i$ cleared earlier, because row $i$ has a $0$ in column $j_{i'} < j_i$ . At the end, every pivot column is a standard basis vector, so the matrix is in RREF, with pivot columns $j_1, \dots, j_s$ .

This matrix is row equivalent to $\mathbf{E}$ , hence to $\mathbf{A}$ (Theorem 3.2.2 (b)). By Theorem 3.3.4 it is the RREF of $\mathbf{A}$ . Therefore the pivot columns of $\mathbf{E}$ are those of $\mathbf{A}$ . Since the non-zero rows of $\mathbf{E}$ correspond one-to-one to its pivots, their number $s$ is the number of pivot columns of $\mathbf{A}$ , whichever $\mathbf{E}$ we chose.

In practice, (b) means we may stop at any row echelon form to find the pivot columns, and (a) means we can sometimes find them with no elimination at all. Part (a) also says that the pivot columns of $\mathbf{A}$ are exactly the columns kept when the list $(\mathbf{a}_1, \dots, \mathbf{a}_n)$ is sifted as in Theorem 1.5.4: a column is kept exactly when it is not in the span of the columns before it. The number of pivot columns is the first candidate for a measure of “how much a matrix contains”; later in this chapter it becomes the rank.

Quick check. Without computing any row operations, find the pivot columns of $\mathbf{A} = \begin{pmatrix} 1 & 2 & 0 & 1 \\ 2 & 4 & 1 & 3 \end{pmatrix}$ over $\mathbb{R}$ .

Solution. Use Corollary 3.3.5 (a) column by column. $\mathbf{a}_1 = (1, 2) \neq \mathbf{0}$ , so it is not in $\operatorname{span}() = \{ \mathbf{0} \}$ : pivot. $\mathbf{a}_2 = (2, 4) = 2\mathbf{a}_1$ : not a pivot. $\mathbf{a}_3 = (0, 1)$ is not a multiple of $(1, 2)$ , and $\operatorname{span}(\mathbf{a}_1, \mathbf{a}_2) = \operatorname{span}((1, 2))$ : pivot. $\mathbf{a}_4 = (1, 3) = \mathbf{a}_1 + \mathbf{a}_3$ : not a pivot. The pivot columns are 1 and 3.

Warning. Uniqueness is a property of the reduced form only. A matrix has many row echelon forms (Example (Two echelon forms, one reduced form) gave two), and it is only their pivot positions that agree. Also, two different matrices in RREF with the same pivot columns need not be row equivalent: $\begin{pmatrix} 1 & 2 \end{pmatrix}$ and $\begin{pmatrix} 1 & 3 \end{pmatrix}$ are both in RREF with pivot column 1, but they are different RREF matrices, so by Theorem 3.3.4 neither is row equivalent to the other.

3.3.5. Exercises

A. Check your understanding

Exercise (A1)

(a) State the uniqueness theorem for the reduced row echelon form.
(b) Determine whether the following statement is true: “if $\mathbf{A}$ and $\mathbf{B}$ are row equivalent, then the columns of $\mathbf{A}$ and the columns of $\mathbf{B}$ span the same subspace.” Justify your answer.
(c) Determine whether the following statement is true: “if $\mathbf{A}$ and $\mathbf{B}$ are row equivalent and $\mathbf{a}_3 = \mathbf{a}_1 - \mathbf{a}_2$ for the columns of $\mathbf{A}$ , then $\mathbf{b}_3 = \mathbf{b}_1 - \mathbf{b}_2$ for the columns of $\mathbf{B}$ .” Justify your answer.
(d) Determine whether the following statement is true: “any two row echelon forms of the same matrix have the same number of zero rows.” Justify your answer.
(e) In the RREF of a matrix, what do the entries of a non-pivot column tell you about the original matrix?

Solution.

(a) If $\mathbf{R}, \mathbf{R}' \in M_{m \times n}(F)$ are in RREF and $\mathbf{R}\mathbf{x} = \mathbf{0} \Leftrightarrow \mathbf{R}'\mathbf{x} = \mathbf{0}$ for all $\mathbf{x} \in F^n$ , then $\mathbf{R} = \mathbf{R}'$ . Hence every matrix is row equivalent to exactly one matrix in RREF.
(b) False. $\begin{pmatrix} 1 & 2 \\ 1 & 2 \end{pmatrix}$ and $\begin{pmatrix} 1 & 2 \\ 0 & 0 \end{pmatrix}$ are row equivalent, but their columns span $\operatorname{span}((1, 1))$ and $\operatorname{span}((1, 0))$ , which are different lines in $\mathbb{R}^2$ .
(c) True, by Lemma 3.3.2 (b) with $l = 3$ , $d_1 = 1$ , $d_2 = -1$ .
(d) True. By Corollary 3.3.5 (b), every row echelon form of an $m \times n$ matrix $\mathbf{A}$ has exactly as many non-zero rows as $\mathbf{A}$ has pivot columns, so the number of zero rows is $m$ minus that number.
(e) If column $l$ is not a pivot column, its entries $r_{il}$ (for the pivot rows $i$ with $j_i < l$ ) are the coefficients expressing column $l$ of the original matrix as a combination of its pivot columns: $\mathbf{a}_l = \sum_{j_i < l} r_{il}\, \mathbf{a}_{j_i}$ .

B. Practice

Exercise (B1: Column relations)

Let $\mathbf{A} = \begin{pmatrix} 1 & -1 & 0 & 2 & 1 \\ 2 & -2 & 1 & 7 & 0 \\ 1 & -1 & 1 & 5 & 1 \end{pmatrix}$ over $\mathbb{R}$ . Find the RREF of $\mathbf{A}$ , naming each operation. Hence find the pivot columns of $\mathbf{A}$ , and express each non-pivot column of $\mathbf{A}$ as a linear combination of the pivot columns before it. Check your answer on the columns of $\mathbf{A}$ .

Solution. $\begin{aligned} \mathbf{A} \xrightarrow{R_2 \to R_2 - 2R_1} \begin{pmatrix} 1 & -1 & 0 & 2 & 1 \\ 0 & 0 & 1 & 3 & -2 \\ 1 & -1 & 1 & 5 & 1 \end{pmatrix} &\xrightarrow{R_3 \to R_3 - R_1} \begin{pmatrix} 1 & -1 & 0 & 2 & 1 \\ 0 & 0 & 1 & 3 & -2 \\ 0 & 0 & 1 & 3 & 0 \end{pmatrix} \\ &\xrightarrow{R_3 \to R_3 - R_2} \begin{pmatrix} 1 & -1 & 0 & 2 & 1 \\ 0 & 0 & 1 & 3 & -2 \\ 0 & 0 & 0 & 0 & 2 \end{pmatrix} \end{aligned}$ $\begin{aligned} &\xrightarrow{R_3 \to \frac12 R_3} \begin{pmatrix} 1 & -1 & 0 & 2 & 1 \\ 0 & 0 & 1 & 3 & -2 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix} \\ &\xrightarrow{R_1 \to R_1 - R_3} \begin{pmatrix} 1 & -1 & 0 & 2 & 0 \\ 0 & 0 & 1 & 3 & -2 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix} \\ &\xrightarrow{R_2 \to R_2 + 2R_3} \begin{pmatrix} 1 & -1 & 0 & 2 & 0 \\ 0 & 0 & 1 & 3 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}. \end{aligned}$ The pivot columns are 1, 3 and 5. By Lemma 3.3.3 (b), in the RREF column 2 is $-1$ times column 1, and column 4 is $2$ times column 1 plus $3$ times column 3. By Lemma 3.3.2 (b), the columns of $\mathbf{A}$ satisfy $\mathbf{a}_2 = -\mathbf{a}_1, \qquad \mathbf{a}_4 = 2\mathbf{a}_1 + 3\mathbf{a}_3 .$ Check: $-(1, 2, 1) = (-1, -2, -1) = \mathbf{a}_2$ , and $2(1, 2, 1) + 3(0, 1, 1) = (2, 7, 5) = \mathbf{a}_4$ .

Exercise (B2: Row equivalence via the RREF)

Prove that two matrices $\mathbf{A}, \mathbf{B} \in M_{m \times n}(F)$ are row equivalent if and only if they have the same RREF.

Solution. $(\Rightarrow)$ Suppose $\mathbf{A}$ and $\mathbf{B}$ are row equivalent, and let $\mathbf{R}$ be the RREF of $\mathbf{B}$ . Then $\mathbf{A}$ is row equivalent to $\mathbf{B}$ , and $\mathbf{B}$ to $\mathbf{R}$ , so $\mathbf{A}$ is row equivalent to $\mathbf{R}$ by transitivity (Theorem 3.2.2 (b)). By the uniqueness in Theorem 3.3.4, $\mathbf{R}$ is the RREF of $\mathbf{A}$ .

$(\Leftarrow)$ Suppose both have the RREF $\mathbf{R}$ . Then $\mathbf{A}$ is row equivalent to $\mathbf{R}$ , and by symmetry $\mathbf{R}$ is row equivalent to $\mathbf{B}$ (Theorem 3.2.2 (b)). By transitivity $\mathbf{A}$ is row equivalent to $\mathbf{B}$ .

Exercise (B3: Row equivalent or not?)

Determine whether the matrices in each pair are row equivalent over $\mathbb{R}$ . Justify your answer.

(a) $\mathbf{P} = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 5 & 7 \end{pmatrix}$ and $\mathbf{Q} = \begin{pmatrix} 1 & 1 & 2 \\ 3 & 4 & 7 \end{pmatrix}$ .
(b) $\mathbf{P} = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 2 & 3 \\ 0 & 1 & 2 \end{pmatrix}$ and $\mathbf{Q} = \begin{pmatrix} 1 & 0 & -1 \\ 0 & 1 & 2 \\ 1 & 1 & 2 \end{pmatrix}$ .

Solution. By Exercise (B2: Row equivalence via the RREF), two matrices of the same size are row equivalent exactly when their RREFs are equal. So we compute both RREFs.

(a) $\mathbf{P} \xrightarrow{R_2 \to R_2 - 2R_1} \begin{pmatrix} 1 & 2 & 3 \\ 0 & 1 & 1 \end{pmatrix} \xrightarrow{R_1 \to R_1 - 2R_2} \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{pmatrix}$ , and $\mathbf{Q} \xrightarrow{R_2 \to R_2 - 3R_1} \begin{pmatrix} 1 & 1 & 2 \\ 0 & 1 & 1 \end{pmatrix} \xrightarrow{R_1 \to R_1 - R_2} \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{pmatrix}$ . The RREFs are equal, so $\mathbf{P}$ and $\mathbf{Q}$ are row equivalent.
(b) $\mathbf{P} \xrightarrow{R_2 \to R_2 - R_1} \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 2 \\ 0 & 1 & 2 \end{pmatrix} \xrightarrow{R_1 \to R_1 - R_2} \begin{pmatrix} 1 & 0 & -1 \\ 0 & 1 & 2 \\ 0 & 1 & 2 \end{pmatrix} \xrightarrow{R_3 \to R_3 - R_2} \begin{pmatrix} 1 & 0 & -1 \\ 0 & 1 & 2 \\ 0 & 0 & 0 \end{pmatrix}$ .

$\begin{aligned} \mathbf{Q} &\xrightarrow{R_3 \to R_3 - R_1} \begin{pmatrix} 1 & 0 & -1 \\ 0 & 1 & 2 \\ 0 & 1 & 3 \end{pmatrix} \xrightarrow{R_3 \to R_3 - R_2} \begin{pmatrix} 1 & 0 & -1 \\ 0 & 1 & 2 \\ 0 & 0 & 1 \end{pmatrix} \\ &\xrightarrow{R_1 \to R_1 + R_3} \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 2 \\ 0 & 0 & 1 \end{pmatrix} \xrightarrow{R_2 \to R_2 - 2R_3} \mathbf{I}_3 . \end{aligned}$

The RREFs differ (one has a zero row, the other is $\mathbf{I}_3$ ), so $\mathbf{P}$ and $\mathbf{Q}$ are not row equivalent. Consistently with Corollary 3.3.5, $\mathbf{P}$ has pivot columns 1, 2 while $\mathbf{Q}$ has 1, 2, 3.

C. Going deeper

Exercise (C1: Counting reduced forms)

(a) List, by pivot columns, all $2 \times 3$ matrices over $\mathbb{F}_2$ in reduced row echelon form, and show that there are exactly $15$ of them.
(b) Deduce that $M_{2 \times 3}(\mathbb{F}_2)$ , which has $64$ elements, splits into exactly $15$ classes of row equivalent matrices.
(c) Show that over a field with $q$ elements there are exactly $2q^2 + 2q + 3$ such matrices.

Solution. We count over a field $F$ with $q$ elements, sorting by the list of pivot columns. In a matrix in RREF, a pivot column is forced (it is $\mathbf{e}_i$ ), an entry before a leading entry or in a zero row is forced to be $0$ , and every other entry, one lying in a non-pivot column to the right of its row’s pivot, is free.

(a) With $q = 2$ , writing $*$ for a free entry:
- no pivots: $\begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}$ , $1$ matrix;
- pivot column 1 only: $\begin{pmatrix} 1 & * & * \\ 0 & 0 & 0 \end{pmatrix}$ , $4$ matrices;
- pivot column 2 only: $\begin{pmatrix} 0 & 1 & * \\ 0 & 0 & 0 \end{pmatrix}$ , $2$ matrices;
- pivot column 3 only: $\begin{pmatrix} 0 & 0 & 1 \\ 0 & 0 & 0 \end{pmatrix}$ , $1$ matrix;
- pivot columns 1, 2: $\begin{pmatrix} 1 & 0 & * \\ 0 & 1 & * \end{pmatrix}$ , $4$ matrices;
- pivot columns 1, 3: $\begin{pmatrix} 1 & * & 0 \\ 0 & 0 & 1 \end{pmatrix}$ , $2$ matrices;
- pivot columns 2, 3: $\begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}$ , $1$ matrix.
A $2 \times 3$ matrix has at most two pivots, so these are all the cases. The total is $1 + 4 + 2 + 1 + 4 + 2 + 1 = 15$ .
(b) Row equivalence is an equivalence relation (Theorem 3.2.2 (b)), so $M_{2 \times 3}(\mathbb{F}_2)$ is partitioned into equivalence classes (Theorem 0.5.2). By Theorem 3.3.4, each class contains exactly one matrix in RREF: at least one by Theorem 3.2.3, and at most one since two RREF matrices in the same class would be row equivalent, hence equal. So the classes correspond one-to-one to the $15$ matrices of (a).
(c) The same list, with each free entry taking $q$ values, gives $1 + q^2 + q + 1 + q^2 + q + 1 = 2q^2 + 2q + 3$ . For $q = 2$ this is $8 + 4 + 3 = 15$ , as in (a).

Exercise (C2: Deleting a column)

Let $\mathbf{A} \in M_{m \times n}(F)$ with $n \ge 2$ , and let $\mathbf{R}$ be its RREF.

(a) Let $\mathbf{A}'$ and $\mathbf{R}'$ be obtained from $\mathbf{A}$ and $\mathbf{R}$ by deleting the last column. Prove that $\mathbf{R}'$ is the RREF of $\mathbf{A}'$ .
(b) Show by an example that the corresponding statement for deleting the first column is false.

Solution.

(a) Let a sequence of row operations turn $\mathbf{A}$ into $\mathbf{R}$ . By Lemma 3.2.1, the same sequence turns $\mathbf{A}'$ into $\mathbf{R}'$ , so $\mathbf{A}'$ is row equivalent to $\mathbf{R}'$ . By Theorem 3.3.4 it suffices to show that $\mathbf{R}'$ is in RREF. Let $j_1 < \dots < j_r$ be the pivot columns of $\mathbf{R}$ . If $j_r < n$ , then deleting column $n$ does not change any leading entry or any pivot column, and the zero rows of $\mathbf{R}$ stay zero, so (E1)–(E4) still hold. If $j_r = n$ , then row $r$ of $\mathbf{R}$ is zero except for its pivot in column $n$ , so in $\mathbf{R}'$ rows $r, \dots, m$ are zero and rows $1, \dots, r - 1$ keep their leading entries in columns $j_1 < \dots < j_{r-1}$ and their pivot columns. Again (E1)–(E4) hold, with $r - 1$ pivots. Hence $\mathbf{R}'$ is in RREF, and it is the RREF of $\mathbf{A}'$ .
(b) Let $\mathbf{A} = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$ over $\mathbb{R}$ . Then $\mathbf{A} \xrightarrow{R_1 \to R_1 - R_2} \mathbf{I}_2$ , so its RREF is $\mathbf{I}_2$ , and deleting the first column of $\mathbf{I}_2$ gives $\begin{pmatrix} 0 \\ 1 \end{pmatrix}$ . But deleting the first column of $\mathbf{A}$ gives $\begin{pmatrix} 1 \\ 1 \end{pmatrix}$ , whose RREF is $\begin{pmatrix} 1 \\ 0 \end{pmatrix}$ , via $R_2 \to R_2 - R_1$ . These differ. The pivot of a later column depends on the columns before it, so removing an early column can move pivots.