An Easy Looking Positive Semidefinite Matrices Implication

I'm reading the article "Controlling the false discovery rate via knockoffs" by Candes and Barber (https://arxiv.org/abs/1404.5609) and faced the following problem that I couldn't handle.

We have $X\in\mathbb{R}^{n\times p}$ with rank $p$.

We define $\Sigma:=X^TX$

We have a vector $s\in \mathbb{R}^p$ with non-negative entries and $diag(s)$ is defined as the $p\times p$ matrix with diagonal entries $s$, zero otherwise.

As I've understood from the beginning of the page 9 in the article, the authors claim that:

\begin{equation} 2\Sigma \succeq \text{diag}(s) \iff 2\text{diag}(s)-\text{diag}(s)\Sigma^{-1}\text{diag}(s)\succeq 0 \end{equation}

(From $X \succeq Y$, I understand that $X-Y$ is positive semidefinite)

I have shown the $2\text{diag}(s)-\text{diag}(s)\Sigma^{-1}\text{diag}(s)\succeq 0 \implies 2\Sigma \succeq \text{diag}(s)$ as follows:

$\Sigma$ is symmetric positive definite. So, we can say, for any coordinate $i\in\{1,2,\dots,p\}$, $\Sigma_{ii}(\Sigma^{-1})_{ii}\geq 1$.

What we have is equivalent to having $e_i^T(2\text{diag}(s)-\text{diag}(s)\Sigma^{-1}\text{diag}(s))e_i\geq0$ for every $i$.

So, we have $2s_i-s_i^2(\Sigma^{-1})_{ii}\geq 0$.

Using $\Sigma_{ii}(\Sigma^{-1})_{ii}\geq 1$, we obtain $2\Sigma_{ii}-s_i\geq 0$ for all $i$. So we can conclude $2\Sigma \succeq \text{diag}(s)$.

But I cannot do the same for the converse, and couldn't figure it out.

I would be glad for any idea. It looks like there could be a counterexample. I feel like I may misunderstood the article.


Let $M=\pmatrix{A&B\\ B^T&D}$ be any real symmetric matrix. When $D$ is invertible, $M$ is congruent to $(M/D)\oplus D$, where $M/D=A-BD^{-1}B^T$ is called the Schur complement of $D$ in $M$.

In particular, when $A=B=S=\operatorname{diag}(s)$ and $D=2\Sigma$, we have $$ M=\pmatrix{S&S\\ S&D}\cong(M/D)\oplus D=(S-SD^{-1}S)\oplus D, $$ where the symbol $\cong$ denotes matrix congruence.

Now, if $D\succeq S$, then $M\succeq\pmatrix{S&S\\ S&S}\succeq0$. Hence $(M/D)\oplus D\succeq0$ and in turn $M/D\succeq0$.

Conversely, if $M/D\succeq0$, then $M\cong(M/D)\oplus D\succeq0$. Therefore $$ D-S=\pmatrix{-I&I}M\pmatrix{-I\\ I}\succeq0. $$


easy case:
all components of $s$ are positive.
$2\cdot\Sigma \succeq \text{diag}(s) \iff \text{diag}(s)^\frac{-1}{2}\cdot\Sigma\cdot\text{diag}(s)^\frac{-1}{2} \succeq \frac{1}{2}I $
via congruence transform (multiply on left and right by $\frac{1}{\sqrt{2}}\text{diag}(s)^\frac{-1}{2}$ on each side)

the RHS reads: we have a real symmetric PD matrix, all of whose eigenvalues are at least $\frac{1}{2}$. We know the inverse will have all eigenvalues being positive but at most $2$ i.e.
$\iff \text{diag}(s)^\frac{1}{2}\cdot\Sigma^{-1}\cdot\text{diag}(s)^\frac{1}{2} \preceq 2I \iff \text{diag}(s)\cdot\Sigma^{-1}\cdot\text{diag}(s) \preceq 2\cdot \text{diag}(s)$
where the RHS follows again by congruence. And this is your claim.

general case:
The general non-negative result then follows by continuity. I.e. do this sequentially: with $\Sigma_k := \Sigma + \frac{1}{2k}I$ and $\text{diag}(s_k):=\text{diag}(s) +\frac{1}{k}I$ for $k\in \mathbb N$. Then by addition we have

$2\cdot\Sigma \succeq \text{diag}(s)\iff 2\cdot\Sigma_k \succeq \text{diag}(s_k)\iff 0\preceq 2\cdot \text{diag}(s_k)-\text{diag}(s_k)\cdot\Sigma_k^{-1}\cdot\text{diag}(s_k) $
where the RHS follows by the easy case since $\text{diag}(s_k)$ is invertible. This holds for all $k$,
so take the limit of the sequence, and by topological continuity of eigenvalues we recover $0\preceq 2\cdot \text{diag}(s)-\text{diag}(s)\cdot\Sigma^{-1}\cdot\text{diag}(s) $

open item:
conversely if you start with $0\preceq 2\cdot \text{diag}(s)-\text{diag}(s)\cdot\Sigma^{-1}\cdot\text{diag}(s) $ you should be able to run another sequential argument, though I am not seeing it currently. The original post says this direction, i.e. $2\text{diag}(s)-\text{diag}(s)\Sigma^{-1}\text{diag}(s)\succeq 0 \implies 2\Sigma \succeq \text{diag}(s)$ has already been proven, though on second look, I don't think that proof works.