[Math] How to show that these two versions of Farkas lemma are equal

linear algebraoptimization

One version of Farkas lemma is that

Let $A$ be a real $m\times n$ matrix and $b$ an $m$-dimensional real vector. Then,
exactly one of the following statements are true.

  1. There exists an $x \in \mathbb{R}^n$ such that $Ax=b$ and $x\ge 0.$
  2. There exists a $y \in \mathbb{R}^m$ such that $y^TA \le 0,\ y^Tb >0$.

Then my book says it uses a slightly modified version that says that if:

  1. $Ax=b$ doesn't have a solution.

Then

  1. there is a vector $y$ such that $y^TA=0$, and $y^Tb > 0$.

I have two questions:

  1. How does the last implication follow from Farkas lemma?
  2. Is the last thing I wrote actually an equivalence? That is is it so that either $Ax=b$ has a solution or $y^TA=0,\ y^Tb>0$ has a solution, but not both?

Best Answer

The trick is to apply Farkas lemma with modified matrix $\tilde A$ and vector $\tilde b$ that are constructed from $A,b$.

Let $A,b$ such that $Ax=b$ has no solution. Then the system $$ A x_1 - Ax_2 = b, \ x_1 \ge 0,\ x_2 \ge0 $$ has no solution, or, equivalently $$ \begin{bmatrix} A & -A \end{bmatrix}x = b, \ x\ge 0 $$ is not solvable. Then by Farkas lemma as cited in the question, it follows that there is a vector $y$ such that $$ y^T\begin{bmatrix} A & -A \end{bmatrix} \le 0, \ y^Tb>0. $$ This implies $y^TA\le0$ and $-y^TA\le0$, hence $y^TA=0$. This proves the implication (1) $\Rightarrow$ (2).

Now assume there is $y$ such that $y^TA=0$ and $y^Tb>0$. Suppose there is $x$ with $Ax=b$. $$ 0= (y^TA)x = y^Tb>0, $$ a contradiction. This proves (2) $\Rightarrow$ (1).

Related Question