One similiarly shows, with the help of Farkas' lemma (...): if a system Ax <=...
pouzdrotf
Answered
2022-07-02
One similiarly shows, with the help of Farkas' lemma (...): if a system Ax <= b of n variables has no solution, then Ax <= b has a subsystem A'x <= b' of at most n + 1 inequalities having no solution.
Answer & Explanation
Tatiana Gentry
Expert
2022-07-03Added 10 answers
Maybe an example will help. The system of four inequalities in 2 variables
has no solutions. The theorem says you can take some three of these inequalities and still have no solution. In this case, there is only one way to choose three of the inequalities and have no solution:
On the other hand, with just two of these inequalities you would always have a solution.
Jameson Lucero
Expert
2022-07-04Added 5 answers
In the light of the above responses the following proof can be given: By Farkas' lemma, Ax <= b has no solution if and only if yb < 0 for each row vector y >= 0 such that yA = 0. Thus, Ax <= b has no solution if and only if yb < 0 for each y >= 0 such that y (A b) = (0 k), where (A b) is an m x (n + 1) matrix whose first n columns are the columns of A and whose last column contains the elements of b, and (0 k) is a row matrix whose first n elements are zero and whose last element is any number < 0. Since y >= 0, y(A b) lies in the convex cone generated by the rows of (A b). By Carathéodory's theorem, if (0 k) = y(A b) is contained in this cone then it is contained in a cone generated by a linearly independent subset of the rows of (A b), which can have at most n + 1 elements. The subset having at most n + 1 elements correspond to a subsystem of inequalities which has no solution if Ax <= b has no solution.