20
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Come on! It must be maximum when they are all equal. :) $\endgroup$
    – user21965
    Commented Dec 6, 2012 at 16:49
  • 3
    $\begingroup$ 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. $\endgroup$ Commented Dec 6, 2012 at 17:32

5 Answers 5

7
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ I think you are actually getting $x_1x_n$ twice in your first inequality. Either that or you're missing an $x_1^2$ $\endgroup$ Commented Dec 6, 2012 at 5:52
  • $\begingroup$ Therefore $x_1(S-x_1)$ is wrong $\endgroup$ Commented Dec 6, 2012 at 6:04
  • $\begingroup$ Yes, it can be replaced by $x_1(S+x_n-x_1)$ but then the rest doesn't work.... $\endgroup$
    – N. S.
    Commented Dec 6, 2012 at 6:16
  • $\begingroup$ A simplification for the $n \geq 4 $ odd case: Reduce it to the $ n -1 $ case by setting $ y_i = x_i \forall i < n-1, y_{n-1} = x_{n-1} + x_{n} $. This would increase the value of the expression (by $x_{n-2}x_n$), but it's still bounded by $ S^2 / 4$. $\endgroup$
    – Calvin Lin
    Commented Sep 7, 2021 at 5:46
5
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – N. S.
    Commented Dec 6, 2012 at 19:36
  • $\begingroup$ 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. $\endgroup$
    – N. S.
    Commented Dec 6, 2012 at 19:50
  • $\begingroup$ It may be long, but it's fairly easy to follow, and seems correct :) $\endgroup$ Commented Dec 7, 2012 at 3:25
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ $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. $\endgroup$ Commented Dec 6, 2012 at 18:53
0
$\begingroup$

Consider graph $G=(V,E)$, where $V=\{1,2,\ldots,n\}$ and corresponding sum $F(x_1,x_2,\ldots,x_n)=\sum\limits_{ij\in E}{x_ix_j}$. We will prove that for $x_1,x_2,\ldots,x_n\in[0,1]$ such that $\sum\limits_{i=1}^{n}x_i=1$ the maximum of $F(x_1,x_2,\ldots,x_n)$ is equal to $\dfrac{1}{2}-\dfrac{1}{2\omega(G)}$, where $\omega(G)$ is a clique number of graph $G$. Firstly, note that the set $$ K=\left\{(x_1,x_2,\ldots,x_n)\mid x_i\in [0,1], \sum_{i=1}^{n}x_i=1\right\} $$ is compact and $F$ is continious, so the maximum of $F$ is attained at some point $A_0=(x_1,x_2,\ldots,x_n)\in K$. We will suppose that among all maxima of $F$ in $E$ point $A_0$ has the least possible number of nonzero coordinates. Now we will prove that the set $C$ of vertices $i\in V$ such that $x_i>0$ form a clique in the graph $G$.

Indeed, consider two indices $i$ and $j$ such that $x_i,x_j>0$. If $ij\notin E$, then consider point $A_t(x_1,\ldots,x_i+t,\ldots,x_j-t,\ldots,x_n)\in K$ (for some small $t$) and the value of $F$ at this point. Note that $$ F(A_t)-F(A_0) $$ is a linear function of the variable $t$ (here we use our assumption $ij\notin E$; terms with $t^2$ can appear only in $(x_i+t)(x_j-t)$) and it's well-defined on some interval $(-\varepsilon,\varepsilon)$ (we can suppose that $A_t\in K$ for $|t|<\varepsilon$).

Since $F(A_t)-F(A_0)\leq 0$ for $|t|\leq\varepsilon$, $F(A_t)$ should be constant, so for all $t$ we have $F(A_t)=F(A_0)$. Thus, for all $t$ such that $A_t\in K$ the point $A_t$ is a maximum of $F$.

Now, observe that $x_i+x_j\leq 1$, so for $t=x_j$ point $A_{x_j}\in K$ has less nonzero coordinates than $A_0$ and it contradicts our assumption.

Thus, vertices of $C=\{i\mid x_i>0\}$ form a clique in the graph $G$. In this case we can compute and estimate the value of $F$ at $A_0$; the first inequality is a consequence of $|C|\cdot\sum\limits_{i\in C}x_i^2\geq\left(\sum\limits_{i\in C}x_i\right)^2$: $$ F(A_0)=\sum_{ij\in E}x_ix_j=\sum_{i,j\in C, ij\in E}x_ix_j\leq\frac{|C|-1}{2|C|}\cdot \left(\sum_{i\in C}x_i\right)^2=\frac{|C|-1}{2|C|}=\frac{1}{2}-\frac{1}{2|C|}\leq\frac{1}{2}-\frac{1}{2\omega(G)}. $$

Hence, $F(x_1,\ldots,x_n)\leq\dfrac{1}{2}-\dfrac{1}{2\omega(G)}$, as desired.

Finally, note that if $\{i_1,i_2,\ldots,i_k\}$ is a clique of size $k=\omega(G)$ in the graph $G$, then $F(x_1,\ldots,x_n)=\dfrac{1}{2}-\dfrac{1}{2\omega(G)}$, where $x_{i}=\frac{1}{k}$ if $i=i_{j}$ for some $j$ and $0$ otherwise (it follows from the previous computations).

Therefore, $$ \max_{K} F=\dfrac{1}{2}-\dfrac{1}{2\omega(G)}. $$


Now return to the original problem. In this case $G=C_n$ (cycle on $n$ vertices), so for $n=3$ the maximum value is $\frac{1}{2}-\frac{1}{6}=\frac{1}{3}$ and for $n>2$ it equals $\frac{1}{2}-\frac{1}{4}=\frac{1}{4}$.

$\endgroup$
1
  • $\begingroup$ The idea is just to "move" variables and increase the value of $F$ (like in linear programming and simplex method). $\endgroup$
    – richrow
    Commented Jul 31, 2020 at 9:57
-1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Florian
    Commented Dec 6, 2012 at 20:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .