Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Problem

Supposing that $A$ is a symmetric real matrix and $\{\mathbf{w}\_i\}_{i=1}^n$ is any orthogonal basis on $\mathbb{R}^n$ such that $W^\top W=WW^\top=\mathbf{I}_n$ where $W=\left[\mathbf{w}_1\;\mathbf{w}_2\;\ldots\;\mathbf{w}_n\right]$, what is the maximum of $\sum\_{i=1}^n{\left(\mathbf{w}\_i^\top A\mathbf{w}_i\right)^2}$?

To be concise, we can reformulate it as the following optimization problem: \begin{equation} \begin{split} \max_W&S(W)=\sum\_{i=1}^n{\left(\mathbf{w}\_i^\top A\mathbf{w}_i\right)^2}\\\ \mathrm{s.t.}\\,&W^\top W=WW^\top=\mathbf{I}\_n, \end{split} \end{equation} where $W=\left[\mathbf{w}_1\;\mathbf{w}_2\;\ldots\;\mathbf{w}_n\right]$.

With help of MATLAB, I found that the maximum of $S(W)$ is always obtained when $W=\bar{W}$ such that $\{\mathbf{w}\_i\}\_{i=1}^n$ are the eigenvectors of $A$ and the optimal value is $S(\bar{W})=\sum\_{i=1}^n{\lambda_i^2}=\|A\|_\mathrm{F}^2$. I had ever given a proof but recently I found it was wrong. However, I think the conclusion should be correct. The constraint that $W$ is orthogonal makes the problem difficult.

Since it is obvious that the assumed optimal value $S(W)=\|A\|_\mathrm{F}^2$ is always obtained by choosing $W$ to be the eigenvectors of $A$, if we can prove that $S(W)\leq\|A\|\_\mathrm{F}^2$ for $\forall W$, the problem is solved. However, this seems to be also difficult.

Comments

Actually, the problem may be furthermore simplified as follows.

Assume the spectral decomposition of $A$ is $A=V\Lambda V^\top$ and let $\tilde{W}=V^\top W$ (or $\tilde{\mathbf{w}}_i=V^\top\mathbf{w}_i$), then we have $S(W)=\sum\_{i=1}^n{\left(\tilde{\mathbf{w}}_i^\top\Lambda\tilde{\mathbf{w}}_i\right)^2}$ where $\Lambda$ is a diagonal matrix contaning the eigenvalues of $A$.

Since $V$ is orthogonal, we can solve for $\tilde{W}$ instead of $W$. Then the problem turns to be \begin{equation} \begin{split} \max_\tilde{W}&S(\tilde{W}) =\sum\_{i=1}^n{\left(\tilde{\mathbf{w}}\_i^\top \Lambda\tilde{\mathbf{w}}_i\right)^2} =\sum\_{i=1}^n{\left(\sum\_j^n{\lambda_j\tilde{w}_{ij}^2}\right)^2}\\\ \mathrm{s.t.}\\,&\tilde{W}^\top\tilde{W}=\tilde{W}\tilde{W}^\top=\mathbf{I}\_n, \end{split} \end{equation} where $\Lambda$ is diagonal and $\tilde{\mathbf{w}}\_i=\left[\tilde{w}\_{i1}\;\tilde{w}\_{i2}\;\ldots\;\tilde{w}\_{in}\right]^\top$.

However, this problem seems to be also difficult to solve. Please help me to give some suggestions about this problem.

Thank you very much!

share|improve this question
    
This is surely a homework or exam problem. It's not appropriate here, so I'm voting to close. –  Robert Bryant Dec 12 '12 at 13:51
    
@Robert Bryant, I am sorry to trouble you all with this simple question and I have solved it. However, I have to say that this is indeed not my homework or exam problem. I will think more by myself before posting the question next time. Thank you very much! –  ppyang Dec 13 '12 at 13:43
add comment

1 Answer

I am sorry to trouble you all and I found the answer to this question finally which is very simple.

Due to the orthogonality of $\tilde{W}$, it is straightforward that $\sum\_{i=1}^n{\tilde{w}\_{ij}^2}=1,\forall j$ and $\sum\_{j=1}^n{\tilde{w}\_{ij}^2}=1,\forall i$.

Then for $\forall i$, from the convexity of $f(x)=x^2$, we have \begin{equation*} \left(\sum\_{j=1}^n{\tilde{w}\_{ij}^2\lambda\_j}\right)^2\leq\sum\_{j=1}^n{\tilde{w}\_{ij}^2\lambda\_j^2}, \end{equation*} and thus \begin{equation*} S(\tilde{W}) =\sum\_{i=1}^n{\left(\sum\_{j=1}^n{\lambda_j\tilde{w}\_{ij}^2}\right)^2} \leq\sum\_{i=1}^n{\sum\_{j=1}^n{\tilde{w}\_{ij}^2\lambda\_j^2}} =\sum\_{j=1}^n{\sum\_{i=1}^n{\tilde{w}\_{ij}^2\lambda\_j^2}} =\sum\_{j=1}^n{\lambda\_j^2} =\|A\|\_\mathrm{F}^2 \end{equation*}

Since $\|A\|\_\mathrm{F}^2$ provides an upper bound for $S(\tilde{W})$ and this value is always obtainable by choosing $\left\{\mathrm{w}_i\right\}\_{i=1}^n$ as the eigenvectors of $A$, this is the maximum value.

share|improve this answer
add comment

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.