Subtracting a positive definite matrix from a diagonal matrix

Question

It is well-known that $$\mathrm{Diag}(x)- xx^\top \succeq 0 \iff x_i \geq 0,\ i=1,\ldots,n,\ \sum_{i=1}^nx_i \leq 1, $$ where $x \in \mathbb{R}^n$, and $\mathrm{Diag}(x)$ is the diagonal matrix whose $i$-th diagonal element is $x_i$.

Let us have another variable $y \in \mathbb{R}^n$ such that $x_i \geq y_i \geq 0$ for all $i=1,\ldots,n$. Obviously, if $y=x$, then we have $\mathrm{Diag}(y)- xx^\top \succeq 0$ by the equivalence above. My question is, can we say that for sure $\mathrm{Diag}(y) - xx^\top \not \succeq 0 $ if $y \neq x$?

As an attempt, I tried to see what happens when $n=2$. $\mathrm{Diag}(y) - xx^\top$ becomes: $$\begin{pmatrix} y_1 - x_1^2 & - x_1x_2 \\ -x_1x_2 & y_2 - x_2^2 \end{pmatrix}$$ so I should show that if $y_1 < x_1$ or $y_2 < x_2$, then assuming diagonal is non-negative, I should show: $$(y_1 - x_1^2)(y_2 - x_2^2) < (x_1x_2)^2.$$ I tried many ways, and I am unable to prove this.

Answer 1

This is not true. Suppose $x>0$ and $\sum_ix_i<1$. Then $\operatorname{diag}(x)-xx^T>0$ and hence $\operatorname{diag}(y)-xx^T>0$ when $y$ is slightly smaller than $x$.

Answer 2

Here is a characterization of when the matrix is positive semidefinite. Using the Schur complement, we find that $$ \operatorname{diag}(y) - xx^\top \succeq 0 \iff \pmatrix{\operatorname{diag}(y) & x\\x^\top & 1} \succeq 0 \iff 1 - x^\top\operatorname{diag}(y)^{-1} x \geq 0. $$ In particular, we find that $\operatorname{diag}(y) - xx^\top$ is positive definite if and only if $$ \sum_{i=1}^n \frac{x_i^2}{y_i} \leq 1. $$ In the case that $y = x$, this simplifies to your result.

As written, this proof only applies to the case where the entries of $y_i$ are positive. However, we can extend this by noting that the limit of positive semidefinite matrices is positive semidefinite.