How to prove that equation system does not have non negative solution?

Question

I have this equation system:

-$\mathbf{x}^{}_{1}$ - $\mathbf{x}^{}_{2}$ - $\mathbf{x}^{}_{3}$ = 1

-2$\mathbf{x}^{}_{1}$ - $\mathbf{x}^{}_{2}$ - 2$\mathbf{x}^{}_{3}$ = 2

knowing that $\mathbf{x}^{}_{}$ = ($\mathbf{x}^{}_{1}$,$\mathbf{x}^{}_{2}$,$\mathbf{x}^{}_{3}$)

Prove that this system does not have non negative solution

In my book there is a brief hint which says we should prove that $ \ \left\{ \begin{array} {A}xA=b \\ x >= 0 \end{array} \right. $ has no non-negative solution where b = (1,2) and

A = $\begin{pmatrix}-1 & -2\\\ -1 & -1 \\\ -1 & -2\end{pmatrix}$

After that takes some y: $\mathbf{y}^{}_{}$=($\mathbf{y}^{}_{1}$,$\mathbf{y}^{}_{2}$), and constructs a system where Ay >= 0 and by < 0

$ \ \left\{ \begin{array} {A}Ay>=0 \\ by < 0 \end{array} \right. $

I can't understand the solution and the hint. Why exactly it takes y and continues in that way?

Answer 1

Let me try to explain the hint:

Suppose you found a $y$ such that $Ay \ge 0$ and $by < 0$ and suppose on the contrary that you can find $x$ such that $x^TA=b$ and $x \ge 0$.

then we have

$$x^TAy=by$$

The right hand side is negative.

But if you examine the left hand side, since $x \ge 0$ and $Ay \ge 0$, we have $x^TAy \ge 0$. The left hand side is nonnegative. Hence, we have found a contradiction.

In summary, the ability to find a $y$ that satisfies $Ay \ge 0$ and $by < 0$ is a certificate of proof that such $x$ cannot exists.

I will leave the task of finding such $y$ as an exercise.

Remark:

This is a glimpse to duality theory/ linear programming/ Farkas Lemma.