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

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?

• Do you not have access to things like row reduction/reduced row echelon form? Nov 1, 2018 at 14:10
• What do you mean by having access? @Randall
– user604383
Nov 1, 2018 at 14:11
• Something is confusing me: why is $(-1,0,0)$ not an acceptable solution to you? Is there some nonnegative assumption that should be imposed? Nov 1, 2018 at 14:12
• This is an example from the textbook @WSL
– user604383
Nov 1, 2018 at 14:14
• @WSL nailed it. Your system does in fact have a solution. Is there a typo somewhere? Nov 1, 2018 at 14:39

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.