Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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

5 Answers 5

up vote 10 down vote accepted

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.

share|improve this answer
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

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.

share|improve this answer
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).

share|improve this answer
Very nice! Thank you. –  Marco Castronovo Sep 2 '10 at 10:01

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\}$

share|improve this answer

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

share|improve this answer

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.

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.