# Show that $\operatorname{rank}(A+B) \leq \operatorname{rank}(A) + \operatorname{rank}(B)$

I know about the fact that $\operatorname{rank}(A+B) \leq \operatorname{rank}(A) + \operatorname{rank}(B)$, where $A$ and $B$ are $m \times n$ matrices.

But somehow, I don't find this as intuitive as the multiplication version of this fact. The rank of $A$ plus the rank of $B$ could have well more than the columns of $(A+B)$! How can I show to prove that this really is true?

-

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
Thanks Pierre-Yves. Yes, of course that would do too, but then you implicitly use a (trivial) property of linear spans, while the edit only uses the definition of the linear span and nothing more. I guess it's just a matter of taste. – TMM Aug 25 '11 at 14:09

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