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⊕Q which is equivalent to P⇔¬Q which is equivalent to ¬P⇔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⇔¬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⇒Q is logically equivalent to ¬P∨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