# Farkas lemma, proof of

We begin by showing that at least one of the systems has a solution.

Suppose that system 2 has no solution. Let $S$ be the cone in $\mathbb{R}^{n}$ generated by nonnegative linear combinations of the rows $a_{1},\dots,a_{m}$ of $A$. The set $S$ is closed and convex. Since system 2 is unsolvable, the vector $c$ is not in $S$; therefore, there exist a scalar $\alpha$ and $n$-column vector $x$ such that the hyperplane $x^{T}v=\alpha$ separates $c$ from $S$ in $\mathbb{R}^{n}$. This hyperplane can be selected so that for any point $v\in S$,

 $x^{T}c^{T}>\alpha>x^{T}v^{T}.$

Since $0\in S$, this implies that $\alpha>0$. Hence for any $w\geq 0$,

 $\alpha>x^{T}(wA)^{T}=wAx=\sum_{i=0}^{m}w_{i}(Ax)_{i}.$

Each $(Ax)_{i}$ is nonpositive. Otherwise, by selecting $w$ with $w_{i}$ sufficiently large and all other $w_{j}=0$, we would get a contradiction. We have now shown that $x$ satisfies $Ax\leq 0$ and $cx=(cx)^{T}=x^{T}c^{T}>\alpha>0$, which means that $x$ is a solution of system 1. Thus at least one of the systems is solvable.

We claim that systems 1 and 2 are not simultaneously solvable. Suppose that $x$ is a solution of system 1 and $w$ is a solution of system 2. Then for each $i$, the inequality $w_{i}(Ax)_{i}\leq 0$ holds, and so $w(Ax)\leq 0$. However,

 $(wA)x=cx>0,$

a contradiction. This completes the proof.

Title Farkas lemma, proof of FarkasLemmaProofOf 2013-03-22 14:12:51 2013-03-22 14:12:51 CWoo (3771) CWoo (3771) 13 CWoo (3771) Proof msc 15A39