Farkas's Lemma in Two Dimensions
![](/img/demonstrations-branding.png)
Requires a Wolfram Notebook System
Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.
This Demonstration shows a two-dimensional graphical exposition of Farkas's lemma: let be a
matrix and
be a
vector. Then either (1) there is a
vector
so that
and
; or (2) there is a vector
satisfying
and
. As is well known, geometrically this statement is equivalent to saying that
is either in the cone spanned by
or not. In this Demonstration,
and
are shown by green and orange lines and the inside of the cone is filled with light blue if (1) is true and with light red if (2) is true.
Contributed by: Tetsuya Saito (March 2011)
Open content licensed under CC BY-NC-SA
Snapshots
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.
Permanent Citation