Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
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

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

share|improve this answer
    
Can you explain what your first line means? The predicate seems incomplete... –  Jonathan Christensen Dec 6 '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 1:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.