boot camp day 2

today, material wise we covered more ground than we did yesterday, which was good. in linear algebra, we proved a fact which the professor then used to prove a whole bunch of simple but fundamental results about finite-dimensionality of vector spaces. the fact is: given any collection of vectors v_1,...,v_k that span your entire vector space, then any collection of vectors w_1,...,w_n with n>k must be linearly dependent. he gave us two proofs, one was brute force computation style and one was slick. i'll write down the slick one below... after classes i came home, made a bunch of spaghetti, ate it, and then took a great nap to the cardinals game, which we lost. (but it's okay, since the cubs lost too.) but for now i'm going to stop writing, so i can maybe get some work done tonight! okay, thanks for reading! the proof is below...

the proof is by contradiction. so first you assume that w_1,...,w_n are linearly independent. then each w_i is nonzero. (proof: without loss of generality, assume w_1=0. then 1*w_1+0w_2+...+0w_n is a nontrivial linear combination of the w_i that equals 0, which implies linear dependence.) since v_1,...,v_k generate the space, you can write w_1 as a linear combination of these vectors. since w_1 is not 0, not all coefficients in this linear combination are 0. take the vector v_i corresponding to the last non-zero coefficient, and remove it from your list v_1,...,v_k, replacing it instead with w_1. the resulting set of vectors w_1,v_1,...,v_{i-1},v_{i+1},...,v_k still generates your entire space. (this is true because you can write v_i as a linear combination of w_1 and v_1,...,v_{i-1}, so that in any representation of a vector using v_i, you can use w_1,v_1,...,v_{i-1} instead of v_i. to see why you can write v_i as a linear combination of these other vectors, note that we have w_1=a_1v_1+...+a_iv_i, where a_i is nonzero. then you can solve this equation for v_i.)

now, you continue this process with w_2,w_3,... each time you remove one of the vectors v_j and add some w_i, and your resulting set of vectors generates the entire space. nick pointed out below that's there's another comment that needs to be made to guarantee that this actually works, i.e. that each time you're actually removing some v_j. to see this, consider the case with w_2. you write w_2 as a linear combination of w_1,v_1,...,v_{i-1},v_{i+1},...,v_k. now, one of the coefficients of the v_j had better be nonzero, since otherwise you would have w_2 as a scalar multiple of w_1, which contradictions linear independent. then you can actually remove the v_j corresponding to the last nonzero coefficient, as you need to. with w_3, you know you have a nonzero coefficient corresponding to one of the v_j because you can't write w_3 as a linear combination of w_1 and w_2 because of linear independence, and so on.

so, if you iterate this process k times, you get rid of all of the v_j! then you have w_1,...,w_k generating the entire space. in particular, you can write the vectors w_{k+1},...,w_n as linear combinations of w_1,...,w_k, which implies that the set w_1,...,w_n is linearly dependent, which is a contradiction, and you're done.