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.

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.

share|improve this question
    
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

6 Answers 6

up vote 11 down vote accepted

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

share|improve this answer

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.

share|improve this answer
    
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)$.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
1  
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.

share|improve this answer
    
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

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.