Basis and dimension

Section 1.7 Basis and dimension

Next, we begin with an important result, sometimes known as the “Fundamental Theorem”:

Theorem 1.7.1. Fundamental Theorem (Steinitz Exchange Lemma).

Suppose

V = span {v_{1}, \dots, v_{n}} .

{w_{1}, \dots, w_{m}}

is a linearly independent set of vectors in

V,

then

m \leq n .

Strategy.

We won’t give a complete proof of this theorem. The idea is straightforward, but checking all the details takes some work. Since

{v_{1}, \dots, v_{k}}

is a spanning set, each of the vectors in our independent set can be written as a linear combination of

v_{1}, \dots, v_{k} .

In particular, we can write

w_{1} = a_{1} v_{1} + a_{2} v_{2} + \dots + a_{n} v_{n}

for scalars

a_{1}, \dots, a_{n},

and these scalars can’t all be zero. (Why? And why is this important?)

The next step is to argue that

V = span {w_{1}, v_{2}, \dots, v_{n}};

that is, that we can replace

v_{1}

w_{1}

without changing the span. This will involve chasing some linear combinations, and remember that we need to check both inclusions to prove set equality. (This step requires us to have assumed that the scalar

a_{1}

is nonzero. Do you see why?)

Next, we similarly replace

v_{2}

with

w_{2} .

Note that we can write

w_{2} = a w_{1} + b_{2} v_{2} + \dots + b_{n} v_{n},

and at least one of the

b_{i}

must be nonzero. (Why can’t they all be zero? What does Exercise 1.6.10 tell you about

{w_{1}, w_{2}} ?

)

If we assume that

b_{2}

is one of the nonzero scalars, we can solve for

v_{2}

in the equation above, and replace

v_{2}

w_{2}

in our spanning set. At this point, you will have successfully argued that

V = span {w_{1}, w_{2}, v_{3}, \dots, v_{n}} .

Now, we repeat the process. If

m \leq n,

we eventually run out of

w_{i}

vectors, and all is well. The question is, what goes wrong if

m > n ?

Then we run out of

v_{j}

vectors first. We’ll be able to write

V = span {w_{1}, \dots, w_{n}},

and there will be some vectors

w_{n + 1}, \dots, w_{m}

leftover. Why is this a problem? (What assumption about the

w_{i}

will we contradict?)

🔗

If a set of vectors spans a vector space

V,

but it is not independent, we observed that it is possible to remove a vector from the set and still span

V

using a smaller set. This suggests that spanning sets that are also linearly independent are of particular importance, and indeed, they are important enough to have a name.

🔗

Definition 1.7.2.

🔗

Let

V

be a vector space. A set

B = {e_{1}, \dots, e_{n}}

is called a basis of

V

B

is linearly independent, and

span B = V .

🔗

The importance of a basis is that vector vector

v \in V

can be written in terms of the basis, and this expression as a linear combination of basis vectors is unique. Another important fact is that every basis has the same number of elements.

🔗

Theorem 1.7.3. Invariance Theorem.

🔗

{e_{1}, \dots, e_{n}}

and

{f_{1}, \dots, f_{m}}

are both bases of a vector space

V,

then

m = n .

Strategy.

One way of proving the equality

m = n

is to show that

m \leq n

and

m \geq n .

We know that since both sets are bases, both sets are independent, and they both span

V .

Can you see a way to use Theorem 1.7.1 (twice)?

Proof.

Let

A = {e_{1}, \dots, e_{n}}

and let

B = {f_{1}, \dots, f_{m}} .

Since both

A

and

B

are bases, both sets are linearly independent, and both sets span

V .

Since

A

is independent and

span B = V,

we must have

n \leq m,

by Theorem 1.7.1. Similarly, since

span A = V

and

B

is independent, we must have

n \geq m,

and therefore,

n = m .

🔗

Suppose

V = span {v_{1}, \dots, v_{n}} .

If this set is not linearly independent, Theorem 1.4.10 tells us that we can remove a vector from the set, and still span

V .

We can repeat this procedure until we have a linearly independent set of vectors, which will then be a basis. These results let us make a definition.

🔗

Definition 1.7.4.

🔗

Let

V

be a vector space. If

V

can be spanned by a finite number of vectors, then we call

V

a finite-dimensional vector space. If

V

is finite-dimensional (and non-trivial), and

{e_{1}, \dots, e_{n}}

is a basis of

V,

we say that

V

has dimension

n,

and write

\dim V = n .

🔗

V

cannot be spanned by finitely many vectors, we say that

