# Sum of rank-$k$ positive semidefinite matrices is at least of rank $k$

I am working on the proof of the title statement. I have the following proof, $$A$$ and $$B$$ being those matrices:

\begin{aligned} \mathrm{Ker}(A + B) &= \{X \,\mid \,X^T(A + B)X = 0 \} \\ &= \{X \,\mid \,X^TAX = 0 \} \cap \{X \,\mid \,X^TBX = 0 \} \\ &= \mathrm{Ker}(A) \cap \mathrm{Ker}(B)\end{aligned}

Where I have used the fact that for semi definite positive matrices, $$\mathrm{Ker} \, A = \{X \,/ \,X^TAX = 0 \}$$. Then using rank theorem and dim $$A \cap B \leq$$ min (dim $$A$$, dim $$B$$) gives rank $$(A + B)$$ $$\geq k$$.

However looking at the correction (this is problem 2.13 from Boyd's Convex Optimization), the author, assuming rank $$(A +B) = r < k$$ defines $$V$$ s.t. $$\mathrm{Im} \, V = \mathrm{Ker} (A +B)$$ with $$V \in \mathcal{M}_{n ,n-r}(\mathbb{R})$$. Saying that $$V^T(A+B)V = V^TAV + V^TBV = 0$$, hence by positive semidefinitiveness of $$A$$ and $$B$$, $$V^TAV = V^TBV =0$$, he claims that this implies that both rank of $$A$$ and rank of $$B$$ are less than $$r$$.

I cannot understand the reason behind this last claim, can someone explain it?

• $\dim\ker A + \rank A =$ dimension of the space – user251257 Sep 8 '16 at 16:23
• I have used rank theorem in my alternate proof but do not see where the author uses it. A more detailed explanation would be welcome: to which matrix do you apply it, how do you get the value of one of the terms on the left side? – P. Camilleri Sep 8 '16 at 18:14
• The book has two authors. – Rodrigo de Azevedo Mar 14 at 4:36

Note that $V^TAV = V^TBV = 0$ implies that the kernels of $A$ and $B$ each has dimension at least $n-r$. By the rank-nullity theorem, this implies that the rank of $A$ and $B$ are at most $r$.
To see that the kernels have dimension at least $n-r$, note that for any vector $x \in \Bbb R^{n-r}$ we have $(Vx)^TA(Vx) = x^T V^T A V x = 0$, hence $A(Vx) = 0$.
In other words, the kernel of $A$ (and the kernel of $B$) contain the image of $V$, which is to say that the kernels of $A$ and $B$ each contain the kernel of $(A + B)$ (a space of dimension $n - r$).
• Why does does it imply that the kernels are of dim at least $n-r$? I suppose you show that they contain a subspace of such dimension, but I am stuck with $V^T$ on the left side and cannot isolate $A$. The only thing I have is Im $AV \subset$ Ker $V^T$. Also the second occurrence of "kernel" in your answer looks like a typo – P. Camilleri Sep 8 '16 at 18:19
• Thanks, I get it. But I think your $\Rightarrow$ should be a hence : the left side is always true, so the right side is true. As you worded it, it means that when the left side is true, so is the right side. – P. Camilleri Sep 8 '16 at 19:40