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?

Solution 1:

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

Solution 2:

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.

Solution 3:

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.