Subsystem of infeasible system of linear inequalities Suppose that we have a system of linear inequ

Jamiya Weber

Jamiya Weber

Answered question

2022-06-14

Subsystem of infeasible system of linear inequalities
Suppose that we have a system of linear inequalities described by
A x b
where A is m × n matrix.
I want to show that if the system is infeasible then it has a subsystem of at most rank(A)+1 inequalities such that the subsystem is also infeasible.
My is initial thought was to use Farkas Lemma on the original system and modify the certificate y to obtain y′ as a certificate for a subsystem of at most rank(A)+1 inequalities, but I am stuck from there, maybe my initial thought it wrong?

Answer & Explanation

aletantas1x

aletantas1x

Beginner2022-06-15Added 22 answers

A system of inequalities A x b is incompatible if and only if the inequality 0 1 is a positive linear combination the inequalities in A x b, that is, if and only if the n + 1 row ( 0 , 0 , , 0 , 1 ) is a positive linear combination of the rows of the augmented matrix ( A , b ). Note that the rank of the matrix ( A , b ) is rank A + 1.
To conclude, you have to use the following: if a vector v is a positive combination of m vectors v 1 , …, v m , then it is a positive combination of a linearly independent subset of the v i 's.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?