Prove solvability of system of equations using Farkas' lemma

Question

Using Farkas' lemma, I have to prove $Ax=b$ ($A\in\mathbb{R}^{m\times n}$, $b\in\mathbb{R}^m$) is solvable iff $b^ty=0$ holds for all $y\in\mathbb{R}^m$ with $A^ty=0$.

Our version of Farkas' lemma goes: For $b\in\mathbb{R}^n$ the following statements are equivalent.

• There is $\gamma\in\mathbb{R}_+^m$ such that $b=A^t\gamma$.
• $b^td\leq0$ for all $d\in\mathbb{R}^n$ with $Ad\leq 0$.

I am able to prove the statement directly but I am not able to apply the lemma.

Answer 1

Hint: (Since it is a homework problem I prefer give you a small clue rather than a solution)

To fit your question into Farkas' lemma setting note that for any matrix $A$ the statement $A y = 0 $ is equivalent to $ \binom{A}{-A} y \leq 0 $.