*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