Farkas' lemma

Remarks

Both cannot hold: if $Ax = b$ with $x \ge 0$ and $A^T y \ge 0$, then $b^T y = x^T (A^T y) \ge 0$. For the other direction, the set $C = \set{Ax : x \ge 0}$ is the convex cone generated by the columns of $A$, and it is closed because it is finitely generated. If $b \notin C$, the hyperplane separation theorem gives a hyperplane through the origin that separates $b$ from $C$; its normal vector $y$ solves the second system. Example: for $A = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$ and $b = (1, -1)^T$, the first system has no solution, and $y = (0, 1)^T$ solves the second, since $A^T y = (0, 1)^T \ge 0$ and $b^T y = -1 < 0$.

Going deeper

For a student

Farkas' lemma is a theorem of the alternative, and it is the basis of the duality theory of linear programming. Many variants follow from it by adding slack variables, for example the version with $Ax \le b$. Gordan's lemma and the Minkowski–Weyl theorem belong to the same circle of ideas about finitely generated cones.