# Maximizing the sum $\sum\limits_{i=1}^nx_ix_{i+1}$ subject to $\sum\limits_{i=1}^nx_i=0$ and $\sum\limits_{i=1}^nx_i^2=1$

Is there an efficient way of solving the following problem?

Given $x_i\in \mathbb R$, and that $\sum\limits_{i=1}^nx_i=0$ and $\sum\limits_{i=1}^nx_i^2=1$. I want to maximize $\sum\limits_{i=1}^nx_ix_{i+1}$ where we take $x_{n+1}=x_1$.

I don't know if this is relevant/useful at all but maybe representing the systems as $\vec{x}^TI\,\,\vec{x}$ and $\vec{x}^T\{\delta_{i , \,\,i+1}\}\,\,\vec{x}$ might help?

Thanks.

-
I have a conjecture that the extremal values are given by one half the eigenvalues of a fairly nice matrix. I added a lot to my response below. – alex.jordan Nov 30 '11 at 4:06
My conjecture turned out to be easy to prove given your suggestion to use a quadratic form matrix. – alex.jordan Nov 30 '11 at 6:24
I removed the [combinatorics] tag since it did not seem relevant. In case, it is relevant to the question, please feel free to add it back. – Srivatsan Nov 30 '11 at 18:39

To make the notation simpler, we will use $x_0=x_n$ and $x_{n+1}=x_1$.

Because $\sum\limits_{i=1}^nx_i=0$, the allowable variations $\{\delta x_i\}$ must satisfy $$\sum_{i=1}^n\delta x_i=0\tag{1}$$ and because $\sum\limits_{i=1}^nx_i^2=1$, $$\sum_{i=1}^nx_i\delta x_i=0\tag{2}$$ To maximize $\sum\limits_{i=1}^nx_ix_{i+1}$, any variations which satisfy $(1)$ and $(2)$ must also satisfy $$\sum_{i=1}^n(x_{i-1}+x_{i+1})\delta x_{i}=0\tag{3}$$ If $(x_{i-1}+x_{i+1})$ is orthogonal to all vectors orthogonal to $1$ and $x_i$, then there must be $\mu$ and $\lambda$ so that $$x_{i-1}+x_{i+1}=\mu+2\lambda x_i\tag{4}$$ Summing $(4)$ in $i$ and considering $\sum\limits_{i=1}^nx_i=0$, we get that $\mu=0$. Therefore, $$x_{i+1}=2\lambda x_i-x_{i-1}\tag{5}$$ Squaring $(5)$, summing in $i$, and using $\sum\limits_{i=1}^nx_i^2=1$ yields $$\lambda=\sum_{i=1}^nx_ix_{i-1}\tag{6}$$ Since the solution of $(5)$ must be $n$-periodic, the roots of $x^2-2\lambda x+1=0$ must both have $r^n=1$.

If we use $r=1$, then $\lambda=1$, but all $x_i$ would be the same. In this case, we cannot satisfy the given constraints.

If we use $r_1=e^{\frac{i2\pi}{n}}$ and $r_2=e^{\frac{-i2\pi}{n}}$, then $\lambda=\cos\left(\frac{2\pi}{n}\right)$ and thus, for $n\ge3$, $$x_i=\sqrt{\frac{2}{n}}\cos\left(\frac{2\pi}{n}i\right)\tag{7}$$ yields the maximum $$\sum_{i=1}^nx_ix_{i-1}=\cos\left(\frac{2\pi}{n}\right)\tag{8}$$ Verification:

Using the formula for the sum of a geometric series yields $$\sum_{k=0}^{n-1}e^{\frac{i2\pi}{n}k}=\frac{e^{\frac{i2\pi}{n}n}-1}{e^{\frac{i2\pi}{n}}-1}=0\tag{9a}$$ $$\sum_{k=0}^{n-1}e^{\frac{i4\pi}{n}k}=\frac{e^{\frac{i4\pi}{n}n}-1}{e^{\frac{i4\pi}{n}}-1}=0\tag{9b}$$ Therefore, the real parts of $(9)$ say that for $n\ge3$ $$\sum_{i=1}^n\cos\left(\frac{2\pi}{n}i\right)=0\tag{10a}$$ $$\sum_{i=1}^n\cos\left(\frac{4\pi}{n}i\right)=0\tag{10b}$$ Thus, $\mathrm{(10a)}$ verifies that $(7)$ satisfies $\sum\limits_{i=1}^nx_i=0$. Furthermore, $\mathrm{(10b)}$ yields \begin{align} \sum_{i=1}^n\cos^2\left(\frac{2\pi}{n}i\right) &=\sum_{i=1}^n\frac{\cos\left(\frac{4\pi}{n}i\right)+1}{2}\\ &=\frac{n}{2}\tag{11} \end{align} which verfies that $(7)$ satisfies $\sum\limits_{i=1}^nx_i^2=1$.

