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

  • $\begingroup$ 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$? $\endgroup$ – robjohn Oct 4 '11 at 21:15
  • $\begingroup$ yes, it is. Actually, I have expanded the sum... $\endgroup$ – Tapu Oct 4 '11 at 21:26
  • $\begingroup$ 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. $\endgroup$ – robjohn Oct 4 '11 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.

  • $\begingroup$ Please let me verify (and how it matches with my original problem)...and I'll then accept your answer. Thanks in advance! $\endgroup$ – Tapu Oct 10 '11 at 17:38

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.