3
$\begingroup$

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?

4 Answers 4

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.

  • 0
    thanks a lot for the clarification!2012-01-19
4

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

1

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.

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

  • 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