# Proving a basic trace inequality

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.

-
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? –  cardinal Jan 2 '12 at 19:21
(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. –  okintheory Jan 2 '12 at 22:13
A link to the paper would be a nice addition. :) –  cardinal Jan 2 '12 at 22:33
renyi.hu/~petz/pdf/64.pdf –  okintheory Jan 2 '12 at 22:40
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. –  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.


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) \> .$$

-
That's great, thanks. –  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.

-