Lemma 10.5 — Farkas' Lemma

Let $A$ be a real $m \times n$ matrix and $b \in \mathbb{R}^m$. The system of linear inequalities $Ax \le b$, in the unknown $x \in \mathbb{R}^n$ (no sign constraint on $x$), has no solution if and only if there is a $y \in \mathbb{R}^m$ such that

Such a $y$ is a certificate of infeasibility: a nonnegative combination of the inequalities whose left-hand side vanishes and whose right-hand side is negative. Farkas' Lemma is the tool behind the Separation Theorem for polyhedra and the strict complementarity results of the same chapter.

Formalization Note Vector inequalities are componentwise. For $m = 0$ the system is always solvable and no $y$ with $b^T y < 0$ exists, consistently with the statement.