Help with proof: $\mathrm{rank}(A+B) \le \mathrm{rank}(A) + \mathrm{rank}(B)$

Question

The question is:

If $A,B$ are any $m\times n$ matrices, prove that $\mathrm{rank}(A+B) \le \mathrm{rank}(A) + \mathrm{rank}(B)$.
($\mathrm{rank}(A)$ is the dimension of the column space of $A$, i.e., the dimension of the subspace of $\mathbb R^m$ spanned by the columns of $A$)

Here is my proof of it. I don't know if it is correct at all, I sort of went on a whim. If it's only slightly flawed could you help tell me what mistakes I have made and if it is completely wrong, any suggestions on how I can go about proving this?

Let $\mathrm{rank}(A) = k$ so that some vectors $\{v_1,\ldots,v_k\}$ form a basis for the column space of $A$.
Let $\mathrm{rank}(B) = r$ where $r\geq k$. By the Basis Theorem, the l.i. set of vectors $\{v_1,...v_k\}$ can be extended to form a basis for the column space of $B$ so that the vectors $\{u_1,\ldots,u_r\}$ with $u_i = v_i$ for each $i=1,...,k$ form a basis for the column space of $B$.

Thus the $j$-th column of $A$, $\alpha_j$ can be written as a linear combination of $\{v_1,\ldots,v_k\}$ and the $j$-th column of $B$, $\beta_j$ can be written as a linear combination of $\{u_1,\ldots,u_r\}$ with $u_i = v_i$ for each $i=1,\ldots,k$.
Hence: $$ \begin{align*} \alpha_j & = a_1v_1 + \ldots + a_kv_k \\ \beta_j & = b_1u_1 + \ldots + b_ru_r \\ & = b_1v_1 + \ldots +b_kv_k + b_{k+1}u_{k+1} + \ldots +b_ru_r \end{align*} $$

If we let $C=A+B$, the the $j$-th column of $C$, $\gamma_j$ is equal to $\alpha_j + \beta_j$ and thus $$ \begin{align*} \gamma_j & = \alpha_j + \beta_j\\ & = a_1v_1 + \ldots + a_kv_k + b_1v_1 + \ldots +b_kv_k + b_{k+1}u_{k+1} + \ldots + b_ru_r\\ & = (a_1+b_1)v_1 + \ldots + (a_k+b_k)v_k + b_{k+1}u_{k+1} + \ldots + b_ru_r \end{align*} $$

Since every column of $C$ is a linear combination of $\{u_1,\ldots,u_r\}$ with $u_i = v_i$ for each $i=1,\ldots ,k$ and $\{u_1,\ldots,u_r\}$ by definition is linearly independent, then it forms a basis for the column space of $C$, and thus the rank of $C =A+B$ is $r$.

Therefore

$$ \mathrm{rank}(A+B) = r\\ \mathrm{rank}(A) + \mathrm{rank}(B) = k + r $$

Thus $$\mathrm{rank}(A+B) \le \mathrm{rank}(A) + \mathrm{rank}(B) $$

QED.

Answer 1

The assumption $u_i = v_i$ for $1\le i\le k$ is plain wrong. A counter-example is trivially $A = e_1, B = e_2$ with $m=2, n=1$ (i.e. $\{A,B\}$ is the canonical basis of $\mathbb R^2$).
For a correct solution, you can simply observe that the column span of $A+B$ is a subset of $$\langle v_i \mid 1\le i\le \mathrm{rank}(A)\rangle + \langle u_i \mid 1\le i\le \mathrm{rank}(B)\rangle$$ wich has dimension at most $\mathrm{rank}(A) + \mathrm{rank}(B)$ (iff the sum is direct).

This observation is basically what you make in the first half of your proof (where you introduce $\gamma_j$). The rest of the proof is faulty for the reason outlined above.

Answer 2

The key idea is to think of $m\times n$ matrices as linear transformations $\mathbb{R}^n\rightarrow\mathbb{R}^m$, and to note that the rank of a matrix is precisely the dimension of its image in $\mathbb{R}^m$.

Thus, for two matrices $A,B : \mathbb{R}^n\rightarrow\mathbb{R}^m$, let $V$ be the subspace of $\mathbb{R}^m$ spanned by the images of $A$ and $B$. If the image of $A$ has basis $a_1,\ldots,a_r$ and the image of $B$ has basis $b_1,\ldots,b_s$ (so that $rank(A) = r, rank(B) = s$), then $V$ clearly is spanned by $a_1,\ldots,a_r,b_1,\ldots,b_s$, so $V$ has dimension at most $r + s = rank(A) + rank(B)$.

Note that for any vector $v\in\mathbb{R}^n$, $(A+B)(v) = Av + Bv$, and so the image of $A+B$ is contained in $V$, thus the image of $A+B$ has dimension at most $rank(A) + rank(B)$.

Thus, $rank(A+B)\le rank(A) + rank(B)$.

Answer 3

That is because $\operatorname{rank}A=\dim\operatorname{Im}(A)$, so $$\operatorname{rank}(A+B)=\dim\operatorname{Im}(A+B)$$ On another hand, there is a surjection: $\:\begin{aligned}[t]\operatorname{Im}A\oplus \operatorname{Im}B&\to \operatorname{Im}A+\operatorname{Im}B\\ (x,y)&\mapsto x+y \end{aligned}$, and $\operatorname{Im}(A+B)\subset \operatorname{Im}A+\operatorname{Im}B$, so \begin{align*}\operatorname{rank}(A+B)=\dim\operatorname{Im}(A+B)&\le\dim(\operatorname{Im}A+\operatorname{Im}B) \\&\le\dim\operatorname{Im}A+\dim\operatorname{Im}B=\operatorname{rank}A +\operatorname{rank}B.\end{align*}