Farkas' Lemma and Theorems of the Alternative

A theorem of the alternative is a statement of the form: "Exactly one of these two systems is feasible." The most famous such theorem in linear programming is Farkas' Lemma.

Farkas' Lemma. Let $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^m.$ Then exactly one of the following systems has a solution:

$$\textbf{(I)} \quad Ax = b, \quad x \geq 0$$ $$\textbf{(II)} \quad A^T y \leq 0, \quad b^T y > 0$$

The two systems cannot both be feasible. If $x \geq 0$ solves (I) and $y$ satisfies the constraints of (II), then

$$b^T y = (Ax)^T y = x^T (A^T y) \leq 0,$$

since $x \geq 0$ and $A^T y \leq 0$ -- contradicting $b^T y > 0.$

The deeper content is that at least one of (I) or (II) is always feasible. This follows from the Strong Duality Theorem applied to an auxiliary LP.

A vector $y$ satisfying both constraints of (II) is called a Farkas certificate: it is a short, easily verifiable proof that (I) has no solution.