Let v_1, ..., v_m element R^n be vectors. We assume that span (v_1, ..., v_m) = R^n. We call an index set I {1, ..., m} a basis, if the vectors {v_i}_i element I are a basis of R^n. We assume that we are given cost c(1), ..., c(m) greaterthanorequalto 0 for all the vectors and abbreviate c(I):= sigma_i elementof Ic(i) as the cost of a basis. We say that a basis I* {1, ..., m} is optimal if c(I*) greaterthanorequalto c(I) for any basis I. i) Let I, J [m] be two different basis. Prove that for all i Element I\J, there is an index j Element J\I so that (I \ {i} union {j} is a basis and also (J \ {j}) Union is a basis. Remark: If you are unsure how to prove this, you may want to lookup Steinitz exchange lemma from your Linear Algebra course. ii) Show that if a basis I is not optimal, then there is an improving swap, which means that there is a pair of indices i Element I and j NotElementof I so that J:= (I \ Union {j} is a basis with c (J)