---
tag: FYZC634H2D
kind: statement
role: lemma
name: Farkas' lemma
msc: [90C05, 52A20, 15A39]
uses: [0VD9ZSWWJG, 09DXWYRD43, 6VE4KA12VD]
about: [6VE4KA12VD]
sources:
  - url: https://en.wikipedia.org/wiki/Farkas'_lemma
same_as:
  wikidata: Q606254
  wikipedia: Farkas' lemma
---

## Statement

Let $A$ be a real $m \times n$ [[matrix|0VD9ZSWWJG]] and let $b \in \R^m$.
For vectors, write $v \ge 0$ when every coordinate of $v$ is nonnegative, and let $A^T$ be the [[transpose|09DXWYRD43]] of $A$.
Then exactly one of the following two systems has a solution:

1. $x \in \R^n$ with $A x = b$ and $x \ge 0$;
2. $y \in \R^m$ with $A^T y \ge 0$ and $b^T y < 0$.

## 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|6VE4KA12VD]] 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$.

## Explanations

### L1 human

Either a vector $b$ can be built from the columns of $A$ with nonnegative weights, or there is a simple certificate that it cannot.
The certificate is a direction $y$ in which all columns point "forward" while $b$ points "backward".
Geometrically, a point outside a cone can be cut off from the cone by a flat wall through the apex.

### L2 human

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