Farkas' Lemma - Statement of The Lemma

Statement of The Lemma

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

  1. There exists an x ∈ Rn such that Ax = b and x ≥ 0.
  2. There exists a y ∈ Rm such that ATy ≥ 0 and bTy < 0.

Here, the notation x ≥ 0 means that all components of the vector x are nonnegative.

There are a number of slightly different (but equivalent) formulations of the Lemma in the literature. The one given here is due to Gale, Kuhn and Tucker in 1951.

Read more about this topic:  Farkas' Lemma

Famous quotes containing the words statement of and/or statement:

    “Eroticism has its own moral justification because it says that pleasure is enough for me; it is a statement of the individual’s sovereignty.”
    —Mario Vargas Llosa (b. 1936)

    “A sentence is made up of words, a statement is made in words.... Statements are made, words or sentences are used.”
    —J.L. (John Langshaw)