Let $A \in \mathbb R^{m\times n}$ and $c \in \mathbb R^{m}$
Show that
either (i) $Ax=c$ has a solution or (ii) $c^{T}y=1$ with $A^{T}y = 0$ has a solution.
My proof:
Let (ii) be satisfied iff there exists $w$ such that $c^{T}w<0$ with $A^{T}w = 0$. This is then equivalent to $\begin{pmatrix} A^{T} \\ -A^{T}\end{pmatrix}x\geq0$ with $c^{T}w < 0$. Then using the Farkas Lemma:
$\begin{pmatrix} A^{T} \\ -A^{T}\end{pmatrix}^{T}x=c$ where $x \geq 0$ does not have a solution.
Now I know that $\begin{pmatrix} A^{T} \\ -A^{T}\end{pmatrix}^{T}=(A, -A)$
but $(A, -A)x=c$ does not even make sense because $(A, -A) \in \mathbb R^{m \times 2n}$ while $x \in \mathbb R^{n}$, so they cannot be multiplied.
How do I get from $(A, -A)x=c, x \geq 0 \Rightarrow Ax=c, \forall x \in \mathbb R^{n}$
Any guidance is greatly appreciated.
Best Answer
So I understand you would like to use the third version of the Farkas lemma as in https://en.wikipedia.org/wiki/Farkas%27_lemma
$Ax = b$ is equivalent to $Ax \leq b, -Ax \leq -b$. Farkas lemma as above tells that $(A^t, -A^t) y = 0$ with $(b, -b)^T y < 0$ and $y \geq 0$, where $ y \in \mathbb R^{2m}$ does not have a solution. Writing $y = (y_1, y_2)$, with $y_1, y_2 \in R^{m}$, this is equivalent to $A^t(y_1-y_2) = 0$, $b^t y_1- b^t y_2 < 0,$ $y_1, y_2 \geq 0$. Define $z = y_1-y_2 \in R^{m}$. Then you get $A^t z =0$, $b^t z \neq 0$ does not have a solution.