For any nonnegative semidefinite matrix $A$ and any matrix $B$, we have
$$\mbox{tr} (AB) \le \mbox{tr} (A) \, \|B\|$$
where $\mbox{tr}(\cdot)$ is the trace and $\|\cdot\|$ is the operator norm. How to prove this?
$\begingroup$
$\endgroup$
4
-
6$\begingroup$ More generally (i.e., also more general than the two answers below), have a look at von Neumann's trace inequality which implies the above one as a special case: en.wikipedia.org/wiki/… $\endgroup$– SuvritCommented Mar 30, 2018 at 13:02
-
15$\begingroup$ This is a standard fact that appears in many textbooks. I don't see how it is research level. $\endgroup$– Nik WeaverCommented Mar 30, 2018 at 17:25
-
$\begingroup$ @NikWeaver I totally agree with you, which is why I left a comment to it (but then seeing that others deemed it worthy of an answer, I elevated my comment to an answer); this one is likely not even the only question on MO that can be answered by von Neumann's inequality, there's been several others in the past I think. Oh well.... $\endgroup$– SuvritCommented Mar 30, 2018 at 23:09
-
1$\begingroup$ @Suvrit Yes, even though the question isn't research level I don't object too strongly because there can still be interesting answers, such as yours. $\endgroup$– Nik WeaverCommented Mar 31, 2018 at 5:22
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
For hermitian $B$, the inequality is very easy to prove: use that $\|B\| - B$ is positive semidefinite together with the fact that the product of two positive semidefinite matrices has nonnegative trace. This gives $\mathrm{tr}(A(\|B\| - B)) \geq 0$, from which the inequality follows immediately.
For general $B$, we can therefore argue that
$$\mathrm{Re}(\mathrm{tr}(AB)) = \tfrac{1}{2}\mathrm{tr}(A(B + B^*))\leq \mathrm{tr}(A)\cdot \tfrac{1}{2}\|B + B^*\| \leq \mathrm{tr}(A) \|B\|.$$
Upon multiplying $B$ by a suitable complex scalar, this implies that
$$|\mathrm{tr}(AB)| \leq \mathrm{tr}(A) \|B\|$$
is true for all positive semidefinite $A$ and any $B$.
I don't have the book at hand right now, but I imagine that this is somewhere to be found in the early chapters of Bhatia's Matrix Analysis.
answered Mar 30, 2018 at 12:02
$\begingroup$
$\endgroup$
3
Expanding my comment into an answer, which offers a more general result.
Theorem (von Neumann). Let $A$ and $B$ be arbitrary $n\times n$ complex matrices. Then, $$|\text{trace}(AB)| \le \sum_{i=1}^n \sigma_i(A)\sigma_i(B),$$ where $\sigma_i(\cdot)$ denotes the $i$-th singular value.
As an immediate corollary we have the OP's result, because for a PSD matrix $A$, $\sigma_i(A)=\lambda_i(A)$.
Corollary. Let $A$ be Hermitian positive semidefinite, and $B$ be arbitrary. Then, $|\text{trace}(AB)| \le \text{trace}(A)\|B\|$, where $\|\cdot\|=\sigma_1(\cdot)$ denotes the operator norm.
Note. Using von Neumann's trace inequality, we can also show the more general version of the OP's question, namely a Hölder inequality: \begin{equation*} |\text{trace}(AB)| \le \langle \sigma(A), \sigma(B)\rangle \le \|\sigma(A)\|_p\|\sigma(B)\|_q = \|A\|_p\|B\|_q, \end{equation*} where $\sigma(A)$ is the vector of singular values, and $\|\cdot\|_p$ denotes the Schatten $p$-norm, and $1/p + 1/q=1$ ($p,q\ge1$). For $p=1$ and $q=\infty$ we recover the OP's question.
-
1$\begingroup$ Great answer! Continuing with the von Neumann theme, it may also be interesting to know that the Hölder inequality, including the case $q=\infty$ discussed here, has been generalized to von Neumann algebras equipped with a normal semifinite trace by Ruskai (projecteuclid.org/euclid.cmp/1103858124). $\endgroup$ Commented Mar 30, 2018 at 16:21
-
$\begingroup$ Can you give a reference to the proof of von Neumann's theorem? $\endgroup$ Commented Mar 30, 2018 at 21:06
-
$\begingroup$ @PiotrHajlasz Please see the wikipedia link in my comment to the OP. $\endgroup$– SuvritCommented Mar 30, 2018 at 23:06
$\begingroup$
$\endgroup$
0
A proof of $$\lambda_n(B)\,{\rm tr}\,A\leq {\rm tr}\,(AB)\leq\lambda_1(B)\,{\rm tr}\,A$$ where $\lambda_n$ is the $n$-th largest eigenvalue of $B$ so $||B||=\lambda_1(B)$ and $A$, $B$ are positive semidefinite $n\times n$ matrices, is given in The design of suboptimal linear time-varying systems (1968). The inequality still holds for $B$ real symmetric and $A$ positive semidefinite, as proven in Trace bounds on the solution of the algebraic matrix Riccati and Lyapunov equation (1986). The restriction of positive semidefinite $A$ cannot be relaxed, as pointed out in Inequalities for the trace of a matrix product (1994).
answered Mar 30, 2018 at 11:38
$\begingroup$
$\endgroup$
We can work in an orthonormal basis in which $A$ is diagonal. In that case the diagonal entries of $AB$ are $a_{ii}b_{ii}$, so $$ tr(AB) \leq|tr(AB)|=\left|\sum a_{ii}b_{ii}\right| \leq \sum a_{ii}|b_{ii}| \leq \sum a_{ii} \|B\|=tr(A)\|B\|. $$
$\begingroup$
$\endgroup$
A more general version of the result Beenakker cites that allows for normal $B$ (not just symmetric):$\newcommand\tr{\operatorname{tr}}\newcommand\E{\mathbb{E}}$
Take $x\sim\mathcal{N}(0,I)$ and recall that $\tr(C) = \E[x^\mathsf{T}Cx]$. If $B = Q \Lambda Q^*$ is unitarily diagonalizable let $\Lambda^{1/2}$ be a (possibly complex) square root of $\Lambda$. Then using the cyclic property of the trace $$ \begin{align} \tr(AB) &= \tr(\Lambda^{1/2} Q^*AQ\Lambda^{1/2})\\ &= \E[(\Lambda^{1/2}x)^\mathsf{T} Q^*AQ (\Lambda^{1/2}x)]\\ &= \sum_{i\neq j} \lambda_i^{1/2}\lambda_j^{1/2}\E[x_ix_j](Q^*AQ)_{ij} + \sum_{i} \lambda_i\E[x_i^2](Q^*AQ)_{ii}\\ &= \sum_{i} \lambda_i(Q^*AQ)_{ii}. \end{align} $$ From here, since $(Q^*AQ)_{ii}\geq 0$ by the PSD condition, it follows that $$\tr(AB) \leq \lambda_{\max}\sum_{i} (P^{-1}A P)_{ii} = \lambda_{\max}\tr(P^{-1}AP) = \lambda_{\max}\tr(A)$$ and $$\tr(AB) \geq \lambda_{\min}\sum_{i} (P^{-1}A P)_{ii} = \lambda_{\min}\tr(P^{-1}AP) = \lambda_{\min}\tr(A)$$ as desired.
