# Duality between $Ax<b$ and another system, but Gordan's just misses

I am trying to show that

$$Ax < b$$

Is feasible

iff

$$A^T y =0 , b^Ty + s = 0, (y,s) \ge 0, (y,s) \ne 0$$

Is infeasible.

## Work So Far

Now when I try to hit this with Gordan's Lemma I seem to get just short of proving it and I don't know how to go over the remaining gap.

Observe the bottom system can be written as

$$G^T w =0, w \ge 0, w \ne 0, G^T = \begin{bmatrix} A^T & 0 \\ b^T & 1\end{bmatrix}, w = \begin{bmatrix} y \\ s \end{bmatrix}$$

So by Gordans Lemma either this is feasible or

$$G \mu < 0, \mu = \begin{bmatrix} x \\ r \end{bmatrix}$$

Is feasible. This of course expands as

$$\begin{bmatrix}A & b \\ 0 & 1 \end{bmatrix} \begin{bmatrix} x \\ r \end{bmatrix} < 0 \rightarrow \begin{matrix} Ax + br < 0 \\r < 0 \end{matrix} \iff \begin{matrix} Ax < bq \\ q > 0 \end{matrix}$$

So it is clear how to proceed in one direction

If $Ax < b$ then $\begin{matrix} Ax < bq \\ q > 0 \end{matrix}$ with $q=1$ that gives us $r=-1$ that solves $$\begin{bmatrix}A & b \\ 0 & 1 \end{bmatrix} \begin{bmatrix} x \\ r \end{bmatrix} < 0$$

And from Gordan's it follows that

$$A^T y =0 , b^Ty + s = 0, (y,s) \ge 0, (y,s) \ne 0$$

Is infeasible.

But now suppose we assume that

$$A^T y =0 , b^Ty + s = 0, (y,s) \ge 0, (y,s) \ne 0$$

Is infeasible.

The furthest we can go is state $\exists q$ such that

$$\begin{matrix} Ax < bq \\ q > 0 \end{matrix}$$

But unless $q = 1$ we don't have

$$Ax < b$$

And it isn't obvious that $q=1$ MUST be able to solve this.