Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

For number 3(a), I don't get how "any of the last 4 columns are linearly dependent" and how x1 is the basic variable... I thought only the last 2 columns were linearly dependent and the first 3 columns are linearly independent. So I thought there would be 7 basic solutions having basic variables: {x1, x2, x4}, {x1, x2, x5}, {x2, x3, x4}, {x2, x3, x5}, {x1, x2, x3}, {x1, x3, x4}, {x1, x3, x5}.

Can someone please help me understand? I feel like I don't thoroughly get the concept of basic solution no matter how much I read about it.

share|cite|improve this question

This is probably too late to answer your question, but in case someone else comes across this, you misunderstand the solution. It is not saying "any of the last 4 columns are linearly dependent" but is instead saying "any 3 of the last 4 columns are linearly dependent.

To form basic solutions the 3 x 3 matrix (index set) must be invertible. For instance, the corresponding matrix for the basic solution {x1, x2, x3} is [A1 A2 A3] and it must be invertible. If it's not invertible then those three variables can't correspond to a basic index set.

Out of the 7 solutions you wrote: {x2,x3,x4} can't possibly be a basic solution because [A2 A3 A4] is not invertible, the first two rows are the same.

Similarly {x2, x3, x5} can't be a basic solution because [A2 A3 A5] is not invertible, again the first two rows are the same.

So the solution is indeed correct, there are 5 basic solutions, of which 3 are feasible (satisfying nonnegativity constraints).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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