Farkas' Lemma is a fundamental result in linear inequalities and optimization theory. It has several equivalent formulations, and it can be proved using various methods, including linear algebra and the theory of convex sets. Here’s a proof using the separation theorem of convex sets:

Farkas' Lemma (Statement)

Given a matrix $A \in \mathbb{R}^{m \times n}$ and a vector $b \in \mathbb{R}^m$, exactly one of the following two statements is true:

1. There exists a vector $x \in \mathbb{R}^n$ such that $Ax = b$ and $x \geq 0$ (i.e., all components of $x$ are non-negative).
2. There exists a vector $y \in \mathbb{R}^m$ such that $A^T y \geq 0$ and $b^T y < 0$.

Proof Using the Separation Theorem

1. Convex Set Definition: Define the set $C = \{ Ax : x \geq 0, x \in \mathbb{R}^n \}$. This set $C$ is the convex cone generated by the columns of $A$.

2. Two Scenarios: Consider whether the vector $b$ lies in the set $C$ or not:

   • If $b \in C$, then there exists some $x \geq 0$ such that $Ax = b$. This corresponds to the first condition of the lemma being true.
   • If $b \notin C$, the vector $b$ lies outside the convex set $C$.

3. Separation Theorem: If $b \notin C$, by the Hyperplane Separation Theorem, there exists a non-zero vector $y \in \mathbb{R}^m$ such that $y^T b < 0$ and $y^T c \geq 0 \quad \text{for all } c \in C.$

4. Relation to the Matrix $A$: Since $C = \{ Ax : x \geq 0 \}$, for any $x \geq 0$, $y^T A x = (A^T y)^T x \geq 0.$ This implies $A^T y \geq 0$.

   Also, since $y^T b < 0$, this matches the second condition of the lemma.

5. Conclusion: Therefore, if $b \notin C$, there exists $y$ such that $A^T y \geq 0$ and $y^T b < 0$. If $b \in C$, then there exists $x \geq 0$ such that $Ax = b$. Hence, exactly one of the two conditions in Farkas' Lemma must hold.

Summary

Farkas' Lemma is proven by showing that if $b$ is not in the convex cone generated by the columns of $A$, then there exists a vector $y$ that separates $b$ from this cone. This separation corresponds to the second condition of the lemma.

Would you like more details or have any questions?

Here are some related questions you might find interesting:

1. How does Farkas' Lemma relate to linear programming duality?
2. Can you provide an example where Farkas' Lemma is applied?
3. What is the geometric interpretation of Farkas' Lemma?
4. How does Farkas' Lemma connect to the theory of convex cones?
5. Can Farkas' Lemma be generalized to nonlinear systems?

Tip: Farkas' Lemma is often used to prove the infeasibility of certain linear systems, making it a powerful tool in both theoretical and practical optimization.