V

is infinite-dimensional.

🔗

Exercise 1.7.5.

🔗

Find a basis for

U = {X \in M_{22} | X A = A X},

A = [\begin{matrix} 1 & 1 \\ 0 & 0 \end{matrix}]

🔗

Example 1.7.6. Standard bases.

🔗

Most of the vector spaces we work with come equipped with a standard basis. The standard basis for a vector space is typically a basis such that the scalars needed to express a vector in terms of that basis are the same scalars used to define the vector in the first place. For example, we write an element of

R^{3}

(x, y, z)

(or

⟨ x, y, z ⟩,

[\begin{matrix} x & y & z \end{matrix}],

[\begin{matrix} x \\ y \\ z \end{matrix}]

…). We can also write

(x, y, z) = x (1, 0, 0) + y (0, 1, 0) + z (0, 0, 1) .

🔗

The set

{(1, 0, 0), (0, 1, 0), (0, 0, 1)}

is the standard basis for

R^{3} .

In general, the vector space

R^{n}

(written this time as column vectors) has standard basis

e_{1} = [\begin{matrix} 1 \\ 0 \\ ⋮ \\ 0 \end{matrix}], e_{2} = [\begin{matrix} 0 \\ 1 \\ ⋮ \\ 0 \end{matrix}], \dots, e_{n} = [\begin{matrix} 0 \\ 0 \\ ⋮ \\ 1 \end{matrix}] .

🔗

From this, we can conclude (unsurprisingly) that

\dim R^{n} = n .

🔗

Similarly, a polynomial

p (x) \in P_{n} (R)

is usually written as

p (x) = a_{0} + a_{1} x + a_{2} x^{2} + \dots + a_{n} x^{n},

🔗

suggesting the standard basis

{1, x, x^{2}, \dots, x^{n}} .

As a result, we see that

\dim P_{n} (R) = n + 1 .

🔗

For one more example, we note that a

2 \times 2

matrix

A \in M_{22} (R)

can be written as

[\begin{matrix} a & b \\ c & d \end{matrix}] = a [\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}] + b [\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix}] + c [\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix}] + d [\begin{matrix} 0 & 0 \\ 0 & 1 \end{matrix}],

🔗

which suggests a standard basis for

M_{22} (R),

with similar results for any other matrix space. From this, we can conclude (exercise) that

\dim M_{m n} (R) = m n .

🔗

Exercise 1.7.7.

🔗

Show that the following sets are bases of

R^{3} .

🔗

(a)

🔗

{(1, 1, 0), (1, 0, 1), (0, 1, 1)}

🔗

(b)

🔗

{(- 1, 1, 1), (1, - 1, 1), (1, 1, - 1)}

🔗

The next two exercises are left to the reader to solve. In each case, your goal should be to turn the questions of independence and span into a system of equations, which you can then solve using the computer.

🔗

Exercise 1.7.8.

🔗

Show that the following is a basis of

M_{22} :

{[\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}], [\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}], [\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix}], [\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}]} .

Hint.

For independence, consider the linear combination

w [\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}] + x [\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}] + y [\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix}] + z [\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}] = [\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}] .

Combine the left-hand side, and then equate entries of the matrices on either side to obtain a system of equations.

🔗

Exercise 1.7.9.

🔗

Show that

{1 + x, x + x^{2}, x^{2} + x^{3}, x^{3}}

is a basis for

P_{3} .

Hint.

For independence, consider the linear combination

a (1 + x) + b (x + x^{2}) + c (x^{2} + x^{3}) + d x^{3} = 0 .

When dealing with polynomials, we need to collect like terms and equate coefficients:

a \cdot 1 + (a + b) x + (b + c) x^{2} + (c + d) x^{3} = 0,

so the coefficients

a, a + b, b + c, c + d

must all equal zero.

🔗

Exercise 1.7.10.

🔗

Find a basis and dimension for the following subspaces of

P_{2} :

🔗

(a)

🔗

U_{1} = {a (1 + x) + b (x + x^{2}) | a, b \in R}

🔗

(b)

🔗

U_{2} = {p (x) \in P_{2} | p (1) = 0}

🔗

(c)

🔗

U_{3} = {p (x) \in P_{2} | p (x) = p (- x)}

🔗

We’ve noted a few times now that if

w \in span {v_{1}, \dots, v_{n}},

then

span {w, v_{1}, \dots, v_{n}} = span {v_{1}, \dots, v_{n}}

🔗

w

is not in the span, we can make another useful observation:

🔗

