25
$\begingroup$

Show $\operatorname{rank}(A) + \operatorname{rank}(B) \ge \operatorname{rank}(A+B)$, where $A,B \in M_{m\times n}(\mathbb{F})$.

I'm trying to think in terms of linear transformations.
We can define $T_a, T_b:\mathbb{F}^n\rightarrow \mathbb{F}^m$.
I know that $\dim_{\mathbb F}\operatorname{Im} T_a, \dim_{\mathbb F}\operatorname{Im} T_b \le m$.

What should I do next?

$\endgroup$
2

2 Answers 2

Reset to default
25
$\begingroup$

Hint: It suffices to prove that $C(A+B)\subseteq C(A)+C(B)$, because $$\begin{align} C(A+B)\subseteq C(A)+C(B) &\implies \dim \left(C(A+B)\right)\leq \dim \left(C(A)+C(B)\right)\\ &\implies \text{rank}(A+B) \leq \dim(C(A))+\dim(C(B))-\dim(C(A)\cap C(B)).\end{align}$$

$\endgroup$
12
  • $\begingroup$ Hmm.. the columns of $C(A+B)$ are linear combination of the columns of $C$. Is that what the hint leading to? $\endgroup$
    – AnnieOK
    Jun 29, 2014 at 20:32
  • $\begingroup$ @AnnieOK $C(X)$ denotes the column space (or range). $\endgroup$
    – Git Gud
    Jun 29, 2014 at 20:33
  • 6
    $\begingroup$ @AnnieOK That proves the inclusion, yes. But I'd rather do it like this: let $X\in C(A+B)$, then $X=(A+B)x$, for some $x$, thus $X=\underbrace{Ax}_{\in C(A)}+\underbrace{Bx}_{\in C(B)}$. $\endgroup$
    – Git Gud
    Jun 29, 2014 at 20:41
  • 4
    $\begingroup$ @gbox It's the definition of $C(M)$ for a $p\times q$ matrix $M$, more precisely $C(M):=\{Mx\colon x\in \mathbb R^{q\times 1}\}$. $\endgroup$
    – Git Gud
    Aug 20, 2014 at 20:55
  • 1
    $\begingroup$ Nice solution +1! $\endgroup$
    – RFZ
    Nov 25, 2019 at 3:07
7
$\begingroup$

How about this: Let $rk A: =a$ , $rk B:=b$. Now we can do Gaussian elimination on both, to end with two matrices $A'$, $B'$ with , respectively, $a$ and $b$ non-zero rows. But the sum $A'+B'$ will have at most max{a,b} nonzero rows. Then $a+b \geq$ Max{$a,b$}

$\endgroup$
6
  • $\begingroup$ I like this solution, though it somewhat technical/arithmetical. $\endgroup$
    – AnnieOK
    Jun 29, 2014 at 20:33
  • $\begingroup$ Thanks; do you want to suggest changes? $\endgroup$
    – user99680
    Jun 29, 2014 at 20:37
  • $\begingroup$ Oops.. auto-correct made it arithmetical. I meant "algorithmical" (If that's a word). The proof is $100$ percent fine, I just want to understand it through another perspective. $\endgroup$
    – AnnieOK
    Jun 29, 2014 at 20:42
  • $\begingroup$ But if you are doing Gaussian elimination on both of them independently, you can't really just add them like that in the end. You have $A'+B' = E_1 A E_1^{-1} + E_2 B E_2^{-1}$, which does not really say much about $A+B$. $\endgroup$
    – Ondrej Draganov
    Mar 25, 2019 at 18:53
  • $\begingroup$ $rank(A+B)$ is equal to $rank((A+B)')$, but not necessarily equal to $rank(A'+B')$ $\endgroup$
    – SOFe
    May 17, 2019 at 4:35

Not the answer you're looking for? Browse other questions tagged .