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


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

  • $\begingroup$ 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? $\endgroup$ – independentvariable Mar 18 at 21:11
  • 2
    $\begingroup$ @independentvariable I'm not familiar with those, so I'm not schur if that is possible (haha!). $\endgroup$ – Mike Earnest Mar 18 at 21:13
  • $\begingroup$ The joke completed the proof :) haha $\endgroup$ – independentvariable Mar 18 at 21:15
  • $\begingroup$ How could you think about the $\bar{a}$ trick? $\endgroup$ – independentvariable Mar 18 at 23:17
  • 1
    $\begingroup$ @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$. $\endgroup$ – Mike Earnest Mar 18 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?

  • $\begingroup$ 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. $\endgroup$ – independentvariable Mar 18 at 19:43
  • $\begingroup$ Or mayne induction on schur complement can work.. i need to think more. $\endgroup$ – independentvariable Mar 18 at 19:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.