# Dimension of vector space (proof)

Hi,
I'm having trouble understanding a proof of the following theorem which allows it to be shown that all bases for a vector space have the same number of vectors, and that number is the dimension of the vector space (as you probably already know):

## Homework Statement

Theorem:
If S = {v1, v2, ... , vn} is a basis for a vector space V and T = {w1, w2, ... , wk} is a linearly independent set of vectors in V, then k < n.

## Homework Equations

Here's the proof: (sorry about all the text)
If k > n, then we consider the set

R1 = {w1,v1, v2, ... , vn}

Since S spans V, w1 can be written as a linear combination of the vi's.

w1 = c1v1 + ... + cnvn

Since T is linearly independent, w1 is nonzero and at least one of the coefficients ci is nonzero. Without loss of generality assume it is c1. We can solve for v1 and write v1 as a linear combination of w1, v2, ... vn. Hence

T1 = {w1, v2, ... , vn}

is a basis for V. Now let

R2 = {w1, w2, v2, ... , vn}

Similarly, w2 can be written as a linear combination of the rest and one of the coefficients is non zero. Note that since w1 and w2 are linearly independent, at least one of the vi coefficients must be nonzero. We can assume that this nonzero coefficient is v2 and as before we see that

T2 = {w1, w2,v3, ... , vn}

is a basis for V. Continuing this process we see that

Tn = {w1, w2, ... , wn}
is a basis for V. But then Tn spans V and hence wn+1 is a linear combination of vectors in Tn. This is a contradiction since the w's are linearly independent. Hence n > k.

## The Attempt at a Solution

Where I get lost is where it says that T1 is a basis for V. Just because one of the vectors from the basis can be written as a linear combination of T1, why does that mean that T1 is linearly independent and that it spans V? When the author writes that we can assume it's v1 without loss of generalization, I guess that he/she means that we could pick any other vector in S, but that still doesn't imply (as far as I can tell) that T1 spans V

Any help will be greatly appreciated

Related Calculus and Beyond Homework Help News on Phys.org
First, w1 cannot be expressed as a linear combination of v2,...,vn. The reason is that if it could be expressed as a linear combination a2v2+...+anvn, then we have w1 = c1v1+...+cnvn = a2v2+...+anvn. Then by subtracting, we see that c1v1+(c2-a2)v2+...+(cn-an)vn = 0. Since v1,...,vn are linearly independent, c1=0 (along will all the other coefficients like c2-a2,...), which contradicts the assumption that c1 is not 0. Therefore the set {w1,v2,...,vn} is independent.

Now, why does this set span V? Well, the reason is that any vector can be written as a linear combination of v1,v2,...,vn, and since you can write v1 as a linear combination of w1, v2, ..., vn, you can substitute v1 for w1,v2,...,vn. So that any vector can be written as a linear combination of w1,v2,...,vn.

murmillo,

That's exactly the leap I wasn't making--you just substitute T1 for v1

Thanks so much