Lemma 1.7.11. Independent Lemma.

🔗

Suppose

{v_{1}, \dots, v_{n}}

is a linearly independent set of vectors in a vector space

V .

u \in V

but

u \notin span {v_{1}, \dots, v_{n}},

then

{u, v_{1}, \dots, v_{n}}

is independent.

Strategy.

We want to show that a set of vectors is linearly independent, so we should begin by setting a linear combination of these vectors equal to the zero vector. Our goal is to show that all the coefficients have to be zero.

Since the vector

u

is “special”, its coefficient gets a different treatment, using a familiar tautology: either this coefficient is zero, or it isn’t.

what if the coefficient of

u

is nonzero? Does that contradict one of our assumptions? If the coefficient of

u

is zero, then it disappears from our linear combination. What assumption applies to the remaining vectors?

Proof.

Suppose

S = {v_{1}, \dots, v_{n}}

is independent, and that

u \notin span S .

Suppose we have

a u + c_{1} v_{1} + c_{2} v_{2} + \dots + c_{n} b_{n} = 0

for scalars

a, c_{1}, \dots, c_{n} .

We must have

a = 0;

otherwise, we can multiply by

\frac{1}{a}

and rearrange to obtain

u = - \frac{c_{1}}{a} v_{1} - \dots - \frac{c_{n}}{a} v_{n},

but this would mean that

u \in span S,

contradicting our assumption.

With

a = 0

we’re left with

c_{1} v_{1} + c_{2} v_{2} + \dots + c_{n} b_{n} = 0,

and since we assumed that the set

S

is independent, we must have

c_{1} = c_{2} = \dots = c_{n} = 0 .

Since we already showed

a = 0,

this shows that

{u, v_{1}, \dots, v_{n}}

is independent.

🔗

This is, in fact, an “if and only if” result. If

u \in span {v_{1}, \dots, v_{n}},

then

{u, v_{1}, \dots, v_{n}}

is not independent. Above, we argued that if

V

is finite dimensional, then any spanning set for

V

can be reduced to a basis. It probably won’t surprise you that the following is also true.

🔗

Lemma 1.7.12.

🔗

Let

V

be a finite-dimensional vector space, and let

U

be any subspace of

V .

Then any independent set of vectors

{u_{1}, \dots, u_{k}}

U

can be enlarged to a basis of

U .

Strategy.

We have an independent set of vectors that doesn’t span our subspace. That means there must be some vector in

U

that isn’t in the span, so Lemma 1.7.11 applies: we can add that vector to our set, and get a larger independent set.

Now it’s just a matter of repeating this process until we get a spanning set. But there’s one gap: how do we know the process has to stop? Why can’t we just keep adding vectors forever, getting larger and larger independent sets?

Proof.

This follows from Lemma 1.7.11. If our independent set of vectors spans

U,

then it’s a basis and we’re done. If not, we can find some vector not in the span, and add it to our set to obtain a larger set that is still independent. We can continue adding vectors in this fashion until we obtain a spanning set.

Note that this process must terminate:

V

is finite-dimensional, so there is a finite spanning set for

V .

By the Steinitz Exchange lemma, our independent set cannot get larger than this spanning set.

🔗

Theorem 1.7.13.

🔗

Any finite-dimensional (non-trivial) vector space

V

has a basis. Moreover:

If $V$ can be spanned by $m$ vectors, then $\dim V \leq m .$
Given an independent set $I$ in $V$ that does not span $V,$ and a basis $B$ of $V,$ we can enlarge $I$ to a basis of $V$ by adding elements of $B .$

Strategy.

Much of this theorem sums up some of what we’ve learned so far: As long as a vector space

V

contains a nonzero vector

v,

the set

{v}

is independent and can be enlarged to a basis, by Lemma 1.7.12. The size of any spanning set is at least as big as the dimension of

V,

by Theorem 1.7.1.

To understand why we can enlarge a given independent set using elements of an existing basis, we need to think about why there must be some vector in this basis that is not in the span of our independent set, so that we can apply Lemma 1.7.12.

Proof.

Let

V

be a finite-dimensional, non-trivial vector space. If

v \neq 0

is a vector in

V,

then

{v}

is linearly independent. By Lemma 1.7.12, we can enlarge this set to a basis of

V,

V

has a basis.

Now, suppose

V = span {w_{1}, \dots, w_{m}},

and let

B = {v_{1}, \dots, v_{n}}

be a basis for

V .

By definition, we have

\dim V = n,

and by Theorem 1.7.1, since

B

