So let's use an example to show you the idea. Suppose I have an original linear program like this, all right? So you may take a look at this figure, so x1 plus 2x2 is less than or equal to 6, two 2x1 plus x2 is less than or equal to 6. So your feasible regions here now I hope it makes sense. And now we have a standard form in this way, all we need to do is to add a two slates and then we get a 2 by 4 linear system as our matrix as dimension. So in this standard form M is 2, M is 2 and N is 4. So in some sense, you have 2 constraints and 4 columns, 4 variables. In each possible way to construct a basic solution, we have two non basic variables and two basic variables, okay? Because we want to find a square matrix, so each time we will choose two columns to be basic all others to be non-basic. So the steps to obtain a basic solution would be first choose M basic variables or choose M columns to form a basis. So the criteria is that the M basic variables, the M columns must form a square matrix, we call it AB and your AB must be invertible or nonsingular. If that's the case, then the remaining variables would be set to be non basic, they would have their values being 0. And our M by M system A B x B equals B may be soft. Then we will get the values of xB, that's a basic solution. So our two equations are here. If we try to have B being x1 and x2, N being x3, x4, that means we want to choose B to be consisting x1, x2. So our AB matrix in this way would be 1, 2, 2, 1, okay? According to this selection. Whether AB is invertible may be checked immediately because we know we have those Jordan elimination, whatever thing, okay? We may check whether it has enough pivots. We do know whether we have independent or dependent columns. So that allows us to see whether this is soluble. And if that's true, then we get a unique solution. So in that way, the basic solution associated with this basis would be 2, 2, 0, 0, okay? So that's the idea. Or we may try another B in that particular case, we're going to say, how about I want to have B being x2 and x3? So if that's the case, then your B is talking about this one. Your AB matrix would be 2, 1, 1, 0, and that gives you this particular system. You solve it again, your x2 and x3 are 6 and -6. So your basic solution is 0.6, -6 and 0. In short, you take these two values being 0 because you say that say they are non-basic and we will solve the remaining basic variables. So in general, we need to choose M out of N variables to be basic. That means we have at most M choose N different basis, okay? So why it is at most? It is because in some cases the M columns you choose would happen to be M dependent columns. So if that's the case, then it's possible that you would have an non-invertible matrix, that does not give you a basis. For A, all we know is that all the rows are independent. But if you select a few columns, it's possible that these columns are dependent, then that does not give you an invertible matrix. So in our previous example, we are lucky we have exactly 4 choose 2 basis. Sometimes we don't really have 6 basis when we have 4 by 2 problems. But anyway, in this particular example, all the selection of two columns, gives us an invertible matrix. And then we will be able to examine all the six basis one by one. We may also list all the values for those basic variables, non-basic variables. So for example, we first may say, okay, I want x1, x2, so the others are 0 and I solve the two selected basic variables. I want x1 and x3, then I would eliminate x2 and x4 and solve for the remaining and so on and so on. So I think it would be helpful if you try to go through this example again and try to list all your basic solutions and the maybe you want to create another example and try to find all the basic solutions. Again, you're going to understand the pretty much all the ideas here.
