# 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

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

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

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

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

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 at 12:10

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

-
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

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

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.

-

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

-

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