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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
up vote 12 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|cite|improve this answer
2  
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}(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 $\operatorname{rank}(DC) \le \operatorname{rank}(C) \implies \operatorname{rank}(C^TD^T)\le \operatorname{rank} (C^T)$, which is $\operatorname{rank}(AB) \le \operatorname{rank}(A)$.

share|cite|improve this answer
    
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? – Ryles2014 Apr 12 at 3:27

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|cite|improve this answer
    
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
1  
@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 '15 at 18:22

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

share|cite|improve this answer

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

share|cite|improve this answer
1  
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$.

share|cite|improve this answer

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

share|cite|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 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?