The Structure Behind a Rank Factorization
A matrix of rank \(r\) has only \(r\) independent columns, even if it has many more than \(r\) columns. This means that every column can be expressed using a selected collection of \(r\) independent columns. A rank factorization records both pieces of information: the selected columns themselves, and the coefficients that express all the other columns in terms of them.
Throughout, matrices and vectors have real entries. Let \(\mathbf{A}\in\mathbb{R}^{m\times n}\), and write its columns as \(\mathbf{a}_1,\dots,\mathbf{a}_n\). The rank of \(\mathbf{A}\) is the number of pivot columns in its reduced row echelon form (RREF); equivalently, it is the dimension of its column space. Row reduction preserves linear relations among columns when the same row operations are applied to every column. The key construction will use the pivot columns of \(\mathbf{A}\), not the pivot columns of its RREF.
Constructing the Factors
Suppose the RREF of \(\mathbf{A}\) has \(r>0\) pivots in columns \(j_1,\dots,j_r\), listed in increasing order. Let \(\mathbf{U}=\operatorname{rref}(\mathbf{A})\). In a pivot column \(j_k\), the pivot is in row \(k\), and that entire column of \(\mathbf{U}\) is the standard basis vector \(\mathbf{e}_k\). Every row below the \(r\) pivot rows is zero. Therefore, if column \(j\) of \(\mathbf{U}\) has entries \(u_{1j},\dots,u_{rj}\) in its first \(r\) rows, then \(\mathbf{u}_j=\sum_{k=1}^r u_{kj}\mathbf{e}_k\).
Row reduction takes \(\mathbf{A}\) to \(\mathbf{U}\) by a sequence of elementary row operations. Each such operation is multiplication on the left by an invertible matrix, so together they give an invertible matrix \(\mathbf{E}\) with \(\mathbf{U}=\mathbf{E}\mathbf{A}\). In particular, \(\mathbf{u}_j=\mathbf{E}\mathbf{a}_j\), and \(\mathbf{u}_{j_k}=\mathbf{E}\mathbf{a}_{j_k}=\mathbf{e}_k\). The RREF column equation thus says that \(\mathbf{E}\mathbf{a}_j=\sum_{k=1}^r u_{kj}\mathbf{E}\mathbf{a}_{j_k}\). Since \(\mathbf{E}\) is invertible, applying \(\mathbf{E}^{-1}\) gives the same relation among the original columns.
Proof. Write \(\mathbf{C}=\begin{bmatrix}\mathbf{a}_{j_1}&\cdots&\mathbf{a}_{j_r}\end{bmatrix}\), and let \(\mathbf{R}\) consist of the first \(r\) rows of \(\mathbf{U}\). For each column index \(j\), its first \(r\) RREF entries are \(u_{1j},\dots,u_{rj}\). The argument above gives \(\mathbf{a}_j=\sum_{k=1}^r u_{kj}\mathbf{a}_{j_k}\). The \(j\)th column of \(\mathbf{C}\mathbf{R}\) is precisely that sum, so it equals \(\mathbf{a}_j\). This holds for every \(j\), proving \(\mathbf{A}=\mathbf{C}\mathbf{R}\).
To prove the columns of \(\mathbf{C}\) are independent, suppose \(\sum_{k=1}^r c_k\mathbf{a}_{j_k}=\mathbf{0}\). Apply \(\mathbf{E}\) to both sides. Since \(\mathbf{E}\mathbf{a}_{j_k}=\mathbf{e}_k\), this gives \(\sum_{k=1}^r c_k\mathbf{e}_k=\mathbf{0}\), which forces every \(c_k=0\). To prove the rows of \(\mathbf{R}\) are independent, suppose a linear combination of its rows with coefficients \(d_1,\dots,d_r\) is the zero row. In column \(j_k\), the entries of \(\mathbf{R}\) are those of \(\mathbf{U}\), and column \(j_k\) is \(\mathbf{e}_k\). The selected column therefore gives \(d_k=0\). This holds for each \(k\), so all the row-combination coefficients are zero. \(\square\)
If \(r=0\), the RREF has no pivots and is the zero matrix, so \(\mathbf{A}\) is the zero matrix as well: the row operations are invertible and hence \(\mathbf{U}=\mathbf{0}\) implies \(\mathbf{A}=\mathbf{0}\). The empty-factor convention in the definition then gives the factorization. Thus the construction also covers rank zero.
Reading the Coefficients Correctly
The coefficient matrix \(\mathbf{R}\) is obtained by taking the first \(r\) rows of the RREF. Consequently, the first \(r\) entries in each column of the RREF give the coefficients for expressing the corresponding original column in terms of the selected original pivot columns. The pivot columns of the RREF themselves are \(\mathbf{e}_1,\dots,\mathbf{e}_r\); they show which positions are pivots, but they are not the selected original columns and do not supply the coefficients for every column.
Worked Example: A Rank-Two Factorization
Construct a rank factorization of \(\mathbf{A}=\begin{bmatrix}1&0&2&-1\\0&1&1&3\\1&1&3&2\end{bmatrix}\).
Subtract row 1 from row 3, then subtract row 2 from row 3. The resulting matrix is already in RREF:
The pivot columns are 1 and 2. Thus \(\mathbf{C}\) consists of columns 1 and 2 of the original matrix, while \(\mathbf{R}\) consists of the first two rows of its RREF:
For instance, the third column of the RREF begins with \((2,1)^\top\), so the third original column is \(2\mathbf{a}_1+\mathbf{a}_2\). The fourth column begins with \((-1,3)^\top\), so the fourth original column is \(-\mathbf{a}_1+3\mathbf{a}_2\). Multiplication verifies every column at once:
The columns of \(\mathbf{C}\) are independent: if \(c_1\mathbf{a}_1+c_2\mathbf{a}_2=\mathbf{0}\), the first coordinate gives \(c_1=0\) and the second gives \(c_2=0\). The rows of \(\mathbf{R}\) are independent because columns 1 and 2 of \(\mathbf{R}\) form the \(2\times2\) identity matrix: a zero combination of the rows must have both coefficients zero.
Worked Example: Pivot Columns That Do Not Start at Column 1
Construct a rank factorization of \(\mathbf{A}=\begin{bmatrix}0&1&0&2\\0&0&1&1\\0&1&1&3\end{bmatrix}\).
Subtract row 1 from row 3, then subtract row 2 from row 3. The pivot columns are 2 and 3; column 1 is zero and is not a pivot column.
Take the original columns 2 and 3 for \(\mathbf{C}\), and take the first two rows of the RREF for \(\mathbf{R}\):
Column 1 of \(\mathbf{R}\) says that the original first column is zero. Its second and third columns select the corresponding columns of \(\mathbf{C}\), and its fourth column says \(\mathbf{a}_4=2\mathbf{a}_2+\mathbf{a}_3\). Direct multiplication checks the entire factorization:
The factors have the required independence. The two columns of \(\mathbf{C}\) are independent, since their first and second coordinates are the two coefficients in any zero combination. In \(\mathbf{R}\), columns 2 and 3 form the \(2\times2\) identity matrix, so a zero combination of its rows has both coefficients zero.
Why the Construction Works and What It Does Not Say
The construction separates the roles of the factors. The columns of \(\mathbf{C}\) are actual columns of \(\mathbf{A}\), chosen to be independent. They provide the vectors from which every column of \(\mathbf{A}\) is built. The columns of \(\mathbf{R}\) store the corresponding coefficients. In particular, for each \(j\), \(\mathbf{a}_j=\sum_{k=1}^r R_{kj}\mathbf{a}_{j_k}\). The pivot columns of \(\mathbf{R}\) are the standard basis vectors, because the selected pivot columns of the RREF are \(\mathbf{e}_1,\dots,\mathbf{e}_r\). This is also why the rows of \(\mathbf{R}\) are independent.
The factors need not be unique if one only asks for a product of two matrices with matching dimensions. The construction gives a specific useful choice: \(\mathbf{C}\) uses original pivot columns, and \(\mathbf{R}\) records their coefficients as read from the RREF. Do not replace \(\mathbf{C}\) with the pivot columns of the RREF; row operations change the columns themselves, even though they preserve their linear relations.
Common mistake: using the RREF as the factor \(\mathbf{C}\). In the first worked example, the pivot columns of the RREF are \((1,0,0)^\top\) and \((0,1,0)^\top\). A tempting but incorrect choice is to use those columns as \(\mathbf{C}\) and keep \(\mathbf{R}\) as the first two RREF rows. That product has third row \((0,0,0,0)\), so it cannot equal the original matrix, whose third row is \((1,1,3,2)\). The correction is to take the pivot columns from the original \(\mathbf{A}\), giving \(\mathbf{C}=\begin{bmatrix}1&0\\0&1\\1&1\end{bmatrix}\). The coefficient entries still come from the first two rows of the RREF. Together, those choices reproduce the original matrix.
A second way to check the construction is to inspect the columns one at a time: the \(j\)th column of \(\mathbf{C}\mathbf{R}\) must equal the original \(\mathbf{a}_j\). If a proposed factorization gives the right pivot columns but not the other columns, its coefficient matrix has not recorded the correct relations. Conversely, matching every column verifies the product, while the pivot structure supplies the independence conditions.
Check Your Understanding
For each question, distinguish the original pivot columns from the columns of the RREF and verify any proposed product by multiplication.
- For \(\mathbf{A}=\begin{bmatrix}1&2&3\\0&1&1\\1&3&4\end{bmatrix}\), find its pivot columns and construct \(\mathbf{C}\) and \(\mathbf{R}\).
- In a rank-three factorization, which entries of the RREF give the coefficients expressing column \(j\) of the original matrix using the selected pivot columns?
- Explain why the pivot columns of the RREF are not generally the columns to use for \(\mathbf{C}\).
- Show that if the pivot-column indices are \(j_1,\dots,j_r\), then columns \(j_1,\dots,j_r\) of the coefficient matrix \(\mathbf{R}\) form \(\mathbf{I}_r\).
- What factorization convention applies when \(\mathbf{A}\) is the zero matrix and has rank zero?
