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  20130322 13:47:37 
Last modified on  20130322 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 