# How to prove and interpret $\operatorname{rank}(AB) \leq \operatorname{min}(\operatorname{rank}(A), \operatorname{rank}(B))$?

Let $$A$$ and $$B$$ be two matrices which can be multiplied. Then $$\operatorname{rank}(AB) \leq \operatorname{min}(\operatorname{rank}(A), \operatorname{rank}(B)).$$

I proved $$\operatorname{rank}(AB) \leq \operatorname{rank}(B)$$ by interpreting $$AB$$ as a composition of linear maps, observing that $$\operatorname{ker}(B) \subseteq \operatorname{ker}(AB)$$ and using the kernel-image dimension formula. This also provides, in my opinion, a nice interpretation: if non-stable, under subsequent compositions the kernel can only get bigger, and the image can only get smaller, in a sort of loss of information.

How do you manage $$\operatorname{rank}(AB) \leq \operatorname{rank}(A)$$? Is there a nice interpretation like the previous one?

• Your proof is fine. Furthermore, the same reasoning will get your desired fact. Again rank-nullity will tell you that the dimension of your vector space minus the dimension of the kernel will give you the rank. Jul 28, 2010 at 16:08

Yes. If you think of A and B as linear maps, then the domain of A is certainly at least as big as the image of B. Thus when we apply A to either of these things, we should get "more stuff" in the former case, as the former is bigger than the latter.

• Thank you. I was so obsessed with the kernel-image dimension formula that I could't recognize this simple fact.
– user365
Jul 30, 2010 at 8:52

Once you have proved $$\operatorname{rank}(AB) \le \operatorname{rank}(A)$$, you can obtain the other inequality by using transposition and the fact that it doesn't change the rank (see e.g. this question).

Specifically, letting $$C=A^T$$ and $$D=B^T$$, we have that $$\operatorname{rank}(DC) \le \operatorname{rank}(D) \implies \operatorname{rank}(C^TD^T)\le \operatorname{rank} (D^T)$$, which is $$\operatorname{rank}(AB) \le \operatorname{rank}(B)$$.

• Very nice! Thank you.
– user365
Sep 2, 2010 at 10:01
• I am doing this problem now too. Why is proving both inequalities enough? Where does the proof take the min idea into account? Apr 12, 2016 at 3:27
• @MathisHard $x<y \wedge x<z \implies x<\min(y,z)$. May 25, 2018 at 15:47

Note that $$\text{Col}(AB) ⊆ \text{Col}(A)$$ since given $$y ∈ \text{Col}(AB)$$ we can choose $$x ∈ F$$ and then we have $$y = (AB)x = A(Bx) ∈ \text{Col}(A)$$.

Since $$\text{Col}(AB) ⊆ \text{Col}(A)$$, any basis for $$\text{Col}(AB)$$ can be extended to a basis for $$\text{Col}(A)$$ and so $$\dim \text{Col}(AB) ≤ \dim \text{Col}(A)$$, that is $$\text{rk}(AB) ≤ \text{rk}(A).$$

Note that $$\text{Null}(B) ⊆ \text{Null}(AB)$$ since given $$x ∈ \text{Null}(B)$$ we have $$(AB)x = A(Bx) = A 0 = 0$$ so that $$x ∈ \text{Null}(AB)$$.

Since $$\text{Null}(B) ⊆ \text{Null}(AB)$$, as above we have $$\dim \text{Null}(B) ≤ \dim \text{Null}(AB)$$, that is, $$\text{Nullity}(B) ≤\text{Nullity}(AB)$$. Thus $$\text{rk}(AB) = n − \text{Nullity}(AB) ≤ n − \text{Nullity}(B) = \text{rk}(B).$$

• You should use MathJax to format your answer. Oct 15, 2015 at 21:06
• Very nice proof! +1
– ZFR
Apr 23, 2020 at 1:41