is linearly independent, we must have

n \leq m .

Let us now consider an independent set

I = {u_{1}, \dots, u_{k}} .

Since

I

is independent and

B

spans

V,

we must have

k \leq n .

span I \neq V,

there must be some element of

B

that is not in the span of

I :

if every element of

B

is in

span I,

then

span I = span (B \cup I)

by Theorem 1.4.10. And since

B

is a basis, it spans

V,

so every element of

I

is in the span of

B,

and we similarly have that

span (B \cup I) = span B,

span B = span I .

Since we can find an element of

B

that is not in the span of

I,

we can add that element to

I,

and the resulting set is still independent. If the new set spans

V,

we’re done. If not, we can repeat the process, adding another vector from

B .

Since the set

B

is finite, this process must eventually end.

🔗

Exercise 1.7.14.

🔗

Find a basis of

M_{22} (R)

that contains the vectors

v = [\begin{matrix} 1 & 1 \\ 0 & 0 \end{matrix}], w = [\begin{matrix} 0 & 1 \\ 0 & 1 \end{matrix}] .

🔗

Exercise 1.7.15.

🔗

Extend the set

{1 + x, x + x^{2}, x - x^{3}}

to a basis of

P_{3} (R) .

🔗

Exercise 1.7.16.

🔗

Give two examples of infinite-dimensional vector spaces. Support your answer.

🔗

Exercise 1.7.17.

🔗

Determine whether the following statements are true or false.

🔗

(a)

🔗

A set of 2 vectors can span

R^{3} .

True.
We know that the standard basis for $R^{3}$ contains three vectors, and as a basis, it is linearly independent. According to Theorem 1.7.1, a spanning set cannot be larger than an independent set.
False.
We know that the standard basis for $R^{3}$ contains three vectors, and as a basis, it is linearly independent. According to Theorem 1.7.1, a spanning set cannot be larger than an independent set.

🔗

(b)

🔗

It is possible for a set of 2 vectors to be linearly independent in

R^{3} .

True.
There are many such examples, including ${(1, 0, 0), (0, 1, 0)} .$
False.
There are many such examples, including ${(1, 0, 0), (0, 1, 0)} .$

🔗

(c)

🔗

A set of 4 vectors can span

R^{3} .

True.
Add any vector you want to a basis for $R^{3},$ and the resulting set will span.
False.
Add any vector you want to a basis for $R^{3},$ and the resulting set will span.

🔗

(d)

🔗

It is possible for a set of 4 vectors to be linearly independent in

R^{3} .

True.
We know that 3 vectors can span $R^{3},$ and an independent set cannot be larger than a spanning set.
False.
We know that 3 vectors can span $R^{3},$ and an independent set cannot be larger than a spanning set.

🔗

Let’s recap our results so far:

A basis for a vector space $V$ is an independent set of vectors that spans $V .$
The number of vectors in any basis of $V$ is a constant, called the dimension of $V .$
The number of vectors in any independent set is always less than or equal to the number of vectors in a spanning set.
In a finite-dimensional vector space, any independent set can be enlarged to a basis, and any spanning set can be cut down to a basis by deleting vectors that are in the span of the remaining vectors.

🔗

Another important aspect of dimension is that it reduces many problems, such as determining equality of subspaces, to counting problems.

🔗

Theorem 1.7.18.

🔗

Let

U

and

W

be subspaces of a finite-dimensional vector space

V .

If $U \subseteq W,$ then $\dim U \leq \dim W .$
If $U \subseteq W$ and $\dim U = \dim W,$ then $U = W .$

Proof.

Suppose $U \subseteq W,$ and let $B = {u_{1}, \dots, u_{k}}$ be a basis for $U .$ Since $B$ is a basis, it’s independent. And since $B \subseteq U$ and $U \subseteq W,$ $B \subseteq W .$ Thus, $B$ is an independent subset of $W,$ and since any basis of $W$ spans $W,$ we know that $\dim U = k \leq \dim W,$ by Theorem 1.7.1.
Suppose $U \subseteq W$ and $\dim U = \dim W .$ Let $B$ be a basis for $U .$ As above, $B$ is an independent subset of $W .$ If $W \neq U,$ then there is some $w \in W$ with $w \notin U .$ But $U = span B,$ so that would mean that $B \cup {w}$ is a linearly independent set containing $\dim U + 1$ vectors. This is impossible, since $\dim W = \dim U,$ so no independent set can contain more than $\dim U$ vectors.

🔗

An even more useful counting result is the following:

🔗

Theorem 1.7.19.

