Maximize $x_1x_2+x_2x_3+\cdots+x_nx_1$

Question

Let $x_1,x_2,\ldots,x_n$ be $n$ non-negative numbers ($n>2$) with a fixed sum $S$. What is the maximum of $x_1 x_2 + x_2 x_3 + \dots + x_n x_1$?

Answer 1

I have to solve this in 3 parts. First for $n=3$, then for $n=4$ and finally for $n>4$.

---

For $n=3$ we can take a tranformation $x'_1=x'_2=(x_1+x_2)/2$ and $x'_3=x_3$. $\sum x_i$ remains fixed while $\sum{x'_i*x'_{i+1}}-\sum{x_i*x_{i+1}} = (x_1+x_2)^2/4-x_1*x_2 = (x_1^2+2x_1x_2+x_2^2)/4-x_1*x_2 = (x_1^2-2x_1x_2+x_2^2)/4 = (x_1-x_2)^2/4$
which is $>0$ if $x_1$ differs from $x_2$.
So an optimal solution must have the first two terms equal (otherwise we can apply this transformation and obtain a higher value), but you can cycle the terms, so they must be all equal to $S/3$ for a total sum of $S^2/3$.

---

For $n=4$ the transformation $x'_1=x_1+x_3$, $x'_3=0$ doesn't change the result, so we take an optimal solution, sum the odd and even terms, and the problem becomes finding the maximum of $(\sum x_{odd})*(\sum x_{even})$, that is maximized if both terms are equal to $S/2$, for a total of $S^2/4$.

---

For $n>4$, I have to prove this lemma first:

For $n>4$, there is at least one optimal configuration that has at least one index $i$ such that $x_i=0$

Take a configuration that is optimal and such that every $x_i>0$ and $x_1 = max(x_i)$.
Now use the following transformation: $x'_2=x_2+x_4$, $x'_4=0$. $\sum x_i$ remains the same but $\sum{x'_i*x'_{i+1}}-\sum{x_i*x_{i+1}}=x_1*(x_2+x_4)+(x_2+x_4)*x_3+\sum_{i>4}{x_i*x_{i+1}}-\sum{x_i*x_{i+1}} = x_1*x_4-x_4*x_5 = x_4*(x_1-x_5) = x_4*(max(x_i)-x_5) \geq x_4*(x_5-x_5) = 0$
So we have another optimal solution with a $0$.

Given that at least an optimal solution contains a $0$ for every $n>4$, the maximum value of $\sum{x_i*x_{i+1}}$ must be non-increasing for $n$ (otherwise we can take a solution for $n$ with a $0$ inside, remove that $0$, and obtain a higher solution for $n-1$).

Now the value of the sum must be $\leq S^2/4$, but taking $x_1=x_2=S/2$ gives that sum, so that configuration is an optimal one, for a sum of $S^2/4$.

This proves that the maximum is $S^2/3$ if $n=3$ and $S^2/4$ otherwise.

I am not satisfied with this answer, because it breaks down to a lot of case analysis. I am still curious to see a simpler proof (or one that requires less space..).

Answer 2

Fixed This is carlop's solution simplifyid, so please upvote that solution.

For $n=3$ we have by C-S or rearrangement

$$x_1x_2+x_2x_3+x_3x_1 \leq x_1^2+x_2^2+x_3^2$$

Adding $2(x_1x_2+x_2x_2+x_3x_1)$ we get

$$3(x_1x_2+x_2x_3+x_3x_1) \leq (x_1+x_2+x_3)^2 \,.$$

For $n \geq 4$ even we have

$$x_1x_2+x_2x_3+....+x_{2k}x_1 \leq (x_1+x_3+..+x_{2k} )( x_2+x_4+...+x_{2k-1})$$

since any term on the LHS appears on the RHS.

Thus

$$\sqrt{x_1x_2+x_2x_3+....+x_{2k}x_1} \leq \frac{x_1+x_3+..+x_{2k} + x_2+x_4+...+x_{2k-1}}{2} =\frac{S}{2}$$

For $n \geq 4$ odd

Since the LHS sum is cyclic, without loss of generality we can assume that $x_{2k+1}$ (otherwise reorder them) is the smallest term. Then $x_{2k+1} \leq x_4$ (here is where we need $n \geq 4$.)

