1
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ This is surely a homework or exam problem. It's not appropriate here, so I'm voting to close. $\endgroup$ Dec 12, 2012 at 13:51
  • $\begingroup$ @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! $\endgroup$
    – ppyang
    Dec 13, 2012 at 13:43

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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