Let $X\in M(\mathbb R)$ and $k\in\mathbb Z^+$, show: $$\left| \operatorname{tr}(X^{2k})\right| \leq \operatorname{tr}((XX^T)^k)$$

I can do the $k=1$ case, but then I'm stumped.

  • $\begingroup$ Two questions to help guide a response: (1) What tools are you familiar with and willing to use, e.g., particular matrix decompositions, and (2) Is this homework? $\endgroup$
    – cardinal
    Jan 2 '12 at 19:21
  • $\begingroup$ (2) This isn't homework. The inequality was used in a paper I'm reading, but the author didn't prove it. (1) I'm familiar with diagonalisation, SVD, LU, and QR decomposition and happy to learn more, especially if you can give a good reference. $\endgroup$
    – okintheory
    Jan 2 '12 at 22:13
  • $\begingroup$ A link to the paper would be a nice addition. :) $\endgroup$
    – cardinal
    Jan 2 '12 at 22:33
  • $\begingroup$ renyi.hu/~petz/pdf/64.pdf $\endgroup$
    – okintheory
    Jan 2 '12 at 22:40
  • $\begingroup$ I was looking for a proof of the Golden-Thompson inequality. It's on pages 3-5 of the paper given in the link above. $\endgroup$
    – okintheory
    Jan 2 '12 at 22:42

Perhaps this uses stronger tools that you were hoping for, but below is a rough sketch of an argument.

Consider the Schur decomposition of $\newcommand{\m}{\mathbf}\newcommand{\X}{\m X}\newcommand{\U}{\m U} \newcommand{\T}{\m T} \newcommand{\tr}{\mathrm{tr}} \X$. That is, $\X = \U \T \U^*$ where $\U$ is a unitary matrix and $\T = (t_{ij})$ is an upper triangular matrix with (possibly) complex entries. Then $$ \X^{2k} = (\U \T \U^*)^{2k} = \U \T^{2k} \U^* \>. $$ Hence $$ \big|\tr(\X^{2k})\big| = \big|\tr(\U^* \U \T^{2k})\big| = \big|\tr(\T^{2k})\big| = \bigg| \sum_i t_{ii}^{2k} \bigg| \> . $$

Now, consider $\X \X^T$. Since $\X$ is real-valued, then $\X^T = \X^*$ and so $\X \X^T = \X \X^* = \U \T \T^* \U^*$. Hence, $$ (\X \X^T)^k = \U (\T \T^*)^k \U^* \>. $$

Let $\newcommand{\A}{\m A}\A = \T \T^* = (a_{ij})$. Note that $a_{ii} \geq |t_{ii}|^2$ with at least one of the inequalities being strict unless $\T$ is, in fact, diagonal.

Then, $$ \tr((\X \X^T)^k) = \tr(\U^* \U \A^k) = \tr(\A^k) \>. $$

To conclude, use the following lemma, for which I leave the proof as, hopefully, an easy exercise (unless I've made a mistake).

Lemma: Let $\A = (a_{ij})$ be any positive semidefinite hermitian matrix. Show that $(\A^k)_{ii} \geq a_{ii}^k$.

(Hint: Prove the stronger result that for any unit vector $\newcommand{\u}{\m u}\u$, we have $\u^* \A^k \u \geq (\u^* \A \u)^k$. The eigendecomposition of $\A$ and Jensen's inequality should suffice.)

The triangle inequality then yields the desired result since $$ \bigg| \sum_i t_{ii}^{2k} \bigg| \leq \sum_i |t_{ii}|^{2k} \leq \tr(\A^k) \> . $$

  • $\begingroup$ That's great, thanks. $\endgroup$
    – okintheory
    Jan 2 '12 at 23:18

Let the (possibly generalized) eigenvalues of $X$ be $\lambda_1$, $\lambda_2$, ..., $\lambda_n$. Let the eigenvalues of $XX^T$ be $\mu_1^2$, ..., $\mu_n^2$. Note that $X X^T$ is positive definite, so the $\mu_i^2$ are positive reals, and we choose the $\mu_i$'s to be the positive square roots. The $\mu_i$ are called the singular values of $X$. Let $\ell_i = \log |\lambda_i|$ and let $m_i = \log \mu_i$.

Then $$\mathrm{Tr}(X^{2k}) = \sum e^{2 k \ell_i} \ \mathrm{and} \ \mathrm{Tr}((X X^T)^{k}) = \sum e^{2k m_i}.$$

We now use Weyl's inequality (see, for example, Theorem 4 here). The statement in the linked file is clearly equivalent to the following:

Order the $m_i$ so that $m_1 \geq m_2 \geq \cdots \geq m_n$. Then, for any subset $\{ i_1, i_2, \ldots, i_k \}$ of $\{1,2,\ldots, n\}$, we have $\ell_{i_1} + \ell_{i_2} + \cdots + \ell_{i_k} \leq m_1 + m_2 + \cdots + m_k$ for $1 \leq k \leq n$.

For our purposes, a more convenient statement of Weyl's inequality is the following:

Let $P$ be the convex hull in $\mathbb{R}^n$ of the $n!$ permutations of $(m_1, \ldots, m_n)$. Then $(\ell_1, \ldots, \ell_n)$ is in $P$.

These two descriptions are equivalent because the intersection of the inequalities in the first statement is the convex hull in the second statement. To see this, note that the first one is the facet description of a permutahedron and the second is the vertex description.

OK, now we finish the proof. The function $f: (x_1, \ldots, x_n) \mapsto \sum e^{2k x_i}$ is a convex function on $\mathbb{R}^n$. So the maximum of $f$, on $P$, must occur at a vertex of $P$. At all of the vertices of $P$, the function $f$ has the same value, $\sum e^{2k m_i}$. In particular, this value must be greater than $\sum e^{2k \ell_i}$. So $$\sum e^{2k m_i} \geq \sum e^{2k \ell_i}$$ as desired.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.