# $k\sum v_i v_i^T-\big(\sum v_i\big)\big(\sum v_i^T\big)\succeq 0$

My professor claimed that $$k\sum_{i=1}^k v_i v_i^T-\Big(\sum_{i=1}^k v_i\Big)\Big(\sum_{i=1}^k v_i^T\Big)\succeq 0,$$ holds for any family of vectors $$\{v_1,\dots,v_k\}$$, and can be shown using the Cauchy Schwarz inequality on the quadratic form.

I'm unsure whether it's necessary assume: $$k$$ is a positive integer, and $$v_i$$ are vectors of ones and zeros such that $$\sum_{i=1}^k v_i=\vec{1}$$. I don't think need to assume this due to the claim that it holds for any family of vectors.

In trying to prove that the above is positive semidefinite, I get the quadratic form \begin{align} k\sum_{i=1}^k x^T v_i v_i^T x-x^T \Big(\sum_{i=1}^k v_i\Big)\Big(\sum_{i=1}^k v_i^T \Big)x &= k\sum_{i=1}^k x^T v_i v_i^T x-|\langle \sum_{i=1}^k v_i, x\rangle|^2\\ &\geq k\sum_{i=1}^k x^T v_i v_i^T x-\|x\|^2 \bigg\|\sum_{i=1}^k v_i\bigg\|^2\\ &\equiv k\sum_{i=1}^k x^T v_i v_i^T x-x^Tx n\\ &= x^T\big(k\sum_{i=1}^k v_i v_i^T-n\mathbb{I}\big)x\\ \end{align} where $$n\geq k$$. I do not think this matrix in the parentheses is positive semidefinite, since its diagonals are negative. Can someone help me prove the claim of my professor?

I guess that the vectors are row vectors of an $$\mathbb{R}^n$$. If the vectors are column vectors, take transposes of the difference and then follow the proof below, to prove that this transpose is positive semi-definite. Then, since $$A$$ is positive semidefinite if-f $$A^{T}$$ is, the desired result follows in the case of column vectors too. In the case of row vectors the inequality is equivalent to proving that

$$k\sum_{i=1}^k||u_i||^2\geq \left|\left|\sum_{i=1}^ku_i\right|\right|^2.\ \ \ (1)$$

Indeed, note that for the difference in your question the matrix multiplication $$x($$this difference$$)x^{T}$$ is equal to

$$||x||^2\left(k\sum_{i=1}^k||u_i||^2-\left|\left|\sum_{i=1}^ku_i\right|\right|^2\right).$$

Examining $$(1)$$ at each coordinate, we conclude that it suffices to show that

$$k\sum_{i=1}^ka_i^2\geq \left(\sum_{i=1}^ka_i\right)^2\ \ \ (2)$$

for any $$k$$-tuple $$(a_1,\ldots,a_k)$$ of real numbers. Indeed, then we will have that

$$k\sum_{i=1}^ku_{ij}^2\geq \left(\sum_{i=1}^ku_{ij}\right)^2,\ \forall j=1,\cdots,n$$

and $$(1)$$ will follow by summing over all $$j$$'s. Now, $$(2)$$ can be easily proved by applying C-S to the vectors $$(1,\ldots,1)$$ and $$(a_1,\ldots,a_k).$$ An other proof of $$(2)$$ can be obtained by applying Jensen's inequality to the convex function $$x\mapsto x^2.$$

• Are you saying that: $x^T \Bigg[ k\sum_{i=1}^k v_i v_i^T-\Big(\sum_{i=1}^k v_i\Big)\Big(\sum_{i=1}^k v_i^T\Big) \Bigg] x = ||x||^2\left(k\sum_{i=1}^k||v_i||^2-\left|\left|\sum_{i=1}^kv_i\right|\right|^2\right)$? Can you explain this? The term in parentheses on the LHS is a matrix, and you aren't normally allowed to pull the $x$ through. – Dan May 4 '19 at 22:49
• @Dan: Well, I understand what you are saying, but when we write $xAx^{T}$ what we mean is $\langle Ax,x\rangle$ (usual inner product). You have to remember that, so that you will not be confused. In general $1\times 1$ matrices are viewed as real numbers and a matrix $A$ is said to be positive semidefinite if-f $\langle Ax, x\rangle\geq 0,\ \forall x$ Check this definition here: en.wikipedia.org/wiki/Definiteness_of_a_matrix. – Στέλιος Σαχπάζης May 4 '19 at 23:19
• I'm now confused as to why you are writing $xAx^T$ instead of $x^TAx$. I was using $x$ to represent a column vector and $x^T$ to represent the transposed row vector. In this case, $x^TAx=\langle x,Ax\rangle =\langle A^Tx,x\rangle$ and is a scalar. (This was the notation I also used in everything I've written above. If you assumed the transpose of what I meant, then it makes sense that you thought that $v_i v_i^T=\|v_i\|^2$) – Dan May 4 '19 at 23:22
• @Dan: Ah, OK, no problem. It's the same thing, because I just work with row vectors. This is why I have the transposes at the other places and $\langle Ax, x\rangle$ instead of $\langle A^{T}x,x\rangle.$ I hope everything is clear now. – Στέλιος Σαχπάζης May 4 '19 at 23:25
• @Dan no problem, that's a reasonable decision. Thank you! Glad that I finally helped you. :) – Στέλιος Σαχπάζης May 4 '19 at 23:53

Indeed, the form of the $$v_i$$ is not needed, but we utilize the fact that $$k$$ is a positive integer: \begin{align} k\sum_{i=1}^k x^T v_i v_i^T x-x^T \left(\sum_{i=1}^k v_i\right)\left(\sum_{i=1}^k v_i^T \right)x &= \left(\sum_{i=1}^k 1\right) \left(\sum_{i=1}^k w_i^2\right) -\left(\sum_{i=1}^k w_i\right)^2,\textrm{ where }w_i\equiv x^Tv_i\\ &=\left\Vert1_k\right\Vert^2 \left\Vert w\right\Vert^2 - \left|\langle 1_k,w\rangle\right|^2, \textrm{ where }w\equiv(w_1,\dots,w_k)^T \\ &\geq ^{CS} \left|\langle 1_k,w\rangle\right|^2 - \left|\langle 1_k,w\rangle\right|^2\\ &=0\\ &\hspace{2.5in}\blacksquare \end{align}