# Factor Characterization of Matrix Rank

I am currently taking a course on communication complexity with Alexander Sherstov. Much of communication complexity involves matrix analysis, so yesterday we did a brief review of results from linear algebra. In the review, Sherstov gave the following definition for the rank of a matrix $$M \in \mathbf{F}^{n \times m}$$:
$\mathrm{rank}(M) = \min{k | M = A B, A \in \mathbf{F}^{n \times k}, B \in \mathbf{F}^{k \times m}}$
Since this “factor” definition of rank appears very different from the standard definition given in a linear algebra course, I thought I would prove that the two definitions are equivalent.

The “standard” definition of rank is
$\mathrm{rank}(M) = \mathrm{dim}\ \mathrm{span} {\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_m}$
where $$\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_m$$ are the columns of $$M$$. Equivalently, $$\mathrm{rank}(M)$$ is the number of linearly independent columns of $$M$$.

An easy consequence of the standard definition of rank is that the rank of a product of matrices is at most the rank of the first matrix: $$\mathrm{rank}(A B) \leq \mathrm{rank}(A)$$. Indeed, the columns of $$AB$$ are linear combinations of the columns of $$A$$, hence the span of the columns of $$AB$$ is a subspace of the span of the columns of $$A$$. Thus, if we can write $$M = A B$$ with $$A \in \mathbf{F}^{n \times k}$$ and $$B \in \mathbf{F}^{k \times m}$$, we must have $$\mathrm{rank}(M) \leq k$$.

It remains to show that if $$\mathrm{rank}(M) = k$$ then we can factor $$M = A B$$ with $$A \in \mathbf{F}^{n \times k}$$ and $$B \in \mathbf{F}^{k \times m}$$. To this end, assume without loss of generality that the first $$k$$ columns of $$M$$ are linearly independent. Write these columns as vectors
$$\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_k$$. Denote the remaining columns by $$\mathbf{w}_1, \mathbf{w}_2, \ldots, \mathbf{w}_{m-k}$$. Since these vectors lie in the span of the first $$k$$ columns of $$M$$, we can write the $$\mathbf{w}_j$$ as linear combinations of the $$\mathbf{v}_i$$:
$\mathbf{w}_j = \sum_{i = 1}^k b_{i, j} \mathbf{v}_i \quad\text{for}\quad j = 1, 2, \ldots, m – k.$
Now define the matrices
$A = (\mathbf{v}_1\ \mathbf{v}_2\ \cdots\ \mathbf{v}_k)$
and
$B = (\mathbf{e}_1\ \mathbf{e}_2\ \cdots\ \mathbf{e}_k\ \mathbf{b}_1\ \mathbf{b}_2\ \cdots\ \mathbf{b}_{m – k})$
where $$\mathbf{e}_j$$ is the $$j$$th standard basis vector in $$\mathbf{F}^k$$ and
$\mathbf{b}_j = \begin{pmatrix} b_{1, j}\ b_{2, j}\ \vdots\ b_{k, j} \end{pmatrix} \quad\text{for}\quad j = 1, 2, \ldots, m – k.$
It is straightforward to verify that we have $$M = A B$$, which proves the equivalence of the two definitions of rank.