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

8 Answers 8

up vote 8 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
1  
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 at 12:10

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

If $f,g:V\to W$ are linear maps, then we have $$(f+g)(V)\subset f(V)+g(V),$$ which implies $$\mathrm{rk}(f+g)=\dim\ (f+g)(V)\le\dim\ (f(V)+g(V))$$ $$\le\dim f(V)+\dim g(V)=\mathrm{rk}(f)+\mathrm{rk}(g).$$ To justify the first display, note that a vector of $W$ is in $(f+g)(V)$ if and only if it is equal to $f(v)+g(v)$ for some $v$ in $V$, whereas it is in $f(V)+g(V)$ if and only if it is equal to $f(v)+g(v')$ for some $v$ and $v'$ in $V$.

share|improve this answer
    
Interesting. Now this is a high road, isn't it? :-D –  user1551 Aug 24 '11 at 16:49

An intuitive picture:

Use the following characterisation of the rank: decompose $A$ into its component column vectors. That is, $A = (a_1, a_2, \ldots, a_n)$, where each $a_i$ is a $m\times 1$ column vector. Then the rank of $A$ is equal to the dimensional of the vector subspace generated by $a_1, \ldots, a_n$.

A vector in the image of $A+B$ is going to be a linear combination of $a_1, \ldots, a_n$ and $b_1, \ldots, b_n$. So we have that the rank of $A+B$ is at most the size of the linear subspace generated by those $2n$ vectors.

But the size of that linear subspace is given by the maximum number of linearly independent vectors one can choose among them. We can choose at most $rank(A)$ many from the $a_i$, and at most $rank(B)$ many from the $b_i$. So this gives an upper bound of $rank(A)+rank(B)$.

share|improve this answer
    
How is $rank(A)+rank(B)$ the upper bound of the rank? The number of independent vectors are surely be less or equals to the number of columns in $(A+B)$. There is this feeling that when $A+B$, the numbers in them add together may be totally off from the original vector direction in $A$ and $B$. –  xenon Aug 24 '11 at 15:25
    
An over-generous upper bound is still an upper bound. Think of the case where $A$ is the projection onto the $x$ axis, and $B$ the projection onto the $y$ axis, then $rank(A+B) = 2 = 1 + 1 = rank(A) + rank(B)$. Of course you also have trivially that $rank(A+B) \leq \min(m,n)$ just by definition. So you could, if you want, combine the two estimates into $rank(A+B) \leq \min (m,n,rank(A)+rank(B))$. –  Willie Wong Aug 24 '11 at 15:35
    
ahh..Thanks a lot! :) –  xenon Aug 24 '11 at 15:57

Let the columns of $A$ and $B$ be $a_1, \ldots, a_n$ and $b_1, \ldots, b_n$ respectively. By definition, the rank of $A$ and $B$ are the dimensions of the linear spans $\langle a_1, \ldots, a_n\rangle$ and $\langle b_1, \ldots, b_n\rangle$. Now the rank of $A + B$ is the dimension of the linear span of the columns of $A + B$, i.e. the dimension of the linear span $\langle a_1 + b_1, \ldots, a_n + b_n\rangle$. Since $\langle a_1 + b_1, \ldots, a_n + b_n\rangle \subseteq \langle a_1, \ldots, a_n, b_1, \ldots, b_n\rangle$ the result follows.

Edit: Let me elaborate on the last statement. Any vector $v$ in $\langle a_1 + b_1, \ldots, a_n + b_n\rangle$ can be written as some linear combination $v = \lambda_1 (a_1 + b_1) + \ldots + \lambda_n (a_n + b_n)$ for some scalars $\lambda_i$. But then we can also write $v = \lambda_1 (a_1) + \ldots + \lambda_n (a_n) + \lambda_1 (b_1) + \ldots + \lambda_n (b_n)$. This implies that also $v \in \langle a_1, \ldots, a_n, b_1, \ldots, b_n\rangle$. We can do this for any vector $v$, so

$$\forall v \in \langle a_1 + b_1, \ldots, a_n + b_n\rangle: v \in \langle a_1, \ldots, a_n, b_1, \ldots, b_n\rangle$$

This is equivalent to saying $\langle a_1 + b_1, \ldots, a_n + b_n\rangle \subseteq \langle a_1, \ldots, a_n, b_1, \ldots, b_n\rangle$.

share|improve this answer
    
How is it that $\langle a_1 + b_1, \ldots, a_n + b_n\rangle \subseteq \langle a_1, \ldots, a_n, b_1, \ldots, b_n\rangle$? It feels like the $a_i + b_i$ may totally change the angle in the subspace and may not be of any multiple of $\langle a_1, \ldots, a_n, b_1, \ldots, b_n\rangle$ and not a subset. –  xenon Aug 24 '11 at 15:13
3  
@xEnOn: The span allows linear combinations. You may wish to review the definition of the linear span. –  Willie Wong Aug 24 '11 at 15:36
1  
+1. Nice answer! [But I slightly prefer the version before the edit: If $V$ is a vector space, and $v_1,...,v_m,w_1,...,w_n$ are vectors of $V$, then $\langle v_1,...,v_m\rangle\subset\langle w_1,...,w_n\rangle$ just means that each $v_i$ is a linear combination of the $w_j$. - It's not really necessary to mention the linear combinations of the $v_i$. (But that's a detail.)] –  Pierre-Yves Gaillard Aug 24 '11 at 18:01

It suffices to show that, Row rank $(A + B)$ ≤ Row rank $A + $Row rank $B$ $(see~here)$

i.e. to show $\dim <a_1 + b_1, a_2 + b_2, …, a_n + b_n>$$\leq \dim <a_1, a_2, … , a_n>$$+\dim <b_1, b_2,$$..., b_n>$ [Letting the row vectors of A and B as $a_1, a_2, … , a_n$ and $b_1, b_2,…, b_n$ respectively]

Let $\{A_1, A_2, …, A_p\}$ & $\{B_1, B_2, … , B_q\}$ be the bases of & respectively.

Case I: $p, q ≥ 1$ Choose $v\in<a_1 + b_1, a_2 + b_2, …, a_n + b_n>$ Then $v = c_1(a_1 + b_1) + … + c_n(a_n + b_n) [$for some scalars $c_i] = ∑c_i (∑g_jA_j) + ∑c_i(∑h_kB_k)$ [for some scalars $g_j, h_k$] i.e. $dim <a_1 + b_1, a_2 + b_2, …, a_n + b_n> \le p + q$. Hence etc.

Case II: $p = 0$ or $q = 0$: One of the bases is empty & the corresponding matrix becomes zero. Rest follows immediately.

share|improve this answer

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

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.