# Rank of the sum of two positive semi-definite matrices

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?

-

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.

-
Is $A$ supposed to be $X$? And wouldn't this also work the other way around, thus showing that $\operatorname{rank}(X+Y)\geq \max \left\{\operatorname{rank}(X),\operatorname{rank}(Y)\right\}$? – joriki Jan 18 '12 at 20:38
Yes $A$ was in fact $X$. In fact, since I actually didn't use the fact that $r\leq \operatorname{rank}(X)$, and what I did shows that the rank of $X+Y$ is greater than the rank of $Y$, so indeed we have the more accurate inequality. Thanks! – Davide Giraudo Jan 18 '12 at 20:41
Thanks a lot. But how do you link the general case to this special case you assume, i.e., $Y$ is diagonal? And why rank($X$) $\geq r$ – mining Jan 18 '12 at 22:01
I have added further details. I didn't say that the rank of $X$ is $\geq r$, since it's not true in general, but denoting $X'=(x_{i,j})_{1\leq i,j\leq r}$, the matrix $X'+Y$ is a matrix of size $r$ which is invertible. – Davide Giraudo Jan 19 '12 at 10:23
thanks a lot for the clarification! – mining Jan 19 '12 at 19:04

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.

$\mathbf X'$ and $\operatorname{diag}(\alpha_1,\dots,\alpha_r)$ are both positive definite, so their sum is also positive definite (this is easy to prove from the definition of positive definite). Thus the sum is invertible, and so must be full rank. The dimension of that matrix is $r \times r$, so for it to be full-rank it must have rank $r$. – Jonathan Christensen Dec 17 '12 at 1:34
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.