Farkas' lemma

Farkas' lemma is a solvability theorem for a finite system of linear inequalities. In its original form it says that for a matrix A and a vector b exactly one of two statements holds: either b can be written as A applied to a vector with nonnegative components, or there is a vector y whose product with the transpose of A has no negative component while its product with b is negative. Geometrically, b either lies in the closed convex cone spanned by the columns of A or can be separated from that cone by a hyperplane, which is why the result is called a theorem of the alternative. It is named for the Hungarian mathematician and physicist Gyula Farkas, who first proved it, and the formulation most often quoted today is due to Gale, Kuhn and Tucker in 1951. The lemma underpins linear programming duality and has played a central role in the development of mathematical optimization. In complexity theory it shows that deciding whether a linear system has a nonnegative solution lies in the intersection of NP and co-NP.