Proving the difference of two matrices is PSD

Question

Claim: For $x\in \mathbb{R}^n$, we have $\operatorname{Diag}(x) - xx^T \succeq 0$ if and only if $x_i \geq 0 \ \forall i\in [n]$ and $\sum_{i} x_i \leq 1$.

Where $\operatorname{Diag}$ denotes the diagonal matrix. How can I prove this?

I tried principal minor test (induction etc.), doesn't work well. Also, tried to decompose to the eigenvalues, not a nice spectral decomposition. My only hope is using the traditional definition: for every $a \in \mathbb{R}^n_{+}$, we have the following equivalence $a^TXa\geq0 \iff X\succeq0$.

When I follow the traditional definition, I come to:

$\sum_{i=1}^n \sum_{j=1}^n a_ia_j(-x_ix_j) + \sum_{i=1}^na_i^2x_i \geq 0$

but stuck again..

Answer 1

$(\Longrightarrow)$ Let $e_i$ be the $i^{th}$ standard basis vector. If $\def\D{\operatorname{Diag}(x)}\D-xx\def\t{^\top}\t\succeq0,$ then $$ e_i\t\D e_i-e_i\t x x\t e_i=x_i-x_i^2=x_i(1-x_i)\ge 0\implies 0\le x_i\le 1. $$ Furthermore, letting $\def\1{{\bf 1}}\1$ be the all ones vector, then $$ \1\t \D \1-\1\t xx\t \1=(\sum_i x_i)-(\sum_ix_i)^2\ge 0\implies 0\le \sum_i x_i\le 1. $$ $(\Longleftarrow)$ For any $a\in\mathbb R^n$, let $\def\a{\overline{a}}\a\in \mathbb R^n$ be the constant vector whose entries are all equal to $\sum_i x_ia_i=a\t x$. Then $$ \begin{align} 0&\le (a-\a)\t\D (a-\a) \\ &= a\t \D a-a\t\D \a -\a \t \D a\t+\a\t \D \a \\ &\stackrel{\star}= a\t \D a-\;\;\;\;\;(a\t x)^2\;\;\; -\;\;\;\;(a\t x)^2\;\;\;\;\;+(a\t x)^2\cdot(\textstyle\sum_i x_i) \\ &\le a\t \D a-\;\;\;\;\;(a\t x)^2\;\;\; -\;\;\;\;(a\t x)^2\;\;\;\;\;+(a\t x)^2 \\ &= a\t \D a-(a\t x)^2 \\ &= a\t \D a-a\t xx\t a \end{align} $$ The magic of the proof is hidden away in $\stackrel{\star}=$; take some time to convince yourself that step is correct.

Answer 2

You can use Schur complements, schur complement wikipedia. An example of the 2 dimensional case:

$$ \begin{align} Diag(x) - xx^T &\succeq0 \\ \begin{bmatrix} x_0-x_0^2 & -x_0x_1 \\ -x_0x_1 & x_1-x_1^2 \\ \end{bmatrix} = \begin{bmatrix} A & B \\ B^T & C \\ \end{bmatrix} & = X \succeq0 \end{align} $$

So from Schur's complement $A \succeq0$ then $X \succeq0 \iff C-B^TA^{-1}B \succeq0$

Solving $C-B^TA^{-1}B$ we get: $$\frac{(x_1x_0)(1-x_0-x_1)}{(x_0-x_0^2)}$$

From the above equation, $x_i \geq 0 \ \forall i\in [n]$ and $\sum_{i} x_i \leq 1$, we can see that: $(x_1x_0)$ and $(1-x_0-x_1)$ are greater than or equal to zero and that $(x_0-x_0^2)$ is greater than 0 but less than 1. This means that $C-B^TA^{-1}B \succeq0$ which means that $X \succeq0$.

Can you generalize this for the nxn case?