11
$\begingroup$

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.

  • 0
    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.2011-11-30

6 Answers 6

11

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.

Answer:

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

5

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.

  • 0
    Last night I sat down and you can explicitly show that the characteristic polynomial of $\frac{1}{2}M_n$ satisfies the second Chebychev recurrence by expanding the determinant along rows and columns a few times. The roots are known, as J.M. says. As Henry says, the eigenspace with eigenvalue of $1$ for $\frac{1}{2}M_n$ is not under consideration, as that space is orthogonal to the constraint that $\sum x_i=0$.2011-11-30
2

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

1

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.

1

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.

  • 0
    Indeed, that will work.2011-11-30
0

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.

  • 0
    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.2011-11-30