The Rank of a Product
Matrix multiplication applies one linear transformation after another. The first matrix acts on the output of the second, so the product cannot produce more independent outputs than either stage can support. This gives an upper bound on the rank of a product. The bound is useful in its own right, but the reason behind each side is also important: one comes from containment of column spaces, and the other from containment of null spaces.
Throughout, matrices have real entries. For \(\mathbf{A}\in\mathbb{R}^{m\times n}\) and \(\mathbf{B}\in\mathbb{R}^{n\times p}\), the product \(\mathbf{A}\mathbf{B}\) is defined and has size \(m\times p\). The rank of a matrix is the dimension of its column space. Equivalently, it is the number of pivot columns in a row reduction. We view \(\mathbf{B}\) as a map from \(\mathbb{R}^p\) to \(\mathbb{R}^n\), and \(\mathbf{A}\) as a map from \(\mathbb{R}^n\) to \(\mathbb{R}^m\).
The two inequalities in the theorem express different restrictions. The left factor determines a space in which all outputs must lie. The right factor limits the set of inputs that can reach the left factor. We prove these restrictions separately.
Why the Left Factor Gives an Upper Bound
For any \(\mathbf{x}\in\mathbb{R}^p\), the vector \(\mathbf{B}\mathbf{x}\) belongs to \(\mathbb{R}^n\), so \(\mathbf{A}(\mathbf{B}\mathbf{x})\) is a linear combination of the columns of \(\mathbf{A}\). Thus every column of \(\mathbf{A}\mathbf{B}\), and indeed every vector in its column space, belongs to \(\operatorname{Col}\mathbf{A}\).
For finite-dimensional subspaces, containment implies that the dimension of the smaller subspace is no larger than the dimension of the larger one: any linearly independent list in the contained subspace is also linearly independent in the containing subspace. Taking dimensions gives \(\operatorname{rank}(\mathbf{A}\mathbf{B})\leq\operatorname{rank}\mathbf{A}\).
In map language, if \(T_{\mathbf{A}}(\mathbf{y})=\mathbf{A}\mathbf{y}\) and \(T_{\mathbf{B}}(\mathbf{x})=\mathbf{B}\mathbf{x}\), then \(T_{\mathbf{A}\mathbf{B}}=T_{\mathbf{A}}\circ T_{\mathbf{B}}\). The image of this composition is \(T_{\mathbf{A}}(\operatorname{im}T_{\mathbf{B}})\), which is contained in \(\operatorname{im}T_{\mathbf{A}}\). The product cannot output a vector outside the image allowed by \(\mathbf{A}\).
Why the Right Factor Gives an Upper Bound
The null space of a matrix \(\mathbf{M}\) is the set of vectors \(\mathbf{x}\) for which \(\mathbf{M}\mathbf{x}=\mathbf{0}\). If \(\mathbf{x}\in\operatorname{Nul}\mathbf{B}\), then \(\mathbf{B}\mathbf{x}=\mathbf{0}\), and therefore \(\mathbf{A}\mathbf{B}\mathbf{x}=\mathbf{A}\mathbf{0}=\mathbf{0}\). Hence \(\operatorname{Nul}\mathbf{B}\subseteq\operatorname{Nul}(\mathbf{A}\mathbf{B})\).
Both null spaces are subspaces of the same domain, \(\mathbb{R}^p\). The matrix rank-nullity theorem says that for a matrix with \(p\) columns, its rank plus the dimension of its null space equals \(p\). A larger null space therefore leaves less rank. Applying the theorem to both matrices gives the second inequality.
Proof. Let \(r=\operatorname{rank}(\mathbf{A}\mathbf{B})\) and \(s=\operatorname{rank}\mathbf{B}\). From the null-space inclusion, \(\operatorname{nullity}(\mathbf{A}\mathbf{B})\geq\operatorname{nullity}\mathbf{B}\). Since both matrices have \(p\) columns, rank-nullity gives \(r=p-\operatorname{nullity}(\mathbf{A}\mathbf{B})\leq p-\operatorname{nullity}\mathbf{B}=s\). Thus \(\operatorname{rank}(\mathbf{A}\mathbf{B})\leq\operatorname{rank}\mathbf{B}\). Together with the column-space inclusion proved above, the rank of the product is bounded by the rank of each factor, and hence by their minimum. \(\square\)
The null-space argument says that any input already erased by \(\mathbf{B}\) is necessarily erased by the product as well. The product may erase additional inputs if \(\mathbf{B}\mathbf{x}\) is nonzero but lies in \(\operatorname{Nul}\mathbf{A}\). This possibility helps explain why the upper bound need not be an equality.
Worked Products and Their Ranks
Worked Example: The Left Factor Sets the Bound
Let \(\mathbf{A}=\begin{bmatrix}1&2&0\\2&4&0\end{bmatrix}\) and \(\mathbf{B}=\begin{bmatrix}1&0\\0&1\\1&1\end{bmatrix}\). Compute the product and compare its rank with the ranks of the factors.
Multiplying row by column gives the first row \((1\cdot1+2\cdot0+0\cdot1,\;1\cdot0+2\cdot1+0\cdot1)=(1,2)\). The second row is \((2\cdot1+4\cdot0+0\cdot1,\;2\cdot0+4\cdot1+0\cdot1)=(2,4)\). Thus \(\mathbf{A}\mathbf{B}=\begin{bmatrix}1&2\\2&4\end{bmatrix}\).
The second row of \(\mathbf{A}\) is twice its first row, and its first row is nonzero, so \(\operatorname{rank}\mathbf{A}=1\). For \(\mathbf{B}\), row reduction gives
There are two pivots, so \(\operatorname{rank}\mathbf{B}=2\). The product has proportional rows, with one nonzero row, and therefore has rank \(1\). Its rank equals the smaller factor rank, which here is the rank of \(\mathbf{A}\).
Check: Direct multiplication confirms the product: the first column of \(\mathbf{B}\) is \((1,0,1)^{\top}\), and \(\mathbf{A}(1,0,1)^{\top}=(1,2)^{\top}\); the second column is \((0,1,1)^{\top}\), and \(\mathbf{A}(0,1,1)^{\top}=(2,4)^{\top}\).
Worked Example: The Right Factor Sets the Bound
Take \(\mathbf{A}=\begin{bmatrix}1&0\\0&1\\1&1\end{bmatrix}\) and \(\mathbf{B}=\begin{bmatrix}1&2&3\\0&0&0\end{bmatrix}\). Find the product and its rank.
Each column of \(\mathbf{B}\) is a multiple of \((1,0)^{\top}\), and the first column is nonzero, so \(\operatorname{rank}\mathbf{B}=1\). The first two rows of \(\mathbf{A}\) are the two standard basis vectors in \(\mathbb{R}^2\), so they are independent and \(\operatorname{rank}\mathbf{A}=2\). Compute each product column: \(\mathbf{A}(1,0)^{\top}=(1,0,1)^{\top}\), \(\mathbf{A}(2,0)^{\top}=(2,0,2)^{\top}\), and \(\mathbf{A}(3,0)^{\top}=(3,0,3)^{\top}\). Consequently, \(\mathbf{A}\mathbf{B}=\begin{bmatrix}1&2&3\\0&0&0\\1&2&3\end{bmatrix}\).
The product is nonzero and all its columns are multiples of its first column, so its rank is \(1\). This time the product rank equals the rank of the right factor, the smaller of the two factor ranks.
Check: The product's second column is \(2(1,0,1)^{\top}\), and its third is \(3(1,0,1)^{\top}\), as the computed matrix shows. The stated rank follows because the first column is nonzero and spans all three columns.
Worked Example: Both Bounds Can Be Strict
Let \(\mathbf{A}=\begin{bmatrix}1&0&0\\0&1&0\end{bmatrix}\) and \(\mathbf{B}=\begin{bmatrix}1&0\\0&0\\0&1\end{bmatrix}\). Both factors have rank \(2\): \(\mathbf{A}\) has two pivot columns, and row reduction of \(\mathbf{B}\) gives \(\begin{bmatrix}1&0\\0&0\\0&1\end{bmatrix}\), with pivots in rows 1 and 3 (interchanging rows 2 and 3 puts it in echelon form).
The first column of \(\mathbf{B}\) is \((1,0,0)^{\top}\), which \(\mathbf{A}\) maps to \((1,0)^{\top}\). Its second column \((0,0,1)^{\top}\) is mapped to \((0,0)^{\top}\). Therefore \(\mathbf{A}\mathbf{B}=\begin{bmatrix}1&0\\0&0\end{bmatrix}\), of rank \(1\). Both upper bounds are strict: \(1<\operatorname{rank}\mathbf{A}=2\) and \(1<\operatorname{rank}\mathbf{B}=2\).
Check: Multiplying \(\mathbf{A}\) by the displayed first column of \(\mathbf{B}\) gives \((1,0)^{\top}\), and multiplying by the displayed second column gives \((0,0)^{\top}\). The resulting product has exactly one nonzero independent column.
Reading the Bound Through Images and Null Spaces
For the left factor, the useful statement is \(\operatorname{Col}(\mathbf{A}\mathbf{B})\subseteq\operatorname{Col}\mathbf{A}\). The product can only use outputs available from \(\mathbf{A}\). Equality of these column spaces is possible, as the first example shows in terms of their one-dimensional ranks, but containment can be strict.
For the right factor, \(\operatorname{Nul}\mathbf{B}\subseteq\operatorname{Nul}(\mathbf{A}\mathbf{B})\). If \(\mathbf{B}\) already sends an input to zero, the product must do the same. The product may also have a larger null space than \(\mathbf{B}\), because some nonzero outputs of \(\mathbf{B}\) may be sent to zero by \(\mathbf{A}\). Rank-nullity then converts this inclusion into the rank bound involving \(\mathbf{B}\).
These inclusions are also useful for checking reasoning. The product has \(p\) columns and \(m\) rows, so its rank cannot exceed either \(p\) or \(m\); the theorem adds the potentially stronger limits supplied by the two factors. In applications, a low-rank stage restricts the number of independent directions that can survive the entire composition, even if the other stage has larger rank.
Common Pitfall: The Bound Is Not an Equality Rule
A frequent mistake is to replace the inequality with the claim that the product rank must equal the smaller factor rank. The third example disproves that claim: both factor ranks are \(2\), but the product rank is \(1\). The second column of \(\mathbf{B}\) in that example lies in \(\operatorname{Nul}\mathbf{A}\), so one of the two independent directions supplied by \(\mathbf{B}\) disappears after applying \(\mathbf{A}\).
Here is the concrete incorrect calculation: “\(\operatorname{rank}\mathbf{A}=2\) and \(\operatorname{rank}\mathbf{B}=2\), so \(\operatorname{rank}(\mathbf{A}\mathbf{B})=2\).” The actual multiplication is
The correction is to use the theorem as an upper bound, not as a formula for the exact rank. To find the exact rank, compute the product and determine its pivot count or column-space dimension. The factor ranks alone do not determine how many directions the second matrix sends into directions that the first matrix annihilates.
Check Your Understanding
For each question, distinguish the two inclusions and the two rank bounds.
- If \(\mathbf{A}\in\mathbb{R}^{4\times 3}\) and \(\mathbf{B}\in\mathbb{R}^{3\times 2}\), what is the size of \(\mathbf{A}\mathbf{B}\), and what two rank inequalities follow?
- Explain why \(\operatorname{Col}(\mathbf{A}\mathbf{B})\subseteq\operatorname{Col}\mathbf{A}\).
- Prove that \(\operatorname{Nul}\mathbf{B}\subseteq\operatorname{Nul}(\mathbf{A}\mathbf{B})\) using the definition of null space.
- For the third worked example, identify a nonzero vector in \(\operatorname{Nul}\mathbf{A}\) that is a column of \(\mathbf{B}\).
- Can the rank of a product be greater than the rank of its right factor? State which part of the proof rules this out.
