Teorema 1 (Lema de Farkas). Sean \(A\in\mathbb{R}^{m\times n}\) y \(b\in\mathbb{R}^m\). Entonces, exactamente uno de los siguientes conjuntos debe ser vacío:
\(A:=\left\{x\in\mathbb{R}^n\,:\, Ax=b,\, x\geq 0\right\}\);
\(B:= \left\{y\in\mathbb{R}^m\,:\,A^Ty\geq 0,\, b^Ty<0\right\}\).
Demostración. Sean \(A\in\mathbb{R}^{m\times n}\) y \(b\in\mathbb{R}^m\), cualesquiera.
Primera etapa En una primera etapa vamos a probar que los conjuntos \(A\) y \(B\) no pueden ser no vacíos al mismo tiempo. Así, supongamos, por contradicción que no lo son y existen \(x\in\mathbb{R}^n\) tal que
\[\tag{1}\label{1} Ax=b \quad x\geq 0.\]
Y, también existe \(y\in\mathbb{R}^m\) tal que
\[\tag{2}\label{2} A^T y \geq 0 \quad y^Tb <0.\]
Así, notemos que usando la ecuación (1) como \(Ax=b\)
\[y^T Ax = y^T (Ax) = y^T b <0\quad\Longrightarrow\quad y^T b <0\]
Además, se tiene que
\[y^T Ax = (y^T A)x = (A^T y)^T x \geq 0\quad\Longrightarrow\quad y^T b \geq 0.\]
nuevamente por las definiciones de los conjuntos. Así, hemos concluido que
\[y^T b\geq 0 \quad \land \quad y^b <0,\]
lo cual no es posible y por lo tanto, los conjuntos \(A\) y \(B\) no pueden ser vacíos simultáneamente.
(Observación: Vamos a probar que \(B\neq\varnothing\) si y solo si \( A\neq\varnothing\), equivalentemente se tiene la negación \(B=\varnothing\) si y solo si \(A\neq\varnothing\).)
Segunda etapa
Supongamos que \(A\) es vacío, vamos a probar que \(B\) es no vacío.
Para esto, consideremos el siguiente conjunto
\[C = \text{cono}(a_1,\ldots,a_n) = \left\{\sum_{i=1}^n \alpha_i a_i\,:\, \alpha_i \geq 0\right\},\]
donde \(\{a_1,\ldots,a_n\}\) es el conjunto de vectores columna de de la matriz \(A\). Equivalentemente, el conjunto \(C\) se puede ver de la siguiente manera:
\[C = \{ s\in\mathbb{R}^m\,: \, s = A \alpha \, , \, \alpha\in\mathbb{R}^n \}.\]
(Observación: Este conjunto se denomina el cono convexo y difiere de la combinación convexa pues no se exige que la suma de las constantes de la combinación sea \(1\), i.e, \(\sum_{i=1}^n \alpha_i= 1\).)
Ahora, notemos que este conjunto es convexo y cerrado.
En efecto, sean \(a,b\in C\), y \(\lambda\in [0,1]\), notemos que
\[\begin{aligned} \lambda a + (1-\lambda)b & = \lambda A \alpha_x + (1-\lambda) A \alpha_y\\ & = A \tilde{\alpha_x} + A \tilde{\alpha_y} \in C, \end{aligned}\]
donde \(\tilde{\alpha_x}= \lambda \alpha_x\geq 0\) y \(\tilde{\alpha_y}= (1-\lambda) \alpha_y\geq 0\), pues \(\lambda \in[0,1]\).
Vamos que probar que \(C\) es cerrado. Sea \(\left(c_n\right)_{n\in\mathbb{\mathbb{N}}}\subseteq C\), una sucesión convergente a un \(c^*\), vamos a probar que \(c^*\in C\). Para ello, se tiene que
\[c_k = A\alpha_{c_k} \quad \alpha_{c_k}\in\mathbb{R}^n \,\, \alpha_{c_k}\geq 0.\]
Luego, se tiene que la sucesión \(\left(c_n\right)_{n\in\mathbb{\mathbb{N}}}\), induce una sucesión \(\left(\alpha_{c_n}\right)_{n\in\mathbb{\mathbb{N}}}\) en \(W:= \left\{\alpha\in\mathbb{R}^n\,:\, \alpha\geq 0\right\}\). Así, como la sucesión es convergente si y solo sí cada una de sus sucesiones componentes converge en \([0,+\infty[\), entonces la sucesión \(\left(\alpha_{c_n}\right)_{n\in\mathbb{\mathbb{N}}}\) converge en \(W\) y más aún, \(\left(c_n\right)_{n\in\mathbb{\mathbb{N}}}\) converge en \(C\). Así como la sucesión fue arbitraria, se sigue que \(C\) es cerrado.
Nuestro objetivo es encontrar un \(y\in\mathbb{R}^m\), tal que
\[A^T y \geq 0 \quad y^T b<0.\]
Para ello, tenemos que \(\{b\}\) es un conjunto compacto pues es cerrado y acotado en \(\mathbb{R}^{m\times 1}\), así por el teorema de Heine-Borel, se tiene que es compacto y más aún es convexo, lo cual se ve fácilmente.
Además, se tiene que \(\{b\}\) y \(C\) son disjuntos pues por hipótesis \(A\) es vacío.
De esta manera, por el teorema de Hanh-Banach, segunda forma geométrica, existe un hiperplano de separación \(H = [f=\gamma]\) cerrado que separa estrictamente a los conjuntos \(\{b\}\) y \(C\), es decir, existe \(\gamma\in\mathbb{R}\) tal que
\[f(b) < \gamma < f(s) \quad \forall s\in C,\]
equivalentemente se tiene que
\[\tag{3}\label{3} f(b) < \gamma < f(s) \quad \forall \alpha \in\mathbb{R}^n \, , \, \alpha\geq 0.\]
Ahora, como el hiperplano \(H\) es cerrado, entonces sabemos que \(f\in(\mathbb{R}^n)^*\), es decir, \(f\) es lineal y continuo de \(\mathbb{R}^n\) en \(\mathbb{R}\). Así, como \(0\in C\) (tomando \(\alpha=0\)), entonces
\[\tag{4}\label{4} f(b) < 0.\]
Luego, por el teorema de representación de Riez, existe un \(q\in\mathbb{R}^m\), tal que
\[f(s) = q^T s \quad \forall s\in \mathbb{R}^m.\]
De donde, usando lo anterior en (3), se sigue que
\[q^T b < \gamma < q^T A\alpha \quad \forall \alpha\in\mathbb{R}^n.\]
De esta manera, en (4) se tiene que
\[\begin{aligned} q^T b <0. \end{aligned}\]
Y, por otro lado, tenemos que
\[\begin{aligned} q^T A\alpha > 0 & \quad\Longrightarrow\quad(A \alpha)^T q >0 \\ & \quad\Longrightarrow\quad \alpha^T A^T q >0 \\ & \quad\Longrightarrow\quad A^T q \geq 0 && \text{Pues }\,\alpha\geq 0. \end{aligned}\]
Así, se tiene que \(q\in B\) y por lo tanto \(B\) es no vacío, como se quería.
Supongamos que \(B\) es no vacío, vamos a probar que \(A\) es vacío.
Por contradicción, supongamos que \(A\) no es vacío. Notemos que esto no es posible pues en una primera etapa probamos que los conjuntos \(A\) y \(B\) no pueden ser no vacíos simultáneamente. Así se tiene que \(A\) es vacío, lo que completa esta etapa.
Notemos que así se ha probado que
\[B\neq\varnothing\quad\Leftrightarrow\quad A= \varnothing,\]
es decir, que solo uno de los conjuntos debe ser vacío.