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

• Just checking; does $$f(x_1,x_2,\dots,x_n)=\sum_{i=1}^nx_i^tAx_i+u^tAu$$ where $u=x_1+x_2+\dots+x_n$?
– robjohn
Oct 4, 2011 at 21:15
• yes, it is. Actually, I have expanded the sum...
– Tapu
Oct 4, 2011 at 21:26
• This looks a lot like an equation I got when I was doing a least squares regression for a rigid rotation. If that is what you are doing, you might want to take a look at something I wrote up for sci.math.
– robjohn
Oct 4, 2011 at 22:55

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