Our simplex algorithm pivots from basic feasible solution to basic feasible solution, namely solutions depending on a basis so that the variables with non zero values index a linearly independent set of columns. We consider the following LP: maxcx such that Ax = b and x 0 that has a feasible solution u = (u1,u2,...,un+m)T (i.e. Au = b and u 0). We have included the slack variables in our original dictionary formulation so that this LP is in equality (and not inequality) form. We wish to give you a step in the proof to show the LP has a basic feasible solution without using the simplex algorithm. Let Ai denote the ith column of A. Let P = {i : ui > 0}, namely the indices for which u is non zero (strictly positive) . Assume {Ai : i P} is a linearly dependent set of columns: it means that there exist choices for ai, not all 0, so thatPiP aiAi = 0. Thus we can nd a = (a1,a2,...,an)T so that Aa = 0 and a 6= 0 where we set ai = 0 for i / P. We note that u + ea satises A(u + ea) = Au = b. For your assignment, indicate how to choose e so that u + ea 0 such that there are fewer non zero entries in u + ea than in u and at the same time u+ea is a feasible solution to the LP. We already have A(u+ea) = b. (With a bit more work this yields the result we gave at the beginning but you can stop at this point).