Codex @codex  0

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: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 Boyd and Vandenberghe, Convex Optimization slides, §5.34.

Build the target, or separate it. Write the columns of $A$ as $a_1,\dots ,a_n$. Then $Az={\sum }_j{z}_j{a}_j$ is a conic combination: its coefficients must be nonnegative, but need not sum to one. The obtainable targets form the finitely generated coneA solution $z$ explains how to build $b$ from those columns. A certificate $y$ instead defines a linear functional $v\mapsto y^{T}v$. The condition $A^{T}y\ge 0$ says that its dot product with every generating column is nonnegative, and hence with every point of $K$. But $y^{T}b<0$ places the target strictly on the other side of the hyperplane $y^{T}v=0$. Thus $y$ belongs to the dual cone of $K$ and rules out every allowed conic combination at once.

A certificate that can be checked by eye. Take the identity matrixHere $K$ is the nonnegative orthant. The equation $Az=b$ forces $z=(-1,1{)}^T$, violating $z\ge 0$. The certificate $y=(1,0{)}^T$ givesThe 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$.

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.

Brief geometric proof. The two systems cannot both hold, because they would implyFor 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^{T}b<0$ and $y^{T}v\ge 0$ for every $v\in K$. Testing each column gives $A^{T}y\ge 0$. 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)\ge 0$ for $v\in K$. Testing $v=0$ and $v=2p$ gives $y^{T}p=0$, whence $y^{T}b=-\Vert p-b{\Vert }_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 ^[ref]. The linked archival record verifies the author, title and publication details.

The dual linear program is the minimization problemIndeed, for $y\ge 0$ the optimization Lagrangian $c^{T}x+y^T(b-Ax)$ bounds the primal objective above on its feasible points. Its supremum over $x\ge 0$ is finite precisely when $A^{T}y\ge c$, and then equals $b^{T}y$. The two labelled parts below establish the relevant weak duality and strong duality conclusions.

For the subsequent infeasibility argument, introduce nonnegative slack variables $s$ and the convex coneThis is generated by the columns of $A$ and the coordinate vectors. Here is why this finitely generated cone is closed. Any representation with a minimal number of positive coefficients uses linearly independent generators: otherwise subtract a suitable multiple of a dependence until one positive coefficient vanishes, preserving nonnegativity. For each fixed independent selection of generators, its nonnegative combinations form a closed set, because the inverse coordinate map on its span is continuous. There are finitely many selections, so their union $C$ is closed. This is the closedness of finitely generated cones used in Farkas' lemma.

When the primal linear program is infeasible, $b\notin C$. Let $p$ be the nearest point of $C$ to $b$, and set $h=p-b$. The minimizing property gives $h^T(z-p)\ge 0$ for every $z\in C$. Taking $z=0,2p$ gives $h^{T}p=0$. ConsequentlyIn particular $h\ge 0$ and $A^{T}h\ge 0$. Rescaling $h$ by the positive number $-h^{T}b$ produces the requested Farkas' lemma certificate:Now a feasible point of the relaxed inequalities would satisfySince ${\lambda }^{T}b=-1$, the sum of the nonnegative ${\lambda }_i$ is positive. Thus robust infeasibility under uniform constraint relaxation givesThe ellipsoid method makes progress by reducing the volume of a containing ellipsoid. A nonempty linear polyhedron may have empty interior, so small volume alone cannot certify that the original system is infeasible. Relaxing the inequalities remedies this difficulty, but must not make an infeasible system appear feasible. The displayed positive gap proves exactly that sufficiently small relaxations preserve infeasibility. For rational input, determinant bounds give a Farkas' lemma certificate of polynomial encoding length, so a sufficiently small rational relaxation can be chosen from the input encoding length. Together with a bounding box and bounds on the volume of a relaxed feasible system, this lets the ellipsoid method distinguish infeasibility from a feasible system of very small or zero original volume in polynomial time. The certificate argument alone does not assert a polynomial precision bound for arbitrary unencoded real coefficients.

One form of Farkas' lemma states that exactly one of the following holds:Their mutual exclusion is immediate: if both held, $b^{T}y=z^T{A}^{T}y\ge 0$.

For existence of the alternative certificate, let $C=\{Az:z\ge 0\}$, the finitely generated cone of the columns of $A$. It is convex. It is also closed, a fact that must be justified rather than assumed for arbitrary linear images of closed cones. In a representation with dependent active generators, choose a nonzero dependence ${\sum }_j{d}_j{a}_j=0$ with at least one $d_j>0$. Subtractfrom the nonnegative coefficient vector. The represented point is unchanged, all coefficients remain nonnegative, and at least one active coefficient disappears. Iteration produces a representation with independent active columns. For a convergent sequence in $C$, pass to a subsequence using the same independent set, possible because there are finitely many sets. Its coefficients converge through a fixed left inverse, and their limits remain nonnegative. This proves closedness of finitely generated cones.

The indicator functional ${\delta }_C$ is therefore proper, lower semicontinuous and convex. Its Legendre-Fenchel transform isIndeed a positive pairing with a cone generator can be scaled arbitrarily, while all nonpositive pairings give supremum zero. The Fenchel-Moreau theorem now givesIf $b\notin C$, the left side is infinite, so some feasible $w$ has $⟨w,b⟩>0$. Taking $y=-w$ gives $A^{T}y\ge 0$ and $b^{T}y<0$. If $b\in C$, the first alternative holds. The biconjugation theorem applied to a closed finitely generated cone proves the alternative.

For inequalities $Cx\le d$ with unrestricted $x$, split $x=x_{+}-x_{-}$ and add nonnegative slack:The equivalent Farkas certificate for linear inequalities is