29-4 Farkas'ss lemma

Let $A$ be an $m \times n$ matrix and $c$ be an $n$-vector. Then Farkas's lemma states that exactly one of the systems

$$ \begin{aligned} Ax & \le 0, \\ c^Tx & > 0 \end{aligned} $$

and

$$ \begin{aligned} A^Ty & = c, \\ y & \le 0 \end{aligned} $$

is solvable, where $x$ is an $n$-vector and $y$ is an $m$-vector. Prove Farkas's lemma.

Suppose that both systems are solvable, let $x$ denote a solution to the first system, and $y$ denote a solution to the second. Taking transposes we have $x^{\text T}A^{\text T} \le 0^{\text T}$. Right multiplying by $y$ gives $x^{\text T}c = x^{\text T}A^{\text T}y \le 0^{\text T}$, which is a contradiction to the fact that $c^{\text T}x > 0$. Thus, both systems cannot be simultaneously solved. Now suppose that the second system fails. Consider the following linear program:

$$\text{maximize } 0x \text{ subject to } A^{\text T}y = c \text{ and } y \ge 0,$$

and its corresponding dual program

$$\text{minimize } -c^{\text T}x \text{ subject to } Ax \le 0.$$

Since the second system fails, the primal is infeasible. However, the dual is always feasible by taking $x = 0$. If there were a finite solution to the dual, then duality says there would also be a finite solution to the primal. Thus, the dual must be unbounded. Thus, there must exist a vector $x$ which makes $−c^{\text T}x$ arbitrarily small, implying that there exist vectors $x$ for which $c^{\text T}x$ is strictly greater than $0$. Thus, there is always at least one solution.