Rank factorization

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

Every finite-dimensional matrix has a rank decomposition: Let ${\textstyle A}${\textstyle A} be an ${\textstyle m\times n}${\textstyle m\times n} matrix whose column rank is ${\textstyle r}${\textstyle r}. Therefore, there are ${\textstyle r}${\textstyle r} linearly independent columns in ${\textstyle A}${\textstyle A}; equivalently, the dimension of the column space of ${\textstyle A}${\textstyle A} is ${\textstyle r}${\textstyle r}. Let ${\textstyle \mathbf {c} _{1},\mathbf {c} _{2},\ldots ,\mathbf {c} _{r}}${\textstyle \mathbf {c} _{1},\mathbf {c} _{2},\ldots ,\mathbf {c} _{r}} be any basis for the column space of ${\textstyle A}${\textstyle A} and place them as column vectors to form the ${\textstyle m\times r}${\textstyle m\times r} matrix ${\textstyle C={\begin{bmatrix}\mathbf {c} _{1}&\mathbf {c} _{2}&\cdots &\mathbf {c} _{r}\end{bmatrix}}}${\textstyle C={\begin{bmatrix}\mathbf {c} _{1}&\mathbf {c} _{2}&\cdots &\mathbf {c} _{r}\end{bmatrix}}}. Therefore, every column vector of ${\textstyle A}${\textstyle A} is a linear combination of the columns of ${\textstyle C}${\textstyle C}. To be precise, if ${\textstyle A={\begin{bmatrix}\mathbf {a} _{1}&\mathbf {a} _{2}&\cdots &\mathbf {a} _{n}\end{bmatrix}}}${\textstyle A={\begin{bmatrix}\mathbf {a} _{1}&\mathbf {a} _{2}&\cdots &\mathbf {a} _{n}\end{bmatrix}}} is an ${\textstyle m\times n}${\textstyle m\times n} matrix with ${\textstyle \mathbf {a} _{j}}${\textstyle \mathbf {a} _{j}} as the ${\textstyle j}${\textstyle j}-th column, then

${\displaystyle \mathbf {a} _{j}=f_{1j}\mathbf {c} _{1}+f_{2j}\mathbf {c} _{2}+\cdots +f_{rj}\mathbf {c} _{r},}${\displaystyle \mathbf {a} _{j}=f_{1j}\mathbf {c} _{1}+f_{2j}\mathbf {c} _{2}+\cdots +f_{rj}\mathbf {c} _{r},}

where ${\textstyle f_{ij}}${\textstyle f_{ij}}'s are the scalar coefficients of ${\textstyle \mathbf {a} _{j}}${\textstyle \mathbf {a} _{j}} in terms of the basis ${\textstyle \mathbf {c} _{1},\mathbf {c} _{2},\ldots ,\mathbf {c} _{r}}${\textstyle \mathbf {c} _{1},\mathbf {c} _{2},\ldots ,\mathbf {c} _{r}}. This implies that ${\textstyle A=CF}${\textstyle A=CF}, where ${\textstyle f_{ij}}${\textstyle f_{ij}} is the ${\textstyle (i,j)}${\textstyle (i,j)}-th element of ${\textstyle F}${\textstyle F}.

If ${\textstyle A=C_{1}F_{1}}${\textstyle A=C_{1}F_{1}} is a rank factorization, taking ${\textstyle C_{2}=C_{1}R}${\textstyle C_{2}=C_{1}R} and ${\textstyle F_{2}=R^{-1}F_{1}}${\textstyle F_{2}=R^{-1}F_{1}} gives another rank factorization for any invertible matrix ${\textstyle R}${\textstyle R} of compatible dimensions.

Conversely, if ${\textstyle A=F_{1}G_{1}=F_{2}G_{2}}${\textstyle A=F_{1}G_{1}=F_{2}G_{2}} are two rank factorizations of ${\textstyle A}${\textstyle A}, then there exists an invertible matrix ${\textstyle R}${\textstyle R} such that ${\textstyle F_{1}=F_{2}R}${\textstyle F_{1}=F_{2}R} and ${\textstyle G_{1}=R^{-1}G_{2}}${\textstyle G_{1}=R^{-1}G_{2}}.^[1]

