[proofplan]
We prove both necessity and sufficiency of the complementary slackness conditions. For necessity, we start from strong duality ($c^\top x = \lambda^\top b$) and sandwich $\lambda^\top(Ax)$ between the two equal quantities using the same componentwise monotonicity arguments from [Weak Duality for Linear Programs](/theorems/2557). Since the outer quantities are equal, both intermediate inequalities hold with equality, which forces both slackness products to vanish. For sufficiency, we expand $c^\top x$ using the two slackness conditions to obtain $c^\top x = \lambda^\top b$, and weak duality then implies both are optimal.
[/proofplan]
[step:Necessity: sandwich $\lambda^\top(Ax)$ between equal quantities using strong duality]
Suppose $x$ is primal optimal and $\lambda$ is dual optimal. By [Strong Duality for Linear Programs](/theorems/2553), $c^\top x = \lambda^\top b$. By the proof of [Weak Duality for Linear Programs](/theorems/2557), we have the chain
\begin{align*}
\lambda^\top b \leq \lambda^\top(Ax) \leq c^\top x.
\end{align*}
Since the leftmost and rightmost quantities are equal ($c^\top x = \lambda^\top b$), both inequalities hold with equality:
\begin{align*}
\lambda^\top(Ax) = \lambda^\top b \quad \text{and} \quad \lambda^\top(Ax) = c^\top x.
\end{align*}
[guided]
Suppose $x$ and $\lambda$ are simultaneously optimal. Strong duality guarantees $c^\top x = \lambda^\top b$. In the proof of weak duality, we established two inequalities:
1. $\lambda^\top b \leq \lambda^\top(Ax)$, using $Ax \geq b$ and $\lambda \geq 0$.
2. $\lambda^\top(Ax) \leq c^\top x$, using $A^\top \lambda \leq c$ and $x \geq 0$.
The quantity $\lambda^\top(Ax)$ sits between $\lambda^\top b$ and $c^\top x$. But strong duality says these outer quantities are equal: $c^\top x = \lambda^\top b$. A number squeezed between two equal numbers must equal both:
\begin{align*}
\lambda^\top b \leq \lambda^\top(Ax) \leq c^\top x = \lambda^\top b \quad \implies \quad \lambda^\top(Ax) = \lambda^\top b = c^\top x.
\end{align*}
This is the key structural observation: at optimality, the "slack" in the weak duality chain must vanish completely.
[/guided]
[/step]
[step:Necessity: extract the two complementary slackness conditions]
From $\lambda^\top(Ax) = \lambda^\top b$:
\begin{align*}
\lambda^\top(Ax - b) = 0.
\end{align*}
Since $\lambda \geq 0$ and $Ax - b \geq 0$ (primal feasibility), every term $\lambda_i(Ax - b)_i$ in the sum $\sum_{i=1}^m \lambda_i(Ax - b)_i = 0$ is non-negative. A sum of non-negative terms equals zero if and only if every term is zero. Therefore $\lambda_i(Ax - b)_i = 0$ for each $i = 1, \ldots, m$.
From $c^\top x = \lambda^\top(Ax) = (A^\top \lambda)^\top x$:
\begin{align*}
(c^\top - \lambda^\top A) x = c^\top x - (A^\top \lambda)^\top x = 0.
\end{align*}
Since $c - A^\top \lambda \geq 0$ (dual feasibility) and $x \geq 0$, every term $(c_j - (A^\top \lambda)_j)x_j$ in the sum $\sum_{j=1}^n (c_j - (A^\top \lambda)_j) x_j = 0$ is non-negative. Therefore $(c_j - (A^\top \lambda)_j) x_j = 0$ for each $j = 1, \ldots, n$.
[guided]
We established $\lambda^\top(Ax - b) = 0$. Expanding: $\sum_{i=1}^m \lambda_i (Ax - b)_i = 0$. Each factor is non-negative: $\lambda_i \geq 0$ by dual feasibility and $(Ax - b)_i \geq 0$ by primal feasibility ($Ax \geq b$). So each summand $\lambda_i(Ax - b)_i \geq 0$. The only way non-negative numbers can sum to zero is if every one of them is zero:
\begin{align*}
\lambda_i (Ax - b)_i = 0 \quad \text{for each } i = 1, \ldots, m.
\end{align*}
This is the **primal complementary slackness** condition: for each constraint $i$, either $\lambda_i = 0$ (the dual variable is zero, meaning the constraint is "free") or $(Ax)_i = b_i$ (the constraint is tight).
Similarly, from $(c - A^\top \lambda)^\top x = 0$, we expand $\sum_{j=1}^n (c_j - (A^\top \lambda)_j) x_j = 0$. Dual feasibility gives $c_j - (A^\top \lambda)_j \geq 0$, and primal feasibility gives $x_j \geq 0$. Each summand is non-negative, so each must vanish:
\begin{align*}
(c_j - (A^\top \lambda)_j) x_j = 0 \quad \text{for each } j = 1, \ldots, n.
\end{align*}
This is the **dual complementary slackness** condition: for each variable $j$, either $x_j = 0$ or the $j$-th dual constraint is tight ($(A^\top \lambda)_j = c_j$). The two conditions together are written compactly as $(c^\top - \lambda^\top A) x = 0$ and $\lambda^\top(Ax - b) = 0$.
[/guided]
[/step]
[step:Sufficiency: the two slackness conditions force $c^\top x = \lambda^\top b$]
Suppose $x$ is primal feasible, $\lambda$ is dual feasible, and the two complementary slackness conditions hold. We compute:
\begin{align*}
c^\top x &= \bigl[(c^\top - \lambda^\top A) + \lambda^\top A\bigr] x = (c^\top - \lambda^\top A) x + \lambda^\top(Ax).
\end{align*}
By the first slackness condition, $(c^\top - \lambda^\top A) x = 0$, so $c^\top x = \lambda^\top(Ax)$. Now:
\begin{align*}
\lambda^\top(Ax) = \lambda^\top b + \lambda^\top(Ax - b).
\end{align*}
By the second slackness condition, $\lambda^\top(Ax - b) = 0$, so $\lambda^\top(Ax) = \lambda^\top b$. Therefore $c^\top x = \lambda^\top b$.
Since $x$ is primal feasible and $\lambda$ is dual feasible, [Weak Duality for Linear Programs](/theorems/2557) gives $\lambda^\top b \leq c^\top x'$ for every primal feasible $x'$ and $\lambda'^\top b \leq c^\top x$ for every dual feasible $\lambda'$. The equality $c^\top x = \lambda^\top b$ then forces $x$ to be primal optimal and $\lambda$ to be dual optimal.
[guided]
Suppose the two slackness conditions hold for a primal-dual feasible pair $(x, \lambda)$. We show $c^\top x = \lambda^\top b$, which by weak duality implies simultaneous optimality.
We split $c^\top$ into two parts — the "slack" part and the part involving $A$:
\begin{align*}
c^\top x = (c^\top - \lambda^\top A) x + \lambda^\top A x.
\end{align*}
The first slackness condition says $(c^\top - \lambda^\top A) x = 0$, so $c^\top x = \lambda^\top(Ax)$. We now split $Ax$ into $b$ and the constraint slack:
\begin{align*}
\lambda^\top(Ax) = \lambda^\top b + \lambda^\top(Ax - b).
\end{align*}
The second slackness condition says $\lambda^\top(Ax - b) = 0$, so $c^\top x = \lambda^\top b$.
Why does $c^\top x = \lambda^\top b$ imply optimality? By [Weak Duality for Linear Programs](/theorems/2557), $\lambda^\top b \leq c^\top x'$ for every primal feasible $x'$. Since $c^\top x = \lambda^\top b$, we have $c^\top x \leq c^\top x'$ for all primal feasible $x'$, so $x$ achieves the primal minimum. Symmetrically, $\lambda'^\top b \leq c^\top x = \lambda^\top b$ for every dual feasible $\lambda'$, so $\lambda$ achieves the dual maximum.
The complementary slackness conditions are therefore a **certificate of optimality**: to verify that a primal-dual pair is optimal, one need only check feasibility and the vanishing of these two bilinear products, without solving any optimisation problem.
[/guided]
[/step]
