Farkas' Lemma: The Theorem of the Alternative

The Precise Statement

Fix A ∈ ℝ^(m×n) and b ∈ ℝ^m. Farkas' Lemma (standard form) asserts that exactly one of the following two systems has a solution:

• System P: there exists x ∈ ℝ^n with Ax = b and x ≥ 0 (componentwise);
• System D: there exists y ∈ ℝ^m with Aᵀy ≥ 0 and bᵀy < 0.

The two are mutually exclusive and exhaustive: at least one holds (exhaustive), and they cannot both hold (exclusive). The exclusivity is the easy half — if both x and y existed, then 0 > bᵀy = (Ax)ᵀy = xᵀ(Aᵀy) ≥ 0, a contradiction, since x ≥ 0 and Aᵀy ≥ 0 force xᵀ(Aᵀy) ≥ 0. The substance is the exhaustiveness: whenever P fails, the certificate y of System D genuinely exists. The finiteness of the constraint set (m, n both finite) is essential and cannot be dropped.

The Geometric Picture

Consider the set C = {Ax : x ≥ 0} ⊆ ℝ^m. This is precisely the cone generated by the columns of A — all nonnegative combinations of a₁, …, aₙ. System P asks a single question: is the point b inside this cone?

If b ∈ C, we are done (P holds). If b ∉ C, then because C is a closed convex cone, the separating hyperplane theorem guarantees a hyperplane through the origin with the cone on one side and b strictly on the other. Its normal vector is exactly y: it satisfies aⱼᵀy ≥ 0 for every generator (so Aᵀy ≥ 0, the cone stays nonnegative) while bᵀy < 0 (b is strictly separated). So Farkas' Lemma is the crisp statement:

• b is in the cone ⟺ no separating y exists;
• b is outside the cone ⟺ a separating y exists.

The whole theorem is the geometry of a point versus a finitely generated cone.

The Key Idea of the Proof

The one non-obvious ingredient is that the cone C = {Ax : x ≥ 0} is closed. This is not automatic for arbitrary generating sets, but it holds for a finitely generated cone — this is the Weyl–Minkowski fact, and it is exactly where finiteness enters.

Given closedness, the proof runs:

• Suppose System P fails, i.e. b ∉ C.
• Let p be the unique closest point of C to b (it exists and is unique because C is closed and convex — this is the projection theorem in ℝ^m).
• Set y = p − b. The obtuse-angle / variational inequality (c − p)ᵀ(b − p) ≤ 0 for all c ∈ C, combined with the cone's scaling structure, yields aⱼᵀy ≥ 0 for each column and bᵀy = −‖p − b‖² < 0.

That y is the certificate. The clever object is the projection onto the cone; the clever fact is that a finitely generated cone is closed. An alternative, purely combinatorial route uses Fourier–Motzkin elimination, avoiding topology entirely.

A Worked Example

Take A with columns a₁ = (1, 0)ᵀ, a₂ = (0, 1)ᵀ, and target b = (−1, 2)ᵀ. System P asks: are there x₁, x₂ ≥ 0 with x₁a₁ + x₂a₂ = b? That means x₁ = −1, x₂ = 2 — but x₁ = −1 violates x₁ ≥ 0. So P fails.

Farkas promises a certificate y = (y₁, y₂)ᵀ with Aᵀy ≥ 0 and bᵀy < 0. Here Aᵀy = (y₁, y₂)ᵀ, so we need y₁ ≥ 0 and y₂ ≥ 0, while bᵀy = −y₁ + 2y₂ < 0. Choose y = (1, 0)ᵀ: then Aᵀy = (1, 0)ᵀ ≥ 0 ✓ and bᵀy = −1 < 0 ✓.

The certificate is geometrically transparent: the cone {x ≥ 0} here is the first quadrant, b = (−1, 2) lies outside it, and y = (1, 0) is the normal to the separating vertical axis — everything in the quadrant has nonnegative first coordinate, but b has first coordinate −1. One vector proves infeasibility, no search required.

Why the Hypotheses Matter

Finiteness / finite dimension is essential. The proof rests on a finitely generated cone being closed. Drop finiteness and the cone can fail to be closed, and the dichotomy breaks. A classic infinite-dimensional cautionary example: in ℓ² or C[0,1], the image of a positive cone under a bounded operator need not be closed, so a point can lie in the closure of the cone without lying in the cone itself — then neither alternative holds cleanly, and one must pass to closures or add constraint-qualification (Slater-type) hypotheses. This is why the infinite-dimensional analogues (in the theory of ordered topological vector spaces) require extra assumptions.

Farkas' Lemma sits at the head of a family. It is equivalent to the separating hyperplane theorem for polyhedral cones, implies LP strong duality and complementary slackness, and specializes to Gordan's, Stiemke's, and Motzkin's transposition theorems. Von Neumann's minimax theorem and the KKT optimality conditions both ultimately lean on it.

Applications and Significance

Farkas' Lemma is the algebraic engine behind linear programming duality. Strong duality — that a primal LP and its dual share the same optimal value when either is feasible and bounded — is essentially a repackaging of the alternative: infeasibility of one system produces the dual certificate that pins the optimum. Every LP solver's infeasibility certificate (a Farkas ray) is literally the y of System D.

• Optimization: the Karush–Kuhn–Tucker (KKT) conditions and Lagrangian duality gaps for convex programs are proved via Farkas-type separation.
• Game theory: the minimax theorem for zero-sum games follows from it.
• Economics: arbitrage-free asset pricing — the fundamental theorem of asset pricing — is a Farkas/Stiemke statement (no arbitrage ⟺ a strictly positive pricing measure exists).
• Combinatorics: integer-programming relaxations, network flow max-flow/min-cut, and the theory of polyhedra all trace back to it.

In short, whenever a solver reports 'infeasible,' Farkas guarantees the report is provable — not merely a failed search.

Farkas' Lemma and its family of transposition (alternative) theorems: each pairs a primal system with a mutually exclusive dual certificate.

Theorem	System (P) is solvable	…or else the alternative (D) is solvable	Exactly one holds
Farkas (standard form)	Ax = b, x ≥ 0	Aᵀy ≥ 0, bᵀy < 0	Yes
Farkas (inequality form)	Ax ≤ b, x ≥ 0	Aᵀy ≥ 0, y ≥ 0, bᵀy < 0	Yes
Gordan (1873)	Ax < 0 (strict)	Aᵀy = 0, y ≥ 0, y ≠ 0	Yes
Stiemke (1915)	Ax = 0, x > 0	Aᵀy ≥ 0, Aᵀy ≠ 0	Yes
Motzkin (1936)	Ax < 0, Bx ≤ 0	combined y,z ≥ 0 nullspace certificate	Yes