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:

    “One is apt to be discouraged by the frequency with which Mr. Hardy has persuaded himself that a macabre subject is a poem in itself; that, if there be enough of death and the tomb in one’s theme, it needs no translation into art, the bold statement of it being sufficient.”
    —Rebecca West (1892–1983)

    “One is apt to be discouraged by the frequency with which Mr. Hardy has persuaded himself that a macabre subject is a poem in itself; that, if there be enough of death and the tomb in one’s theme, it needs no translation into art, the bold statement of it being sufficient.”
    —Rebecca West (1892–1983)