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

$\begin{array}{rl}-{x}_{1}+{x}_{2}& \le 0\\ -{x}_{1}-{x}_{2}& \le 0\\ {x}_{1}& \le -1\\ {x}_{2}& \le 2\end{array}$

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:

$\begin{array}{rl}-{x}_{1}+{x}_{2}& \le 0\\ -{x}_{1}-{x}_{2}& \le 0\\ {x}_{1}& \le -1\end{array}$

On the other hand, with just two of these inequalities you would always have a solution.

$\begin{array}{rl}-{x}_{1}+{x}_{2}& \le 0\\ -{x}_{1}-{x}_{2}& \le 0\\ {x}_{1}& \le -1\\ {x}_{2}& \le 2\end{array}$

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:

$\begin{array}{rl}-{x}_{1}+{x}_{2}& \le 0\\ -{x}_{1}-{x}_{2}& \le 0\\ {x}_{1}& \le -1\end{array}$

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.

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.

Most Popular Questions