In practice, we can construct one specific rank factorization as follows: we can compute ${\textstyle B}${\textstyle B}, the reduced row echelon form of ${\textstyle A}${\textstyle A}. Then ${\textstyle C}${\textstyle C} is obtained by removing from ${\textstyle A}${\textstyle A} all non-pivot columns (which can be determined by looking for columns in ${\textstyle B}${\textstyle B} which do not contain a pivot), and ${\textstyle F}${\textstyle F} is obtained by eliminating any all-zero rows of ${\textstyle B}${\textstyle B}.

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

Consider the matrix

${\displaystyle 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{.}}}${\displaystyle 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{.}}}

${\textstyle B}${\textstyle B} is in reduced echelon form.

Then ${\textstyle C}${\textstyle C} is obtained by removing the third column of ${\textstyle A}${\textstyle A}, the only one which is not a pivot column, and ${\textstyle F}${\textstyle F} by getting rid of the last row of zeroes from ${\textstyle B}${\textstyle B}, so

${\displaystyle 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{.}}}${\displaystyle 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

${\displaystyle 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{.}}}${\displaystyle 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{.}}}

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

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

If ${\displaystyle \mathbb {F} \in \{\mathbb {R} ,\mathbb {C} \},}${\displaystyle \mathbb {F} \in \{\mathbb {R} ,\mathbb {C} \},} then one can also construct a full-rank factorization of ${\textstyle A}${\textstyle A} via a singular value decomposition

${\displaystyle 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).}${\displaystyle 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 ${\textstyle U_{1}}${\textstyle U_{1}} is a full-column-rank matrix and ${\textstyle \Sigma _{r}V_{1}^{*}}${\textstyle \Sigma _{r}V_{1}^{*}} is a full-row-rank matrix, we can take ${\textstyle C=U_{1}}${\textstyle C=U_{1}} and ${\textstyle F=\Sigma _{r}V_{1}^{*}}${\textstyle F=\Sigma _{r}V_{1}^{*}}.

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

Proof: To see why this is true, let us first define rank to mean column rank. Since ${\textstyle A=CF}${\textstyle A=CF}, it follows that ${\textstyle A^{\textsf {T}}=F^{\textsf {T}}C^{\textsf {T}}}${\textstyle A^{\textsf {T}}=F^{\textsf {T}}C^{\textsf {T}}}. From the definition of matrix multiplication, this means that each column of ${\textstyle A^{\textsf {T}}}${\textstyle A^{\textsf {T}}} is a linear combination of the columns of ${\textstyle F^{\textsf {T}}}${\textstyle F^{\textsf {T}}}. Therefore, the column space of ${\textstyle A^{\textsf {T}}}${\textstyle A^{\textsf {T}}} is contained within the column space of ${\textstyle F^{\textsf {T}}}${\textstyle F^{\textsf {T}}} and, hence, ${\textstyle \operatorname {rank} \left(A^{\textsf {T}}\right)\leq \operatorname {rank} \left(F^{\textsf {T}}\right)}${\textstyle \operatorname {rank} \left(A^{\textsf {T}}\right)\leq \operatorname {rank} \left(F^{\textsf {T}}\right)}.

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

Now apply the result to ${\textstyle A^{\textsf {T}}}${\textstyle A^{\textsf {T}}} to obtain the reverse inequality: since ${\textstyle \left(A^{\textsf {T}}\right)^{\textsf {T}}=A}${\textstyle \left(A^{\textsf {T}}\right)^{\textsf {T}}=A}, we can write ${\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)}${\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 ${\textstyle \operatorname {rank} \left(A\right)\leq \operatorname {rank} \left(A^{\textsf {T}}\right)}${\textstyle \operatorname {rank} \left(A\right)\leq \operatorname {rank} \left(A^{\textsf {T}}\right)}.

We have, therefore, proved ${\textstyle \operatorname {rank} \left(A^{\textsf {T}}\right)\leq \operatorname {rank} \left(A\right)}${\textstyle \operatorname {rank} \left(A^{\textsf {T}}\right)\leq \operatorname {rank} \left(A\right)} and ${\textstyle \operatorname {rank} \left(A\right)\leq \operatorname {rank} \left(A^{\textsf {T}}\right)}${\textstyle \operatorname {rank} \left(A\right)\leq \operatorname {rank} \left(A^{\textsf {T}}\right)}, so ${\textstyle \operatorname {rank} \left(A\right)=\operatorname {rank} \left(A^{\textsf {T}}\right)}${\textstyle \operatorname {rank} \left(A\right)=\operatorname {rank} \left(A^{\textsf {T}}\right)}.

• Matrix decompositions
• Linear algebra

• Articles with short description
• Short description matches Wikidata