What's the maximum of $w'Aw$?

Question

Let $A$ be a $N\times N$ real symmetric matrix, $\{v_i: i = 1,\cdots, K\}$ be a set of orthonormal vectors in $\mathbb{R}^N$, and $w = \sum_{k=0}^Kv_k$, what is the maximum of $w'Aw$?

Intuitively my guess is $w'Aw \le \sum_{k=1}^K\lambda_k$, where $\{\lambda_k: k = 1,\cdots N\}$ is the set of eigevalues of $A$, in descending order.

Where $K=1$, it is trivial to prove this statement. But when $K > 1$, the cross terms made the analysis quite messy and I couldn't get to the desired conclusion.

Can anyone either prove it or disprove it?

Answer 1

The claim is false for $K=2$. Consider $w=u_m+u_{m-1}$ with $u_m$ an unitary eigenvector for the greater eigenvalue $\lambda_m$ and $u_{m-1}$ another unitary vector but for the greater without $\lambda_m$

$w'Aw=\lambda_m+\lambda_{m-1}$

Consider now $n_1+n_2=ku_m$ with $n_1,n_2$ unitary and mutually orthogonal and $u_m$ as before. Then

$\Vert ku_m\Vert^2=(n_1+n_2)·(n_1+n_2)=\Vert n_1\Vert^2+\Vert n_2\Vert^2+2n_1·n_2=2+0\implies$

$ k=\sqrt{2}$

This time we have: $w'Aw=2\lambda_m$

If the max for any $w$ is $\Vert w\Vert^2\lambda_m$, then the max for that configuration is $K\lambda_m$

Answer 2

Since $A$ is symmetric the maximum of the quadratic form $w'Aw$ is equal to $\|w\|^2\lambda_m$, where $\lambda_m$ the maximum eigenvalue of $A$.

Why?

Since $A$ is symmetric, the spectral theorem guarantees that it has a basis of eigenvectors, say $\{v_a\}_a$, corresponding to $N$ distinct eigenvalues. Since mutual eigenvectors are orthogonal, we can assume this basis is orthonormal. Writing $w =\|w\|\sum_aw_av_a$, where we have $\sum_aw_a^2 = 1$, we find $$ w'Aw = \|w\|^2(\sum_aw_av_a)'A(\sum_bw_bv_b) = \|w\|^2\sum_a\sum_bw_aw_b\lambda_bv_a'v_b, $$ which is $$ \|w\|^2\sum_aw_a^2\lambda_a $$ by the orthonormality of the eigenbasis. Since the $w_a$ will always form a unit vector, the maximum value of the sum has to be equal to one times the maximum eigenvalue, the latter of which must exist because the eigenvalues of $A$ are distinct. Thus the claim follows.