Proving the difference of two matrices with similar properties is psd

Question

I have a vector $w \in \mathbb{R}^n$ and a symmetric matrix $V \in \mathbb{S}^{n}$.

I have the following properties:

• $w_i \geq 0$ for all $i=1,\ldots,n$
• $\sum \limits_{i=1}^n w_i = 1$
• $V_{i,j} \geq 0$ for all $i=1,\ldots,n, \ j =1,\ldots,n$
• $V_{i,1} + V_{i,2} + \ldots, V_{i,n} =V_{1,i} + V_{2,i} + \ldots, V_{n,i} = w_i$ for all $i=1,\ldots,n$
• $\sum_{i,j} V_{i,j} = 1$

In other words, the elements of $w$ are non-negative, so are the elements of $V$. Moreover the elements of $w$ and $V$ both sum to $1$. Finally, the $i$-th row and $i$-th column of $V$ sum to $w_i$.

I know that $V - ww^\top \succeq 0$, i.e., the difference is positive semi-definite. I know this because of my numerical experiments, but I need theoretical proof.

Answer 1

Let $V=\begin{bmatrix} p & q \\ q & p \end{bmatrix}$ and $w=(\frac12, \frac12)^T$.

$V-ww^T=\begin{bmatrix} p-\frac14 & q-\frac14 \\ q - \frac14& p-\frac14\end{bmatrix}$

Let $p=0, q=\frac12$, and we found that the difference is not positive semi-definite.

octave:3> A= [0 , 0.5; 0.5, 0]-[0.5; 0.5]*[0.5, 0.5]
A =

  -0.25000   0.25000
   0.25000  -0.25000

octave:4> eig(A)
ans =

  -0.50000
   0.00000