Page 215 - 35Linear Algebra

215

Worked Example

Next, we would like to establish a method for determining whether a
n
collection of vectors forms a basis for R . But first, we need to show that
any two bases for a finite-dimensional vector space has the same number of
vectors.

Lemma 11.0.2. If S = {v 1 , . . . , v n } is a basis for a vector space V and
T = {w 1 , . . . , w m } is a linearly independent set of vectors in V , then m ≤ n.

The idea of the proof is to start with the set S and replace vectors in S
one at a time with vectors from T, such that after each replacement we still
have a basis for V .

Reading homework: problem 1

Proof. Since S spans V , then the set {w 1 , v 1 , . . . , v n } is linearly dependent.
Then we can write w 1 as a linear combination of the v i ; using that equation,
we can express one of the v i in terms of w 1 and the remaining v j with j 6=
i. Then we can discard one of the v i from this set to obtain a linearly
independent set that still spans V . Now we need to prove that S 1 is a basis;
we must show that S 1 is linearly independent and that S 1 spans V .
The set S 1 = {w 1 , v 1 , . . . , v i−1 , v i+1 , . . . , v n } is linearly independent: By
the previous theorem, there was a unique way to express w 1 in terms of
the set S. Now, to obtain a contradiction, suppose there is some k and
i
constants c such that
n
0
1
v k = c w 1 + c v 1 + · · · + c i−1 v i−1 + c i+1 v i+1 + · · · + c v n .
Then replacing w 1 with its expression in terms of the collection S gives a way
to express the vector v k as a linear combination of the vectors in S, which
contradicts the linear independence of S. On the other hand, we cannot
express w 1 as a linear combination of the vectors in {v j |j 6= i}, since the
expression of w 1 in terms of S was unique, and had a non-zero coefficient for
the vector v i . Then no vector in S 1 can be expressed as a combination of
other vectors in S 1 , which demonstrates that S 1 is linearly independent.
The set S 1 spans V : For any u ∈ V , we can express u as a linear com-
bination of vectors in S. But we can express v i as a linear combination of

215