I will rate asap as the answer seems correct. Thx

Let vi, , v,n Rn be vectors. We assume that span(VI, ,v,n) = Rn. We call an index set I {1,..., m) a basis, if the vectors [vidiel are a basis of R". We assume that we are given cost c(1),...,c(m) 2 0 for all the vectors and abbreviate c(I) ILielc(i) as the cost of a basis. We say that a basis ,m is optimal if c() c() for any basis I i) Let I,J Cm] be two different basis. Prove that for a iEIJ, there is an index jEJ I so that (Ii)Uj is a basis and also (Jj))Ui} is a basis. Remark: If you are unsure how to prove this, you may want to lookup Steinitz exchange lemma from your Linear Algebra cours 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 1 and j 1 so that J := (lV Ujjs a basis with c(J)e() Remark: The proof of this claim is actually along the lines of Theorem 4 on page 15 in the lecture notes. I recommend to read that proof before iii) We want to compute an optimum basis and we want to use the following algorithm: (1) Set I:-0 (2) Sort the vectors so that c(1) (3) FOR i- 1 TO m DO c(2) . . . c(m) (4) If the vectors (v): jeluit are linearly independent, then update 1 := 1U Prove that the computed basis I is optimal. Remark: Again, you might want to have a look into the correctness proof for Kruskal's algo- rithm in order to solve this. Let vi, , v,n Rn be vectors. We assume that span(VI, ,v,n) = Rn. We call an index set I {1,..., m) a basis, if the vectors [vidiel are a basis of R". We assume that we are given cost c(1),...,c(m) 2 0 for all the vectors and abbreviate c(I) ILielc(i) as the cost of a basis. We say that a basis ,m is optimal if c() c() for any basis I i) Let I,J Cm] be two different basis. Prove that for a iEIJ, there is an index jEJ I so that (Ii)Uj is a basis and also (Jj))Ui} is a basis. Remark: If you are unsure how to prove this, you may want to lookup Steinitz exchange lemma from your Linear Algebra cours 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 1 and j 1 so that J := (lV Ujjs a basis with c(J)e() Remark: The proof of this claim is actually along the lines of Theorem 4 on page 15 in the lecture notes. I recommend to read that proof before iii) We want to compute an optimum basis and we want to use the following algorithm: (1) Set I:-0 (2) Sort the vectors so that c(1) (3) FOR i- 1 TO m DO c(2) . . . c(m) (4) If the vectors (v): jeluit are linearly independent, then update 1 := 1U Prove that the computed basis I is optimal. Remark: Again, you might want to have a look into the correctness proof for Kruskal's algo- rithm in order to solve this