# 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)$ 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 to 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. – BBischof Jul 28 '10 at 16:08

## 8 Answers

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 '10 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 '10 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? – MathIsHard Apr 12 '16 at 3:27
• @MathisHard $x<y \wedge x<z \implies x<\min(y,z)$. – stillanoob May 25 '18 at 15:47

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... :-) – Kevin H. Lin Jul 29 '10 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 ? – nicolas Apr 13 '14 at 12:10
• So you're saying that rank of linear map is somehow like image of a function? – Mihail Feb 12 '15 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. – Mariano Suárez-Álvarez Feb 12 '15 at 18:22

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

Since Col(AB) ⊆ Col(A), any basis for Col(AB) can be extended to a basis for Col(A) and so dim Col(AB) ≤ dim Col(A), that is rank(AB) ≤ rank(A).

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

Since Null(B) ⊆ Null(AB), as above we have dim Null(B) ≤ dim Null(AB), that is, nullity(B) ≤ nullity(AB). Thus rank(AB) = n − nullity(AB) ≤ n − nullity(B) = rank(B).

• You should use MathJax to format your answer. – Michael Albanese Oct 15 '15 at 21:06

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" ? – Mary Star Jan 7 '17 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 – Black-horse Jan 8 '17 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$.

## protected by Alexander Gruber♦Jul 5 '13 at 16:16

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?