Prove a rank equality for PSD matrices (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?
 A: 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$.
A: 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)
$$
