Proof of The Positive Semidefinite Ordering Compared by Differences

Throughout, $[n]$ is the initial segment determined by $n$, entries of real matrices are written as there, and we use the elementary order arithmetic of the ordered field $\mathbb{R}$.

Step 1: $Y-X$ is symmetric. By the definition of the transpose, a square real matrix $A$ is symmetric exactly when $A_{ij}=A_{ji}$ for all $i,j\in[n]$. Since $X$ and $Y$ lie in $\mathcal{S}(n)$, they are symmetric, so for all $i,j\in[n]$ the definition of the difference gives

Hence $Y-X$ is symmetric, so the phrase positive semidefinite applies to it.

Step 2: the quadratic forms differ by subtraction. Let $z=(z_1,\dots,z_n)\in\mathbb{R}^n$. By the definition of the matrix-vector product and the definition of the difference, for every $\alpha\in[n]$

using distributivity in the field $\mathbb{R}$ termwise, and then splitting the finite sum of differences into the difference of the two finite sums, which is an instance of the same distributive and associative laws applied finitely many times. Consequently, by the definition of the dot product,

by the same finite manipulation.

Step 3: the equivalence. Fix $z\in\mathbb{R}^n$. By claim 1 of Elementary Order Arithmetic in an Ordered Field, adding $z\cdot(Xz)$ to both sides is an equivalence, and adding it to the two sides of

yields $z\cdot(Xz)\le z\cdot(Yz)$; conversely, adding $-z\cdot(Xz)$ to the two sides of $z\cdot(Xz)\le z\cdot(Yz)$ yields $0\le z\cdot(Yz)-z\cdot(Xz)=z\cdot((Y-X)z)$. (Claim 1 of that lemma is stated for the strict order; the same argument with condition 1 of the definition of an ordered field, applied in both directions with $z\cdot(Xz)$ and with its additive inverse, gives the equivalence for $\le$.)

So $0\le z\cdot((Y-X)z)$ holds if and only if $z\cdot(Xz)\le z\cdot(Yz)$ holds, for each individual $z\in\mathbb{R}^n$. Quantifying over all $z\in\mathbb{R}^n$, the statement that $Y-X$ is positive semidefinite is exactly the statement that $X\preceq Y$ in the positive semidefinite ordering.