For a real matrix $A$ and real vector $b$, exactly one of the following conditions is true:
- There exists a real nonnegative vector $x$ such that $Ax = b$
- 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