Prove first that if $f:X\to Y$ and $g:Y\to Z$ are functions between finite sets, then $|g(f(X))| \leq \min \{ |f(X)|, |g(Y)| \}.$

Then use the same idea.

• Categorification... :-) Jul 29, 2010 at 21:50
• I am not familiar with the 'categorification'. How can one go from this to the rank inequality ? What functor is to be applied ? Apr 13, 2014 at 12:10
• So you're saying that rank of linear map is somehow like image of a function? Feb 12, 2015 at 10:15
• @Mihail, it is like the size of the image of a function. in fact, if $f$ is a linear map, the rank of $f$ is the dimension of the image of $f$ and the dimension is a measure of the size of a space. Feb 12, 2015 at 18:22

Here is another simple answer. When you multiply a matrix and a vector $Ax$ you end up with a linear combination of the columns of $A$.

$$Ax = \; x_1\,A_1 \;+\; x_2\,A_2 \;+\; x_3\,A_3 \;+\;\; ...\;\; \\$$

When we multiply two matrices $AB = C$, we have $AB_i = C_i$, which means that each column of $C$ is a linear combination of the columns of $A$, so $\text{rank}(AB) \leq \text{rank}(A)$. To show that $\text{rank}(AB) \leq \text{rank}(B)$ we follow a similar argument -- when you multiply $x^{\top}B$, you end up with a linear combination of the rows of $B$.

Already you have proved $$rank(AB)\leq rank(B)$$

For other part

rank of $A=$ dim range $A$

As range $AB \subset$ range $A\implies$ dim range $AB\leq$ dim range $A$ . Hence $$rank(AB)\leq rank (A)$$

• Hello!! Why does it hold that "range AB $\subset$ range A" ? Jan 7, 2017 at 10:01
• If $x\in$ range $AB,$ then $x=(AB)y$ for some $y.$ Thus $x=A(By).$ Thus $x\in$ range $A.$@ Mary Star Jan 8, 2017 at 17:48

Let $m \le n, A \in M_{m\times n}, B\in M_{n\times m}$.

$\mbox{rank } A\le m$ and $\text{rank }B\le m$. (Obvious fact as rank A = dimension of the columnspace of A = dimension of the row space of A.)

Let $E_{n\times n}B$ be the row echelon form of $B$ and let $AE_{m\times m}$ be the column echelon form of $A$. ($E_{n\times n} ,E_{m\times m}$ are elementary matrices.)

We know $\operatorname{rank}(BA)=\operatorname{rank}(E_{n\times n}BA )=\operatorname{rank}(E_{n\times n}BAE_{m\times m} )$.

But $E_{n\times n}BAE_{m\times m} =\begin{pmatrix} L&0\\ 0&0\\ \end{pmatrix},$ where $L$ is an $k\times l$ matrix with $k\le \operatorname{rank}(B),l\le \operatorname{rank}(A)$.

So $\operatorname{rank}(E_{n\times n}BAE_{m\times m} )=\operatorname{rank}\begin{pmatrix} L&0\\ 0&0\\ \end{pmatrix}\le \min\{k,l\}\le \min\{\mbox{rank } A,\mbox{rank }B\}.$

Another way of showing that $\text{Rank} (AB) \leq \text{Rank}(B)$ without using rank-nullity: Note that if $v_1,\dots,v_n$ is a basis of $\text{Range} B$, then $Av_1,\dots,Av_n$ is a spanning list of $\text{Range} AB$.

Each column of $$AB$$ is a linear combination of columns of $$A$$ so $$\text{Range}(AB)\subseteq \text{Range} (A)$$ equivalently $$rank(AB)\leq rank(A).$$

Similarly, Each row of $$AB$$ is a linear combination of rows of $$B$$ so $$rowspace(AB)\subseteq rowspace(B)$$.

Since rowspace=columnspace. Thus $$rank(AB)\leq rank(B)$$.

From both of the inequality we deduce that $$rank(AB)\leq \min\{rank A, rank B\}$$.