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

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