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?

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

1 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


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.


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


You must log in to answer this question.