0
$\begingroup$

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$

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

2 Answers 2

2
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .