Minimum of squared sum minus sum of squares

Question

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?

Answer 1

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

Answer 2

If $z_k = x_k y_k$, the quantity you're looking at is $$ y^T D Q D y = \left(\sum_k z_k\right)^2 - \sum_k z_k^2$$

where $Q$ is the $n \times n$ symmetric matrix with diagonal terms $0$ and off-diagonal terms $1$, and $D$ is the diagonal matrix with diagonal entries $x_k$. What you're asking for is the least eigenvalue of $DQD$. Now $Q = -I + e e^T$ where $e$ is the vector of all $1$'s, so $$DQD = -D^2 + (De)(e^TD) = -D^2 + x x^T$$ is a rank-one perturbation of $-D^2$. This sort of thing has been studied quite a bit, I think. See for example this recent paper. (Cheng, Guanghui; Luo, Xiaoxue; Li, Liang, The bounds of the smallest and largest eigenvalues for rank-one modification of the Hermitian eigenvalue problem, Appl. Math. Lett. 25, No. 9, 1191-1196 (2012). ZBL1255.15025. MR2930744.)