# How to maximize $\sum x_i\times x_j$ as $1\leq i,j\leq n$ with $i\neq j$ subject to $\sum x_i=1$?

I want to maximize $$\sum_{i,j \in [n], i \ne j} x_i \times x_j$$ where $$\forall i ~~$$ $$0\le x_i \le 1$$ and $$x_1 + x_2 + x_3 + \ldots +x_n = 1$$

I want to prove that the sum will be maximized when $$\forall i ~~$$ $$x_i = \frac{1}{n}$$. I don't know whether this statement is true or not.

Note:- It would be more helpful if you can prove that using shifting of weights from one $$x_i$$ and $$x_j$$. Even the proof is not following that method it is fine.

## 2 Answers

Your summation is $$x_1(\sum_{j\ne1}x_j)+x_2(\sum_{j\ne2}x_j)+...+x_n(\sum_{j\ne n}x_j)$$ which is $$x_1(1-x_1)+...+x_n(1-x_n)=(x_1+...+x_n)-(x_1^2+...+x^2_n)=1-(x_1^2+...+x^2_n)$$. To maximize this, we need to minimize $$\sum_{i\in[n]}x_i^2$$.

We know $$\sum_{i=1}^nx_i^2\ge \frac{(\sum_{i=1}^nx_i)^2}n=1/n$$.

And indeed this minimum is observed when $$x_1=x_2=...=x_n=1/n$$. The maximum value is $$1-1/n$$.

If you take the derivative wrt $$x_i$$ you get, for each $$i$$

$$\sum_{j=1}^n x_j-x_i-\lambda=0\implies x_i=1-\lambda$$

where $$\lambda$$ is the Lagrange multiplier. This means that all the $$x_i$$ need to take the same value. Adding the $$n$$ FOC's results in

$$1=n(1-\lambda)\implies \lambda=\frac{n-1}{n},$$

and, therefore, $$x_i=\frac{1}{n}$$