PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (200)
Orphanage
Unclass'd
Unproven (511)
Corrections (9)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: No information on entry rating
Farkas lemma (Theorem)

Given an $ m\times n$ matrix $ A$ and an $ 1\times n$ real row vector $ c$, both with real coefficients, one and only one of the following systems has a solution:

  1. $ Ax\leq 0$ and $ cx > 0$ for some $ n$-column vector $ x$;
  2. $ wA = c$ and $ w\geq 0$ for some $ m$-row vector $ w$.
Equivalently, one and only one of the following has a solution:
  1. $ Ax\leq 0$, $ x\leq 0$ and $ cx>0$ for some $ n$-column vector $ x$;
  2. $ wA\leq c$ and $ w\geq 0$ for some $ m$-row vector $ w$.

Remark. Here, $ Ax\geq 0$ means that every component of $ Ax$ is nonnegative, and similarly with the other expressions.



"Farkas lemma" is owned by Koro.
(view preamble)

View style:

Other names:  Farkas theorem

Attachments:
proof of Farkas lemma (Proof) by CWoo
generalized Farkas lemma (Theorem) by stevecheng
Log in to rate this entry.
(view current ratings)

Cross-references: expressions, vector, solution, coefficients, row vector, real, matrix
There are 2 references to this entry.

This is version 8 of Farkas lemma, born on 2003-07-25, modified 2004-02-25.
Object id is 4508, canonical name is FarkasLemma.
Accessed 10495 times total.

Classification:
AMS MSC: 15A39 (Linear and multilinear algebra; matrix theory :: Linear inequalities)
Pending Errata and Addenda
None.
[ View all 5 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | prove | add result | add corollary | add example | add (any)