# 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 Commented Sep 8, 2016 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? Commented Sep 8, 2016 at 18:14
• The book has two authors. Commented Mar 14, 2021 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 Commented Sep 8, 2016 at 18:19
• See my latest edit Commented Sep 8, 2016 at 19:07
• 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. Commented Sep 8, 2016 at 19:40
• I guess I can see why that could be confusing. You're welcome, at any rate. Commented Sep 8, 2016 at 19:43