Show that if System 1 has no solution, System 2 has a solution.

Question

Let $\mathbf{A}$ be a $p \times n$ matrix and $\mathbf{B}$ be a $q \times n$ matrix.

System 1: $\mathbf{Ax} < \mathbf{0}$ and $\mathbf{Bx} = \mathbf{0}$ for some $\mathbf{x} \in R^n$.

System 2: $\mathbf{A}^t\mathbf{u} + \mathbf{B}^t\mathbf{v} = \mathbf{0}$ for some nonzero $(\mathbf{u},\mathbf{v})$ with $\mathbf{u} \geq \mathbf{0}$

As the title says, I need to show that if System 1 has no solution, System 2 has a solution.

I am not quite sure what to do.

I know that it has something to do with Farkas's Lemma and the various corollaries of Farkas's Lemma, etc.

I can also see that if System 1 does not have a solution, then specifically there does not exist an $\mathbf{x} \in R^n$ in which $\mathbf{Ax} < \mathbf{0}$ because $\mathbf{Bx} = \mathbf{0}$ can always be satisfied by $\mathbf{x} = \mathbf{0}$.

Answer 1

Let $e$ be the all one vector.

Consider the optimization problem,

$$\min 0$$

Subject to $$Ax \le -e$$ $$Bx=0$$

Of which the dual is

$$\max -e^Tu$$

subject to $$A^Tu+B^Tv=0$$

$$u \ge 0$$

Since the primal is infeasible but the dual is feasible, the dual must be unbounded.

Since it is unbounded, we can find $(u, v) \ne 0, u \ge 0$ that is feasible to the dual problem.