6

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?

glS
  • 6,818
mining
  • 1,075

4 Answers4

14

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

Shiyu
  • 5,228
4

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.

Davide Giraudo
  • 172,925
  • 1
    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
2

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.

Zhanxiong
  • 14,040
0

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

Jonathan Christensen
  • 3,870
  • 15
  • 21
Hugo
  • 1
  • Can you explain what your first line means? The predicate seems incomplete... – Jonathan Christensen Dec 06 '12 at 19:40
  • My 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. – Hugo Dec 16 '12 at 17:28
  • $\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 01:34