1. Suppose the vectors in the set E = {v₁, v₂, ..., v_m} span an n-dimensional vector space V (and so necessarily n ≤ m). Let
c : E → R
be a cost function on E. Show that the following algorithm finds a basis B ⊂ E for V of least total cost c(B) := ∑_{e &isin B} c(e).

1. Let B₀ = ∅
2. Given B_i, i < n, choose x_i+1 ∈ E \ B_i such that
   i. B_i+1 := B_i ∪ {x_i+1} is linearly independant, and
   ii. x_i+1 is the cheapest such element of E \ B_i.
3. Let B = B_n.

2. 3B

3. 3G

4. 3I