🔗

Let

V

be an

n

-dimensional vector space. If the set

S

contains

n

vectors, then

S

is independent if and only if

span S = V .

Strategy.

This result is a combination of three observations:

The dimension of $V$ is the size of any basis
Any independent set can be enlarged to a basis, and cannot have more vectors than a basis.
Any spanning set contains a basis, and cannot have fewer vectors than a basis.

Proof.

S

is independent, then it can be extended to a basis

B

with

S \subseteq B .

But

S

and

B

both contain

n

vectors (since

\dim V = n

), so we must have

S = B .

S

spans

V,

then

S

must contain a basis

B,

and as above, since

S

and

B

contain the same number of vectors, they must be equal.

🔗

Theorem 1.7.19 saves us a lot of time, since it tells us that, when we know the dimension of

V,

we do not have to check both independence and span to confirm a basis; checking one of the two implies the other. (And usually independence is easier to check.)

🔗

We saw this in Exercise 1.7.7: given a set of vectors in

R^{3},

we form the matrix

A

with these vectors as columns. This matrix becomes the coefficient matrix for the system of equations we obtain when checking for independence, and for the system we obtain when checking for span. In both cases, the condition on

A

is the same; namely, that it must be invertible.

🔗

Exercises Exercises

🔗

1.

🔗

Find a basis

{p (x), q (x)}

for the vector space

{f (x) \in P_{2} (R) ∣ f^{'} (3) = f (1)}

where

P_{2} (R)

is the vector space of polynomials in

x

with degree less than or equal to 2.

🔗

2.

🔗

Find a basis for the vector space

{A \in M_{22} (R) ∣ tr (A) = 0}

2 \times 2

matrices with trace 0.

🔗

3.

🔗

True or false: if a set

S

of vectors is linearly independent in a vector space

V,

but

S

does not span

V,

then

S

can be extended to a basis for

V

by adding vectors.

True.
What if $V$ is infinite-dimensional?
False.
What if $V$ is infinite-dimensional?

🔗

4.

🔗

True or false: if

V = span {v_{1}, v_{2}, v_{3}},

then

\dim V = 3 .

True.
What if the set ${v_{1}, v_{2}, v_{3}}$ is linearly dependent?
False.
What if the set ${v_{1}, v_{2}, v_{3}}$ is linearly dependent?

🔗

5.

🔗

True or false: if

U

is a subspace of a vector space

V,

and

U = span (S)

for a finite set of vectors

S,

then

S

contains a basis for

U .

True.
Since $S$ is finite and spans $U,$ the subspace $U$ is finite-dimensional. If $S$ is linearly dependent, we can remove vectors from $S$ until we obtain a set that spans $U$ and is linearly independent.
False.
Since $S$ is finite and spans $U,$ the subspace $U$ is finite-dimensional. If $S$ is linearly dependent, we can remove vectors from $S$ until we obtain a set that spans $U$ and is linearly independent.

🔗

6.

🔗

Suppose that

S_{1}

and

S_{2}

are nonzero subspaces, with

S_{1}

contained inside

S_{2},

and suppose that

\dim (S_{2}) = 3 .

🔗

(a) What are the possible dimensions of

S_{1} ?

🔗

(b) If

S_{1} \neq S_{2}

then what are the possible dimensions of

S_{1} ?

🔗

7.

🔗

Let

P_{2}

be the vector space of all polynomials of degree 2 or less, and let

H

be the subspace spanned by

7 x^{2} - x - 2, 4 x^{2} - 1

and

2 - (9 x^{2} + x) .

🔗

(a) What is the dimension of the subspace

H ?

🔗

(b) Is

{7 x^{2} - x - 2, 4 x^{2} - 1, 2 - (9 x^{2} + x)}

a basis for

P_{2} ?

🔗

Be sure you can explain and justify your answer.

🔗

(c) Give a basis for the subspace

H .

🔗

8.

🔗

Let

P_{2}

be the vector space of all polynomials of degree 2 or less, and let

H

be the subspace spanned by

7 x^{2} - 10 x - 5, 19 x^{2} - 7 x - 7

and

- (3 x + 1) .

🔗

(a) What is the dimension of the subspace

H ?

🔗

(b) Is

{7 x^{2} - 10 x - 5, 19 x^{2} - 7 x - 7, - (3 x + 1)}

a basis for

P_{2} ?

🔗

Be sure you can explain and justify your answer.

🔗

(c) Give a basis for the subspace

H .

You have attempted 1 of 21 activities on this page.

Prev Top Next