Rank factorization

Given an m × n { extstyle m imes n} matrix A { extstyle A} of rank r { extstyle r} , a rank decomposition or rank factorization of A { extstyle A} is a product A = C F { extstyle A=CF} , where C { extstyle C} is an m × r { extstyle m imes r} matrix and F { extstyle F} is an r × n { extstyle r imes n} matrix. Given an m × n { extstyle m imes n} matrix A { extstyle A} of rank r { extstyle r} , a rank decomposition or rank factorization of A { extstyle A} is a product A = C F { extstyle A=CF} , where C { extstyle C} is an m × r { extstyle m imes r} matrix and F { extstyle F} is an r × n { extstyle r imes n} matrix. Every finite-dimensional matrix has a rank decomposition: Let A { extstyle A} be an m × n { extstyle m imes n} matrix whose column rank is r { extstyle r} . Therefore, there are r { extstyle r} linearly independent columns in A { extstyle A} ; equivalently, the dimension of the column space of A { extstyle A} is r { extstyle r} . Let c 1 , c 2 , … , c r { extstyle c_{1},c_{2},ldots ,c_{r}} be any basis for the column space of A { extstyle A} and place them as column vectors to form the m × r { extstyle m imes r} matrix C = [ c 1 : c 2 : … : c r ] { extstyle C=} . Therefore, every column vector of A { extstyle A} is a linear combination of the columns of C { extstyle C} . To be precise, if A = [ a 1 : a 2 : … : a n ] { extstyle A=} is an m × n { extstyle m imes n} matrix with a j { extstyle a_{j}} as the j { extstyle j} -th column, then where f i j { extstyle f_{ij}} 's are the scalar coefficients of a j { extstyle a_{j}} in terms of the basis c 1 , c 2 , … , c r { extstyle c_{1},c_{2},ldots ,c_{r}} . This implies that A = C F { extstyle A=CF} , where f i j { extstyle f_{ij}} is the ( i , j ) { extstyle (i,j)} -th element of F { extstyle F} . If A = C 1 F 1 { extstyle A=C_{1}F_{1}} is rank factorization, taking C 2 = C 1 R { extstyle C_{2}=C_{1}R} and F 2 = R − 1 F 1 { extstyle F_{2}=R^{-1}F_{1}} gives another rank factorization for any invertible matrix R { extstyle R} of compatible dimensions. Conversely, if A = F 1 G 1 = F 2 G 2 { extstyle A=F_{1}G_{1}=F_{2}G_{2}} are two rank factorizations of A { extstyle A} , then there exists an invertible matrix R { extstyle R} such that F 1 = F 2 R { extstyle F_{1}=F_{2}R} and G 1 = R − 1 G 2 { extstyle G_{1}=R^{-1}G_{2}} . In practice, we can construct one specific rank factorization as follows: we can compute B { extstyle B} , the reduced row echelon form of A { extstyle A} . Then C { extstyle C} is obtained by removing from A { extstyle A} all non-pivot columns, and F { extstyle F} by eliminating all zero rows of B { extstyle B} .