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?


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

  • $\begingroup$ 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. $\endgroup$ – Borol Sep 14 '20 at 11:54
  • $\begingroup$ @Borol In the general I would be calculate a rank of the given system and the rest depends on this rank. $\endgroup$ – Michael Rozenberg Sep 14 '20 at 11:59
  • $\begingroup$ 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? $\endgroup$ – Borol Sep 14 '20 at 12:02
  • $\begingroup$ @Borol Your approach is not general. $\endgroup$ – Michael Rozenberg Sep 14 '20 at 12:05
  • $\begingroup$ @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)$. $\endgroup$ – RobPratt Sep 14 '20 at 13:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.