6
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Dan May 4 '19 at 22:49
  • $\begingroup$ @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. $\endgroup$ – Στέλιος Σαχπάζης May 4 '19 at 23:19
  • $\begingroup$ 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$) $\endgroup$ – Dan May 4 '19 at 23:22
  • $\begingroup$ @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. $\endgroup$ – Στέλιος Σαχπάζης May 4 '19 at 23:25
  • 1
    $\begingroup$ @Dan no problem, that's a reasonable decision. Thank you! Glad that I finally helped you. :) $\endgroup$ – Στέλιος Σαχπάζης May 4 '19 at 23:53
4
$\begingroup$

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}

$\endgroup$

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.