Rank factorization

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

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

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

where f i j {\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 = C F {\textstyle A=CF} , where f i j {\textstyle f_{ij}} is the ( i , j ) {\textstyle (i,j)} -th element of F {\textstyle F} .

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}} .[1]

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).

Consider the matrix

A = [ 1 3 1 4 2 7 3 9 1 5 3 1 1 2 0 8 ] ∼ [ 1 0 − 2 0 0 1 1 0 0 0 0 1 0 0 0 0 ] = B . {\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{.}}}

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 = [ 1 3 4 2 7 9 1 5 1 1 2 8 ] , F = [ 1 0 − 2 0 0 1 1 0 0 0 0 1 ] . {\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

A = [ 1 3 1 4 2 7 3 9 1 5 3 1 1 2 0 8 ] = [ 1 3 4 2 7 9 1 5 1 1 2 8 ] [ 1 0 − 2 0 0 1 1 0 0 0 0 1 ] = C F . {\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 P {\textstyle P} be an n × n {\textstyle n\times n} permutation matrix such that A P = ( 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 = C G {\textstyle D=CG} , where the columns of G {\textstyle G} contain the coefficients of each of those linear combinations. So A P = ( C , C G ) = 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 ) = F P {\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 E A P = B P = E C ( I r , G ) {\textstyle EAP=BP=EC(I_{r},G)} , where E C = ( I r 0 ) {\textstyle EC={\begin{pmatrix}I_{r}\\0\end{pmatrix}}} . We then can write B P = ( I r G 0 0 ) {\textstyle BP={\begin{pmatrix}I_{r}&G\\0&0\end{pmatrix}}} , which allows us to identify ( I r , G ) = F P {\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 A P = C F P {\textstyle AP=CFP} , and since P {\textstyle P} is invertible this implies A = C F {\textstyle A=CF} , and the proof is complete.

If F ∈ { R , C } , {\displaystyle \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 Σ V ∗ = [ U 1 U 2 ] [ Σ r 0 0 0 ] [ V 1 ∗ V 2 ∗ ] = U 1 ( Σ r V 1 ∗ ) . {\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 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}^{*}} .

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.[2]

Proof: To see why this is true, let us first define rank to mean column rank. Since A = C F {\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)} .