I know that
$$
\min\_{\|x\|\_2=1=\|y\|\_2} \left(\sum\_{k=1}^nx\_ky\_k\right)^2-\sum\_{k=1}^nx\_k^2y\_k^2 \geq -1/2
$$
with equality whenever $|x\_k|=\frac{1}{\sqrt{2}}=|y\_k|$ for two coordinates. 


I'm wondering if there's a sharper version that one can prove wherein $x$ is *fixed* and we only minimize over $y$, i.e.,
$$
\min\_{\|y\|\_2=1} \left(\sum\_{k=1}^nx\_ky\_k\right)^2-\sum\_{k=1}^nx\_k^2y\_k^2 \geq\ ??
$$


Presumably the lower bound should depend on the sparsity of $x$, and something like its `variance'
$$
\sigma(x) = \frac{1}{n}\sum\_{k=1}^n(x\_k-\mu(x))^2.
$$


For example, in the initial problem, if $n$ is even and we take $|x\_k|=\frac{1}{\sqrt{n}}$ with an alternating sign, then the minimum grows to $-1/n$. Here $\mu(x)=0$ and $\sigma(x)=1/n^2$. The minimum is achieved for $y$ with the same mean and variance. On the contrary, if $x\_1=1$ (so $x$ has maximal variance) we find the minimum is 0 and is achieved for *any* $y$.


**Are there any inequalities that reduce to these extreme cases but shed light on the intermediate ones as well?** 



Minimum of squared sum minus sum of squares
To elaborate some on the last two sentences of Robert's answer, here's what I would view as the standard procedure to analyze the rank one perturbation $D^2-xx^t$. I'll proceed as in [this answer](https://mathoverflow.net/questions/193527/about-adding-a-negative-definite-rank-1-matrix-to-a-symmetric-matrix/193592#193592) of mine. It's convenient to have $x$ as a cyclic vector for $D^2$; this will be the case in the generic situation where all $x\_j^2$ are distinct and non-zero, and I can then obtain the other cases by approximation. Let's in fact assume that $0<x\_1^2<\ldots < x\_n^2$.


As spelt out in that answer, the eigenvalues of $A=D^2-xx^t$ are then the points $\lambda$ with $F(\lambda)=1$, where $F(z)=x^t(D^2-z)^{-1}x$ is the matrix element of the resolvent. Since $D$ is diagonal, this is easily evaluated and we obtain
$$
F(\lambda) = \sum \frac{x\_j^2}{x\_j^2-\lambda} = 1
$$
as the condition determining the eigenvalues. There is one such $\lambda$ in each interval $(-\infty, x\_1^2)$, $(x\_1^2,x\_2^2), \ldots, (x\_{n-1}^2,x\_n^2)$. As explained by Robert, here we are interested in the solution $\lambda\in (x\_{n-1}^2,x\_n^2)$, and your minimum equals $-\lambda$.


In the cases you mentioned, this gives $-\lambda = -1/n$ (for the simple reason that we must find $\lambda$ between $x\_{n-1}^2=1/n$ and $x\_n^2=1/n$) and $\lambda=0$, respectively. In general, we see that quantities such as $\mu(x)$ or $\sigma(x)$ are in fact not very relevant (certainly not if $x\_{n-1}^2$ is close to $x\_n^2$).


