# Rank factorization

In mathematics, given a field $\mathbb {F}$, non-negative integers $m,n$, and a matrix $A\in \mathbb {F} ^{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 {F} ^{m\times r}$ and $F\in \mathbb {F} ^{r\times n}$, where $r=\operatorname {rank} A$ is the rank of $A$.

## Existence

Every finite-dimensional matrix has a rank decomposition: Let A{\textstyle A} be an m×n{\textstyle m\times n} matrix whose column rank is r{\textstyle r}. Therefore, there are r{\textstyle r} linearly independent columns in A{\textstyle A}; equivalently, the dimension of the column space of A{\textstyle A} is r{\textstyle r}. Let c$_1$, c$_2$, …, c$_r${\textstyle \mathbf {c} _{1}, \mathbf {c} _{2}, \ldots , \mathbf {c} _{r}} be any basis for the column space of A{\textstyle A} and place them as column vectors to form the m×r{\textstyle m\times r} matrix C=[c$_1$c$_2$⋯c$_r$]{\textstyle C={\begin{bmatrix}\mathbf {c} _{1}&\mathbf {c} _{2}&\cdots &\mathbf {c} _{r}\end{bmatrix}}}. Therefore, every column vector of A{\textstyle A} is a linear combination of the columns of C{\textstyle C}. To be precise, if A=[a$_1$a$_2$⋯a$_n$]{\textstyle A={\begin{bmatrix}\mathbf {a} _{1}&\mathbf {a} _{2}&\cdots &\mathbf {a} _{n}\end{bmatrix}}} is an m×n{\textstyle m\times n} matrix with a$_j${\textstyle \mathbf {a} _{j}} as the j{\textstyle j}-th column, then
    $\mathbf {a} _{j}=f_{1j}\mathbf {c} _{1}+f_{2j}\mathbf {c} _{2}+\cdots +f_{rj}\mathbf {c} _{r},$
where f$_{ij}${\textstyle f_{ij}}'s are the scalar coefficients of a$_j${\textstyle \mathbf {a} _{j}} in terms of the basis c$_1$, c$_2$, …, c$_r${\textstyle \mathbf {c} _{1}, \mathbf {c} _{2}, \ldots , \mathbf {c} _{r}}. This implies that A=CF{\textstyle A=CF}, where f$_{ij}${\textstyle f_{ij}} is the (i, j){\textstyle (i, j)}-th element of F{\textstyle F}.

## Non-uniqueness

If A=C$_1$F$_1${\textstyle A=C_{1}F_{1}} is a rank factorization, taking C$_2$=C$_1$R{\textstyle C_{2}=C_{1}R} and F$_2$=R$^{−1}$F$_1${\textstyle F_{2}=R^{-1}F_{1}} gives another rank factorization for any invertible matrix R{\textstyle R} of compatible dimensions.
Conversely, if A=F$_1$G$_1$=F$_2$G$_2${\textstyle A=F_{1}G_{1}=F_{2}G_{2}} are two rank factorizations of A{\textstyle A}, then there exists an invertible matrix R{\textstyle R} such that F$_1$=F$_2$R{\textstyle F_{1}=F_{2}R} and G$_1$=R$^{−1}$G$_2${\textstyle 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{\textstyle B}, the reduced row echelon form of A{\textstyle A}. Then C{\textstyle C} is obtained by removing from A{\textstyle A} all non-pivot columns (which can be determined by looking for columns in B{\textstyle B} which do not contain a pivot), and F{\textstyle F} is obtained by eliminating any all-zero rows of B{\textstyle B}.
Note: For a full-rank square matrix (i.e. when n=m=r{\textstyle n=m=r}), this procedure will yield the trivial result C=A{\textstyle C=A} and F=B=I$_n${\textstyle F=B=I_{n}} (the n×n{\textstyle n\times n} identity matrix).

#### 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{\textstyle B} is in reduced echelon form.
Then C{\textstyle C} is obtained by removing the third column of A{\textstyle A}, the only one which is not a pivot column, and F{\textstyle F} by getting rid of the last row of zeroes from B{\textstyle B}, 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{\textstyle P} be an n×n{\textstyle n\times n} permutation matrix such that AP=(C, D){\textstyle AP=(C, D)} in block partitioned form, where the columns of C{\textstyle C} are the r{\textstyle r} pivot columns of A{\textstyle A}. Every column of D{\textstyle D} is a linear combination of the columns of C{\textstyle C}, so there is a matrix G{\textstyle G} such that D=CG{\textstyle D=CG}, where the columns of G{\textstyle G} contain the coefficients of each of those linear combinations. So AP=(C, CG)=C(I$_r$, G){\textstyle AP=(C, CG)=C(I_{r}, G)}, I$_r${\textstyle I_{r}} being the r×r{\textstyle r\times r} identity matrix. We will show now that (I$_r$, G)=FP{\textstyle (I_{r}, G)=FP}.
Transforming A{\textstyle A} into its reduced row echelon form B{\textstyle B} amounts to left-multiplying by a matrix E{\textstyle E} which is a product of elementary matrices, so EAP=BP=EC(I$_r$, G){\textstyle EAP=BP=EC(I_{r}, G)}, where EC=(I$_r$0){\textstyle EC={\begin{pmatrix}I_{r}\\0\end{pmatrix}}}. We then can write BP=(I$_r$G00){\textstyle BP={\begin{pmatrix}I_{r}&G\\0&0\end{pmatrix}}}, which allows us to identify (I$_r$, G)=FP{\textstyle (I_{r}, G)=FP}, i.e. the nonzero r{\textstyle r} rows of the reduced echelon form, with the same permutation on the columns as we did for A{\textstyle A}. We thus have AP=CFP{\textstyle AP=CFP}, and since P{\textstyle P} is invertible this implies A=CF{\textstyle A=CF}, and the proof is complete.

### Singular value decomposition

If $\mathbb {F} \in \{\mathbb {R} ,\mathbb {C} \},$ then one can also construct a full-rank factorization of A{\textstyle A} via a singular value decomposition
    $A=U\Sigma V^{*}={\begin{bmatrix}U_{1}&U_{2}\end{bmatrix}}{\begin{bmatrix}\Sigma _{r}&0\\0&0\end{bmatrix}}{\begin{bmatrix}V_{1}^{*}\\V_{2}^{*}\end{bmatrix}}=U_{1}\left(\Sigma _{r}V_{1}^{*}\right).$
Since U$_1${\textstyle U_{1}} is a full-column-rank matrix and Σ$_r$V$_1$$^∗${\textstyle \Sigma _{r}V_{1}^{*}} is a full-row-rank matrix, we can take C=U$_1${\textstyle C=U_{1}} and F=Σ$_r$V$_1$$^∗${\textstyle F=\Sigma _{r}V_{1}^{*}}.

## Consequences
### rank(A) = rank(A$^T$)

An immediate consequence of rank factorization is that the rank of A{\textstyle A} is equal to the rank of its transpose A$^T${\textstyle A^{\textsf {T}}}. Since the columns of A{\textstyle A} are the rows of A$^T${\textstyle A^{\textsf {T}}}, the column rank of A{\textstyle A} equals its row rank.
Proof: To see why this is true, let us first define rank to mean column rank. Since A=CF{\textstyle A=CF}, it follows that A$^T$=F$^T$C$^T${\textstyle A^{\textsf {T}}=F^{\textsf {T}}C^{\textsf {T}}}. From the definition of matrix multiplication, this means that each column of A$^T${\textstyle A^{\textsf {T}}} is a linear combination of the columns of F$^T${\textstyle F^{\textsf {T}}}. Therefore, the column space of A$^T${\textstyle A^{\textsf {T}}} is contained within the column space of F$^T${\textstyle F^{\textsf {T}}} and, hence, rank⁡(A$^T$)≤rank⁡(F$^T$){\textstyle \operatorname {rank} \left(A^{\textsf {T}}\right)\leq \operatorname {rank} \left(F^{\textsf {T}}\right)}.
Now, F$^T${\textstyle F^{\textsf {T}}} is n×r{\textstyle n\times r}, so there are r{\textstyle r} columns in F$^T${\textstyle F^{\textsf {T}}} and, hence, rank⁡(A$^T$)≤r=rank⁡(A){\textstyle \operatorname {rank} \left(A^{\textsf {T}}\right)\leq r=\operatorname {rank} \left(A\right)}. This proves that rank⁡(A$^T$)≤rank⁡(A){\textstyle \operatorname {rank} \left(A^{\textsf {T}}\right)\leq \operatorname {rank} \left(A\right)}.
Now apply the result to A$^T${\textstyle A^{\textsf {T}}} to obtain the reverse inequality: since (A$^T$)$^T$=A{\textstyle \left(A^{\textsf {T}}\right)^{\textsf {T}}=A}, we can write rank⁡(A)=rank⁡((A$^T$)$^T$)≤rank⁡(A$^T$){\textstyle \operatorname {rank} \left(A\right)=\operatorname {rank} \left(\left(A^{\textsf {T}}\right)^{\textsf {T}}\right)\leq \operatorname {rank} \left(A^{\textsf {T}}\right)}. This proves rank⁡(A)≤rank⁡(A$^T$){\textstyle \operatorname {rank} \left(A\right)\leq \operatorname {rank} \left(A^{\textsf {T}}\right)}.
We have, therefore, proved rank⁡(A$^T$)≤rank⁡(A){\textstyle \operatorname {rank} \left(A^{\textsf {T}}\right)\leq \operatorname {rank} \left(A\right)} and rank⁡(A)≤rank⁡(A$^T$){\textstyle \operatorname {rank} \left(A\right)\leq \operatorname {rank} \left(A^{\textsf {T}}\right)}, so rank⁡(A)=rank⁡(A$^T$){\textstyle \operatorname {rank} \left(A\right)=\operatorname {rank} \left(A^{\textsf {T}}\right)}.