14
$\begingroup$

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?

$\endgroup$

closed as off-topic by Johannes Hahn, Mark Sapir, David Handelman, Chris Godsil, Ben McKay Apr 28 '18 at 6:36

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Mark Sapir, David Handelman, Chris Godsil, Ben McKay
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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$ – Suvrit Mar 30 '18 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 Weaver Mar 30 '18 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$ – Suvrit Mar 30 '18 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 Weaver Mar 31 '18 at 5:22
18
$\begingroup$

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.

$\endgroup$
17
$\begingroup$

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.

$\endgroup$
  • 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$ – Tobias Fritz Mar 30 '18 at 16:21
  • $\begingroup$ Can you give a reference to the proof of von Neumann's theorem? $\endgroup$ – Piotr Hajlasz Mar 30 '18 at 21:06
  • $\begingroup$ @PiotrHajlasz Please see the wikipedia link in my comment to the OP. $\endgroup$ – Suvrit Mar 30 '18 at 23:06
11
$\begingroup$

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

$\endgroup$
9
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

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