In mathematics, given a field \mathbb F, nonnegative integers m,n, and a matrix, a rank decomposition or rank factorization of A is a factorization of A of the form A = CF , where and, where is the rank of A.

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 be any basis for the column space of A and place them as column vectors to form the m\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\times n matrix with as the j-th column, then where f_{ij}'s are the scalar coefficients of in terms of the basis. 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 a rank factorization, taking C_2 = C_1 R and gives another rank factorization for any invertible matrix R of compatible dimensions. Conversely, if are two rank factorizations of A, then there exists an invertible matrix R such that F_1 = F_2 R and.

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\times n identity matrix).

Example

Consider the matrix 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 It is straightforward to check that

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, I_r being the r\times r identity matrix. We will show now that. 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, where. We then can write, which allows us to identify , 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 then one can also construct a full-rank factorization of A via a singular value decomposition Since U_1 is a full-column-rank matrix and is a full-row-rank matrix, we can take C = U_1 and.

Consequences

rank(A) = rank(AT)

An immediate consequence of rank factorization is that the rank of A is equal to the rank of its transpose. Since the columns of A are the rows of, 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. From the definition of matrix multiplication, this means that each column of is a linear combination of the columns of. Therefore, the column space of is contained within the column space of and, hence,. Now, is n \times r, so there are r columns in and, hence,. This proves that. Now apply the result to to obtain the reverse inequality: since, we can write. This proves. We have, therefore, proved and, so.