Prove $\max_X tr(X^TAX) = $ k largest eigenvalues of $A$ for real, symmetric $A$ and $X^TX=I$

Question

I know how to prove this if $X$ is a vector (eigendecomposition with orthogonal eigenvectors, picking the largest eigenvalue), but I'm not sure how to proceed if $X$ is a matrix. Say, $X \in \mathbb{R}^{n \times k}, A \in \mathbb{R}^{n \times n}$. The book I'm reading suggests a proof by induction, but I don't know how the induction step would work here.

Answer 1

It is more convenient to write as $\operatorname{tr} (Y AY^T)$ where $Y Y^T = I$.

Since $A$ is symmetric we can write $Q^T A Q = \Lambda$ for some orthogonal $Q$ and diagonal $\Lambda$. If $P$ is a permutation matrix, then we have $P^T Q^T A Q P = P^T \Lambda P$. This is a diagonal matrix whose entries (the eigenvalues of $A$) are permuted by $P$.

Note that $Y P^T Q^T Q P Y = I$, hence we can write $\max_{Y Y^T =I} \operatorname{tr} (Y AY^T) = \max_{Y Y^T =I, P \text{ permutation}} \operatorname{tr} (Y P^T \Lambda P Y^T)$

We can write $YP^T \Lambda PY^T = \sum_{i=1}^k [P^T\Lambda P]_{ii} Y_i Y_i^T$, where $Y_i$ is the $i$th column of $Y$, and $\operatorname{tr} (Y P^T \Lambda P Y^T) = \sum_{i=1}^k [P^T \Lambda P]_{ii} \operatorname{tr} ( Y_i Y_i^T ) = \sum_{i=1}^k [P^T \Lambda P]_{ii} \operatorname{tr} ( Y_i^T Y_i ) =\sum_{i=1}^k [P^T \Lambda P]_{ii} $.

In particular, if the sum of the $k$ largest eigenvalues is $S$, we see that $\operatorname{tr} (Y AY^T) \le S$ and if we choose $P$ appropriately we get equality.