Farkas' Lemma is a fundamental result in linear algebra and optimization. It provides a condition for the solvability of a system of linear inequalities. The lemma states:

**Farkas' Lemma**: 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 \) (component-wise).
2. There exists a vector \( y \in \mathbb{R}^m \) such that \( y^T A \geq 0 \) and \( y^T b < 0 \).

### Proof of Farkas' Lemma:

1. **Suppose (1) is true**:
   - If there exists \( x \geq 0 \) such that \( Ax = b \), we need to show that (2) cannot be true.
   - Assume \( y \in \mathbb{R}^m \) is such that \( y^T A \geq 0 \) and \( y^T b < 0 \).
   - Then, \( y^T b = y^T A x \), since \( Ax = b \).
   - However, since \( y^T A \geq 0 \) and \( x \geq 0 \), \( y^T A x \geq 0 \), contradicting the assumption that \( y^T b < 0 \).
   - Therefore, if (1) holds, (2) must be false.

2. **Suppose (1) is false**:
   - This means there is no \( x \geq 0 \) such that \( Ax = b \).
   - We aim to prove that (2) must then be true, which would mean that there exists \( y \) such that \( y^T A \geq 0 \) and \( y^T b < 0 \).
   - Consider the set \( C = \{Ax : x \geq 0\} \). This is a convex cone in \( \mathbb{R}^m \).
   - Since \( b \notin C \), by the separating hyperplane theorem, there exists a hyperplane defined by a non-zero vector \( y \) that strictly separates \( b \) from \( C \). 
   - Specifically, \( y \) satisfies \( y^T A \geq 0 \) for all \( x \geq 0 \), meaning \( y^T C \geq 0 \), and \( y^T b < 0 \).
   - This establishes (2).

Thus, either \( x \) exists satisfying the first condition, or \( y \) exists satisfying the second condition, but not both.

Would you like to explore this proof further or have any questions?

### Related Questions
1. How does Farkas' Lemma relate to the theory of linear programming?
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 with the Duality Theorem in linear programming?
5. What are some generalizations of Farkas' Lemma?

### Tip:
Understanding the geometric interpretation of Farkas' Lemma can provide deeper insights into linear programming and optimization problems.

Explore the proof of Farkas' Lemma, a crucial result in linear algebra and optimization. Understand the conditions for the solvability of systems of linear inequalities. Suitable for advanced undergraduate students and researchers.

Math Problem Statement

Solution

Ask a new question for Free

By Image

Math Problem Analysis

Mathematical Concepts

Formulas

Theorems

Suitable Grade Level

Related Recommendation