Computation of Matrix Subspaces

Rank Factorization

Definition 65: Rank Factorization of a Matrix

Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ . A rank factorization or column-row factorization of $𝐴$ is a factorization of the form:

𝐴 = 𝐶 𝑅,

where $𝐶 \in 𝐹^{𝑚 \times 𝑟}$ and $𝑅 \in 𝐹^{𝑟 \times 𝑛}$ , with $𝑟 = rank (𝐴)$ .

Proposition 15: Basis for Column and Row Spaces from Rank Factorizations

In any rank factorization $𝐴 = 𝐶 𝑅$ , the columns of $𝐶$ form a basis for $col (𝐴)$ . Similarly, the rows of $𝑅$ form a basis for $row (𝐴)$ .

Theorem 55: Existence of Rank Factorizations

Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ be a finite matrix of rank $𝑟$ . Then there must exist matrices $𝐶 \in 𝐹^{𝑚 \times 𝑟}$ and $𝑅 \in 𝐹^{𝑟 \times 𝑛}$ such that $𝐴 = 𝐶 𝑅$ .

Proof: Theorem 55.

Suppose $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ has rank $𝑟$ . Then $𝐴$ has exactly $𝑟$ linearly independent columns $𝐜_{1}, 𝐜_{2}, \dots, 𝐜_{𝑟} \in 𝐹^{𝑚}$ , so choose $𝐶 = (\begin{matrix} 𝐜_{1} & 𝐜_{2} & \dots & 𝐜_{𝑟} \end{matrix}) \in 𝐹^{𝑚 \times 𝑟}$ . Since $𝐴$ has rank $𝑟$ , the $𝑟$ columns of $𝐶$ must be a basis for $col (𝐴)$ , which implies that any column, say the $𝑗$ ^th column $𝐚_{𝑗}$ , of $𝐴$ can be expressed as a linear combination of the columns of $𝐶$ :

𝐚_{𝑗} = \sum_{𝑖 = 1}^{𝑟} 𝛽_{𝑖 𝑗} 𝐜_{𝑖},

where $𝛽_{𝑖 𝑗} \in 𝐹$ is the coefficient of $𝐜_{𝑖}$ in the linear combination used to express $𝐚_{𝑗}$ . Define a matrix $𝑅$ such that its $(𝑖, 𝑗)$ ^th entry is $𝛽_{𝑖 𝑗}$ . Since $1 \leq 𝑖 \leq 𝑟$ in the summation, $𝑅$ has $𝑟$ rows. Since there are $𝑛$ columns in $𝐴$ and $𝑗$ is the index of each column of $𝐴$ , $𝑅$ has $𝑛$ columns. Therefore, $𝑅 \in 𝐹^{𝑟 \times 𝑛}$ . ∎

Corollary 32: Alternative Rank Factorizations

Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ be a finite matrix of rank $𝑟$ . If $𝐴 = 𝐶_{1} 𝑅_{1}$ is a rank factorization of $𝐴$ (which follows that $𝐶_{1} \in 𝐹^{𝑚 \times 𝑟}$ and $𝑅_{1} \in 𝐹^{𝑟 \times 𝑛}$ ), then for any invertible matrix $𝑃 \in 𝐹^{𝑟 \times 𝑟}$ , the matrices $𝐶_{2} = 𝐶_{1} 𝑃$ and $𝑅_{2} = 𝑃^{- 1} 𝑅_{1}$ also form a rank factorization of $𝐴$ , i.e., $𝐴 = 𝐶_{2} 𝑅_{2}$ .

Algorithm 2: Finding the Rank Factorization of a Matrix

Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ be a finite matrix of rank $𝑟$ .

Find the row-reduced echelon form of $𝐴$ , say $𝐴^{'} = rref (𝐴)$ .
For every pivot column in $𝐴^{'}$ , identify the corresponding column in $𝐴$ and include it in the matrix $𝐶$ .
Form $𝑅$ by removing any all-zero rows from $𝐴^{'}$ .

Now, $𝐴 = 𝐶 𝑅$ is a rank factorization of $𝐴$ .