Minimising the squared sum minus the sum of squares

Question

I'd like to know how to show $$\min_{\Vert x\Vert_2=1=\Vert y\Vert_2}\left(\sum_{k=1}^nx_ky_k\right)^2-\sum_{k=1}^nx_k^2y_k^2\geq -1/2.$$

The inequality is discussed in a previous post Minimum of squared sum minus sum of squares but it's not clear to me how to prove this.

Answer 1

It should oftentimes be the case that, analyzing a "thoughtless" Lagrange multiplier solution, one finds a more elegant, "clever" solution. At least, this is the case here. Analyzing the previous Lagrange multiplier solution, one can obtain the following.

We need to show that $$\sum x_j^2 y_j^2\le1/2+\Big(\sum x_j y_j\Big)^2\tag{0}$$ given that $\sum x_j^2=1$ and $\sum y_j^2=1$.

Let $$s_+:=\sum_{j\colon\,x_jy_j>0}x_jy_j,\quad s_-:=-\sum_{j\colon\,x_jy_j<0}x_jy_j.$$ Then $s_+-s_-=\sum x_jy_j$ and $s_++s_-=\sum|x_jy_j|\le\sqrt{\sum x_j^2}\sqrt{\sum y_j^2}=1$, by the Cauchy--Schwarz inequality. Also, $\sum x_j^2 y_j^2\le s_+^2+s_-^2$. So, (0) reduces to $s_+^2+s_-^2\le1/2+(s_+-s_-)^2$, which simplifies to $s_+ s_-\le1/4$, which latter holds because $s_\pm\ge0$ and $s_++s_-\le1$. So, (0) is proved.

Answer 2

We need to show that $$\sum x_j^2 y_j^2\le1/2+\Big(\sum x_j y_j\Big)^2\tag{0}\label{0}$$ given that $\sum x_j^2=1$ and $\sum y_j^2=1$.

Consider the maximization of $\sum x_j^2 y_j^2$ for a fixed value of $\sum x_j y_j$ assuming also $\sum x_j^2=1$ and $\sum y_j^2=1$. Then (see e.g. the Carathéodory Multiplier Rule, page 441) $$Ax_j y_j^2=ax_j+cy_j,\tag{1}\label{1}$$ $$Ax_j^2 y_j=by_j+cx_j\tag{2}\label{2}$$ for any maximizer $((x_j),(y_j))$, some real Lagrange multipliers $A\in\{0,1\},a,b,c$ (not all of which equal $0$), and all $j$.

Multiplying \eqref{1} and \eqref{2} by $x_j$ and $y_j$, respectively, and then subtracting, we get $ax_j^2=by_j^2$ for all $j$. Summing in $j$, we get $a=b$.

Case 1: $a=b\ne0$. Then for each $j$ we have $x_j^2=y_j^2=:u_j\ge0$ and hence $y_j=\pm x_j$. Then \eqref{0} becomes $$\sum u_j^2\le1/2+(s_+-s_-)^2,\tag{0'}\label{0'}$$ where $$s_\pm:=\sum_{j\colon\, y_j=\pm x_j}u_j.$$ Note that $\sum u_j^2\le s_+^2+s_-^2$. So, \eqref{0'} reduces to $s_+s_-\le1/4$, which holds because $s_+ + s_-=\sum u_j=\sum x_j^2=1$. So, \eqref{0} holds in Case 1.

Case 2: $a=b=0$ and $A=1$. Then, by \eqref{1} and \eqref{2}, for each $j$ we have $x_jy_j=0$ or $x_jy_j=c$. So, \eqref{0} becomes $$kc^2\le1/2+(kc)^2,\tag{0''}\label{0''}$$ where $k$ is the cardinality of the set $\{j\colon x_jy_j=c\}$. Since $k=0$ or $k\ge1$, \eqref{0''} holds and hence \eqref{0} holds in Case 2.

Case 3: $a=b=0$ and $A=0$. Then $c\ne0$ and hence, by \eqref{1}, $y_j=0$ for all $j$, which contradicts the condition $\sum y_j^2=1$. So, Case 3 cannot occur.

Thus, \eqref{0} holds in all the cases.