Proof of the rank inequality for a product of matrices

Proof

We compare column spaces, and then pass to transposes for the second inequality.

1. Let $A = (a_{ij})$ be $m \times n$ and $B = (b_{jk})$ be $n \times p$. Let $\alpha_1, \dots, \alpha_n \in F^m$ be the columns of $A$.
2. By the definition of the matrix product, entry $i$ of column $k$ of $AB$ is $\sum_{j=1}^n a_{ij} b_{jk}$. So column $k$ of $AB$ equals $\sum_{j=1}^n b_{jk} \alpha_j$.
3. Hence each column of $AB$ lies in the column space $\operatorname{Col}(A)$. Since $\operatorname{Col}(A)$ is a subspace, $\operatorname{Col}(AB) \subseteq \operatorname{Col}(A)$.
4. $F^m$ has dimension $m$ by the dimension of the coordinate space, so $\operatorname{Col}(A)$ is finite-dimensional by the dimension of a subspace.
5. Applying the dimension of a subspace inside $\operatorname{Col}(A)$ gives $\dim \operatorname{Col}(AB) \le \dim \operatorname{Col}(A)$. By the definition of rank, $\rank(AB) \le \rank A$.
6. Step 5 holds for any two matrices whose product is defined.
7. By row rank equals column rank, $\rank(AB) = \rank\left((AB)^T\right)$, with the transpose.
8. By the transpose of a product, $(AB)^T = B^T A^T$, where $B^T$ is $p \times n$ and $A^T$ is $n \times m$.
9. By step 6 applied to $B^T$ and $A^T$, $\rank(B^T A^T) \le \rank B^T$.
10. By row rank equals column rank again, $\rank B^T = \rank B$. So $\rank(AB) \le \rank B$.
11. By steps 5 and 10, $\rank(AB) \le \min(\rank A, \rank B)$.