# 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

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. –  Marco Castronovo Jul 30 '10 at 8:52

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$.

-

Let $m < n, A \in M_{mxn}, B\in M_{nxm}$

$\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 $\text{rank }(BA)=\text{rank }(E_{n\times n}BA )=\text{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 rank (B),l\le rank(A)$.

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

-

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
+1 for generalisation, but there is some error in the formatting. Latex code is verbatim. –  mpiktas Jan 16 '11 at 19:07
@mkpiktas: thank's for noticing. This was to adapt to an earlier latex implementation on the site, but the fix was messing with the current one. –  Mariano Suárez-Alvarez Jan 16 '11 at 19:11
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
@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-Alvarez Feb 12 at 18:22

Once you have proved rank(AB) <= rank(B), 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 rank(DC) <= rank(C) implies rank(C^TD^T) <= rank (C^T), which is rank(AB) <= rank(A).

-
Very nice! Thank you. –  Marco Castronovo Sep 2 '10 at 10:01

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

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.