2-16-2008

Bases for Vector Spaces

Linear independence has to do with the nonredundancy of a set of vectors. On the other hand,
spanning has to do with being able to build everything in a subspace from a set of vectors. Heres how
these ideas are related.
Denition. Let V be an F-vector space. A subset B of V is a basis if it is linearly independent and spans
V .
The number of elements in a basis for V is called the dimension of V , and is denoted dimV .
Someone could object at this point that I dont know that two bases for V might not have dierent
numbers of elements in which case the dimension of V wouldnt make sense. Ill show later that this cant
happen.
Example. The standard basis vectors
_
_
_
_
_
1
0
0
_
_
,
_
_
0
1
0
_
_
,
_
_
0
0
1
_
_
_
_
_
are a basis for R
3
over R.
I observed earlier that this set is independent, and
a, b, c) = a 1, 0, 0) +b 0, 1, 0) +c 0, 0, 1)
shows that every vector in R
3
can be written as a linear combination of the vectors.
Example. The vectors
_
_
_
_
_
1
1
0
_
_
,
_
_
0
1
1
_
_
,
_
_
1
0
1
_
_
_
_
_
are a basis for R
3
over R.
To see this, row reduce:
_
_
1 0 1
1 1 0
0 1 1
_
_

_
_
1 0 0
0 1 0
0 0 1
_
_
This shows two things. First, since the matrix row reduces to the identity, the algorithm for testing
independence shows that theyre independent.
Second, since the matrix row reduces to the identity, the system
_
_
1 0 1
1 1 0
0 1 1
_
_
_
_
x
y
z
_
_
=
_
_
a
b
c
_
_
has a unique solution for every vector a, b, c).
But this matrix equation can be written as
x 1, 1, 0) +y 0, 1, 1) +z 1, 0, 1) = a, b, c).
In other words, any vector a, b, c) R
3
can be written as a linear combination of the given vectors:
The given vectors span R
3
.
1
Hence, the given set of vectors is a basis for R
3
.
The following result is clear from the last example.
Proposition. Let F be a eld. v
1
, v
2
, . . . , v
n
is a basis for F
n
if and only if
_
_

v
1
v
2
v
n

_
_
row reduces to the identity.
A basis for V is a spanning set for V , so every vector in V can be written as a linear combination of
basis elements. The next result says that such a linear combination is unique.
Lemma. Let v
1
, v
2
, . . . , v
n
be a basis for a vector space V . Every v V can be written in exactly one way
as
v = a
1
v
1
+a
2
v
2
+ +a
n
v
n
, a
i
F.
Proof. Let v V . Since v
1
, v
2
, . . . , v
n
spans V , I can write
v = a
1
v
1
+a
2
v
2
+ +a
n
v
n
for some scalars a
1
, a
2
, . . . , a
n
.
Suppose that there is another way to do this:
v = b
1
v
1
+b
2
v
2
+ +b
n
v
n
.
Then
a
1
v
1
+a
2
v
2
+ +a
n
v
n
= b
1
v
1
+b
2
v
2
+ +b
n
v
n
,
so
(a
1
b
1
)v
1
+ (a
2
b
2
)v
2
+ + (a
n
b
n
)v
n
= 0.
Since v
1
, v
2
, . . . , v
n
is independent,
a
1
b
1
= 0, a
2
b
2
= 0, . . . , a
n
b
n
= 0.
Therefore,
a
1
= b
1
, a
2
= b
2
, . . . , a
n
= b
n
.
That is, the two linear combinations were actually the same. This proves that theres only one way to
write v as a linear combination of the v
i
s.
I want to show that two bases for a vector space must have the same number of elements. I need some
preliminary results, which are important in their own right.
Lemma. If A is an mn matrix with m < n, the system Ax = 0 has nontrivial solutions.
Proof. Write
A =
_

_
a
11
a
12
a
1n
a
21
a
22
a
2n
.
.
.
.
.
.
.
.
.
a
m1
a
m2
a
mn
_

_
.
The condition m < n means that the system
_

_
a
11
a
12
a
1n
a
21
a
22
a
2n
.
.
.
.
.
.
.
.
.
a
m1
a
m2
a
mn
_

_
_

_
x
1
x
2
.
.
.
x
n
_

_
=
_

_
0
0
.
.
.
0
_

_
2
has more unknowns than equations.
If A row reduces to a row reduced echelon matrix R, then R can have at most m leading coecients.
Therefore, some of the variables x
1
, x
2
, . . . , x
n
will be free variables (parameters); if I assign nonzero values
to the free variables (e.g. by setting all of them equal to 1), the resulting solution will be nontrivial.
Theorem. Let v
1
, v
2
, . . . , v
n
be a basis for a vector space V .
(a) Any subset of V with more than n elements is dependent.
(b) Any subset of V with fewer than n elements cannot span.
Proof. (a) Suppose w
1
, w
2
, . . . , w
m
is a subset of V , and that m > n. I want to show that w
1
, w
2
, . . . , w
m

is dependent.
Write each w as a linear combination of the vs:
w
1
= a
11
v
1
+a
12
v
2
+ +a
1n
v
n
w
2
= a
21
v
1
+a
22
v
2
+ +a
2n
v
n
.
.
.
w
m
= a
m1
v
1
+a
m2
v
2
+ +a
mn
v
n
A little bit of thought shows that this can be represented as the following matrix equation:
_
_

w
1
w
2
w
m

_
_
=
_
_

v
1
v
2
v
n

_
_
_

_
a
11
a
21
a
m1
a
12
a
22
a
m2
.
.
.
.
.
.
.
.
.
a
1n
a
2n
a
mn
_

