# How to show that a system of linear equations is not solvable given certain constraints?

Imagine you have the following system of linear equations,

$$1 - 3x_1 - x_2 + x_3 + 3x_4 = 0$$ $$1 - x_1 - 5x_2 + 2x_3 + 4x_4 = 0$$ $$1 + x_1 + 2x_2 - x_3 - 2x_4 = 0$$ $$1 + 3x_1 + 4x_2 - 2x_3 - 5x_4 = 0,$$ and the constraints that $$x_1, x_2, x_3, x_4 \ge 0$$ and that $$x_1 + x_2 = x_3 + x_4.$$ I want to show that this system of linear equations is not solvable given the constraints, especially by using the second constraint. So for example, one could calculate $$(I) - (III)$$, which yields the equation $$-4x_1 - 3x_2 + 2x_3 + 5x_4 = 0,$$ which is equivalent to $$4x_1 + 3x_2 = 2x_3 + 5x_4.$$

Obviously, comparing the coefficients yields that this does not fullfill the second constraint. The only possibility would be that $$x_1 = x_2 = x_3 = x_4 = 0,$$ but in that case, we'd have $$1 - 0 = 0,$$ which is obviously false. Is this enough to show that the system can't be solved given the constraints?

## 1 Answer

Because summing gives $$4=0,$$ which is wrong.

• Thank you. I didn't even see that it's not solvable in general in the first case. My question still stands: given that it would be solvable in principal without the constraints (if it would be some other system), is it a valid approach to contradict the solvability given the constraints by using them in the way I did it? I'm asking since this is an old exam question and the system might be a different one in my upcoming exam. – Borol Sep 14 '20 at 11:54
• @Borol In the general I would be calculate a rank of the given system and the rest depends on this rank. – Michael Rozenberg Sep 14 '20 at 11:59
• But how would I use the constraints by calculating the rank? This is not a Linear Algebra class by the way, it's about optimization. We didn't use any rank stuff in the past. Isn't it way easier to simply use the constraints the way I did it? Or is that an incorrect approach? – Borol Sep 14 '20 at 12:02
• @Borol Your approach is not general. – Michael Rozenberg Sep 14 '20 at 12:05
• @Borol Linear programming duality provides a certificate of infeasibility in the form of dual multipliers for the constraints. In Michael's answer, "summing" corresponds to dual multipliers $(1,1,1,1)$. – RobPratt Sep 14 '20 at 13:31