4
$\begingroup$

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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Can anything explicit be said about the minimum? $\endgroup$
    – AmorFati
    Commented Sep 29, 2021 at 1:02
  • $\begingroup$ @AmorFati The minimum of what? $\endgroup$
    – user1551
    Commented Sep 29, 2021 at 4:43
  • $\begingroup$ $$\min_{Q Q^T = I} \text{trace}(DQ^T SQ).$$ $\endgroup$
    – AmorFati
    Commented Sep 29, 2021 at 5:32
  • $\begingroup$ @AmorFati The same argument still applies. Thus $\min_{QQ^T=I}\operatorname{trace}(DQ^TSQ)=\sum_id_is_{\sigma(i)}$ for some permutation $\sigma$. By the rearrangement inequality, the optimal $\sigma$ is the one that reverse the order of the $s_i$s. In other words, $\min_{QQ^T=I}\operatorname{trace}(DQ^TSQ)=\sum_id_is_{n+1-i}$. $\endgroup$
    – user1551
    Commented Sep 29, 2021 at 6:55
  • $\begingroup$ Of course, the minimum of a linear function still occurs at the extrema of the compact set. Sorry about that, thanks for clarifying though :) $\endgroup$
    – AmorFati
    Commented Sep 29, 2021 at 7:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .