2
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ $\dim\ker A + \rank A = $ dimension of the space $\endgroup$
    – user251257
    Commented Sep 8, 2016 at 16:23
  • $\begingroup$ 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? $\endgroup$ Commented Sep 8, 2016 at 18:14
  • $\begingroup$ The book has two authors. $\endgroup$ Commented Mar 14, 2021 at 4:36

1 Answer 1

1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$ Commented Sep 8, 2016 at 18:19
  • $\begingroup$ See my latest edit $\endgroup$ Commented Sep 8, 2016 at 19:07
  • $\begingroup$ 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. $\endgroup$ Commented Sep 8, 2016 at 19:40
  • $\begingroup$ I guess I can see why that could be confusing. You're welcome, at any rate. $\endgroup$ Commented Sep 8, 2016 at 19:43

You must log in to answer this question.

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