Theorem (Farkas’ lemma)
(1) linear system has a solution in the first orthant;
(2) there exists such that and
It has an elementary analogue known from a course of linear algebra:
Theorem (Fredholm’s alternative)
Exactly one of the following holds:
(1′) linear system has a solution;
(2′) there exists such that and
Rather than giving a detailed self-contained proof, I’ll just provide a geometric intuition behind it. Note that (2) implies the negation of (1). To see it, transpose and then multiply by from (2). Now it remains to prove that the negation of (1) implies (2).
Let us start with a notion of a cone. A cone is any set which is closed under multiplication by positive scalars. In other words, implies for any Note that this definition aligns with the geometric notion of a (non-truncated) cone with apex in the origin. Cones are convex sets, i.e.they can contain two points only with the entire segment between these points.
Further, for any set of vectors its conic hull is defined as a minimal cone containing them. It is easy to make sure that it is given (parametrized) by for If we rewrite as the columns of a matrix then their conic hull will be the set
Now we can see that geometrically (1) simply says that is in the conic hull of columns of . Indeed, there exist a coefficient vector such that
Remark. Farkas’ lemma has an interesting consequence. It occurs that the LP feasibility problem (“determine if (2) is feasible”) is essentially as difficult as the separation problem for a cone and a point (given a cone and a point, output the separation hyperplane if the point does not belong to the cone and the negative answer if it does).