Using the identity $\cos(x+y)+\cos(x-y)=2\cos(x)\cos(y)$ shows that \begin{align} \sum_{i=1}^n\cos\left(\frac{2\pi}{n}i\right)\cos\left(\frac{2\pi}{n}(i-1)\right) &=\frac{1}{2}\sum_{i=1}^n\left(\cos\left(\frac{2\pi}{n}\right)+\cos\left(\frac{2\pi}{n}(2i-1)\right)\right)\\ &=\frac{n}{2}\cos\left(\frac{2\pi}{n}\right)+\frac{1}{2}\sum_{i=1}^{2n}\cos\left(\frac{2\pi}{n}i\right)-\frac{1}{2}\sum_{i=1}^n\cos\left(\frac{4\pi}{n}i\right)\\ &=\frac{n}{2}\cos\left(\frac{2\pi}{n}\right)\tag{12} \end{align} which verifies that $(7)$ yields $\sum\limits_{i=1}^nx_ix_{i-1}=\cos\left(\frac{2\pi}{n}\right)$.

-

You can use Lagrange multipliers. There are probably good books that do a better job explaining this subject than this Wikipedia article.

EDIT: What was earlier a conjecture is now proved.

Following this approach, the maximal value is one half of the largest eigenvalue of a certain matrix $M$ below.

You have a function to optimize: $$F(\vec{x})=\sum x_ix_{i+1}$$ subject to two constraints: \begin{align}G(\vec{x})&=\sum x_i=0\\ H(\vec{x})&=\sum x_i^2=1 \end{align}

With such simple polynomial functions as these, the method of Lagrange multipliers states that if $\vec{x}$ is a potential extremal point, then for some $\lambda$ and $\mu$, \begin{align}\nabla F&=\lambda\nabla G+\mu\nabla H\\ M\vec{x} & = \lambda\vec{1}+2\mu\vec{x} \end{align} where \begin{align} M&=\ \begin{bmatrix}0&1&0&0&\cdots&0&1\\ 1&0&1&0&\cdots&0&0\\ 0&1&0&1&\cdots&0&0\\ 0&0&1&0&\cdots&0&0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots&\vdots\\ 0&0&0&0&\cdots&0&1\\ 1&0&0&0&\cdots&1&0\end{bmatrix}\\ \vec{1}&=\begin{bmatrix}1\\1\\1\\1\\\vdots\\1\\1\end{bmatrix} \end{align}

Summing the equation $M\vec{x} = \lambda\vec{1}+2\mu\vec{x}$ over all rows and using the first constraint shows than $\lambda=0$, and $\vec{x}$ must be an eigenvector of $M$ in the eigenspace $V_{2\mu}$. This gives more constraints: $J(\vec{x})=(M-2\mu I)\vec{x}=0$. Since $\nabla F$ is a linear combination of $\nabla J$ and $\nabla H$, $F$ must be constant subject to the constraints $H(\vec{x})=1$ and $J(\vec{x})=0$.

So $F$ takes constant values on the eigenspaces of $M$ intersected with the sphere given by $H(\vec{x})=1$. "All" that remains is to find one eigenvector from each eigenspace of $M$ (other than $V_2$ which is orthogonal to the constraint $G(\vec{x})=0$) and compute $F$. I do not know a way to handle this matrix $M$ for all values of $n$ simultaneously though.

If $\vec{x}$ is an eigenvector for $M$ with eigenvalue $2\mu$ satisfying $H(\vec{x})=1$, then \begin{align} F(\vec{x}) & =\vec{x}^t\left(\frac{1}{2}M\right)\vec{x}\\ &=\vec{x}^t\frac{1}{2}(2\mu\vec{x})\\ &=\mu\ \vec{x}^t\vec{x}\\ &=\mu \end{align}

So in summary, the only potential extremal points for $F$ happen at the intersections of the unit sphere with the various eigenspaces of $M$. In these intersections, $F$ has constant value $\mu$, which is one half of the eigenvalue of $M$ for that eigenspace. If you can find the eigenvalues of $M$, you have the answers to your question.

-
It seems to me like the largest eigenvalue of $M$ is 2. – Aleks Vlasev Nov 30 '11 at 7:48
Your $\mathbf M$ is what's known as a circulant matrix. From the formulae in the wiki article, the eigenvalues of $M$ take the form $\mu_k=2\cos\left(\frac{2\pi(k-1)}{n}\right)$. This would confirm @Henry's and Aleks's observations. – J. M. Nov 30 '11 at 13:08
One of the most important properties of the circulant matrix is that it can be diagonalized by the discrete Fourier transform. – J. M. Nov 30 '11 at 13:12
@J.M.: it's probably not a coincidence that those eigenvalues agree with the possibilities for $2\lambda$ in my answer. – robjohn Nov 30 '11 at 13:20
It's definitely not a coincidence, @rob. As I said in another answer on another topic, the Chebyshev polynomials figure prominently in the theory of Toeplitz matrices. I was in fact racking my brains for the past hour trying to remember where I once saw alex's matrix. – J. M. Nov 30 '11 at 13:24

