Constraint optimization problem for any dimensionality $n>1$. I am going to post a particular example for the sake of clarity.

One needs to maximize a real function 
$F = a_1a_2 + a_2a_3 + \cdots + a_{n -
> 1}a_n  + a_na_1;$
with active constraints
$h_1 = a_1 + a_2 + \cdots + a_n = 0;$
$h_2 = a_1^2 + a_2^2 + \cdots +a_n^2 =
> 1;$

The gradients in question
$\nabla F = (a_2+a_n,a_3+a_1, \ldots , a_{n-2}+a_n,a_{n-1}+a_1);$
$\nabla h_1 = (1, 1, \ldots ,1, 1);$
$\nabla h_2 = (2a_1,2a_2,\ldots , 2a_{n-1}, 2a_n);$
Because of Kuhn–Tucker conditions it is reasonable to write $\nabla F$ in terms of $\nabla h_1$ and $\nabla h_1$ 
$$\begin{cases}
a_2+a_n = \lambda_1 + 2\lambda_2a_1; \\\
a_3+a_1 = \lambda_1 + 2\lambda_2a_2; \\\
a_4+a_2 = \lambda_1 + 2\lambda_2a_3; \\\
\ldots \\\
a_{n-2} + a_n = \lambda_1 + 2\lambda_2 a_{n-1}; \\\
a_{n-1} + a_1 = \lambda_1 + 2\lambda_2 a_n;
\end{cases}$$
$$\begin{pmatrix}
2\lambda_2 & -1 & 0 & 0 & \ldots & 0 & -1 \\\
-1 & 2\lambda_2 & -1 & 0 & \ldots & 0 & 0 \\\
0 & -1 & 2\lambda_2 & -1 & \ldots &0 & 0 \\\
\ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\\
0 &0 &0 & 0 & \ldots & 2\lambda_2 & -1 \\\
-1 &0 &0 & 0 & \ldots & -1 & 2\lambda_2
\end{pmatrix}
\begin{pmatrix}
a_1 \\\ a_2 \\\ a_3 \\\ \vdots \\\ a_{n-1} \\\ a_n
\end{pmatrix} =
- \lambda_1\begin{pmatrix}
1 \\\ 1 \\\ 1 \\\ \vdots \\\ 1 \\\ 1
\end{pmatrix}
$$
By adding up all equations it follows that $\lambda_1 = 0$ so it's a matter of nullspaces.
However is this attempt fruitless? I'm getting nowhere, so at this point references to similar problems would also be appreciated.

A few remarks:


*

*Case $n=2$ is somewhat trivial, for
all valid combinations (there are
two of them) $F = -1$.

*Case $n=3$ brings up the same
problem since for all valid
combinations $F = -1/2$.

*$F \le 1$ is an exact upper bound (it follows from properties of scalar multiplication and constructing silly yet valid combinations for sufficiently large $n$).

 A: Since you asked so nicely, here we go: Let $a_k = \sum_{q=0}^{n-1}b_q \exp(2\pi i k q/n)$ (where $b_q=b_{n-q}^*$ by realness). Up to normalization factors I have dropped, $F=\sum_{q=0}^{n-1}|b_q|^2\exp(2\pi i q/n)$ and your constraints give $\sum_{q=0}^{n-1} |b_q|^2 = 1$ and $b_0=0$. So it is easy now to see that $F$ is maximum when $b_1=b_{n-1}=\tfrac{1}{\sqrt{2}}$. In real space, $a_k = C \cos(2\pi k/n+\phi)$.
A: Here's an alternative way of proving (what Yoav already did), but using different notation.
Let us first write the optimization problem in matrix form. First, define
\begin{equation*}
  d =
  \begin{bmatrix}
    0 & 1 & & \cdots &0\\\\
    0 & 0 & 1 & \\\\
    \vdots &  & \ddots & \\\\
    0 & 0 & \cdots & &1\\\\
    1 & \cdots &&& 0
  \end{bmatrix}.
\end{equation*}
The optimization problem at hand is
\begin{equation*}
  \max a^Tda\quad \text{s.t.}\ a^T1 = 0, a^Ta=1.
\end{equation*}
Writing $D=(d+d^T)/2$, we see that $a^Tda = a^TDa$. So we may actually solve the problem
\begin{equation*}
  \max a^TDa\quad \text{s.t.}\ a^T1 = 0, a^Ta=1.
\end{equation*}
If we pick $a$ to be the eigenvector corresponding to the second largest eigenvalue of $D$, we see that it satisfies $a^T1=0$ and $a^Ta=1$ (the first largest does not sum to zero).
(to see the $a^T1=0$ part is where we use the DFT insight used by Yoav)
A: I tried a mathematical experiment, using the DirectSearch package http://www.maplesoft.com/applications/view.aspx?SID=101333 , and obtained $\max f = 0.809126470893692 $ for $a_1 = .243175515810934, a_2 = .417367431111117, a_3 = .432125841032896,$ $ a_4 = .281815795280440, a_5= 0.239770895080612e-1, a_6 = -.243248539429584,$ $ a_7 = -.417366236874912, a_8 = -.432123102835062, a_9 = -.281798611220396,$ $ a_{10} = -0.0239247832264742$ in the case $n=10$. The optimal solution is not unique.
