Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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_1x_2+x_2x_3+\cdots+x_nx_1$?

share|improve this question
    
Come on! It must be maximum when they are all equal. :) –  Ustun Dec 6 '12 at 16:49
2  
I also thought so, but my friend, check the comments in here. It is not!. One intuitive way to look, the function is not symmetric in its variables. –  dineshdileep Dec 6 '12 at 17:32

4 Answers 4

up vote 4 down vote accepted

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

share|improve this answer
    
For $n=3$ you can use the fact that $2(x_1x_2+x_2x_3+x_3x_1)=S^2-(x_1^2+x_2^2+x_3^2)$. Add this to $x_1x_2+x_2x_3+x_3x_1 \leq x_1^2+x_2^2+x_3^2$ and you are done. –  N. S. Dec 6 '12 at 19:36
    
Check my answer: if you are happy with the way I edited your answer copy it and then I can delete mine ;) Or if you OK it, I can edit your answer. –  N. S. Dec 6 '12 at 19:50
    
It may be long, but it's fairly easy to follow, and seems correct :) –  aditsu Dec 7 '12 at 3:25

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} $$

share|improve this answer
    
I think you are actually getting $x_1x_n$ twice in your first inequality. Either that or you're missing an $x_1^2$ –  aditsu Dec 6 '12 at 5:52
    
Therefore $x_1(S-x_1)$ is wrong –  aditsu Dec 6 '12 at 6:04
    
Yes, it can be replaced by $x_1(S+x_n-x_1)$ but then the rest doesn't work.... –  N. S. Dec 6 '12 at 6:16

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.

share|improve this answer
    
$e_2$ is not the function what the OP wants to be maximized. Note that $e_2$ has more than $n$ terms but the function OP has specified has only $n$ terms. –  dineshdileep Dec 6 '12 at 18:53

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

share|improve this answer
    
No, $x^T C x=1/2$ for this $x$. You get 1 for choosing the unit eigenvector of $1$, which is a $(1/\sqrt{n}) (1,...1)$, and this is the maximizer of of this function on the unit sphere. This is not what the question is about. –  Florian Dec 6 '12 at 20:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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