Rank factorization

Short description: Concept in linear algebra

In mathematics, given a field $\mathbb{𝔽}$, non-negative integers $m,n$, and a matrix $A\in {\mathbb{𝔽}}^{m\times n}$, a rank decomposition or rank factorization of A is a factorization of A of the form A = CF, where $C\in {\mathbb{𝔽}}^{m\times r}$ and $F\in {\mathbb{𝔽}}^{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 ${\mathbf{𝐜}}_1,{\mathbf{𝐜}}_2,\dots ,{\mathbf{𝐜}}_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}{\mathbf{𝐜}}_1& {\mathbf{𝐜}}_2& \cdots & {\mathbf{𝐜}}_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}{\mathbf{𝐚}}_1& {\mathbf{𝐚}}_2& \cdots & {\mathbf{𝐚}}_n\end{array}\right]$ is an $m\times n$ matrix with ${\mathbf{𝐚}}_j$ as the $j$-th column, then

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

where $f_{ij}$'s are the scalar coefficients of ${\mathbf{𝐚}}_j$ in terms of the basis ${\mathbf{𝐜}}_1,{\mathbf{𝐜}}_2,\dots ,{\mathbf{𝐜}}_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 $\mathbb{𝔽}\in \{\mathbb{ℝ},\mathbb{ℂ}\},$ then one can also construct a full-rank factorization of $A$ via a singular value decomposition

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

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

Consequences

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, $\mathrm{rank}\left(A^{\text{T}}\right)\le \mathrm{rank}\left(F^{\text{T}}\right)$.

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

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

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

References

• Banerjee, Sudipto; Roy, Anindya (2014), Linear Algebra and Matrix Analysis for Statistics, Texts in Statistical Science (1st ed.), Chapman and Hall/CRC, ISBN 978-1420095388 
• Lay, David C. (2005), Linear Algebra and its Applications (3rd ed.), Addison Wesley, ISBN 978-0-201-70970-4 
• Golub, Gene H.; Van Loan, Charles F. (1996), Matrix Computations, Johns Hopkins Studies in Mathematical Sciences (3rd ed.), The Johns Hopkins University Press, ISBN 978-0-8018-5414-9 
• Stewart, Gilbert W. (1998), Matrix Algorithms. I. Basic Decompositions, SIAM, ISBN 978-0-89871-414-2 
• Piziak, R.; Odell, P. L. (1 June 1999). "Full Rank Factorization of Matrices". Mathematics Magazine 72 (3): 193. doi:10.2307/2690882.