Rank factorization

Given an $m\times n$ matrix $A$ of rank $r$ , a rank decomposition or rank factorization of $A$ is a product $A=CF$ , where $C$ is an $m\times r$ matrix and $F$ is an $r\times n$ matrix.

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 $c_1,c_2,\ldots,c_r$ be any basis for the column space of $A$ and place them as column vectors to form the $m\times r$ matrix $C=[c_{1}:c_{2}:\ldots :c_{r}]$ . Therefore, every column vector of $A$ is a linear combination of the columns of $C$ . To be precise, if $A=[a_{1}:a_{2}:\ldots :a_{n}]$ is an $m\times n$ matrix with $a_{j}$ as the $j$ -th column, then

a_{j}=f_{{1j}}c_{1}+f_{{2j}}c_{2}+\cdots +f_{{rj}}c_{r},

where $f_{ij}$ 's are the scalar coefficients of $a_{j}$ in terms of the basis $c_1,c_2,\ldots,c_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 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}$ .^[1]

Construction

Rank factorization from 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, and $F$ by eliminating all zero rows of $B$ .

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$ 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, 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$ 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 $AP$ into its reduced row echelon form amounts to left-multiplying by a matrix $E$ which is a product of elementary matrices, so $EAP=BP=EC(I_{r},G)$ , where $EC={\begin{pmatrix}I_{r}\\0\end{pmatrix}}$ . We then can write $BP={\begin{pmatrix}I_{r}&G\\0&0\end{pmatrix}}$ , 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

One can also construct a full rank factorization of $A$ by using its 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}(\Sigma _{r}V_{1}^{*}).

Since $U_{1}$ is a full column rank matrix and $\Sigma _{r}V_{1}^{*}$ is a full row rank matrix, we can take $C=U_{1}$ and $F=\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, rank( $A^{{\text{T}}}$ ) ≤ rank( $F^{{\text{T}}}$ ). Now, $F^{{\text{T}}}$ is $n$ × $r$ , so there are $r$ columns in $F^{{\text{T}}}$ and, hence, rank( $A^{{\text{T}}}$ ) ≤ $r$ = rank( $A$ ). This proves that rank( $A^{{\text{T}}})$ ≤ rank( $A$ ). Now apply the result to $A^{{\text{T}}}$ to obtain the reverse inequality: since $(A^{{\text{T}}})^{{\text{T}}}$ = $A$ , we can write rank( $A$ ) = rank( $(A^{{\text{T}}})^{{\text{T}}})$ ≤ rank( $A^{{\text{T}}}$ ). This proves rank( $A)$ ≤ rank( $A^{{\text{T}}}$ ). We have, therefore, proved rank( $A^{{\text{T}}})$ ≤ rank( $A$ ) and rank( $A$ ) ≤ rank( $A^{{\text{T}}}$ ), so rank( $A$ ) = rank( $A^{{\text{T}}}$ ). (Also see the first proof of column rank = row rank under rank).

Notes

↑ Piziak, R.; Odell, P. L. (1 June 1999). "Full Rank Factorization of Matrices". Mathematics Magazine. 72 (3): 193. doi:10.2307/2690882.

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.

This article is issued from Wikipedia - version of the 5/31/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.