Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to prove the Farkas Lemma using the Fourier-Motzkin elimination algorithm. From Wikipedia:

Let A be an $m \times n$ matrix and $b$ an $m$-dimensional vector. Then, exactly one of the following two statements is true:

  1. There exists an $x \in \Bbb R^n$ such that $Ax = b$ and $x \ge 0$.
  2. There exists a $y \in \Bbb R^m$ such that $A^Ty \ge 0$ and $b^Ty < 0$.

The first direction is quite easy. I assume that there is a vector $y$ and I found a contradiction. To the other direction I have used the fourier-motzkin elimination to reduce the number of variables. I assume that $Ax \le b$ and I do one step from the algorithm. I create a new system $A'x' \le b'$. I know that there exist a non-negative matrix $M$ that is a linear combination of the new system to the original. I have followed the direction of repeating the algorithm $n$ times to eliminate all the variables and create the system: $0 \le b''$.

Now in order this system to be infeasible it must be that: $b''<0$. So I can assume that exist vector $y''$ such that $y''A''=0$ and also $y''b''<0$ because $b'<0$ and $y\ge 0$. Now I can prove that also there is a vector $y$ for the original system. But the repetition of $n$ steps seems to me a bit arbitrary. If I just do one step and create the system $A'x'\le b'$ how I can use it is infeasible?

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.