[Math] Derive this variant of Farkas’ lemma, through another variant of Farkas’ lemma.

duality-theoremslinear algebralinear programming

Derive the following variant of Farkas' lemma:

For each $mxn$ matrix A and vector $b\in\mathbb{R^m}$ one of the following statements is true:

  • $\exists x\in\mathbb{R^n}$ such that $Ax=b$

  • $\exists y\in\mathbb{R^m}$ such that $y^TA=0$ and $y^Tb=1$

By this version of Farkas' lemma:

For each $mxn$ matrix A and vectors $b\in\mathbb{R^m}$ and $c\in\mathbb{R^n}$ one of the following statements is true:

  • $\{x\in\mathbb{R^n}\mid Ax=b,x\geq0\}\neq \emptyset$

  • $\{y\in\mathbb{R^m}\mid y^TA\geq0,y^Tb<0\}\neq \emptyset$

I have no idea where to start this. Can someone help me in which direction to start?

Best Answer

Just use the second variant of Farkas's lemma for matrix $A$ and vector $-b$. So now you also have For each $m$x$n$ matrix A and vector $b\in R^m$ one of the following statements is true:

{$x\in R^n | Ax=b,x\le0$}$\ne\varnothing$

{$y\in R^m | y^TA\le0,y^Tb\gt0$}$\ne\varnothing$

Denoting $y^Tb=k, k\ne0$ use Farkas's lemma one more time now for vector $b/k$

Related Question