Rank factorization

In mathematics, given a field $𝔽$, non-negative integers $m,n$, and a matrix $A\in {𝔽}^{m\times n}$, a rank decomposition or rank factorization of A is a factorization of A of the form A = CF, where $C\in {𝔽}^{m\times r}$ and $F\in {𝔽}^{r\times n}$, where $r=\mathrm{rank}A$ is the rank of $A$.

Existence

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 ${𝐜}_1,{𝐜}_2,\dots ,{𝐜}_r$ be any basis for the column space of $A$ and place them as column vectors to form the $m\times r$ matrix $C=\left[\begin{array}{cccc}{𝐜}_1& {𝐜}_2& \cdots & {𝐜}_r\end{array}\right]$. Therefore, every column vector of $A$ is a linear combination of the columns of $C$. To be precise, if $A=\left[\begin{array}{cccc}{𝐚}_1& {𝐚}_2& \cdots & {𝐚}_n\end{array}\right]$ is an $m\times n$ matrix with ${𝐚}_j$ as the $j$-th column, then

${𝐚}_j=f_{1j}{𝐜}_1+f_{2j}{𝐜}_2+\cdots +f_{rj}{𝐜}_r,$

where $f_{ij}$'s are the scalar coefficients of ${𝐚}_j$ in terms of the basis ${𝐜}_1,{𝐜}_2,\dots ,{𝐜}_r$. This implies that $A=CF$, where $f_{ij}$ is the $(i,j)$-th element of $F$.

Non-uniqueness

If $A=C_1{F}_1$ is a rank factorization, taking $C_2=C_{1}R$ and $F_2=R^{-1}{F}_1$ gives another rank factorization for any invertible matrix $R$ of compatible dimensions.

Conversely, if $A=F_1{G}_1=F_2{G}_2$ are two rank factorizations of $A$, then there exists an invertible matrix $R$ such that $F_1=F_{2}R$ and $G_1=R^{-1}{G}_2$.

Construction

Rank factorization from reduced 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 (which can be determined by looking for columns in $B$ which do not contain a pivot), and $F$ is obtained by eliminating any all-zero rows of $B$.

Note: For a full-rank square matrix (i.e. when $n=m=r$), this procedure will yield the trivial result $C=A$ and $F=B=I_n$ (the $n\times n$ identity matrix).

Example

Consider the matrix

$A=\left[\begin{array}{cccc}1& 3& 1& 4\\ 2& 7& 3& 9\\ 1& 5& 3& 1\\ 1& 2& 0& 8\end{array}\right]\sim \left[\begin{array}{cccc}1& 0& -2& 0\\ 0& 1& 1& 0\\ 0& 0& 0& 1\\ 0& 0& 0& 0\end{array}\right]=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 from $B$, so

$C=\left[\begin{array}{ccc}1& 3& 4\\ 2& 7& 9\\ 1& 5& 1\\ 1& 2& 8\end{array}\right]\text{,}F=\left[\begin{array}{cccc}1& 0& -2& 0\\ 0& 1& 1& 0\\ 0& 0& 0& 1\end{array}\right]\text{.}$

It is straightforward to check that

$A=\left[\begin{array}{cccc}1& 3& 1& 4\\ 2& 7& 3& 9\\ 1& 5& 3& 1\\ 1& 2& 0& 8\end{array}\right]=\left[\begin{array}{ccc}1& 3& 4\\ 2& 7& 9\\ 1& 5& 1\\ 1& 2& 8\end{array}\right]\left[\begin{array}{cccc}1& 0& -2& 0\\ 0& 1& 1& 0\\ 0& 0& 0& 1\end{array}\right]=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 $A$ into its reduced row echelon form $B$ amounts to left-multiplying by a matrix $E$ which is a product of elementary matrices, so $EAP=BP=EC(I_r,G)$, where $EC=\left(\begin{array}{c}{I}_r\\ 0\end{array}\right)$. We then can write $BP=\left(\begin{array}{cc}{I}_r& G\\ 0& 0\end{array}\right)$, 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.

Singular value decomposition

If $𝔽\in \{ℝ,ℂ\},$ then one can also construct a full-rank factorization of $A$ via a singular value decomposition

$A=U\Sigma V^{*}=\left[\begin{array}{cc}{U}_1& U_2\end{array}\right]\left[\begin{array}{cc}{\Sigma }_r& 0\\ 0& 0\end{array}\right]\left[\begin{array}{c}{V}_1^{*}\\ V_2^{*}\end{array}\right]=U_1\left({\Sigma }_r{V}_1^{*}\right).$

Since $U_1$ is a full-column-rank matrix and ${\Sigma }_r{V}_1^{*}$ is a full-row-rank matrix, we can take $C=U_1$ and $F={\Sigma }_r{V}_1^{*}$.

Consequences

rank(A) = rank(A^T)

See also: Proofs that column rank = row rank

An immediate consequence of rank factorization is that the rank of $A$ is equal to the rank of its transpose $A^{\mathsf{\text{𝖳}}}$. Since the columns of $A$ are the rows of $A^{\mathsf{\text{𝖳}}}$, 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^{\mathsf{\text{𝖳}}}=F^{\mathsf{\text{𝖳}}}{C}^{\mathsf{\text{𝖳}}}$. From the definition of matrix multiplication, this means that each column of $A^{\mathsf{\text{𝖳}}}$ is a linear combination of the columns of $F^{\mathsf{\text{𝖳}}}$. Therefore, the column space of $A^{\mathsf{\text{𝖳}}}$ is contained within the column space of $F^{\mathsf{\text{𝖳}}}$ and, hence, $\mathrm{rank}\left(A^{\mathsf{\text{𝖳}}}\right)\le \mathrm{rank}\left(F^{\mathsf{\text{𝖳}}}\right)$.

Now, $F^{\mathsf{\text{𝖳}}}$ is $n\times r$, so there are $r$ columns in $F^{\mathsf{\text{𝖳}}}$ and, hence, $\mathrm{rank}\left(A^{\mathsf{\text{𝖳}}}\right)\le r=\mathrm{rank}\left(A\right)$. This proves that $\mathrm{rank}\left(A^{\mathsf{\text{𝖳}}}\right)\le \mathrm{rank}\left(A\right)$.

Now apply the result to $A^{\mathsf{\text{𝖳}}}$ to obtain the reverse inequality: since ${\left(A^{\mathsf{\text{𝖳}}}\right)}^{\mathsf{\text{𝖳}}}=A$, we can write $\mathrm{rank}\left(A\right)=\mathrm{rank}\left({\left(A^{\mathsf{\text{𝖳}}}\right)}^{\mathsf{\text{𝖳}}}\right)\le \mathrm{rank}\left(A^{\mathsf{\text{𝖳}}}\right)$. This proves $\mathrm{rank}\left(A\right)\le \mathrm{rank}\left(A^{\mathsf{\text{𝖳}}}\right)$.

We have, therefore, proved $\mathrm{rank}\left(A^{\mathsf{\text{𝖳}}}\right)\le \mathrm{rank}\left(A\right)$ and $\mathrm{rank}\left(A\right)\le \mathrm{rank}\left(A^{\mathsf{\text{𝖳}}}\right)$, so $\mathrm{rank}\left(A\right)=\mathrm{rank}\left(A^{\mathsf{\text{𝖳}}}\right)$.