One similiarly shows, with the help of Farkas' lemma (...): if a system Ax &lt;= b of n variables has no solution, then Ax &lt;= b has a subsystem A'x &lt;= b' of at most n + 1 inequalities having no solution.

Question

One similiarly shows, with the help of Farkas&#039; lemma (...): if a system Ax &amp;lt;= b of n variables has no solution, then Ax &amp;lt;= b has a subsystem A&#039;x &amp;lt;= b&#039; of at most n + 1 inequalities having no solution.

Tatiana Gentry · Accepted Answer

Maybe an example will help. The system of four inequalities in 2 variables                    −                  x          1                +                  x          2                            ≤        0                            −                  x          1                −                  x          2                            ≤        0                                      x          1                            ≤        −        1                                      x          2                            ≤        2            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:                    −                  x          1                +                  x          2                            ≤        0                            −                  x          1                −                  x          2                            ≤        0                                      x          1                            ≤        −        1            On the other hand, with just two of these inequalities you would always have a solution.

Jameson Lucero · Accepted Answer

In the light of the above responses the following proof can be given:By Farkas&#039; lemma, Ax &amp;lt;= b has no solution if and only if yb &amp;lt; 0 for each row vector y &amp;gt;= 0 such that yA = 0.Thus, Ax &amp;lt;= b has no solution if and only if yb &amp;lt; 0 for each y &amp;gt;= 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 &amp;lt; 0.Since y &amp;gt;= 0, y(A b) lies in the convex cone generated by the rows of (A b). By Carathéodory&#039;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 &amp;lt;= b has no solution.

One similiarly shows, with the help of Farkas' lemma (...):

Answered question

Answer & Explanation

New Questions in Algebra I