Saturday, October 26, 2013

Theorem of the alternative and logical equivalence

In the theory of linear equalities and inequalities, several fundamental results are formulated as a theorem of the alternative: two alternatives are given, and exactly one of the alternatives is satisfied at any one time. A well known example is Farkas' lemma (1894):

For a real matrix $A$ and real vector $b$, exactly one of the following conditions is true:


  1. There exists a real nonnegative vector $x$ such that $Ax = b$
  2. There exists a real row vector y such that $yA$ is nonnegative and $yb$ is negative. 

where we say a real vector is (non)negative if all its entries are (non)negative.  Consider a theorem of the alternative given in the following form: given two alternatives $P$ or $Q$, only one of them is true at any time, no more and no less.  The truth table for this conclusion (denoted as $Z$) is then:

P Q Z
0 0 0
1 0 1
0 1 1
1 1 0

This means that $Z$ is equal to $P\oplus Q$ which is equivalent to $P\Leftrightarrow \neg Q$ which is equivalent to $\neg P\Leftrightarrow  Q$.
Thus the theorem

Exactly one of the two statements $P$ and $Q$ is true

can also be restated as:

P is true if and only if Q is false

or as:

P is false if and only if Q is true

Setting the 2 statements in Farkas' Lemma above as $P$ and $Q$, then
$P\Leftrightarrow \neg Q$ is written as

Let $A$ be a real matrix and let $b$ be a real vector.  Then there exists a nonnegative real vector $x$ such that $Ax=b$ if and only if for each row vector $y$ either $yA$ is not a nonnegative vector or $yb$ is nonnegative.

Given that $P\Rightarrow Q$ is logically equivalent to $\neg P \vee Q$, this can be rewritten as

Let $A$ be a real matrix and let $b$ be a real vector.  Then there exists a nonnegative real vector $x$ such that $Ax=b$ if and only if $yb$ is nonnegative for each row vector $y$ such that $yA$ is a nonnegative vector.

which is the form of Farkas' Lemma as stated in A. Schrijver, Theory of Linear and Integer Programming, Wiley, 1998.

No comments:

Post a Comment