# An Application of Farkas' Lemma

The Farkas' lemma I know is:

Exactly one of the following systems has a solution. $$$$\left\{ \begin{array}{l} Ax=b,\ x\geq0 \\ A^Ty\geq0, \ y^Tb<0 \end{array} \right.$$$$

I want to find the alternative system for $$$$c^Tx<0,Ax\geq0,Bx=0$$$$

My solution is:

$$$$\left( \begin{array}{c} A\\ B\\ -B \end{array} \right)x\geq0, x^Tc<0$$$$ By Farkas' Lemma, we have the corresponding alternative system $$$$(A^T\ B^T\ -B^T) \left( \begin{array}{c} y_1\\ y_2\\ y_3 \end{array} \right)=c,\quad y_1,y_2,y_3\geq0$$$$

Can anyone tell me whether my solution is correct? I'm not sure about $$y_2$$ and $$y_3$$, it seems there's some relation between $$y_2$$ and $$y_3$$ through $$B^T$$... Should I "rewrite" $$y_2$$ and $$y_3$$ into a vector $$v$$ such that $$v=y_2-y_3$$?

Your solution is correct. Your equation is $$A^T y_1 + B^T y_2 - B^T y_3 = c$$, which is equivalent to to $$A^T y_1 + B^T( y_2 - y_3) = c$$. You can indeed replace $$y_2-y_3$$ with $$v$$. What can you say about the sign of $$v$$?
• I can not tell the sign of $v$... So it is correct to just left $y_1$, $y_2$ and $y_3$ over there? It is confused to me that at the beginning we have only $x$ but end up with three $y$s. – Huaixin Nov 17 '19 at 1:16
• what do you mean that you cannot tell the sign of $v$? – LinAlg Nov 17 '19 at 13:54
• Oh sorry, I mean I don't know the sign of $v$. – Huaixin Nov 17 '19 at 14:27
• that's right, so you get $A^Ty_1 + B^T v = c$, with $y_1 \geq 0$ and $v \in \mathbb{R}^m$ – LinAlg Nov 17 '19 at 15:25