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.

Explore the proof of Farkas' Lemma, a fundamental result in linear inequalities and optimization theory. This detailed proof utilizes the separation theorem of convex sets, demonstrating how it applies to linear systems. Ideal for undergraduate and graduate students in mathematics or related fields.

Math Problem Statement

Solution

Ask a new question for Free

By Image

Math Problem Analysis

Mathematical Concepts

Formulas

Theorems

Suitable Grade Level

Related Recommendation