From Row Reduction to a Rank Factorization
A rank factorization expresses a matrix as the product of two smaller matrices, with the number of columns in the first factor equal to the rank of the original matrix. For a rectangular matrix, this can expose how its columns are built from a smaller collection of independent columns. The construction depends on a careful distinction: row reduction identifies which column positions are pivots, but the first factor uses the corresponding columns of the original matrix—not the columns of its reduced form.
Throughout, matrices and vectors have real entries. The rank of a matrix is the dimension of its column space, equivalently the number of pivot columns in its reduced row echelon form (RREF). If \(\mathbf{A}\in\mathbb{R}^{m\times n}\) has rank \(r\), a rank factorization has the form \(\mathbf{A}=\mathbf{C}\mathbf{R}\), where \(\mathbf{C}\) has size \(m\times r\), \(\mathbf{R}\) has size \(r\times n\), and both factors have rank \(r\).
To construct the factors, reduce \(\mathbf{A}\) to RREF. Suppose its pivot columns have indices \(j_1,\dots,j_r\), and its pivot positions are in rows \(1,\dots,r\). Form \(\mathbf{C}\) by taking columns \(j_1,\dots,j_r\) from the original matrix. Form \(\mathbf{R}\) from the first \(r\) rows of \(\operatorname{rref}(\mathbf{A})\). In the reduced matrix, the pivot columns are the first \(r\) standard coordinate columns, which is why these rows give the coefficients needed to rebuild every column.
Proof. Row reduction is a sequence of elementary row operations, each represented by multiplication on the left by an invertible elementary matrix. Consequently, there is an invertible matrix \(\mathbf{E}\) such that \(\mathbf{B}=\mathbf{E}\mathbf{A}\). In RREF, pivot columns \(j_1,\dots,j_r\) are the standard coordinate columns \(\mathbf{e}_1,\dots,\mathbf{e}_r\) in \(\mathbb{R}^m\). For any column index \(j\), let \(b_{ij}\) be the entry of \(\mathbf{B}\) in row \(i\), column \(j\). Then \(\mathbf{B}\)'s column \(j\) is \(\sum_{i=1}^{r} b_{ij}\mathbf{e}_i\). Substituting \(\mathbf{B}=\mathbf{E}\mathbf{A}\) gives \(\mathbf{E}\mathbf{a}_j=\sum_{i=1}^{r}b_{ij}\mathbf{E}\mathbf{a}_{j_i}\). Since \(\mathbf{E}\) is invertible, \(\mathbf{a}_j=\sum_{i=1}^{r}b_{ij}\mathbf{a}_{j_i}\). These coefficients are exactly column \(j\) of \(\mathbf{R}\), so this equality for every column proves \(\mathbf{A}=\mathbf{C}\mathbf{R}\). To check the ranks, if a linear combination of the columns of \(\mathbf{C}\) is zero, applying \(\mathbf{E}\) makes it the same combination of \(\mathbf{e}_1,\dots,\mathbf{e}_r\), so all coefficients must be zero; hence \(\mathbf{C}\) has rank \(r\). The columns of \(\mathbf{R}\) in positions \(j_1,\dots,j_r\) form \(\mathbf{I}_r\), so its \(r\) rows are independent and its rank is \(r\). \(\square\)
Worked Problems
Worked Example: A Matrix of Rank Two
Find a rank factorization of
Subtract row 1 from row 3, then subtract row 2 from the new row 3. Finally, subtract twice row 2 from row 1:
The pivot columns are 1 and 2, so \(r=2\). Take columns 1 and 2 from the original matrix for \(\mathbf{C}\), and take the first two rows of the RREF for \(\mathbf{R}\):
The dimensions are \(3\times2\) and \(2\times4\), so \(\mathbf{C}\mathbf{R}\) has the required \(3\times4\) size. The two columns of \(\mathbf{C}\) are independent: if \(a(1,0,1)^{\top}+b(2,1,3)^{\top}=\mathbf{0}\), the second coordinate gives \(b=0\), and the first then gives \(a=0\). The first two columns of \(\mathbf{R}\) form \(\mathbf{I}_2\), so \(\mathbf{R}\) has rank 2.
Multiplying row by row gives the check:
For example, the third row of the product is the first row of \(\mathbf{R}\) plus three times its second row, namely \((1,0,1,-1)+3(0,1,1,2)=(1,3,4,5)\). The factors both have rank 2, as required.
Worked Example: A Rank-One Matrix
Factor the matrix
Swap rows 1 and 2, then eliminate the entries below the first pivot:
There is one pivot, in column 1, so take the first column of the original matrix and the one nonzero row of its RREF:
Here \(\mathbf{C}\) is \(3\times1\) and nonzero, so its rank is 1. The \(1\times3\) matrix \(\mathbf{R}\) is nonzero, so its rank is also 1. Their product is
In particular, the second row is \(1(1,-2,3)=(1,-2,3)\), and the third is \(3(1,-2,3)=(3,-6,9)\). The multiplication verifies every entry of the original matrix.
Worked Example: Pivot Columns That Are Not Consecutive
Find a rank factorization of
First eliminate below the pivot in column 1, then use the pivot in column 3:
The pivots are in columns 1 and 3, not columns 1 and 2. Therefore \(\mathbf{C}\) must use columns 1 and 3 of the original matrix; \(\mathbf{R}\) consists of the first two rows of the displayed RREF:
The dimensions are \(4\times2\) and \(2\times4\). The columns of \(\mathbf{C}\) are independent because the first coordinate of a zero combination forces the coefficient of column 1 to be zero, and the second coordinate then forces the coefficient of column 3 to be zero. Columns 1 and 3 of \(\mathbf{R}\) form \(\mathbf{I}_2\), so \(\mathbf{R}\) has rank 2.
To verify the product, the first row is row 1 of \(\mathbf{R}\); the second is row 2; the third is their sum; and the fourth is twice row 1 minus row 2. Hence
This example emphasizes why the pivot indices must be read from the reduced matrix and then used to select columns from the original matrix.
Why the Inner Dimension Is the Rank
The construction above gives factors whose shared dimension equals the rank. This is not an arbitrary choice of size: no factorization through a smaller intermediate dimension can represent the same matrix.
Proof. Write the columns of \(\mathbf{X}\) as \(\mathbf{x}_1,\dots,\mathbf{x}_k\). Each column of \(\mathbf{A}=\mathbf{X}\mathbf{Y}\) is a linear combination of these \(k\) columns, since column \(j\) of \(\mathbf{A}\) is \(\sum_{i=1}^{k}y_{ij}\mathbf{x}_i\). Thus the column space of \(\mathbf{A}\) is contained in \(\operatorname{span}\{\mathbf{x}_1,\dots,\mathbf{x}_k\}\). A space spanned by \(k\) vectors has dimension at most \(k\), so \(\operatorname{rank}\mathbf{A}\le k\). \(\square\)
Applying this proposition to a rank factorization shows why a smaller inner dimension cannot work: the inner dimension must be at least \(\operatorname{rank}\mathbf{A}\), while the construction uses exactly that many columns in \(\mathbf{C}\) and rows in \(\mathbf{R}\). The two factors also have distinct roles. The columns of \(\mathbf{C}\) give independent directions that span the columns of \(\mathbf{A}\), while \(\mathbf{R}\) records the coefficients used to form each original column.
Common Mistake: Using Reduced Columns in the First Factor
A tempting but incorrect approach is to take the pivot columns from the RREF as the first factor. In the last example, doing so would give \(\widetilde{\mathbf{C}}=\begin{bmatrix}1&0\\0&1\\0&0\\0&0\end{bmatrix}\), while the coefficient factor would be \(\mathbf{R}\) as displayed. Their product is
which is not \(\mathbf{A}\): its third and fourth rows are zero, unlike those of the original matrix. Row operations preserve the relationships among columns, but they change the columns themselves. The correction is to use the pivot column indices found in the RREF to select columns from the original matrix. Then the product reconstructs \(\mathbf{A}\), as the verified factorization shows.
Before accepting a proposed rank factorization, check three things: the factor dimensions multiply to the size of \(\mathbf{A}\); both factors have rank equal to the rank of \(\mathbf{A}\); and direct multiplication gives \(\mathbf{A}\). A correct-looking pattern of pivot entries is not a substitute for the final product check.
Check Your Understanding
For each problem, identify the pivot columns and use them to construct and verify a rank factorization.
- Find a rank factorization of \(\begin{bmatrix}1&3&2\\2&6&4\end{bmatrix}\). State the dimensions and ranks of both factors.
- For \(\begin{bmatrix}1&0&2\\0&1&-1\\1&1&1\end{bmatrix}\), determine the rank and construct the factors from its RREF.
- Explain why the coefficient factor in the construction has a pivot-column submatrix equal to an identity matrix.
- A proposed factorization has factors of sizes \(5\times2\) and \(2\times3\). What size must the original matrix have, and what upper bound does the inner dimension give for its rank?
- In constructing a rank factorization, why must the first factor use columns of the original matrix rather than columns of its RREF?
