Rank factorization

In mathematics, given an matrix of rank , a rank decomposition or rank factorization of is a factorization of of the form , where is an matrix and is an matrix.
Existence.
Every finite-dimensional matrix has a rank decomposition: Let formula_1 be an formula_2 matrix whose column rank is formula_3. Therefore, there are formula_3 linearly independent columns in formula_1; equivalently, the dimension of the column space of formula_1 is formula_3. Let formula_8 be any basis for the column space of formula_1 and place them as column vectors to form the formula_10 matrix formula_11. Therefore, every column vector of formula_1 is a linear combination of the columns of formula_13. To be precise, if formula_14 is an formula_2 matrix with formula_16 as the formula_17-th column, then
where formula_19's are the scalar coefficients of formula_16 in terms of the basis formula_8. This implies that formula_22, where formula_19 is the formula_24-th element of formula_25. 
Non-uniqueness.
If formula_26 is rank factorization, taking formula_27 and 
formula_28 gives another rank factorization for any invertible matrix formula_29 of compatible dimensions. 
Conversely, if formula_30 are two rank factorizations of formula_1, then there exists an invertible matrix formula_29 such that formula_33 and formula_34.
Construction.
Rank factorization from reduced row echelon forms.
In practice, we can construct one specific rank factorization as follows: we can compute formula_35, the reduced row echelon form of formula_1. Then formula_13 is obtained by removing from formula_1 all non-pivot columns (which can be determined by looking for columns in formula_35 which do not contain a pivot), and formula_25 is obtained by eliminating any all-zero rows of formula_35.
Note: For a full-rank square matrix (i.e. when formula_42), this procedure will yield the trivial result formula_43 and formula_44 (the formula_45 identity matrix).
Example.
Consider the matrix
formula_35 is in reduced echelon form.
Then formula_13 is obtained by removing the third column of formula_1, the only one which is not a pivot column, and formula_25 by getting rid of the last row of zeroes from formula_35, so
It is straightforward to check that
Proof.
Let formula_54 be an formula_45 permutation matrix such that formula_56 in block partitioned form, where the columns of formula_13 are the formula_3 pivot columns of formula_1. Every column of formula_60 is a linear combination of the columns of formula_13, so there is a matrix formula_62 such that formula_63, where the columns of formula_62 contain the coefficients of each of those linear combinations. So formula_65, formula_66 being the formula_67 identity matrix. We will show now that formula_68.
Transforming formula_1 into its reduced row echelon form formula_35 amounts to left-multiplying by a matrix formula_71 which is a product of elementary matrices, so formula_72, where formula_73. We then can write formula_74, which allows us to identify formula_68, i.e. the nonzero formula_3 rows of the reduced echelon form, with the same permutation on the columns as we did for formula_1. We thus have formula_78, and since formula_54 is invertible this implies formula_22, and the proof is complete.
Singular value decomposition.
One can also construct a full rank factorization of formula_1 by using its singular value decomposition
Since formula_83 is a full column rank matrix and formula_84 is a full row rank matrix, we can take formula_85 and formula_86.
Consequences.
rank(A) = rank(AT).
An immediate consequence of rank factorization is that the rank of formula_1 is equal to the rank of its transpose formula_88. Since the columns of formula_1 are the rows of formula_88, the column rank of formula_1 equals its row rank. 
Proof: To see why this is true, let us first define rank to mean column rank. Since formula_22, it follows that formula_93. From the definition of matrix multiplication, this means that each column of formula_88 is a linear combination of the columns of formula_95. Therefore, the column space of formula_88 is contained within the column space of formula_95 and, hence, formula_98.
Now, formula_95 is formula_100, so there are formula_3 columns in formula_95 and, hence, formula_103. This proves that formula_104.
Now apply the result to formula_88 to obtain the reverse inequality: since formula_106, we can write formula_107. This proves formula_108.
We have, therefore, proved formula_104 and formula_108, so formula_111. (Also see the first proof in ).