Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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 '11 at 21:15
    
yes, it is. Actually, I have expanded the sum... –  Tapu Oct 4 '11 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 '11 at 22:55

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
Please let me verify (and how it matches with my original problem)...and I'll then accept your answer. Thanks in advance! –  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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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