Rank factorization

Given an $m \times n$ matrix $A$ of rank $r$, a rank decomposition or rank factorization of $A$ is a product $A=CF$, where $C$ is an $m \times r$ matrix and $F$ is an $r \times n$ matrix.

Every finite-dimensional matrix has a rank decomposition: Let $A$ be an $m\times n$ matrix whose column rank is $r$. Therefore, there are $r$ linearly independent columns in $A$; equivalently, the dimension of the column space of $A$ is $r$. Let $c_1,c_2,\ldots,c_r$ be any basis for the column space of $A$ and place them as column vectors to form the $m\times r$ matrix $C = [c_1:c_2:\ldots:c_r]$. Therefore, every column vector of $A$ is a linear combination of the columns of $C$. To be precise, if $A = [a_1:a_2:\ldots:a_n]$ is an $m\times n$ matrix with $a_j$ as the $j$-th column, then

$a_j = f_{1j}c_1 + f_{2j}c_2 + \cdots + f_{rj}c_r,$

where $f_{ij}$'s are the scalar coefficients of $a_j$ in terms of the basis $c_1,c_2,\ldots,c_r$. This implies that $A = CF$, where $f_{ij}$ is the $(i,j)$-th element of $F$.

rank(A) = rank(A^T)

An immediate consequence of rank factorization is that the rank of $A$ is equal to the rank of its transpose $A^\text{T}$. Since the columns of $A$ are the rows of $A^\text{T}$, the column rank of $A$ equals its row rank.

Proof: To see why this is true, let us first define rank to mean column rank. Since $A = CF$, it follows that $A^\text{T} = F^\text{T}C^\text{T}$. From the definition of matrix multiplication, this means that each column of $A^\text{T}$ is a linear combination of the columns of $F^\text{T}$. Therefore, the column space of $A^\text{T}$ is contained within the column space of $F^\text{T}$ and, hence, rank($A^\text{T}$) ≤ rank($F^\text{T}$). Now, $F^\text{T}$ is $n$×$r$, so there are $r$ columns in $F^\text{T}$ and, hence, rank($A^\text{T}$) ≤ $r$ = rank($A$). This proves that rank($A^\text{T})$ ≤ rank($A$). Now apply the result to $A^\text{T}$ to obtain the reverse inequality: since $(A^\text{T})^\text{T}$ = $A$, we can write rank($A$) = rank($(A^\text{T})^\text{T})$ ≤ rank($A^\text{T}$). This proves rank($A)$ ≤ rank($A^\text{T}$). We have, therefore, proved rank($A^\text{T})$ ≤ rank($A$) and rank($A$) ≤ rank($A^\text{T}$), so rank($A$) = rank($A^\text{T}$). (Also see the first proof of column rank = row rank under rank).

Rank factorization from row echelon forms

In practice, we can construct one specific rank factorization as follows: we can compute $B$, the reduced row echelon form of $A$. Then $C$ is obtained by removing from $A$ all non-pivot columns, and $F$ by eliminating all zero rows of $B$.

Example

Consider the matrix

$A = \begin{bmatrix} 1 & 3 & 1 & 4 \\ 2 & 7 & 3 & 9 \\ 1 & 5 & 3 & 1 \\ 1 & 2 & 0 & 8 \end{bmatrix}\sim \begin{bmatrix} 1 & 0 & -2 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix}=B\text{.}$

$B$ is in reduced echelon form. Then $C$ is obtained by removing the third column of $A$, the only one which is not a pivot column, and $F$ by getting rid of the last row of zeroes, so

$C = \begin{bmatrix} 1 & 3 & 4 \\ 2 & 7 & 9 \\ 1 & 5 & 1 \\ 1 & 2 & 8 \end{bmatrix}\text{,}\qquad F = \begin{bmatrix} 1 & 0 & -2 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}\text{.}$

It is straightforward to check that

$A = \begin{bmatrix} 1 & 3 & 1 & 4 \\ 2 & 7 & 3 & 9 \\ 1 & 5 & 3 & 1 \\ 1 & 2 & 0 & 8 \end{bmatrix} = \begin{bmatrix} 1 & 3 & 4 \\ 2 & 7 & 9 \\ 1 & 5 & 1 \\ 1 & 2 & 8 \end{bmatrix}\begin{bmatrix} 1 & 0 & -2 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} = CF\text{.}$

Proof

Let $P$ be an $n\times n$ permutation matrix such that $AP=(C,D)$ in block partitioned form, where the columns of $C$ are the $r$ pivot columns of $A$. Every column of $D$ is a linear combination of the columns of $C$, so there is a matrix $G$ such that $D=CG$, where the columns of $G$ contain the coefficients of each of those linear combinations. So $AP=(C,CG)=C(I_r,G)$, $I_r$ being the $r\times r$ identity matrix. We will show now that $(I_r,G)=FP$.

Transforming $AP$ into its reduced row echelon form amounts to left-multiplying by a matrix $E$ which is a product of elementary matrices, so $EAP=BP=EC(I_r,G)$, where $EC=\begin{pmatrix} I_r \\ 0 \end{pmatrix}$. We then can write $BP=\begin{pmatrix} I_r & G \\ 0 & 0 \end{pmatrix}$, which allows us to identify $(I_r,G)=FP$, i.e. the nonzero $r$ rows of the reduced echelon form, with the same permutation on the columns as we did for $A$. We thus have $AP=CFP$, and since $P$ is invertible this implies $A=CF$, and the proof is complete.