Consider a system Ax = b, a: 2 D where A is an m x n matrix whose rows are linearly independent. Let it be a solution to Ax = b. Let J be the support of :3; so J consists exactly of the column indices j of A for which 5:]- 0. (a) (b) ((1) Show that if the columns of A J are linearly dependent, then :7: is not a basic solution. (3 marks) Conversely, show that if the columns of A J are linearly independent then it is a basic solution. (5 marks) (Hint: Recall the following fact from linear algebra: let S' be a set of vectors and let it be the rank of S, i.e., the maximum number of linearly independent vectors in S. Then, for any R Q S where the vectors in R are linearly independent, there is a subset R' of S with R' 2 R, |R'| = t such that the vectors in R' are linearly independent.) Let in 2 (D, and suppose that i is not a basic solution. Show that there exists a vector d such that (ii = O for all 3' e3 J, Ad = (U, and at, < 0 for some 3' E J. Deduce that there exists an E > 0 such that :L" = .2": + ed is also as a feasible solution to A1: = b, a: 2 D, and |{j:sc;- >0}! < |J|. (7 marks) (Hint: To obtain (1, use part (b), possibly replacing d by d.) Suppose that the system Ax = b, a: 2 0 has a feasible solution :2. Explain how to obtain a basic feasible solution to that system. You may use the (1 vector from part c) with respect to any feasible solution, without further justication. (4 marks)