5
$\begingroup$

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?

$\endgroup$
0

2 Answers 2

5
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ I should also point out that the inequality $x_{n-1}^2\le\lambda\le x_n^2$ is just the interlacing property, I don't need to look at resolvents for this. $\endgroup$ May 15, 2015 at 1:35
  • $\begingroup$ Very nice! Follow-up question: suppose we're looking at $D^2+\alpha xx^T$ for some $\alpha>0$. Then your analysis yields the largest eigenvalue is lower-bounded by $\alpha x_n^2$. It seems that it might be possible to analyze $F(\lambda)$ further and deduce a more interesting upper-bound than $\sum x_k^2$? $\endgroup$
    – squattyroo
    May 15, 2015 at 17:27
  • $\begingroup$ @squattyroo: This (a rank-one perturbation with a coupling constant) is actually the situation I'm most familiar with. Somewhat unexpectedly, it's a pretty interesting subject; Barry Simon has a very readable review article on this, if you want to know more. $\endgroup$ May 15, 2015 at 19:09
  • $\begingroup$ @squattyroo: To address your actual comment, if $A=D^2+\alpha xx^t$ with $\alpha\in\mathbb R$, then the calculation from the other answer now gives $G_{\alpha}=F/(1+\alpha F)$, and thus the eigenvalues of $A$ are now the solutions of $F(\lambda)=-1/\alpha$ (above we're in the special case $\alpha=-1$). The (interlacing) bounds stay the same though (if $\alpha>0$, there's no eigenvalue below the spectrum of $D^2$ and instead there's one above the spectrum). $\endgroup$ May 15, 2015 at 19:12
6
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.