Dual Linear Program I was asked to construct dual linear program to prove the following statement: $S_1=\{A^Ty\leq0, b^Ty>0\}$ is nonempty iff $S_2=\{Ax=b,x\geq0\}$ is empty.
I'm trying to begin with $$\min_{A^Ty\geq0} b^Ty$$ and its dual $$\max_{x\geq0, Ax=b} c^Tx$$ with $c=0$ but stuck after that.
Any help would be greatly appreciated!
 A: This is what's known as a "theorem of the alternative". We can show it using a powerful tool for LPs, strong duality.
From the primal LP
$$
\max_x \;\{c^\top x : Ax=b,\,x\geq0\}\tag{$P$}
$$
we can find the dual (which we will call $(D)$) by $(i)$ replacing the constraints with appropriate penalization and $(ii)$ using the minmax inequality (aka weak duality)
$$
(P) \overset{(i)}{\equiv} \max_{x\geq0}\big\{\min_y \{c^\top x + y^\top(b-Ax)\}\big\} \overset{(ii)}{\leq} \min_y\max_{x\geq0} c^\top x + y^\top(b-Ax)
=\begin{cases}-\infty,\quad&\text{if $Ax\neq b$}\\\min_y\{b^\top y : A^\top y\geq c\},\quad&\text{o.w.}\end{cases} \equiv (D).
$$
By strong duality, we know that the optimal values $\nu(P)$ and $\nu(D)$ are equal if both programs are feasible.
Returning to the question, let $S_2 = \{x:Ax=b,x\geq0\}$, $S_1=\{y:A^\top y\geq0,b^\top y>0\}$ and $c=0$.
We can make the following argument to show that $S_1\neq\emptyset \iff S_2=\emptyset$.
$(\impliedby)$: If $S_2=\emptyset$, then problem $(P)$ is infeasible.
By strong duality, the dual of $(P)$ (i.e.,  problem $(D)$) is unbounded or infeasible.
Since $y=0$ is always feasible for $(D)$, then we must have that $\nu(D)=+\infty$ and hence there exists a feasible $y$ with $b^\top y>0$.
$(\implies)$: We will consider the contrapositive.
If $S_2\neq\emptyset$, then $(P)$ is feasible and has optimal value $\nu(P)=0$.
By strong duality, since $(D)$ is always feasible from $y=0$, we have that $\nu(P)=\nu(D)=0$.
Hence there cannot be a feasible $y$ that attains a strictly better objective value than zero, meaning that $S_1=\emptyset$.
