1
$\begingroup$

Find a necessary and sufficient condition for the linear equation Ax = b to have no solution. (hint: Use duality to find a strong alternative to Ax = b).

  • 0
    More generally, you've asked a lot of interesting linear programming questions over the past few weeks that I've enjoyed thinking about and sometimes answering. Because of that I'm curious why you are asking all of these questions.2010-11-10
  • 0
    @Mike: This is not homework but a review problem I'm having trouble with. I'm currently studying various aspects of linear-optimization and implementing them with a computer science background. When problems scale to hundreds of dimensions these problems can help to save many CPU cycles. Mike, I greatly appreciate all the help you've given so far.2010-11-11
  • 0
    You're welcome. It's been fun. And thanks for satisfying my curiosity.2010-11-11

1 Answers 1

1

Solution exists iff $b$ is orthogonal to the null space of $A^{*}$. This is typically referred to as the Fundamental Theorem of Linear Algebra.

  • 0
    where does duality fit into this?2010-11-10
  • 0
    @ Djaian: Not needed. If b =0, then there always exists the trivial solution x = 0.2010-11-10
  • 0
    sorry, I didn't read your answer correctly, I thought you had given a condition for non-existence :-) Comment deleted.2010-11-10
  • 1
    @ Mark: The dual to the above is $b^{*}z = 0$ subject to $A^{*}z = 0$2010-11-10