Farkas lemma

Given an $m\times n$ matrix $A$ and an $1\times n$ real row vector $c$, both with real coefficients, one and only one of the following systems has a solution:

1. $Ax\le 0$ and $cx>0$ for some $n$-column vector $x$;

2. $wA=c$ and $w\ge 0$ for some $m$-row vector $w$.

Equivalently, one and only one of the following has a solution:

1. $Ax\le 0$, $x\le 0$ and $cx>0$ for some $n$-column vector $x$;

2. $wA\le c$ and $w\ge 0$ for some $m$-row vector $w$.

Remark. Here, $Ax\ge 0$ means that every of $Ax$ is nonnegative, and similarly with the other expressions.

Title	Farkas lemma
Canonical name	FarkasLemma
Date of creation	2013-03-22 13:47:37
Last modified on	2013-03-22 13:47:37
Owner	Koro (127)
Last modified by	Koro (127)
Numerical id	11
Author	Koro (127)
Entry type	Theorem
Classification	msc 15A39
Synonym	Farkas theorem