Let the vector of eigenvalues of a $n\times n$ matrix $U$
is denoted by
$$
\lambda(U)=\big(\lambda_1(U),\lambda_2(U),\ldots,\lambda_i(U),\ldots\lambda_{n-1}(U),\lambda_n(U)\big)^T.
$$
where the eigenvalues are ordered as $\lambda_1(U)\leq\lambda_2(U)\leq\ldots\leq\lambda_i(U)\leq\ldots\lambda_{n-1}(U)\leq\lambda_n(U)$.
I would like to prove ( or get a counterexample) the following inequality for symmetric matrices $X$ and $Y$
$$
\mbox{trace}(XY)\leq \lambda(X)^T\lambda(Y).
$$
Thanks in advance.
Best Answer
The proof is essentially the same as in the case where $X$ and $Y$ are positive semi-definite.
Let $d_1\le\ldots\le d_n$ and $s_1\le\ldots\le s_n$ be the eigenvalues of $X$ and $Y$ respectively and let $D=\operatorname{diag}(d_1,\ldots,d_n),\ S=\operatorname{diag}(s_1,\ldots,s_n)$. Then $\operatorname{trace}(XY)=\operatorname{trace}(DQ^TSQ)$ for some real orthogonal matrix $Q$. Note that the Hadamard product $Q\circ Q=(q_{ij}^2)$ is a doubly stochastic matrix. Therefore \begin{align} \max_{QQ^T=I} \operatorname{trace}(DQ^TSQ) &=\max_{QQ^T=I} \sum_{i,j}s_id_jq_{ij}^2\\ &\le\max_M \sum_{i,j}s_id_jm_{ij};\ M=(m_{ij}) \textrm{ is doubly stochastic}.\tag{1} \end{align} As $\sum_{i,j}s_id_jm_{ij}$ is a linear function in $M$ and the set of all doubly stochastic matrices is compact and convex, $\max\limits_M \sum_{i,j}s_id_jm_{ij}$ occurs at an extreme point of this convex set. By Birkhoff's theorem, the extreme points of doubly stochastic matrices are exactly those permutation matrices. Since permutation matrices are real orthogonal, it follows that equality holds in $(1)$ and $\max\limits_{QQ^T=I} \operatorname{trace}(DQ^TSQ)=\max\limits_\sigma\sum_i d_is_{\sigma(i)}$, where $\sigma$ runs over all permutations of the indices $1,2,\ldots,n$. However, by mathematical induction on $n$, one can prove that $\sum_i d_is_{\sigma(i)}\le\sum_i d_is_i$ (note that the base case here is $n=2$, not $n=1$). Hence the assertion follows.