# 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. 1.

$Ax\leq 0$ and $cx>0$ for some $n$-column vector $x$;

2. 2.

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

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

1. 1.

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

2. 2.

$wA\leq c$ and $w\geq 0$ for some $m$-row vector $w$.

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

Title Farkas lemma FarkasLemma 2013-03-22 13:47:37 2013-03-22 13:47:37 Koro (127) Koro (127) 11 Koro (127) Theorem msc 15A39 Farkas theorem