= Farkas' lemma
{c}
{title2=$Az=b,\ z\geq0\quad\text{or}\quad A^Ty\geq0,\ b^Ty<0$}
{wiki}
= Farkas alternative
{c}
{synonym}
For a real <matrix> $A\in\mathbb R^{m\times n}$ and a <vector> $b\in\mathbb R^m$, exactly one of the following systems has a solution:
$$
\begin{aligned}
&Az=b,\qquad z\in\mathbb R^n,\quad z\geq0;\\
&A^Ty\geq0,\qquad y\in\mathbb R^m,\quad b^Ty<0.
\end{aligned}
$$
The <linear inequalities> here are componentwise. In the first system $z$ is nonnegative; in the second system $y$ is unrestricted in sign. The second system is a certificate that the first has no <feasible point>. This nonnegative-equations alternative is developed in https://web.stanford.edu/~boyd/cvxbook/bv_cvxslides.pdf#page=188[Boyd and Vandenberghe, Convex Optimization slides, §5.34].
\b[Build the target, or separate it.] Write the columns of $A$ as $a_1,\ldots,a_n$. Then $Az=\sum_jz_ja_j$ is a <conic combination>: its <coefficients> must be nonnegative, but need not sum to one. The obtainable targets form the <finitely generated cone>
$$
K=\{Az:z\geq0\}=\operatorname{cone}\{a_1,\ldots,a_n\}.
$$
A solution $z$ explains how to build $b$ from those columns. A certificate $y$ instead defines a <linear functional> $v\mapsto y^Tv$. The condition $A^Ty\geq0$ says that its <dot product> with every generating column is nonnegative, and hence with every point of $K$. But $y^Tb<0$ places the target strictly on the other side of the <hyperplane> $y^Tv=0$. Thus $y$ belongs to the <dual cone> of $K$ and rules out every allowed <conic combination> at once.
\b[A certificate that can be checked by eye.] Take the <identity matrix>
$$
A=I_2=\begin{pmatrix}1&0\\0&1\end{pmatrix},\qquad
b=\begin{pmatrix}-1\\1\end{pmatrix}.
$$
Here $K$ is the <nonnegative orthant>. The equation $Az=b$ forces $z=(-1,1)^T$, violating $z\geq0$. The certificate $y=(1,0)^T$ gives
$$
A^Ty=\begin{pmatrix}1\\0\end{pmatrix}\geq0,\qquad b^Ty=-1<0.
$$
The <linear functional> simply reads the first coordinate: all allowed column combinations have a nonnegative first coordinate, while $b$ has first coordinate $-1$. For comparison, the target $(1,1)^T$ is obtained with $z=(1,1)^T$.
\Image[/farkas-cone-separation.png]
{title=Nonnegative column combinations lie in a cone, while a Farkas certificate separates the target}
{description=For $A=I_2$, the shaded <nonnegative orthant> is the <conic hull> of the two columns. The <hyperplane> $y^Tv=0$ for $y=(1,0)^T$ is the vertical axis; $b=(-1,1)^T$ lies strictly on its negative side. The obtainable target $(1,1)^T$ illustrates the other alternative.}
\b[Why this is useful and striking.] A successful search can exhibit one <feasible point>; an unsuccessful search alone cannot explain why every candidate fails. <Farkas' lemma> guarantees an equally concrete witness of impossibility for this finite linear problem. Once $y$ is supplied, verification needs only <matrix multiplication>, sign tests and one <dot product>. The same idea gives a <Farkas certificate for linear inequalities> and underlies <linear programming duality>.
\b[Brief geometric proof.] The two systems cannot both hold, because they would imply
$$
0>b^Ty=(Az)^Ty=z^T(A^Ty)\geq0.
$$
For existence of a certificate when $b\notin K$, <closedness of finitely generated cones> makes $K$ a <closed convex cone>, so <separation from a closed convex cone> supplies $y^Tb<0$ and $y^Tv\geq0$ for every $v\in K$. Testing each column gives $A^Ty\geq0$. Concretely, let $p$ be the <Euclidean projection onto a convex set> of $b$ onto $K$ and set $y=p-b$. The projection inequality gives $y^T(v-p)\geq0$ for $v\in K$. Testing $v=0$ and $v=2p$ gives $y^Tp=0$, whence $y^Tb=-\|p-b\|_2^2<0$. In the example, $p=(0,1)^T$ and $y=(1,0)^T$. Alternatively, the <Fenchel-Moreau theorem> applied to the cone's <indicator functional> proves the same separation through its polar cone.
An original historical source is Julius Farkas's https://geodesic.mathdoc.fr/item/JRAM_1902__124_149129/[Theorie der einfachen Ungleichungen, Journal für die reine und angewandte Mathematik 124 (1902), pp. 1–27]{ref}. The linked archival record verifies the author, title and publication details.
Back to article page