_
.
Since m > n, the matrix of as has more columns than rows. Therefore, the system
_

_
a
11
a
21
a
m1
a
12
a
22
a
m2
.
.
.
.
.
.
.
.
.
a
1n
a
2n
a
mn
_

_
_

_
x
1
x
2
.
.
.
x
m
_

_
=
_

_
0
0
.
.
.
0
_

_
has a nontrivial solution x
1
= b
1
, x
2
= b
2
, . . . x
m
= b
m
. That is, not all the bs are 0, but
_

_
a
11
a
21
a
m1
a
12
a
22
a
m2
.
.
.
.
.
.
.
.
.
a
1n
a
2n
a
mn
_

_
_

_
b
1
b
2
.
.
.
b
m
_

_
=
_

_
0
0
.
.
.
0
_

_
.
But then
_
_

w
1
w
2
w
m

_
_
_

_
b
1
b
2
.
.
.
b
m
_

_
=
_
_

v
1
v
2
v
n

_
_
_

_
a
11
a
21
a
m1
a
12
a
22
a
m2
.
.
.
.
.
.
.
.
.
a
1n
a
2n
a
mn
_

_
_

_
b
1
b
2
.
.
.
b
m
_

_
,
so
_
_

w
1
w
2
w
m

_
_
_

_
b
1
b
2
.
.
.
b
m
_

_
=
_

_
0
0
.
.
.
0
_

_
.
3
In equation form,
b
1
w
1
+b
2
w
2
+ +b
m
w
m
= 0.
This is a nontrivial linear combination of the ws which adds up to 0, so the ws are dependent.
(b) Suppose that w
1
, w
2
, . . . , w
m
is a set of vectors in V and m < n. I want to show that w
1
, w
2
, . . . , w
m

does not span V .

Suppose on the contrary that the ws span V . Then each v can be written as a linear combination of
the ws:
v
1
= a
11
w
1
+a
12
w
2
+ +a
1m
w
m
v
2
= a
21
w
1
+a
22
w
2
+ +a
2m
w
m
.
.
.
v
n
= a
n1
w
1
+a
n2
w
2
+ +a
nm
w
m
In matrix form, this is
_
_

v
1
v
2
v
n

_
_
=
_
_

w
1
w
2
w
m

_
_
_

_
a
11
a
21
a
n1
a
12
a
22
a
n2
.
.
.
.
.
.
.
.
.
a
1m
a
2m
a
nm
_

_
.
Since n > m, the coecient matrix has more columns than rows. Hence, the system
_

_
a
11
a
21
a
n1
a
12
a
22
a
n2
.
.
.
.
.
.
.
.
.
a
1m
a
2m
a
nm
_

_
_

_
x
1
x
2
.
.
.
x
n
_

_
=
_

_
0
0
.
.
.
0
_

_
has a nontrivial solution x
1
= b
1
, x
2
= b
2
, . . . x
n
= b
n
:
_

_
a
11
a
21
a
n1
a
12
a
22
a
n2
.
.
.
.
.
.
.
.
.
a
1m
a
2m
a
nm
_

_
_

_
b
1
b
2
.
.
.
b
n
_

_
=
_

_
0
0
.
.
.
0
_

_
.
Multiplying the v and w equation on the right by the b-vector gives
_
_

v
1
v
2
v
n

_
_
_

_
b
1
b
2
.
.
.
b
n
_

_
=
_
_

w
1
w
2
w
m

_
_
_

_
a
11
a
21
a
n1
a
12
a
22
a
n2
.
.
.
.
.
.
.
.
.
a
1m
a
2m
a
nm
_

_
_

_
b
1
b
2
.
.
.
b
n
_

_
,
so
_
_

v
1
v
2
v
n

_
_
_

_
b
1
b
2
.
.
.
b
n
_

_
=
_

_
0
0
.
.
.
0
_

_
.
In equation form, this is
b
1
v
1
+b
2
v
2
+ +b
n
v
n
= 0.
Since not all the bs are 0, this is a nontrivial linear combination of the vs which adds up to 0
contradicting the independence of the vs.
This contradiction means that the ws cant span after all.
4
Example. The standard basis for R
3
contains 3 vectors.
Hence, the set of four vectors
_
_
_
_
_
1
0
1
_
_
,
_
_
2
3
10
_
_
,
_
_
1
1
1
_
_
,
_
_
0
11
7
_
_
_
_
_
cannot be independent and I know this without doing any computation.
Likewise, the set of two vectors
_
_
_
_
_
2
1
2
_
_
,
_
_
3
1
5
_
_
_
_
_
cannot span R
3
.
Corollary. If v
1
, . . . , v
n
is a basis for a vector space V , then every basis for V has n elements.
Proof. If w
1
, . . . , w
m
is another basis for V , then m cant be less than n or w
1
, . . . , w
m
couldnt span.
Likewise, m cant be greater than n or w
1
, . . . , w
m
couldnt be independent. Therefore, m = n.
The Corollary shows that the dimension of a nite-dimensional vector space is well-dened that is, in
a nite-dimensional vector space, any two bases have the same number of elements. This is true in general;
Ill state the relevant results without proof.
Every vector space has a basis. The proof requires a set-theoretic result called Zorns Lemma.
Two bases for any vector space have the same number of elements. Specically, if B and ( are bases for
a vector space V , there is a bijective function f : B (.
Ive already given one example of an innite basis:
1, x, x
2
, x
3
, . . ..
This set is a basis for the vector space R[x] of polynomials with real coecients over the eld of real
numbers.
c _2008 by Bruce Ikenaga 5