Rank factorization explained

In mathematics, given a field

F , nonnegative integers m,n , and a matrix A\in F ^{m x} , a rank decomposition or rank factorization of is a factorization of of the form, where C\in F ^{m x} and F\in F ^{r x} , where r = \operatorname{rank} A is the rank of A .

Existence

Every finite-dimensional matrix has a rank decomposition: Let $A$ be an $m\backslash 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 $\backslash mathbf\_1,\; \backslash mathbf\_2,\; \backslash ldots,\; \backslash mathbf\_r$ be any basis for the column space of $A$ and place them as column vectors to form the $m\backslash times\; r$ matrix . Therefore, every column vector of $A$ is a linear combination of the columns of $C$. To be precise, if is an $m\backslash times\; n$ matrix with $\backslash mathbf\_j$ as the $j$-th column, then

a _{j} = f _{1j} c _{1} + f _{2j} c _{2} + … + f _{rj} c _{r,}

where $f\_$'s are the scalar coefficients of $\backslash mathbf\_j$ in terms of the basis $\backslash mathbf\_1,\; \backslash mathbf\_2,\; \backslash ldots,\; \backslash mathbf\_r$. This implies that $A\; =\; CF$, where $f\_$ 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^\; F\_1$ gives another rank factorization for any invertible matrix $R$ of compatible dimensions.

Conversely, if $A\; =\; F\_G\_\; =\; F\_G\_$ are two rank factorizations of $A$, then there exists an invertible matrix $R$ such that $F\_1\; =\; F\_2\; R$ and $G\_1\; =\; R^\; G\_$.^[1]

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\backslash 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 .

$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 = \begin{bmatrix} 1 & 3 & 4 \ 2 & 7 & 9 \ 1 & 5 & 1 \ 1 & 2 & 8 \end{bmatrix} , F = \begin{bmatrix} 1 & 0 & -2 & 0 \ 0 & 1 & 1 & 0 \ 0 & 0 & 0 & 1 \end{bmatrix} .

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 .

Proof

Let $P$ be an $n\backslash 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\backslash 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\; =\; \backslash begin\; I\_r\; \backslash \backslash \; 0\; \backslash end$. We then can write , 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

F\in\{ R, C\}, then one can also construct a full-rank factorization of $A$ via a singular value decompositionA = 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 ^{*\right)} _{1} .

Since $U\_1$ is a full-column-rank matrix and $\backslash Sigma\_r\; V\_1^*$ is a full-row-rank matrix, we can take $C\; =\; U\_1$ and $F\; =\; \backslash 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^\backslash textsf$. Since the columns of $A$ are the rows of $A^\backslash textsf$, 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^\backslash textsf\; =\; F^\backslash textsfC^\backslash textsf$. From the definition of matrix multiplication, this means that each column of $A^\backslash textsf$ is a linear combination of the columns of $F^\backslash textsf$. Therefore, the column space of $A^\backslash textsf$ is contained within the column space of $F^\backslash textsf$ and, hence, $\backslash operatorname\backslash left(A^\backslash textsf\backslash right)\; \backslash leq\; \backslash operatorname\backslash left(F^\backslash textsf\backslash right)$.

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

Now apply the result to $A^\backslash textsf$ to obtain the reverse inequality: since $\backslash left(A^\backslash textsf\backslash right)^\backslash textsf\; =\; A$, we can write $\backslash operatorname\backslash left(A\backslash right)=\; \backslash operatorname\backslash left(\backslash left(A^\backslash textsf\backslash right)^\backslash textsf\backslash right)\; \backslash leq\; \backslash operatorname\backslash left(A^\backslash textsf\backslash right)$. This proves $\backslash operatorname\backslash left(A\backslash right)\; \backslash leq\; \backslash operatorname\backslash left(A^\backslash textsf\backslash right)$.

We have, therefore, proved $\backslash operatorname\backslash left(A^\backslash textsf\backslash right)\; \backslash leq\; \backslash operatorname\backslash left(A\backslash right)$ and $\backslash operatorname\backslash left(A\backslash right)\; \backslash leq\; \backslash operatorname\backslash left(A^\backslash textsf\backslash right)$, so $\backslash operatorname\backslash left(A\backslash right)\; =\; \backslash operatorname\backslash left(A^\backslash textsf\backslash right)$.

References

• • • • • Piziak. R.. Odell. P. L.. Full Rank Factorization of Matrices. Mathematics Magazine. 1 June 1999. 72. 3. 193. 10.2307/2690882. 2690882.

Notes and References

1. Piziak. R.. Odell. P. L.. Full Rank Factorization of Matrices. Mathematics Magazine. 1 June 1999. 72. 3. 193. 10.2307/2690882. 2690882.