Proving the difference of two matrices is PSD

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

$$\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..

$$(\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.

• That is a very nice proof. Thank you for the effort. Just for curiosity: do you think we can also do it with induction on schur complements? Or is it harder? Mar 18 '19 at 21:11
• @independentvariable I'm not familiar with those, so I'm not schur if that is possible (haha!). Mar 18 '19 at 21:13
• The joke completed the proof :) haha Mar 18 '19 at 21:15
• How could you think about the $\bar{a}$ trick? Mar 18 '19 at 23:17
• @independentvariable The condition $x_i\ge 0$ and $\sum_i \le x_i$ made me think of probability distributions. In that viewpoint, $a^Tx$ is the expected value of $a_i$, when the probability $a_i$ is chosen is proportional to $x_i$, and $a^T\text{diag}(x)a$ is the expected value of $a_i^2$, so the inequality follows from $E[a^2]\ge E[a]^2$. Mar 18 '19 at 23:24

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?

• Actually I was using schur complement and obtained the final form of what I asked. I don't think your answer can be generalized. Do you think for $n$ dimension you can generalize this? $A$ and $C$ matrices will not be as easy as this case to select. Mar 18 '19 at 19:43
• Or mayne induction on schur complement can work.. i need to think more. Mar 18 '19 at 19:53