$$x_1x_2+x_2x_3+....+x_{2k+1}x_1 \leq x_1x_2+x_2x_3+....+x_{2k}x_{2k+1}+x_{4}x_1 \leq (x_1+x_3+..+x_{2k} )( x_2+x_4+...+x_{2k-1})$$

Again BY AM_GM you get

$$\sqrt{x_1x_2+x_2x_3+....+x_{2k+1}x_1} \leq \frac{x_1+x_3+..+x_{2k+1} + x_2+x_4+...+x_{2k}}{2} = \frac{S}{2} $$

Answer 3

This should be a comment, but I don't have the reppts.

Consider $x^n-Sx^{n-1}+e_2x^{n-2}+\ldots+(-1)^ne_n=\prod_{i=1}^n(x-x_i)$, rephrasing, quite wrongly, the question to be about finding the maximal $e_2$.

Let $x_i=\frac{S}{n}\forall i$. Then $(x-\frac{S}{n})^n=x^n-n(\frac{S}{n})x^{n-1}+{n\choose 2}(\frac{S}{n})^2x^{n-2}+\ldots$ so we can get as high as $\frac{n-1}{2n}S^2$; tending to but always smaller than $\frac{S^2}{2}$ in general.

This is $\frac{S^2}{3}$ for $n=3$, and $\frac{3}{8}S^2>\frac{S^2}{4}$ for $n=4$.

Edit: $e_2\geq x_1x_2+x_2x_3+\ldots+x_nx_1$, not necessarily equal. Keeping it up, as someone else may make the same error.

Answer 4

This is WRONG. It is kept here so that no one else will make the same blunder.

The answer is $\frac{S^2}{4}$. There are $nC_2$ answers that will give this value. All of them are the all-possible permutations of the vector $x=[\frac{S}{2},\frac{S}{2},0,0,\dots,0]^T$. I was able to prove this since I already knew the solution from the comments of user N.S. on user Ross Millikan's answer. So the credit goes to him. I will demonstrate the concepts using $5 \times 5$ matrix. The result is easily generalizable.

Define column vector $x=[x_1,x_2,x_3,x_4,x_5]^T$. Then the function in question can be written as \begin{align} f(x)=x_1x_2+x_2x_3+x_3x_4+x_5x_1=x^TQx \end{align} where \begin{align} Q=\begin{bmatrix}0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\0 & 0 & 0 & 1 & 0 \\0 & 0 & 0 & 0 & 1 \\1 & 0 & 0 & 0 & 0 \\\end{bmatrix} \end{align} Note that $Q$ is a permutation matrix and also non-symmetric. For every non-symmetric matrix $Q$, we have $x^TQx=x^TCx$ where $C=(1/2)*(Q+Q^T)$ and is a symmetric matrix. So we have \begin{align} f(x)=x^TCx \end{align} Also note that \begin{align} C=\begin{bmatrix}0 & .5 & 0 & 0 & .5 \\ .5 & 0 & .5 & 0 & 0 \\0 & .5 & 0 & .5 & 0 \\0 & 0 & .5 & 0 & .5 \\.5 & 0 & 0 & .5 & 0 \\\end{bmatrix} \end{align} Note that the diagonals on either side of the main diagonal are all .5 and values on top-right and left-bottom corner are also $.5$. Now $C$ is a symmetric matrix and hence \begin{align} \lambda_{min}(C)\leq x^TCx \leq \lambda_{max}(C)\text{ $\quad \forall x,$ $x^Tx=1$} \end{align} Now $C$ is a doubly stochastic matrix (column sum and row sum is one). So $1$ is always an eigenvalue. Most importantly, $C$ is an irreducible primitive matrix. This follows from perron-frobenius theory. Hence $1 $ is the largest eigenvalue. Now observe that $x=[\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}},0,0,0]^T$ has $f(x)=x^TCx=1$. Also it has unit norm. In fact, all permutations of this vector (all possible rearrangements of its entries), has the same value for $f(x)$ and they all have unit norm. This $f(x)$ is always maximized in this unit-vectors direction. Now $x^Tx=1$ is not our requirement. But, sum of its elements should be $S$. From the above the discussion, one can conclude that all the elements except two of vector $x$ should be zero and the non-zero entries should be equal if $f(x)$ is to be maximized. By symmetry, it is see to that all permutations of the vector $x=[\frac{S}{2},\frac{S}{2},0,0,0]$ is the only set of vectors that satisfies the sum condition while giving the maximum of $f(x)$.