Rank factorization

In mathematics, given a field \mathbb F , non-negative integers m,n , and a matrix A\in\mathbb F^{m\times n} , a rank decomposition or rank factorization of is a factorization of of the form , where C\in\mathbb F^{m\times r} and F\in\mathbb F^{r\times n} , where r=\operatorname{rank} A is the rank of A .

In mathematics, given a field \mathbb F , non-negative integers m,n , and a matrix A\in\mathbb F^{m\times n} , a rank decomposition or rank factorization of is a factorization of of the form , where C\in\mathbb F^{m\times r} and F\in\mathbb F^{r\times n} , where r=\operatorname{rank} A is the rank of A . 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 \mathbf{c}_1, \mathbf{c}_2, \ldots, \mathbf{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 = \begin{bmatrix}\mathbf{c}_1 & \mathbf{c}_2 & \cdots & \mathbf{c}_r\end{bmatrix} . Therefore, every column vector of A is a linear combination of the columns of C . To be precise, if A = \begin{bmatrix}\mathbf{a}_1 & \mathbf{a}_2 & \cdots & \mathbf{a}_n\end{bmatrix} is an m\times n matrix with \mathbf{a}_j as the j -th column, then \mathbf{a}_j = f_{1j} \mathbf{c}_1 + f_{2j} \mathbf{c}_2 + \cdots + f_{rj} \mathbf{c}_r, where f_{ij} 's are the scalar coefficients of \mathbf{a}_j in terms of the basis \mathbf{c}_1, \mathbf{c}_2, \ldots, \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} . 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\times n identity 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} 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 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 = \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. If \mathbb F\in\{\mathbb R,\mathbb C\}, then one can also construct a full-rank factorization of A via a singular value decomposition A = U \Sigma V^* 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^* . === 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^\textsf{T} . Since the columns of A are the rows of A^\textsf{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^\textsf{T} = F^\textsf{T}C^\textsf{T} . From the definition of matrix multiplication, this means that each column of A^\textsf{T} is a linear combination of the columns of F^\textsf{T} . Therefore, the column space of A^\textsf{T} is contained within the column space of F^\textsf{T} and, hence, \operatorname{rank}\left(A^\textsf{T}\right) \leq \operatorname{rank}\left(F^\textsf{T}\right) . Now, F^\textsf{T} is n \times r , so there are r columns in F^\textsf{T} and, hence, \operatorname{rank}\left(A^\textsf{T}\right) \leq r = \operatorname{rank}\left(A\right) . This proves that \operatorname{rank}\left(A^\textsf{T}\right) \leq \operatorname{rank}\left(A\right) . Now apply the result to A^\textsf{T} to obtain the reverse inequality: since \left(A^\textsf{T}\right)^\textsf{T} = A , we can write \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 \operatorname{rank}\left(A\right) \leq \operatorname{rank}\left(A^\textsf{T}\right) . We have, therefore, proved \operatorname{rank}\left(A^\textsf{T}\right) \leq \operatorname{rank}\left(A\right) and \operatorname{rank}\left(A\right) \leq \operatorname{rank}\left(A^\textsf{T}\right) , so \operatorname{rank}\left(A\right) = \operatorname{rank}\left(A^\textsf{T}\right) .

Notes

References

Text derived from https://en.wikipedia.org/w/index.php?oldid=1310010178 under CC BY-SA 4.0; modifications have been made.