Prove $\max_X tr(X^TAX) = $ k largest eigenvalues of $A$ for real, symmetric $A$ and $X^TX=I$ 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.
 A: 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.
