Trace-duality bound (source code)

= Trace-duality bound

Let $A$ be a <Hermitian matrix>, $M$ a <positive semidefinite matrix>, and $s\ge0$ with $\operatorname{tr}M\le s$. Then
$$
\operatorname{tr}(MA)\le s\max\{\lambda_{\max}(A),0\}\le s\lVert A\rVert_{\rm op}.
$$
The Hermitian assumption gives real <eigenvalues> and makes this an ordered real inequality.

By the <finite-dimensional spectral theorem>, choose an <orthonormal basis> of <eigenvectors> for $A$. In that <basis>, write the diagonal entries of $M$ as $m_i\ge0$. Then $\operatorname{tr}(MA)=\sum_i m_i\lambda_i$, while $\sum_i m_i=\operatorname{tr}M\le s$. Replacing each $\lambda_i$ by $\max\{\lambda_{\max}(A),0\}$ proves the first bound; the <operator norm> proves the second.

The first bound is optimal. If $A$ has a positive largest <eigenvalue> with unit <eigenvector> $u$, choose $M=suu^*$. If all <eigenvalues> are nonpositive, choose $M=0$.