maximum of the $\sum_{1\le i<j\le n}a_{i}a_{j}(x_{i}y_{j}-x_{j}y_{i})^2$

220 Views Asked by At

Give the $x_{1},x_{2},\cdots,x_{n},y_{1},y_{2},\cdots,y_{n}$ such $$x^2_{i}+y^2_{i}=1$$ Find the maximum of the value $$\sum_{1\le i<j\le n}a_{i}a_{j}(x_{i}y_{j}-x_{j}y_{i})^2$$ on the $a_{1},a_{2},\cdots,a_{n}\ge 0,\sum_{i=1}^{n}a_{i}=1$

maybe this can use quadratic forms solve it?

2

There are 2 best solutions below

0
On

I assume the intention is that we are given $(x_i, y_i)$ and must optimize the $a_i$. Put $(x_i,y_i) = (\cos \theta_i, \sin \theta_i)$ and notice that $$(x_i y_j - x_j y_i)^2 = \sin^2 (\theta_i - \theta_j) = \tfrac{1}{2} (1 - \cos (2\theta_i - 2\theta_j)).$$

The sum was given as running over $i<j$, but the expression is symmetric in switching $i$ and $j$, and is $0$ when $i=j$, so we can just sum over all $1 \leq i,j \leq n$. Our goal is to maximize $$\sum_{1 \leq i,j \leq n} a_i a_j (1 - \cos (2\theta_i - 2\theta_j)) = \left( \sum_i a_i \right)^2 - \sum_{1 \leq i,j \leq n} a_i a_j \cos (2 \theta_i - 2 \theta_j).$$ We have $\sum a_i=1$, so our goal is to minimize $\sum_{1 \leq i,j \leq n} a_i a_j \cos (2 \theta_i - 2 \theta_j)$. Letting $\vec{v}_i = (\cos 2 \theta_i, \sin 2 \theta_i)$, we want to minimize $$\sum_{1 \leq i,j \leq n} a_i a_j (\vec{v}_i \cdot \vec{v}_j) = \left( \sum a_i \vec{v}_i \right) \cdot \left( \sum a_j \vec{v}_j \right).$$ Here $\cdot$ is dot product.

As $a_i$ suns over $a_i \geq 0$, $\sum a_i =1$, the quantity $\sum a_i \vec{v}_i$ runs over the convex hull of the $\vec{v}_i$, so we want to find the point of shortest length in this convex hull. There are two cases:

$0$ is in the convex hull of the $\vec{v}_i$ In this original variables, this corresponds to saying that the $(x_i, y_i)$ do not lie within any $90^{\circ}$ wedge. Then we should take $\sum a_i \vec{v}_i=0$, in which case the original quantity is $1/4$.

All the $\vec{v}_i$ lie in a half plane. In the original variables, this corresponds to the $(x_i, y_i)$ lying in a $90^{\circ}$ wedge. Order the variables in circular order $\theta_1$, $\theta_2$, \dots, $\theta_n$ and the optimum is to take $\sum a_i \vec{v}_i$ to be the midpoint of the line segment from $\vec{v}_1$ to $\vec{v}_n$. In other words, $a_1=a_n=1/2$, the others are $0$, and the final answer is $\tfrac{1}{4} (x_1 y_n - x_n y_1)^2$.

0
On

By Cauchy-Schwartz inequality we get for every $i,j$: $$(x_iy_j-x_jy_i)^2\leqslant (x_i^2+y_i^2)((-x_j)^2+y_j^2)=1\cdot 1=1$$ The equality is reached for $x_i=y_j$ and $y_i=-x_j$ (this amounts to say that the vectors $(x_i,y_i)$ and $(x_j,y_j)$ are perpendicular). Therefore $$\sum_{i<j}a_ia_j(x_iy_j-x_jy_i)^2\leqslant \sum_{i<j}a_ia_j$$ On the other hand one has the identity $$\Big(\sum_{i=1}^na_i\Big)^2=\sum_{i=1}^na_i^2+2\sum_{i<j}a_ia_j$$ Therefore $$\sum_{i<j}a_ia_j=\frac{1}{2}\Big[\Big(\sum_{i=1}^na_i\Big)^2-\sum_{i=1}^na_i^2\Big]=\frac{1}{2}\Big[1-\sum_{i=1}^na_i^2\Big]$$ from the constraint $\sum_ia_i=1$. It is sufficient to look at the problem $$\max_{a_1,...,a_n}\frac{1}{2}\Big[1-\sum_{i=1}^na_i^2\Big]$$ subject to $\sum_ia_i=1$ and $a_i\geqslant 0$ for all $i$. Using standard techniques from Lagrange multipliers one finds that $a_i=a_j$ for all $i,j$ and so from the constraint we get $a_i=1/n$ for all $i$. So the maximum value would be $$\frac{1}{2}\Big[1-\sum_{i=1}^na_i^2\Big]=\frac{1}{2}\Big(1-\frac{1}{n}\Big)\Rightarrow \sum_{i<j}a_ia_j(x_iy_j-x_jy_i)^2\leqslant\frac{1}{2}\Big(1-\frac{1}{n}\Big)$$