Given a system of n linear equations. Prove that the system is inconsistent if and only if you can obtain 0 = 1, by using linear combinations.I do not want to apply theorems from linear algebra here. Instead of it I want to use Farkas' lemma.Every equation can be rewrited in form of two inequalities with ≤ and ≥, now I got 2 n inequalities instead of n equations.I think that's the moment for me to apply Farkas' lemma, but why I can always get 0 ≤ 1 and 0 ≥ 1?

Question

Given a system of n linear equations. Prove that the system is inconsistent if and only if you can obtain   0  =  1, by using linear combinations.I do not want to apply theorems from linear algebra here. Instead of it I want to use Farkas&#039; lemma.Every equation can be rewrited in form of two inequalities with   ≤ and   ≥, now I got   2  n inequalities instead of   n equations.I think that&#039;s the moment for me to apply Farkas&#039; lemma, but why I can always get   0  ≤  1 and   0  ≥  1?

Ryan Fitzgerald · Accepted Answer

It is very easy to prove the result from linear algebra (Gauss eliminations). If you prefer to work it out using Farkas lemma then you can do the following: the equation   A  x  =  b fits the best to the first alternative of the Farkas lemma, we only missing the positivity of   x. To get positivity one can write   x  =  v  −  w, where   v  ,  w  ≥  0. It is the standard rewriting in Linear Programming. You get      (                            A                          −          A                      )        (                            v                                      w                      )    =  b  ,    v  ,  w  ≥  0.This is exactly the first alternative. If it has no solution then the dual system      (                                        A            T                                                −                      A            T                                )    y  ≤      (                            0                                      0                      )    ,        b    T    y  &amp;gt;  0has a solution. The dual system is the same as      A    T    y  =  0  ,        b    T    y  &amp;gt;  0    ⇔        y    T    A  =  0  ,        y    T    b  &amp;gt;  0.One can always scale   y to get       y    T    b  =  1.It means that if you multiply your original equation   A  x  =  b by       y    T   from the left you will get                                y          T                A            ⏟              =      0        x  =                                y          T                b            ⏟              =      1          ⇒    0  =  1.

Given a system of n linear equations. Prove that the system is inconsistent if and only if you can o

Answered question

Answer & Explanation

New Questions in Algebra I