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

• Commented Apr 22, 2017 at 9:35

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. Commented Aug 24, 2011 at 15:13
• @xEnOn: The span allows linear combinations. You may wish to review the definition of the linear span. Commented Aug 24, 2011 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.)] Commented Aug 24, 2011 at 18:01
• This answer is missing a key detail, namely that the rank of $\langle a_1,\ldots,a_n,b_1,\ldots,b_n\rangle$ is the rank of $A$ + the rank of $B$, or at least that the latter is an upper bound (it's obvious: it's freely generated on the basis, but this is essentially the contribution of Willie Wong's answer) Commented Jun 1 at 9:08
• This is a rather important fact to observe, since we could simply take $A = B = [1]$ in which case $\langle a_1, b_1\rangle = \langle 1,1\rangle = \mathbb R$ which has rank $1$, while the sum of ranks of $A$ and $B$ is $2$. You otherwise need to argue the notation $\langle \cdot \rangle$ be used in the sense of a finite presentation, where each element is viewed as being distinct even if given the same name (i.e. where we take the disjoint union of the generating set) Commented Jun 1 at 9:13

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 Commented Aug 24, 2011 at 16:49
• $dim(f(V)+g(V))$ is not defined as the sum of $f(V)+g(V)$ need not be a vector space.
– Debu
Commented May 2 at 12:44
• I think $f(V)+g(V)$ is a vector space. Commented May 2 at 12: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$. Commented Aug 24, 2011 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))$. Commented Aug 24, 2011 at 15:35
• ahh..Thanks a lot! :) Commented Aug 24, 2011 at 15:57

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

i.e. to show $\dim \langle a_1 + b_1, a_2 + b_2, …, a_n + b_n\rangle \leq \dim \langle a_1, a_2, … , a_n\rangle+\dim \langle b_1, b_2,..., b_n\rangle$ [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 $\langle a_1, a_2, … , a_n\rangle$ and $\langle b_1, b_2,…, b_n\rangle$ respectively.

Case I: $p, q ≥ 1$ Choose $v\in\langle a_1 + b_1, a_2 + b_2, …, a_n + b_n\rangle$ 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 \langle a_1 + b_1, a_2 + b_2, …, a_n + b_n \rangle \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.

$$\newcommand{\rank}{{\rm rank}\;{}}$$We already have some very good answers to this question, but I would like to add one more using an approach based on partitioned matrices. For a partitioned matrix $$M = \begin{bmatrix}A&B \\ C&D\end{bmatrix},$$ let us define the invertible operations $${\sf rowSwap}(M) = \begin{bmatrix}C&D \\ A&B\end{bmatrix},$$ and $${\sf rowSynth}_{X}(M) {}={} \begin{bmatrix} A & B \\ C + XA & D+XB \end{bmatrix}.$$ It is easy to see that $${\sf rowSwap}^{-1} = {\sf rowSwap}$$ and $${\sf rowSynth}_{X}^{-1} = {\sf rowSynth}_{-X}$$. These operations do not affect the rank of the original matrix.

Now, we start with the observation that $$\rank \begin{bmatrix}A & 0 \\ B & B\end{bmatrix} = \rank A + \rank B.$$ Then, by applying the above elementary operations $$\begin{bmatrix}A & 0 \\ B & B\end{bmatrix} \overset{{\sf rowSwap}}{\longrightarrow} \begin{bmatrix}B & B \\ A & 0\end{bmatrix} \overset{{\sf rowSynth}_{I}}{\longrightarrow} \begin{bmatrix}B & B \\ A+B & B\end{bmatrix},$$ and \begin{aligned} \rank A + \rank B {}={}& \rank \begin{bmatrix}A & 0 \\ B & B\end{bmatrix} \\ {}={}& \rank \begin{bmatrix}B & B \\ A+B & B\end{bmatrix} \\ {}\geq{}& \rank \begin{bmatrix}A+B & B\end{bmatrix} \\ {}\geq{}& \rank(A+B). \end{aligned}

There's also a proof based on the rank-nullity theorem. Let $$n_1$$ be the dimension of the nullspace $$N(A)$$ of $$A$$ and $$n_2$$ the dimension of the nullspace $$N(B)$$ of $$B$$. Let $$n_3$$ be the dimension of the nullspace of $$A+B$$.

Since $$N(A) \cap N(B) \subset N(A+B)$$, we have $$n_1+n_2 - \text{dim}(N(A)+N(B)) \le n_3$$. So $$-n_3 \le -n_1 - n_2 + \text{dim}(N(A)+N(B)) \le -n_1-n_2+n$$. Therefore, $$n-n_3 \le n-n_1 +n-n_2$$, and so by the Rank-Nullity Theorem, $$\text{rank}(A+B) \le \text{rank}(A) + \text{rank}(B)$$.