Prove a rank equality for PSD matrices

Question

(To make things a bit easier perhaps, we assume that $A,B$ are symmetric at least. If you find out that this assumption can be dropped, please also give your stronger version of course.)

Prove that: $B$ is PSD (positive semi-definite) iff for any $A$ PSD we have $$r(A+B)=r([A |B])$$ where $r$ denotes the matrix rank and $|$ denotes matrix concatenation.

This might be one of the few times that I haven't had any clue to the problem I'm asking on this site.

Any help?

Answer 1

I assume that both $A$ and $B$ are symmetric.

For one direction: suppose that $A$ is positive semidefinite. Then the kernel of $A$ is spanned by the $x$ satisfying $x^TAx = 0$. Conclude that $\ker(A + B) = \ker(A) \cap \ker(B)$. Similarly, note that $$ \operatorname{rank}\pmatrix{A & B} = \operatorname{rank}\pmatrix{A & B}^T = \operatorname{rank}\pmatrix{A\\B} $$ and $$ \pmatrix{A\\B}x = \pmatrix{Ax\\Bx} \implies \ker \pmatrix{A\\B} = \ker(A) \cap \ker(B) $$ Conversely, suppose that $A$ is symmetric but not positive semidefinite. Let $x$ be a unit eigenvector of $B$ associated with a negative eigenvalue, $- \mu$. If we take $B = \mu xx^T$, then we find that $$ \operatorname{rank}(A + B) = \operatorname{rank}(A) - 1\\ \operatorname{rank}(A\mid B) = \operatorname{rank}(A) $$

Answer 2

Was typing this up when Omnomnomnom beat me to the punch :(

---

$B$ PSD $\implies$ $r(A+B) = r([A \mid B])$ for all PSD $A$:

The image of $[A \mid B]$ is simply $\text{im}(A) + \text{im}(B)$. Thus it suffices to prove that $B$ being PSD implies $\text{im}(A+B) = \text{im}(A) + \text{im}(B)$. The inclusion $\subseteq$ always holds, so we only need to show the reverse inclusion $\supseteq$, which further reduces to showing $\text{im}(A) \subseteq \text{im}(A+B)$ and $\text{im}(B) \subseteq \text{im}(A+B)$.

Note $\ker(A+B) \subseteq \ker(A)$ because $v \in \ker(A+B)$ implies $$0 = v^\top (A+B) v = v^\top A v + v^\top B v \ge v^\top A v \ge 0$$ due to PSD-ness of $A$ and $B$. By symmetry of $A$, $\text{im}(A) = \ker(A)^\perp \subseteq \ker(A+B)^\perp = \text{im}(A+B)$. An identical argument implies $\text{im}(B) \subseteq \text{im}(A+B)$.

---

$B$ not PSD $\implies$ there exists PSD $A$ such that $r(A+B) \ne r([A \mid B])$:

If $B$ is symmetric and not PSD, there exists an eigenvector $v$ of $B$ associated with a negative eigenvalue $\lambda < 0$. Let $A = -\lambda vv^\top$ then $\text{im}(A+B) = \text{im}(B)$ while $\text{im}(A+B)$ is the span of all eigenvectors associated with nonzero eigenvalues of $B$ that are orthogonal to $v$. Thus $r(A+B) = r(B)$ while $r(A+B) = r(B) - 1$.