Maximization over vectors (seen as column matrices) I am trying to solve the following question:
 $$\text{Maximize } f(x_1,x_2,\ldots, x_n)=2\sum\limits_{i=1}^n x_i^t A x_i+\sum\limits_{i=1}^{n-1}\sum\limits_{j>i}^n (x_i^tAx_j+x_j^tAx_i)$$ subject to
$$x_i^t x_j=\left\{\begin{array}{cc}
                       1&~i=j \\
                       -\frac{1}{n}&~i\ne j
                     \end{array}\right.$$
 where $x_i$'s are column vectors ($m\times1$ matrices) with real entries and A is an $m\times m$ $(n<m)$ real symmetric matrix.
From some source, I know the answer as $$f_\max=\frac{n+1}n \sum\limits_{i=1}^n\lambda_i^\downarrow,$$ $\lambda_i^\downarrow$ being the eigenvalues of $A$ sorted in non-increasing order (counting multiplicity). But I am unable to prove it. I will appreciate any help (preferably with established matrix inequality, or Lagrange's multiplier method). 
 A: Why Lagrange multipliers? Your maximization problem can be solved in a rather straightforward manner using some standard tricks in matrix theory. Let $e=\frac1{\sqrt{n}}(1,\ldots,1)^T\in\mathbb{R}^n$ and $X=(x_1,\ldots,x_n)\in M_{m,n}(\mathbb{R})$ (hence $X$ is "tall" and $X^T$ is "wide"). The problem can be formulated as maximizing
$$
f(X)=\textrm{tr}(X^TAX)+ne^TX^TAXe=\textrm{tr}\left((I+nee^T)X^TAX\right)
$$
subject to the constraint $X^TX=\frac{n+1}{n}I-ee^T$.
The eigenvalues of $X^TX$ are $\frac{n+1}{n}$ (with multiplicities $n-1$) and $\frac{1}{n}$ (with $e$ being an eigenvector). Pick any orthogonal matrix $V$ whose last column is $e$. Then every $X$ that satisfies $X^TX=\frac{n+1}{n}I-ee^T$ can be written as $X=U\Sigma V^T$, where $U$ is some $m\times m$ orthogonal matrix, $\Sigma$ is the $m\times n$ (tall) diagonal matrix with diagonal $\left(\sqrt{\frac{n+1}{n}},\ldots,\sqrt{\frac{n+1}{n}},\sqrt{\frac{1}{n}}\right)$, and $V$ is an $n\times n$ orthogonal matrix. Now let $e_n=(0,\ldots,0,1)^T\in\mathbb{R}^n$. Then
$$
\begin{align}
\Sigma V^T(I+nee^T)V\Sigma^T &= \Sigma\left[I+n(V^Te)(e^TV)\right]\Sigma^T \\
&= \Sigma(I+ne_ne_n^T)\Sigma^T \\
&=\textrm{diag}\left(\underbrace{\frac{n+1}{n},\ldots,\frac{n+1}{n}}_{n \textrm{ entries}},\ \underbrace{0,\ldots,0}_{m-n \textrm{ entries}}\right)
= D\quad\textrm{(say)}.
\end{align}
$$
Hence
$$
\begin{align}
f(X)&=\textrm{tr}\left((I+nee^T)X^TAX\right)\\
&=\textrm{tr}\left((I+nee^T)V\Sigma^T U^TAU\Sigma V^T\right)\\
&=\textrm{tr}\left(\Sigma V^T(I+nee^T)V\Sigma^T U^TAU\right)\\
&=\textrm{tr}\left(DU^TAU\right)
\end{align}
$$
and the maximum of $f$ occurs when $U^TAU$ is a diagonal matrix whose diagonal entries are in descending order. Thus the answer follows.
A: This is not an answer but a reformulation of the question. As robjohn stated, the question becomes: Maximize $f:\mathbb{M}^{m\times n}\mapsto \mathbb{R}$ such that
$$
f(X) = \operatorname{tr}(X^TAX) + \underbrace{u^TAu}_{\in\mathbb{R}}
$$
This can be combined into
$$
\operatorname{tr}(X^TAX) + \operatorname{tr}(u^TAu) = \operatorname{tr}\left(\begin{bmatrix}X&u\end{bmatrix}^T A  \begin{bmatrix} X &u\end{bmatrix} \right) = \operatorname{tr}\left(\pmatrix{I &\mathbf{1}}^TX^TAX\pmatrix{I &\mathbf{1}}\right)
$$
where $I$ is the identity matrix and $\mathbf{1}$ is the all-ones vector. You might want to check these lecture notes page 123. I would try something similar by myself but I am burned out and I need to rest. I will edit later if I can come with anything.
