# How to apply Farkas lemma in the form: there is $x\ge0$ st $Ax=0$ iff there is no $y$ st $y^T A>0$?

Let $A\in \mathbb R^{m,n}$ then there exists and $x \in \mathbb R^n x \neq0 ;x \ge 0; Ax=0$ if and only if there exists no vector $y$ such that $y^tA \gt 0$

I do know Farkas Lemma but I dont know how to apply it to that specific case. Would appreciate any help, hints.

The version of Farkas Lemma I know is the following with $A,x,y$ as above :

There exists and $x \ge 0$ such that $Ax=b$ if and only if there does not exist a vector $y$ such that $y^TA \ge 0$ and $b^ty\lt 0$

Edit: $x\ge 0$ means $x_i\ge 0$ for every $i=1....n$

• What version do you know? Commented Jul 9, 2017 at 12:18
• What does "$x\ge 0$" mean for $x\in R^n$? What order are you using? Commented Jul 9, 2017 at 12:24
• @user247327 $x≥0$ means $x$ lies in the first quadrant, ie using the standard coordinate frame all components of $x$ are greater than $0$. Commented Jul 9, 2017 at 12:25
• @user247327 it means that $x_i \ge 0$ Commented Jul 9, 2017 at 12:25

First note that all alternative theorems are very very special cases of separation theorem. So you can solve them using separation theorem. I myself have not memorized either of them, since they all saying separating two sets (usually cones) in different languages.

But here you want solve problem using Farkas Lemma. I'll give you hint:

Left to Right : If there exist $x \in \mathbb R^n x \neq0 ;x \ge 0; Ax=0$ and there is $y \in \Bbb R^n$ such that $y^t A > 0$ then $0 = y^t Ax > 0$ which is contradiction.

Right to Left: Assume the inequality system $y^t A > 0$ has no solution! Thus for all scalar $s > 0$ the inequality system $y^t A - s e \ge 0$ has no solution, where $e= (1,1,...,1)$ therefore setting $z=\begin{pmatrix} y \\ -s \end{pmatrix}$ and $\bar{A} =\begin{pmatrix} A\\ e \end{pmatrix}$ and $b^t :=(0,0,0...,0,1)$, one can observe that in newly defined symbols we have the system $$z^t \bar{A} \ge 0 , \quad b^t z <0$$ has no solution, Now just apply farkas lemma to new system!

This is just Gordan's theorem. In order to deduce this result from Farkas Lemma, notice that:

$$A^Ty>0 \textrm{ if and only if }\; \exists\; s>0: A^Ty-se\geq 0,$$ where $e=(1,\ldots,1)^T \in \mathbb{R}^n.$

So, the system $A^Ty>0$ has no solution if and only if the system

$$[A^T,\;-e]y'\geq 0,\; [0,\ldots,0,-1]y'<0$$ has no solution in $\mathbb{R}^{n+1}$

Apply now Farkas's Lemma. Hope this helps.