[proofplan]
We prove $\lambda^\top b \leq c^\top x$ for any primal feasible $x$ and dual feasible $\lambda$ by a chain of two inequalities. The first uses dual feasibility ($A^\top \lambda \leq c$) together with $x \geq 0$ to replace $c$ by $A^\top \lambda$. The second uses primal feasibility ($Ax \geq b$) together with $\lambda \geq 0$ to replace $Ax$ by $b$. Both steps rely on the elementary fact that if $u \leq v$ componentwise and $w \geq 0$ componentwise, then $w^\top u \leq w^\top v$.
[/proofplan]
[step:Establish the componentwise inner-product monotonicity used in both steps]
We use the following elementary fact throughout: if $u, v \in \mathbb{R}^k$ satisfy $u \leq v$ componentwise and $w \in \mathbb{R}^k$ satisfies $w \geq 0$ componentwise, then
\begin{align*}
w^\top u = \sum_{i=1}^k w_i u_i \leq \sum_{i=1}^k w_i v_i = w^\top v,
\end{align*}
since each term satisfies $w_i u_i \leq w_i v_i$ (the product of a non-negative number $w_i$ with a weakly larger number $v_i \geq u_i$).
[/step]
[step:Use dual feasibility and $x \geq 0$ to bound $c^\top x$ from below]
Since $\lambda$ is dual feasible, $A^\top \lambda \leq c$ componentwise. Since $x$ is primal feasible, $x \geq 0$. Applying the componentwise monotonicity with $u = A^\top \lambda$, $v = c$, $w = x$:
\begin{align*}
(A^\top \lambda)^\top x \leq c^\top x.
\end{align*}
Rewriting the left-hand side using the identity $(A^\top \lambda)^\top x = \lambda^\top(Ax)$:
\begin{align*}
\lambda^\top(Ax) \leq c^\top x.
\end{align*}
[guided]
Dual feasibility says $A^\top \lambda \leq c$, meaning $(A^\top \lambda)_j \leq c_j$ for every $j = 1, \ldots, n$. Primal feasibility gives $x_j \geq 0$ for every $j$. We multiply the $j$-th inequality by $x_j \geq 0$:
\begin{align*}
(A^\top \lambda)_j \cdot x_j \leq c_j \cdot x_j \quad \text{for each } j = 1, \ldots, n.
\end{align*}
Summing over $j$:
\begin{align*}
\sum_{j=1}^n (A^\top \lambda)_j x_j \leq \sum_{j=1}^n c_j x_j, \quad \text{i.e.} \quad (A^\top \lambda)^\top x \leq c^\top x.
\end{align*}
The left-hand side simplifies via the transpose identity: $(A^\top \lambda)^\top x = \lambda^\top A x$. So we have $\lambda^\top(Ax) \leq c^\top x$. This bound replaces $c$ (which appears in the primal objective) by $A^\top \lambda$ (which links primal and dual via the constraint matrix).
[/guided]
[/step]
[step:Use primal feasibility and $\lambda \geq 0$ to bound $\lambda^\top(Ax)$ from below]
Since $x$ is primal feasible, $Ax \geq b$ componentwise. Since $\lambda$ is dual feasible, $\lambda \geq 0$. Applying the componentwise monotonicity with $u = b$, $v = Ax$, $w = \lambda$:
\begin{align*}
\lambda^\top b \leq \lambda^\top(Ax).
\end{align*}
Combining with the previous step:
\begin{align*}
\lambda^\top b \leq \lambda^\top(Ax) \leq c^\top x.
\end{align*}
This is the desired weak duality inequality.
[guided]
Primal feasibility gives $Ax \geq b$, i.e., $(Ax)_i \geq b_i$ for each $i = 1, \ldots, m$. Dual feasibility gives $\lambda_i \geq 0$ for each $i$. Multiplying the $i$-th inequality by $\lambda_i \geq 0$:
\begin{align*}
\lambda_i (Ax)_i \geq \lambda_i b_i \quad \text{for each } i = 1, \ldots, m.
\end{align*}
Summing over $i$:
\begin{align*}
\lambda^\top(Ax) = \sum_{i=1}^m \lambda_i (Ax)_i \geq \sum_{i=1}^m \lambda_i b_i = \lambda^\top b.
\end{align*}
Chaining with the bound from the previous step:
\begin{align*}
\lambda^\top b \leq \lambda^\top(Ax) \leq c^\top x.
\end{align*}
The two non-negative sign conditions ($x \geq 0$ and $\lambda \geq 0$) are essential: the first allows us to exploit $A^\top \lambda \leq c$, and the second allows us to exploit $Ax \geq b$. If either sign condition failed, the corresponding inequality would reverse direction when multiplied by a negative component, and the chain would break.
[/guided]
[/step]
