Proof of Trace Inequalities for Positive Semidefinite Matrices

Routine facts about the matrix product, the trace and the semidefinite ordering are used without comment (Toolkit for AL3).

Let $R=P^{1/2}$ be the positive semidefinite square root of $P$, which exists by Every Positive Semidefinite Matrix Has Exactly One Positive Semidefinite Square Root (i); so $R\in\mathcal{S}(n)$, $R^{\top}=R$ and $RR=P$. We first show that for every $Z\in\mathcal{S}(n)$

$$\operatorname{tr}(PZ)=\sum_{i=1}^{n}(Re_{i})\cdot\bigl(Z(Re_{i})\bigr),$$

where $e_{1},\dots,e_{n}$ are the standard basis vectors of $\mathbb{R}^{n}$.

For any $M\in\mathcal{M}_{n}(\mathbb{R})$ and $i\in[n]$, the $i$-th component of $Me_{i}$ is $M_{ii}$ by Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes (vi), and the dot product of $e_{i}$ with a point is its $i$-th component by Standard Basis Vectors of ℝ^q: Coordinates, Orthonormality and Unit Length (i); hence $M_{ii}=e_{i}\cdot(Me_{i})$, and the trace formula gives $\operatorname{tr}(M)=\sum_{i=1}^{n}e_{i}\cdot(Me_{i})$.

Now $PZ=(RR)Z=R(RZ)$ by Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes (i), so Basic Properties of the Trace (iii), applied with $U=R$ and $V=RZ$, gives $\operatorname{tr}(PZ)=\operatorname{tr}\bigl((RZ)R\bigr)$. For $M=(RZ)R$ we have $Me_{i}=R\bigl(Z(Re_{i})\bigr)$ by the compatibility of the matrix-vector product with the matrix product in Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes (v). Using the symmetry of the dot product (The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite (i)), then Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes (viii) together with $R^{\top}=R$, and the symmetry once more,

$$e_{i}\cdot(Me_{i})=\bigl(R(Z(Re_{i}))\bigr)\cdot e_{i}=\bigl(Z(Re_{i})\bigr)\cdot(R^{\top}e_{i})=(Re_{i})\cdot\bigl(Z(Re_{i})\bigr).$$

Summing over $i$ and using the formula for the trace of $M$ above proves the displayed identity.

If $X$ is positive semidefinite, then every term $(Re_{i})\cdot\bigl(X(Re_{i})\bigr)$ of the identity with $Z=X$ is nonnegative by the definition of positive semidefiniteness, applied at the point $Re_{i}$. Hence $\operatorname{tr}(PX)\ge0$, a finite sum of nonnegative real numbers being nonnegative (Finite Sums in a Commutative Ring and in an Ordered Field: Distributivity, Differences, Telescoping, Constant Terms, Comparison and the Triangle Inequality (vi)), which is (i).

Next let $X',Y'\in\mathcal{S}(n)$ with $X'\preceq Y'$. By the definition of the ordering, applied at the point $z=Re_{i}$, we have $(Re_{i})\cdot\bigl(X'(Re_{i})\bigr)\le(Re_{i})\cdot\bigl(Y'(Re_{i})\bigr)$ for each $i$, and summing the identity for $Z=X'$ and for $Z=Y'$ term by term (Finite Sums in a Commutative Ring and in an Ordered Field: Distributivity, Differences, Telescoping, Constant Terms, Comparison and the Triangle Inequality (v)) gives

$$\operatorname{tr}(PX')\le\operatorname{tr}(PY')\qquad\text{for all }X',Y'\in\mathcal{S}(n)\text{ with }X'\preceq Y'.$$

With $X'=X$ and $Y'=Y$ this is (ii).

Finally, by Eigenvalue, Quadratic-Form and Order Bounds for a Symmetric Matrix (iii), $\lambda_{n}(X)I_{n}\preceq X\preceq\lambda_{1}(X)I_{n}$, so the display above gives

$$\operatorname{tr}\bigl(P(\lambda_{n}(X)I_{n})\bigr)\le\operatorname{tr}(PX)\le\operatorname{tr}\bigl(P(\lambda_{1}(X)I_{n})\bigr).$$

For $t\in\mathbb{R}$, Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes (iii), Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes (iv) and Basic Properties of the Trace (i) give

$$\operatorname{tr}\bigl(P(tI_{n})\bigr)=\operatorname{tr}(tP)=t\operatorname{tr}(P),$$

and with $t=\lambda_{n}(X)$ and $t=\lambda_{1}(X)$ this turns the previous display into (iii).