Is the rank of the sum of two positive semi-definite matrices larger than their individual ranks? How to prove $\operatorname{rank}(X+Y) \geq \min(\operatorname{rank}(X),\operatorname{rank}(Y))$, where $X$ and $Y$ are both positive semi-definite matrices?
 A: We assume that $Y$ is diagonal, $\operatorname{rank}(Y)=r$, so $Y=\operatorname{diag}(\alpha_1,\ldots,\alpha_r,0\ldots,0)$, for some $\alpha_i> 0$. Let $X'$ the matrix which has $r$ rows and $r$ column which are the same as the first $r$ rows and column of $X$. Then $X'+\operatorname{diag}(\alpha_1,\ldots,\alpha_r)$ is positive, hence invertible. So $\operatorname{rank}(X+Y)\geq r=\operatorname{rank}(Y)$, and by symmetry, as @Joriki pointed out, $\operatorname{rank}(X+Y)\geq\operatorname{rank}(X)$, so in fact $\operatorname{rank}(X+Y)\geq\max\left\{ \operatorname{rank}(X),\operatorname{rank}(Y)\right\}$.
Now in general we can find an orthogonal matrix $P$ such that $^tP YP=\operatorname{diag}(\alpha_1,\ldots,\alpha_r,0\ldots,0)$. The rank of $X+Y$ is the same as the rank of $^tP(X+Y)P=^tPXP+\operatorname{diag}(\alpha_1,\ldots,\alpha_r,0\ldots,0)$ since we multiply by invertible matrices. $^tPXP$ is still positive semi-definite, so the result follows.
A: Since $X$ and $Y$ are positive semi-definite, they can be decomposed as follows:
$$X = P'P, \quad Y = Q'Q.$$
(for example, take $P = X^{1/2}$), therefore
$$X + Y = P'P + Q'Q = (P', Q')\begin{pmatrix}P \\ Q\end{pmatrix}.$$
Use the fact that $\text{rank}(A) = \text{rank}(A'A)$ for any squared matrix, and the rank of a sub-matrix of any matrix cannot be greater than that matrix, the result follows.
A: This answer does not involve any decompositions. 
Let $N(X)$ be the null space of $X$. For any $v\in N(X+Y)$, we have $$v^T(X+Y)v=0\Leftrightarrow v^TXv=0,v^TYv=0$$
Consequently, $v\in N(X)$ and $v\in N(Y)$ and hence
$$N(X+Y)=N(X)\cap N(Y)$$
Then,
\begin{align}
rank(X+Y)
&=n-dim(N(X+Y))\\
&=n-dim(N(X)\cap N(Y))\\
&\ge n-dim(N(X))\\
&=rank(X)
\end{align}
Similarly, it can be shown $rank(X+Y)\ge rank(Y)$
A: How can you briefly prove that if $\mathbf X'+\operatorname{diag}(\alpha_1,...,\alpha_r)$ then $\operatorname{rank}(X+Y)\geq r$ ? You still have to take into account the off diagonal elements of $X + Y$ when considering the rank of that matrix.
Thank you in advance.
Hugo
