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 1


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
    Commented Sep 14, 2020 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$ Commented Sep 14, 2020 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
    Commented Sep 14, 2020 at 12:02
  • $\begingroup$ @Borol Your approach is not general. $\endgroup$ Commented Sep 14, 2020 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
    Commented Sep 14, 2020 at 13:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .