Proof of The Extremal Values of $\operatorname{tr}(AX)$ over Symmetric Matrices between $aI$ and $bI$

Routine facts about the matrix product, the trace and scalars in the dot product are used without comment (Toolkit for AL3).

Write $\lambda_{k}=\lambda_{k}(X)$ and $\lambda=(\lambda_{1},\dots,\lambda_{n})$. By The Spectral Theorem for Real Symmetric Matrices (i) there are $Q\in\mathrm{O}(n)$ and $\mu\in\mathbb{R}^{n}$ with $\mu_{1}\ge\dots\ge\mu_{n}$ and $X=(Q\operatorname{diag}(\mu))Q^{\top}$, and $\mu=\lambda$ by The Ordered Eigenvalues of a Symmetric Matrix (i); so

$$X=(Q\operatorname{diag}(\lambda))Q^{\top}.$$

Put $q_{k}=Qe_{k}$ for $k\in[n]$; then $q_{j}\cdot q_{k}=\delta_{jk}$ by Rules for Orthogonal Matrices: Inverse, Products, Isometry, Columns, Determinant, Orthonormal Extension and Expansion (iv), and in particular $\lVert q_{k}\rVert^{2}=1$. Let

$$K_{+}=\{k\in[n]:\lambda_{k}>0\},\qquad K_{-}=\{k\in[n]:\lambda_{k}<0\},\qquad K_{0}=\{k\in[n]:\lambda_{k}=0\},$$

which partition $[n]$ (these are sets defined by predicative conditions, The Graph Reading of a Formula Tree Is Predicative and Agrees with Its Reading, So the Reading Is Predicative), and let $V^{+}$ and $V^{-}$ be the right-hand values in (i) and (ii). We first express $\operatorname{tr}(AX)$ through the columns $q_{k}$, then bound it on $\mathcal{A}_{a,b}$, and finally exhibit matrices attaining the bounds.

A trace formula. We show that for every $A\in\mathcal{S}(n)$

$$\operatorname{tr}(AX)=\sum_{k=1}^{n}\lambda_{k}\,q_{k}\cdot(Aq_{k}).$$

Let $N=(Q^{\top}A)Q$. Regrouping by Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes (i) and moving $Q^{\top}$ to the front by Basic Properties of the Trace (iii) gives $\operatorname{tr}(AX)=\operatorname{tr}(N\operatorname{diag}(\lambda))$. Since $e_{k}$ is an eigenvector of $\operatorname{diag}(\lambda)$ with eigenvalue $\lambda_{k}$ (Eigenvalues: the Determinant Criterion, Diagonal Matrices, Orthogonal Similarity and Orthogonality of Eigenvectors of Symmetric Matrices (iii)), the $k$th diagonal entry of $N\operatorname{diag}(\lambda)$ is, by Rules for Symmetric and Positive Semidefinite Matrices: Closure, Self-Adjointness, Polarization, Congruence and Cones (iii), Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes (v) and The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite (iii),

$$e_{k}\cdot\bigl(N\operatorname{diag}(\lambda)e_{k}\bigr)=e_{k}\cdot\bigl(N(\lambda_{k}e_{k})\bigr)=\lambda_{k}\,e_{k}\cdot(Ne_{k}).$$

By Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes (v) again, $Ne_{k}=Q^{\top}(Aq_{k})$, and $e_{k}\cdot(Q^{\top}(Aq_{k}))=q_{k}\cdot(Aq_{k})$ by Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes (viii) and The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite (i). Summing the diagonal entries (trace formula) gives the displayed formula.

