The trace of a symmetric matrix

Question

If A is an $n\times n$ symmetric matrix with eigenvalues $c_1 \ge ... \ge c_n$, and $U$ is an $ n \times k$ semi-orthogonal matrix, with $ k \le n$, how to prove that $\text{tr}(U^TAU) \le \sum\limits_{i=1}^kc_i$ ?

Answer 1

If you want a short proof using existing theorems, perform a singular value decomposition on $U$. Then the problem boils down to proving that whenever $B$ is a real symmetric matrix with eigenvalues $c_1\ge c_2\ge\cdots\ge c_n$, the trace of the leading principal $k\times k$ submatrix of $B$ is less than or equal to $\sum_{i=1}^k c_k$. Now this is a direct consequence of the interlacing inequality for the eigenvalues of bordered matrices (see, e.g. theorem 4.3.8 of Horn and Johnson, Matrix Analysis, 1/e, Cambridge University Press, 1985, pp.185-186).

Inequalities of this sort are usually proved using Courant-Fischer minimax principle. I'm not sure if there is any short proof of your statement from scratch.

Answer 2

Another proof similar to @user1551's without using the interlacing inequality for the eigenvalues of bordered matrices.

Since A can be diagonalized, we can harmlessly assume A is a diagonal matrix. Thus $ \text{tr}(U^TAU) = \sum_ic_iu_{i*}u_{i*}^T$.

Because $0\le u_{i*}u_{i*}^T \le 1$ and $\sum_iu_{i*}u_{i*}^T = \sum_iu_{*i}^Tu_{*i} = k$, it is easy to see that $\sum_ic_iu_{i*}u_{i*}^T \le \sum_{i=1}^{k}c_i$ .