[proofplan] The proof first expands the primal-dual objective gap using the primal equations $\langle A_i,X\rangle=b_i$ and the definition of the dual slack $S$. Dual feasibility and primal feasibility make this gap equal to the nonnegative trace [inner product](/page/Inner%20Product) $\langle S,X\rangle$, so equality of objective values is exactly [complementary slackness](/theorems/2559). The optimality statement then follows from equality of the primal and dual optimal values. Finally, when $X$ and $S$ are positive semidefinite, the scalar condition $\operatorname{tr}(SX)=0$ is converted into the matrix condition $SX=0$ using positive semidefinite square roots and the Frobenius norm. [/proofplan] [step:Rewrite the objective gap as the slack inner product] Let $X \in \mathbb{R}^{n \times n}$ be primal feasible, and let $y \in \mathbb{R}^m$ be dual feasible. Define the dual slack matrix $S \in \mathbb{R}^{n \times n}$ by \begin{align*} S := C - \sum_{i=1}^m y_i A_i. \end{align*} Since $X$ is primal feasible, $\langle A_i,X\rangle = b_i$ for every $i \in \{1,\dots,m\}$. Therefore \begin{align*} \langle S,X\rangle = \left\langle C - \sum_{i=1}^m y_i A_i, X \right\rangle. \end{align*} By linearity of the trace inner product, \begin{align*} \langle S,X\rangle = \langle C,X\rangle - \sum_{i=1}^m y_i \langle A_i,X\rangle. \end{align*} Substituting $\langle A_i,X\rangle=b_i$ gives \begin{align*} \langle S,X\rangle = \langle C,X\rangle - \sum_{i=1}^m y_i b_i. \end{align*} Since $b^\top y = \sum_{i=1}^m b_i y_i$, we obtain \begin{align*} \langle C,X\rangle - b^\top y = \langle S,X\rangle. \end{align*} [guided] We want to compare the primal objective $\langle C,X\rangle$ with the dual objective $b^\top y$. The only expression that contains both $C$ and $y$ is the slack matrix, so we expand the slack inner product. Define $S \in \mathbb{R}^{n \times n}$ by \begin{align*} S := C - \sum_{i=1}^m y_i A_i. \end{align*} Taking the trace inner product of this identity with the primal feasible matrix $X$ gives \begin{align*} \langle S,X\rangle = \left\langle C - \sum_{i=1}^m y_i A_i, X \right\rangle. \end{align*} The trace inner product is linear in its first argument, so \begin{align*} \langle S,X\rangle = \langle C,X\rangle - \sum_{i=1}^m y_i \langle A_i,X\rangle. \end{align*} Now we use primal feasibility. For each $i \in \{1,\dots,m\}$, the constraint says $\langle A_i,X\rangle=b_i$. Hence \begin{align*} \langle S,X\rangle = \langle C,X\rangle - \sum_{i=1}^m y_i b_i. \end{align*} Because scalar multiplication commutes in $\mathbb{R}$, $\sum_{i=1}^m y_i b_i = \sum_{i=1}^m b_i y_i = b^\top y$. Therefore \begin{align*} \langle C,X\rangle - b^\top y = \langle S,X\rangle. \end{align*} This identity is the algebraic core of complementary slackness: the whole primal-dual objective gap is exactly the part of $C$ left over after subtracting the dual linear combination of the constraint matrices. [/guided] [/step] [step:Use positive semidefiniteness to identify equality of objective values] Because $X \succeq 0$ and $S \succeq 0$, the matrix $X^{1/2} S X^{1/2}$ is positive semidefinite. Its trace is nonnegative, and by cyclic invariance of trace, \begin{align*} \langle S,X\rangle = \operatorname{tr}(SX) = \operatorname{tr}(X^{1/2} S X^{1/2}) \ge 0. \end{align*} Combining this nonnegativity with \begin{align*} \langle C,X\rangle - b^\top y = \langle S,X\rangle \end{align*} shows \begin{align*} \langle C,X\rangle = b^\top y \end{align*} if and only if \begin{align*} \langle S,X\rangle = 0. \end{align*} [/step] [step:Derive optimality from equality of the attained primal and dual values] Assume that the primal and dual optimal values are equal and attained. Let their common value be $\nu \in \mathbb{R}$. If $X$ is primal feasible, $y$ is dual feasible, and $\langle S,X\rangle=0$, then the previous step gives \begin{align*} \langle C,X\rangle = b^\top y. \end{align*} [Weak duality](/theorems/2549) is already encoded by the identity \begin{align*} \langle C,X\rangle - b^\top y = \langle S,X\rangle \ge 0, \end{align*} so every dual feasible value is at most every primal feasible value. Since the infimum primal value and the supremum dual value both equal $\nu$, the common feasible objective value must be $\nu$. Thus $X$ is primal optimal and $y$ is dual optimal. Conversely, if $X$ is primal optimal and $y$ is dual optimal, then \begin{align*} \langle C,X\rangle = \nu = b^\top y. \end{align*} By the equivalence already proved, this implies \begin{align*} \langle S,X\rangle = 0. \end{align*} [/step] [step:Convert zero trace complementarity into the matrix equation $SX=0$] Assume now that $X,S \in \mathbb{R}^{n \times n}$ are symmetric positive semidefinite matrices. Let $X^{1/2}$ and $S^{1/2}$ denote their symmetric positive semidefinite square roots. By cyclic invariance of trace, \begin{align*} \langle S,X\rangle = \operatorname{tr}(SX) = \operatorname{tr}(S^{1/2} X S^{1/2}). \end{align*} Since $X = X^{1/2}X^{1/2}$, \begin{align*} \operatorname{tr}(S^{1/2} X S^{1/2}) = \operatorname{tr}(S^{1/2} X^{1/2} X^{1/2} S^{1/2}). \end{align*} Set $M := X^{1/2}S^{1/2} \in \mathbb{R}^{n \times n}$. Then $M^\top = S^{1/2}X^{1/2}$, so \begin{align*} \langle S,X\rangle = \operatorname{tr}(M^\top M). \end{align*} The Frobenius identity gives \begin{align*} \operatorname{tr}(M^\top M)=\sum_{i=1}^n \sum_{j=1}^n M_{ij}^2. \end{align*} Therefore $\langle S,X\rangle=0$ if and only if $M=0$, that is, \begin{align*} X^{1/2}S^{1/2}=0. \end{align*} Taking transposes gives \begin{align*} S^{1/2}X^{1/2}=0. \end{align*} Multiplying on the left by $S^{1/2}$ and on the right by $X^{1/2}$ yields \begin{align*} SX = S^{1/2}(S^{1/2}X^{1/2})X^{1/2}=0. \end{align*} Conversely, if $SX=0$, then taking traces gives \begin{align*} \langle S,X\rangle = \operatorname{tr}(SX)=0. \end{align*} Thus, for symmetric positive semidefinite $X$ and $S$, the scalar complementary slackness condition $\langle S,X\rangle=0$ is equivalent to the matrix condition $SX=0$. [/step]