Bounds. Let $A\in\mathcal{A}_{a,b}$. Since $\lVert q_{k}\rVert^{2}=1$, Eigenvalue, Quadratic-Form and Order Bounds for a Symmetric Matrix (i) gives $a\le q_{k}\cdot(Aq_{k})\le b$ for every $k$. Multiplying by $\lambda_{k}$: for $k\in K_{+}$, $a\lambda_{k}\le\lambda_{k}\,q_{k}\cdot(Aq_{k})\le b\lambda_{k}$; for $k\in K_{-}$, $b\lambda_{k}\le\lambda_{k}\,q_{k}\cdot(Aq_{k})\le a\lambda_{k}$; and for $k\in K_{0}$ the term is $0$. Summing termwise (Sums over Finite Sets in a Commutative Ring and in an Ordered Field: Distributivity, Products of Sums, Vanishing Terms, Sums over Pairs, Expanding Products of Sums, Counting, Comparison, Monotonicity and the Triangle Inequality (viii)) over the partition (Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (ii)), pulling out the constants $a$ and $b$ (Sums over Finite Sets in a Commutative Ring and in an Ordered Field: Distributivity, Products of Sums, Vanishing Terms, Sums over Pairs, Expanding Products of Sums, Counting, Comparison, Monotonicity and the Triangle Inequality (i)) and dropping the vanishing terms over $K_{0}$ (Sums over Finite Sets in a Commutative Ring and in an Ordered Field: Distributivity, Products of Sums, Vanishing Terms, Sums over Pairs, Expanding Products of Sums, Counting, Comparison, Monotonicity and the Triangle Inequality (iv)), and using the trace formula,

$$V^{-}\le\operatorname{tr}(AX)\le V^{+}.$$

Matrices diagonal in the basis of $X$. Let $c\in\mathbb{R}^{n}$ with $a\le c_{k}\le b$ for every $k\in[n]$, and put $A_{c}=(Q\operatorname{diag}(c))Q^{\top}$. Then $A_{c}\in\mathcal{S}(n)$, by the rules for transposes of products in Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes (vii), Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes (i), and the symmetry of $\operatorname{diag}(c)$ (Eigenvalues: the Determinant Criterion, Diagonal Matrices, Orthogonal Similarity and Orthogonality of Eigenvectors of Symmetric Matrices (ii)). For $\xi\in\mathbb{R}^{n}$ put $y=Q^{\top}\xi$. By Toolkit for AL3 (xxi) and Toolkit for AL3 (xxii),

$$\xi\cdot(A_{c}\xi)=\sum_{k=1}^{n}c_{k}y_{k}^{2},\qquad\lVert\xi\rVert^{2}=\sum_{k=1}^{n}y_{k}^{2}.$$

Since $a\le c_{k}\le b$ for every $k$, the first sum lies between $a\lVert\xi\rVert^{2}$ and $b\lVert\xi\rVert^{2}$. So $A_{c}\in\mathcal{A}_{a,b}$ by Eigenvalue, Quadratic-Form and Order Bounds for a Symmetric Matrix (i). By The Spectral Theorem for Real Symmetric Matrices (ii), applied to $A_{c}$, $Q$ and $c$, each $q_{k}$ is an eigenvector of $A_{c}$ with eigenvalue $c_{k}$, so $q_{k}\cdot(A_{c}q_{k})=c_{k}\,q_{k}\cdot q_{k}=c_{k}$ by The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite (iii), and the trace formula gives

$$\operatorname{tr}(A_{c}X)=\sum_{k=1}^{n}\lambda_{k}c_{k}.$$

Maximum. Let $c^{+}_{k}=b$ for $k\in K_{+}$ and $c^{+}_{k}=a$ otherwise (a point of $\mathbb{R}^{n}$ defined by cases, Maps Defined by Cases (i)), which is admissible as $a\le b$, and put $A^{*}=A_{c^{+}}$. By the previous paragraph, $A^{*}\in\mathcal{A}_{a,b}$ and

$$\operatorname{tr}(A^{*}X)=b\sum_{k\in K_{+}}\lambda_{k}+a\sum_{k\in K_{-}}\lambda_{k}+a\sum_{k\in K_{0}}\lambda_{k}=V^{+},$$

the last sum being $0$. Together with the bounds this is (i).

Minimum. Let $c^{-}_{k}=a$ for $k\in K_{+}$ and $c^{-}_{k}=b$ otherwise, and put $A_{*}=A_{c^{-}}$. As for the maximum, $A_{*}\in\mathcal{A}_{a,b}$ and $\operatorname{tr}(A_{*}X)=V^{-}$; together with the bounds this is (ii).