1
$\begingroup$

http://www.math.toronto.edu/kergin/236_t1_2.pdf

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.

1 Answers 1

1

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).