Rank factorization

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\{c\}\_1,\; \backslash mathbf\{c\}\_2,\; \backslash ldots,\; \backslash mathbf\{c\}\_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\{a\}\_j$ as the $j$-th column, then

:$\backslash mathbf\{a\}\_j\; =\; f\_\{1j\}\; \backslash mathbf\{c\}\_1\; +\; f\_\{2j\}\; \backslash mathbf\{c\}\_2\; +\; \backslash cdots\; +\; f\_\{rj\}\; \backslash mathbf\{c\}\_r,$

where $f\_\{ij\}$'s are the scalar coefficients of $\backslash mathbf\{a\}\_j$ in terms of the basis $\backslash mathbf\{c\}\_1,\; \backslash mathbf\{c\}\_2,\; \backslash ldots,\; \backslash mathbf\{c\}\_r$. This implies that $A\; =\; CF$, where $f\_\{ij\}$ is the $(i,j)$-th element of $F$.

If $A\; =\; C\_1\; F\_1$ is a 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\}$.{{cite journal|last1=Piziak|first1=R.|last2=Odell|first2=P. L.|title=Full Rank Factorization of Matrices|journal=Mathematics Magazine|date=1 June 1999|volume=72|issue=3|pages=193|doi=10.2307/2690882|jstor=2690882}}

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

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

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\{pmatrix\}\; I\_r\; \backslash \backslash \; 0\; \backslash end\{pmatrix\}$. 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.

If $\backslash mathbb\; F\backslash in\backslash \{\backslash mathbb\; R,\backslash mathbb\; C\backslash \},$ then one can also construct a full-rank factorization of $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$ 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^*$.

{{See also|1=Rank_(linear_algebra)#Proofs_that_column_rank_=_row_rank|label 1=Proofs that column rank = row rank}}

An immediate consequence of rank factorization is that the rank of $A$ is equal to the rank of its transpose $A^\backslash textsf\{T\}$. Since the columns of $A$ are the rows of $A^\backslash textsf\{T\}$, the column rank of $A$ equals its row rank.{{Citation | last1 = Banerjee | first1 = Sudipto | last2 = Roy | first2 = Anindya | date = 2014 | title = Linear Algebra and Matrix Analysis for Statistics | series = Texts in Statistical Science | publisher = Chapman and Hall/CRC | edition = 1st | isbn = 978-1420095388}}

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\{T\}\; =\; F^\backslash textsf\{T\}C^\backslash textsf\{T\}$. From the definition of matrix multiplication, this means that each column of $A^\backslash textsf\{T\}$ is a linear combination of the columns of $F^\backslash textsf\{T\}$. Therefore, the column space of $A^\backslash textsf\{T\}$ is contained within the column space of $F^\backslash textsf\{T\}$ and, hence, $\backslash operatorname\{rank\}\backslash left(A^\backslash textsf\{T\}\backslash right)\; \backslash leq\; \backslash operatorname\{rank\}\backslash left(F^\backslash textsf\{T\}\backslash right)$.

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

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

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

{{reflist}}

{{refbegin}}

• {{Citation | last1 = Banerjee | first1 = Sudipto | last2 = Roy | first2 = Anindya | date = 2014 | title = Linear Algebra and Matrix Analysis for Statistics | series = Texts in Statistical Science | publisher = Chapman and Hall/CRC | edition = 1st | isbn = 978-1420095388}}
• {{Citation | last = Lay | first = David C. | date = 2005 | title = Linear Algebra and its Applications | publisher = Addison Wesley | edition = 3rd | isbn = 978-0-201-70970-4}}
• {{Citation | last1 = Golub | first1 = Gene H. | last2 = Van Loan | first2 = Charles F. | date = 1996 | title = Matrix Computations | series = Johns Hopkins Studies in Mathematical Sciences | publisher = The Johns Hopkins University Press | edition = 3rd | isbn = 978-0-8018-5414-9}}
• {{Citation | last = Stewart | first = Gilbert W. | date = 1998 | title = Matrix Algorithms. I. Basic Decompositions | publisher = SIAM | isbn = 978-0-89871-414-2}}
• {{cite journal|last1=Piziak|first1=R.|last2=Odell|first2=P. L.|title=Full Rank Factorization of Matrices|journal=Mathematics Magazine|date=1 June 1999|volume=72|issue=3|pages=193|doi=10.2307/2690882|jstor=2690882}}

{{refend}}

Category:Matrix decompositions

Category:Linear algebra