Details

Consider a linear system equation , where is in general an matrix and and are respectively an and an vector. Then Farkas's lemma states that one but not both of the following two statements is true: (1) there is a vector solving the equation; or (2) there is a vector satisfying and , where is the zero vector. Geometrically, this is equivalent to saying that: (1) is in the cone spanned by ; or (2) is not in . To show the equivalence is simple. The first statement requires directly that is in , so that . If (1) does not hold, then is not in ; therefore, we will find a separating hyperplane between and . In that case, we can find a vector whose angles with each row of are at most . Because such a is included in , its angle with must be greater than . In order to understand this lemma intuitively, it is more or less sufficient to understand the two-dimensional case.