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?
Rank of the sum of two positive semi-definite matrices
4 Answers
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.
-
1Is $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\}$? – 2012-01-18
-
0Yes $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! – 2012-01-18
-
0Thanks 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$ – 2012-01-18
-
0I 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. – 2012-01-19
-
0thanks a lot for the clarification! – 2012-01-19
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)$
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.
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
-
0Can you explain what your first line means? The predicate seems incomplete... – 2012-12-06
-
0My question was about the fact in Davide's answer, once he proved the fact that X′+diag(\alfa_1,...,\alpha_r), hence invertible, he states that rank(X+Y)\geq r = rank(Y). I found out later that we can see the matrix X+Y as a block matrix, and prove the statement with the results present in the paper "Generalized Inverses and Ranks of Block Matrices" by Carl D. Meyer. Best regards. – 2012-12-16
-
0$\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$. – 2012-12-17