This is similar to alex.jordan's answer, but from a different perspective. Let $P\$ be the permutation matrix $(\delta_{i+1,j})$ and $A=\frac12(P+P^\top)$. Let also $\mathbf{u}=(1,1,\ldots,1)^\top$. Then $$\max\{\mathbf{x}^\top P\mathbf{x} : \|\mathbf{x}\|=1,\ \mathbf{x}\perp \mathbf{u}\} = \max\{\mathbf{x}^\top A\mathbf{x} : \|\mathbf{x}\|=1,\ \mathbf{x}\perp \mathbf{u}\}.$$ Since $\mathbf{u}$ is an eigenvector of $A$ corresponding to the eigenvalue $1$, the RHS is equal to the maximum eigenvalue of $A$ when the eigenvalue $1$ is excluded. Note that $A$ is a circulant matrix. In general, for a circulant matrix whose first row is some $(c_0, c_1, \ldots, c_{n-1})$, the eigenvalues are given by

$$\lambda_k = c_0 + c_1\omega_k + c_2\omega_k^2 + \ldots + c_{n-1}\omega_k^{n-1}; \quad k=0,1,\ldots,n-1,$$ where $\omega_k=\exp\left(2\pi k\sqrt{-1}/n\right)$. The eigenvector corresponding to $\lambda_k$ is $$\mathbf{v}_k = (1,\,\omega_k,\,\omega_k^2,\ldots,\omega_k^{n-1})^\top.$$ For our $A$, we have $c_1=c_{n-1}=\frac12$ and $c_k=0$ otherwise. Therefore $$\lambda_k=\frac12(\omega_k + \omega_k^{n-1})=\cos\left(2\pi k/n\right).$$ Hence the maximum of the eigenvalues (excluding $1$) is $\lambda_1=\cos\left(2\pi/n\right)$. Taking the real part of $\mathbf{v}_1$, we get a real eigenvector $\mathrm{Re}(\mathbf{v}_1) = \left(1, \mathrm{Re}(\omega_1), \mathrm{Re}(\omega_1^2), \ldots, \mathrm{Re}(\omega_1^{n-1})\right)^\top$. Normalize it, we obtain the solutions $(x_1,\ldots,x_n)=\mathrm{Re}(\mathbf{v}_1)/\|\mathrm{Re}(\mathbf{v}_1)\|$. As robjohn has worked out, the normalizing factor is $\sqrt{\dfrac2n}$ and hence $x_j = \sqrt{\dfrac2n}\cos\left(\dfrac{2\pi j}{n}\right)$.

-

Your proposed method should work. You're trying to maximize a quadratic form on a vector space (namely the $(n-1)$-dimensional subspace of ${\mathbb R}^n$ given by the equation $\sum_{i=1}^n x_i = 0$) restricted to vectors of length 1 (that's the effect of the second constraint). The answer is going to be related to the dominant eigenvalue of the corresponding matrix on that (sub)space.

-

Some experimentation suggests that for reasonably sized $n$, $$x_i = \sqrt{\frac{2}{n}}\cos\left(2\pi\frac{ i}{n}\right)$$ works well, and gives $\sum\limits_{i=1}^nx_ix_{i+1}$ slightly above $1-\frac{20}{\; n^2}$. Clearly there are more solutions with a different phase.

-
To be exact, $\sum\limits_{i=1}^nx_ix_{i+1}=\cos\left(\frac{2\pi}{n}\right)$ – robjohn Nov 30 '11 at 8:13
It now looks to me as if you can add a constant term $k$ to give $x_i = \sqrt{\frac{2}{n}}\cos\left(k+2\pi\frac{ i}{n}\right)$ – Henry Nov 30 '11 at 9:14
Indeed, that will work. – robjohn Nov 30 '11 at 9:39

Using the Cauchy-Schwarz inequality we obtain the upper bound

$$\left|\sum_{i=1}^{n} x_i x_{i+1}\right| \leq \sum_{i=1}^{n} x_i^2 \sum_{i=1}^{n} x_{i+1}^2 = 1\cdot 1 = 1.$$

Therefore the maximum of the sum is less than or equal to 1. All we need to do to finish this off is to exhibit a sequence of numbers $\{x_1,x_2,\dots,x_n\}$ that satisfies the conditions and attains the maximum. I am finding it somewhat tricky to define such a sequence restraining the terms to the real numbers. I will edit my answer when/if I find one.

-
You will not find equality as to do so you would need $x_{i+1}$ to be positively linearly dependnet on $x_i$, which is inconsistent with the other two constraints. – Henry Nov 30 '11 at 8:39