Maximization over vectors (seen as column matrices)

Question

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

Answer 1

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.

Answer 2

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.