NICEFA Logo
nicefa.
Library
←Module

Farkas' Lemma: A Fundamental Theorem of Alternatives

Exploring the cinematic intuition of Farkas' Lemma: A Fundamental Theorem of Alternatives.

Visualizing...

Our institutional research engineers are currently mapping the formal proof for Farkas' Lemma: A Fundamental Theorem of Alternatives.

Apply for Institutional Early Access →

The Formal Theorem

Let A A be an m×n m \times n matrix and b b be a vector in Rm \mathbb{R}^m . Exactly one of the following two systems has a solution: (1) there exists x∈Rn x \in \mathbb{R}^n such that Ax=b Ax = b and x≥0 x \ge 0 , or (2) there exists y∈mathbbRm y \in \\mathbb{R}^m such that ATy≥0 A^T y \ge 0 and bTy<0 b^T y < 0 . This is expressed formally as:
{x∈Rn:Ax=b,x≥0}≠∅  ⟺  ∄y∈Rm:ATy≥0,bTy<0 \{ x \in \mathbb{R}^n : Ax=b, x \ge 0 \} \neq \emptyset \iff \nexists y \in \mathbb{R}^m : A^T y \ge 0, b^T y < 0

Analytical Intuition.

Imagine you are standing in a high-dimensional space defined by the columns of A A . System (1) asks: can we form the vector b b by taking a non-negative linear combination of these columns? Geometrically, this means b b must lie within the convex cone generated by the columns of A A . Farkas' Lemma acts as a binary gatekeeper. If b b sits outside this cone, there must exist a 'separating hyperplane' that keeps all the columns of A A on one side (where the dot product ATy≥0 A^T y \ge 0 holds) while leaving b b on the 'wrong' side (where bTy<0 b^T y < 0 holds). The vector y y is the normal to this magical partition. If you can't build your destination b b using the available directions, there exists a 'proof of impossibility'—a direction y y that proves b b is fundamentally unreachable, no matter how much you scale your ingredients. It is the bedrock upon which the duality of linear programming is built.
CAUTION

Institutional Warning.

Students often struggle with the 'exclusive or' nature of the lemma. It is not that both cannot exist, but that the existence of one logically precludes the other. Furthermore, confusing the role of y y as a witness to non-membership rather than just an arbitrary vector is a common hurdle.

Academic Inquiries.

01

Why is this called a Theorem of the Alternative?

Because it asserts that for any given system of linear inequalities, either a solution exists or a certificate of infeasibility exists, but never both.

02

How does this relate to the Karush-Kuhn-Tucker (KKT) conditions?

Farkas' Lemma is the primary mathematical engine used to derive the KKT conditions for optimality, as it provides the necessary conditions for the existence of Lagrange multipliers in constrained optimization.

Standardized References.

  • Definitive Institutional SourceBertsimas, D., & Tsitsiklis, J. N., Introduction to Linear Optimization.

Related Proofs Cluster.

Intermediate

Weierstrass Extreme Value Theorem: Guaranteeing Existence of Optima

Exploring the cinematic intuition of Weierstrass Extreme Value Theorem: Guaranteeing Existence of Optima.

Intermediate

Local Optima are Global Optima for Convex Functions

Exploring the cinematic intuition of Local Optima are Global Optima for Convex Functions.

Intermediate

Hessian Matrix and Second-Order Optimality Conditions

Exploring the cinematic intuition of Hessian Matrix and Second-Order Optimality Conditions.

Intermediate

Jensen's Inequality for Convex Functions

Exploring the cinematic intuition of Jensen's Inequality for Convex Functions.

Institutional Citation

Reference this proof in your academic research or publications.

NICEFA Visual Mathematics. (2026). Farkas' Lemma: A Fundamental Theorem of Alternatives: Visual Proof & Intuition. Retrieved from https://nicefa.org/library/fundamentals-of-optimization/farkas--lemma--a-fundamental-theorem-of-alternatives

Dominate the Logic.

"Abstract theory is just a movement we haven't seen yet."

Subscribe for Full ProofsEarly Access