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

$$\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)$$

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

## 1 Answer

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
• See my latest edit – Omnomnomnom Sep 8 '16 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. – P. Camilleri Sep 8 '16 at 19:40
• I guess I can see why that could be confusing. You're welcome, at any rate. – Omnomnomnom Sep 8 '16 at 19:43