If $uA=0, u\geq0, u1=1$ has not solution then $Ax<0$ yes has solution.

42 Views Asked by At

Prove that given a matrix $m \times n$, the system $A x < 0$ has solution if and only if $u A = 0, u \geqslant 0, u 1 = 1$ has not solution.

My attempt: I was able to prove the necessary condition but I have problems with the sufficiency.

Assuming that exists $x$ such that $A x < 0$, we suppose that exists $u$ such that \begin{eqnarray} u A & = & 0 \nonumber\\ u & \geqslant & 0 \tag{1}\\ u 1 & = & 1. \nonumber \end{eqnarray} For the last condition, $u$ can't be zero. Then exists at least a coordenate $u_i$ of $u$ that is positive. Then \begin{eqnarray*} u (A x) & < & u. 0\\ (u A) x & < & 0\\ 0 x & < & 0\\ 0 & < & 0, \end{eqnarray*} which is a contradiction, therefore the system 1 has not solution.

For the reverse I don't know how to begin. I only know if I take $u=(1,0,...,0)$ then $[A_{1j}]$ must has someone cordenate diferent to zero, and thus for the others rows of $A$.

Any help will be appreciate.

1

There are 1 best solutions below

0
On

For the reverse, we proced for contradiction. Let's suppose $Ax<0$ has not solution. So we take any vector $b<0$, then $$Ax\leq b$$ has not solution too. Then, for Farkas' lemma, the system $$uA=0,ub<0,u\geq0$$ has solution, i.e., exists $u$ such that satisfies the last system. Note $u$ has to be different to zero. We make $$u'=\frac{1}{\sum_{i=1}^mu_i}u,$$ then $u'$ satisfies $$u'A=0,u'\geq0,u'1=1,$$ which is a contradiction with hypothesis.