IB Linear Algebra - Vector spaces

1Vector spaces

IB Linear Algebra

1.2 Linear independence, bases and the Steinitz exchange

lemma

Recall that in

, we had the “standard basis” made of vectors of the form

= (0

, ··· ,

0), with 1 in the

th component and 0 otherwise. We

call this a basis because everything in

can be (uniquely) written as a sum

of (scalar multiples of) these basis elements. In other words, the whole

generated by taking sums and multiples of the basis elements.

We would like to capture this idea in general vector spaces. The most

important result in this section is to prove that for any vector space

, any two

basis must contain the same number of elements. This means we can define the

“dimension” of a vector space as the number of elements in the basis.

While this result sounds rather trivial, it is a very important result. We will

in fact prove a slightly stronger statement than what was stated above, and this

ensures that the dimension of a vector space is well-behaved. For example, the

subspace of a vector space has a smaller dimension than the larger space (at

least when the dimensions are finite).

This is not the case when we study modules in IB Groups, Rings and Modules,

which are generalizations of vector spaces. Not all modules have basis, which

makes it difficult to define the dimension. Even for those that have basis, the

behaviour of the “dimension” is complicated when, say, we take submodules.

The existence and well-behavedness of basis and dimension is what makes linear

algebra different from modules.

Definition

(Span)

Let

be a vector space over

and

S ⊆ V

. The span of

is defined as

hSi =

(

i=1

: λ

∈ F, s

∈ S, n ≥ 0

)

This is the smallest subspace of V containing S.

Note that the sums must be finite. We will not play with infinite sums, since

the notion of convergence is not even well defined in a general vector space.

Example.

(i) Let V = R

and S =





































. Then

hSi =















: a, b ∈ R







Note that any subset of S of order 2 has the same span as S.

(ii) Let X be a set, x ∈ X. Define the function δx : X → F by

δx(y) =

(

1 y = x

0 y 6= x

Then hδx : x ∈ Xi is the set of all functions with finite support.

Definition

(Spanning set)

Let

be a vector space over

and

S ⊆ V

spans

V if hSi = V .

Definition

(Linear independence)

Let

be a vector space over

and

S ⊆ V

Then S is linearly independent if whenever

i=1

= 0 with λ

∈ F, s

, s

, ··· , s

∈ S distinct,

we must have λ

= 0 for all i.

If S is not linearly independent, we say it is linearly dependent.

Definition

(Basis)

Let

be a vector space over

and

S ⊆ V

. Then

is a

basis for V if S is linearly independent and spans V .

Definition

(Finite dimensional)

A vector space is finite dimensional if there

is a finite basis.

Ideally, we would want to define the dimension as the number of vectors in

the basis. However, we must first show that this is well-defined. It is certainly

plausible that a vector space has a basis of size 7 as well as a basis of size 3. We

must show that this can never happen, which is something we’ll do soon.

We will first have an example:

Example.

Again, let

and





































. Then

linearly dependent since









+ 2









+ (−1)









= 0.

S also does not span V since









6∈ hSi.

Note that no linearly independent set can contain

, as 1

· 0

. We also

have h∅i = {0} and ∅ is a basis for this space.

There is an alternative way in which we can define linear independence.

Lemma. S ⊆ V

is linearly dependent if and only if there are distinct

, ··· , s

∈

S and λ

, ··· , λ

∈ F such that

i=1

= s

Proof.

is linearly dependent, then there are some

, ··· , λ

∈ F

not all

zero and s

, ··· , s

∈ S such that

= 0. Wlog, let λ

6= 0. Then

i=2

−

Conversely, if s

i=1

, then

(−1)s

i=1

= 0.

So S is linearly dependent.

This in turn gives an alternative characterization of what it means to be a

basis:

Proposition.

, ··· , e

}

is a subset of

over

, then it is a basis if

and only if every

v ∈ V

can be written uniquely as a finite linear combination

of elements in S, i.e. as

v =

i=1

Proof.

We can view this as a combination of two statements: it can be spanned

in at least one way, and it can be spanned in at most one way. We will see that

the first part corresponds to

spanning

, and the second part corresponds to

S being linearly independent.

In fact,

spanning

is defined exactly to mean that every item

v ∈ V

can

be written as a finite linear combination in at least one way.

Now suppose that S is linearly independent, and we have

v =

i=1

Then we have

0 = v − v =

i=1

(λ

− µ

Linear independence implies that

− µ

= 0 for all

. Hence

. So

can

be expressed in a unique way.

On the other hand, if S is not linearly independent, then we have

0 =

i=1

where λ

6= 0 for some i. But we also know that

0 =

i=1

0 · e

So there are two ways to write 0 as a linear combination. So done.

Now we come to the key theorem:

Theorem

(Steinitz exchange lemma)

Let

be a vector space over

, and

, ··· , e

}

a finite linearly independent subset of

, and

a spanning

subset of

. Then there is some

⊆ T

of order

such that (

T \ T

)

∪ S

still

spans V . In particular, |T | ≥ n.

What does this actually say? This says if

is spanning and

is independent,

there is a way of grabbing

|S|

many elements away from

and replace them

with S, and the result will still be spanning.

In some sense, the final remark is the most important part. It tells us that

we cannot have a independent set larger than a spanning set, and most of our

corollaries later will only use this remark.

This is sometimes stated in the following alternative way for |T | < ∞.

Corollary.

Let

, ··· , e

}

be a linearly independent subset of

, and sup-

pose

, ··· , f

}

spans

. Then there is a re-ordering of the

}

such that

, ··· , e

, f

n+1

, ··· , f

} spans V .

The proof is going to be slightly technical and notationally daunting. So it

helps to give a brief overview of what we are going to do in words first. The idea

is to do the replacement one by one. The first one is easy. Start with

. Since

T is spanning, we can write

for some

∈ T, λ

∈ F

non-zero. We then replace with

with

. The result is

still spanning, since the above formula allows us to write

in terms of

and

the other t

We continue inductively. For the rth element, we again write

We would like to just pick a random

and replace it with

. However, we

cannot do this arbitrarily, since the lemma wants us to replace something in T

with with

. After all that replacement procedure before, some of the

might

have actually come from S.

This is where the linear independence of

kicks in. While some of the

might be from S, we cannot possibly have all all of them being from S, or else

this violates the linear independence of

. Hence there is something genuinely

from T , and we can safely replace it with e

We now write this argument properly and formally.

Proof.

Suppose that we have already found

⊆ T

of order 0

≤ r < n

such that

= (T \ T

) ∪ {e

, ··· , e

}

spans V .

(Note that the case

= 0 is trivial, since we can take

∅

, and the case

r = n is the theorem which we want to achieve.)

Suppose we have these. Since T

spans V , we can write

r+1

i=1

, λ

∈ F, t

∈ T

We know that the

are linearly independent, so not all

’s are

’s. So there is

some j such that t

∈ (T \ T

). We can write this as

r+1

i6=j

−

We let T

r+1

= T

∪ {t

} of order r + 1, and

r+1

= (T \ T

r+1

) ∪ {e

, ··· , e

r+1

} = (T

\ {t

}} ∪ {e

r+1

}

Since t

is in the span of T

∪ {e

r+1

}, we have t

∈ hT

r+1

i. So

V ⊇ hT

r+1

i ⊇ hT

i = V.

So hT

r+1

i = V .

Hence we can inductively find T

From this lemma, we can immediately deduce a lot of important corollaries.

Corollary. Suppose V is a vector space over F with a basis of order n. Then

(i) Every basis of V has order n.

(ii) Any linearly independent set of order n is a basis.

(iii) Every spanning set of order n is a basis.

(iv) Every finite spanning set contains a basis.

(v) Every linearly independent subset of V can be extended to basis.

Proof. Let S = {e

, ··· , e

} be the basis for V .

(i)

Suppose

is another basis. Since

is independent and

is spanning,

|T | ≥ |S|.

The other direction is less trivial, since

might be infinite, and Steinitz

does not immediately apply. Instead, we argue as follows: since

linearly independent, every finite subset of

is independent. Also,

spanning. So every finite subset of

has order at most

|S|

. So

|T | ≤ |S|

So |T | = |S|.

(ii)

Suppose now that

is a linearly independent subset of order

, but

hT i 6

. Then there is some

v ∈ V \hT i

. We now show that

T ∪ {v}

independent. Indeed, if

v +

i=1

= 0

with λ

∈ F, t

, ··· , t

∈ T distinct, then

v =

i=1

(−λ

Then

v ∈ hT i

. So

= 0. As

is linearly independent, we have

···

= 0. So

T ∪ {v}

is a linearly independent subset of size

> n. This is a contradiction since S is a spanning set of size n.

(iii)

Let

be a spanning set of order

. If

were linearly dependent, then

there is some t

, ··· , t

∈ T distinct and λ

, ··· , λ

∈ F such that

∈ hT \ {t

, i.e.

hT \ {t

. So

T \ {t

}

is a spanning set of

order n − 1, which is a contradiction.

(iv)

Suppose

is any finite spanning set. Let

⊆ T

be a spanning set of least

possible size. This exists because

is finite. If

has size

, then done

by (iii). Otherwise by the Steinitz exchange lemma, it has size

| > n

must be linearly dependent because

is spanning. So there is some

, ··· , t

∈ T

distinct and

, ··· , λ

∈ F

such that

. Then

\ {t

} is a smaller spanning set. Contradiction.

(v)

Suppose

is a linearly independent set. Since

spans, there is some

⊆ S

of order

|T |

such that (

S \S

)

∪T

spans

by the Steinitz exchange

lemma. So by (ii), (S \ S

) ∪ T is a basis of V containing T.

Note that the last part is where we actually use the full result of Steinitz.

Finally, we can use this to define the dimension.

Definition

(Dimension)

is a vector space over

with finite basis

, then

the dimension of V , written

dim V = dim

V = |S|.

By the corollary,

dim V

does not depend on the choice of

. However, it does

depend on

. For example,

dim

= 1 (since

{

}

is a basis), but

dim

= 2

(since {1, i} is a basis).

After defining the dimension, we can prove a few things about dimensions.

Lemma.

is a finite dimensional vector space over

U ⊆ V

is a proper

subspace, then U is finite dimensional and dim U < dim V .

Proof.

Every linearly independent subset of

has size at most

dim V

. So let

S ⊆ U

be a linearly independent subset of largest size. We want to show that

spans U and |S| < dim V .

v ∈ V \hSi

, then

S ∪{v}

is linearly independent. So

v 6∈ U

by maximality

of S. This means that hSi = U.

Since

U 6

, there is some

v ∈ V \ U

V \ hSi

. So

S ∪ {v}

is a linearly

independent subset of order

|S|

+ 1. So

|S|

+ 1

≤ dim V

. In particular,

dim U

|S| < dim V .

Proposition.

U, W

are subspaces of a finite dimensional vector space

, then

dim(U + W ) = dim U + dim W − dim(U ∩ W ).

The proof is not hard, as long as we manage to pick the right basis to do the

proof. This is our slogan:

When you choose a basis, always choose the right basis.

We need a basis for all four of them, and we want to compare the bases. So we

want to pick bases that are compatible.

Proof.

Let

, ··· , v

}

be a basis for

U ∩W

. This is a linearly independent

subset of U. So we can extend it to be a basis of U by

S = {v

, ··· , v

, u

r+1

, ··· , u

Similarly, for W , we can obtain a basis

T = {v

, ··· , v

, w

r+1

, ··· , w

We want to show that

dim

(

) =

t − r

. It is sufficient to prove that

S ∪ T is a basis for U + W .

We first show spanning. Suppose

w ∈ U

u ∈ U, w ∈ W

. Then

u ∈ hSi and w ∈ hT i. So u + w ∈ hS ∪ T i. So U + W = hS ∪ T i.

To show linear independence, suppose we have a linear relation

i=1

j=r+1

k=r+1

= 0.

= −

Since the left hand side is something in

, and the right hand side is something

in W , they both lie in U ∩ W .

Since

is a basis of

, there is only one way of writing the left hand vector

as a sum of

and

. However, since

is a basis of

U ∩ W

, we can write the

left hand vector just as a sum of

’s. So we must have

= 0 for all

. Then

we have

= 0.

Finally, since

is linearly independent,

= 0 for all

i, k

. So

S ∪ T

linearly independent.

Proposition.

is a finite dimensional vector space over

and

U ∪ V

is a

subspace, then

dim V = dim U + dim V /U.

We can view this as a linear algebra version of Lagrange’s theorem. Combined

with the first isomorphism theorem for vector spaces, this gives the rank-nullity

theorem.

Proof.

Let

, ··· , u

}

be a basis for

and extend this to a basis

, ··· , u

m+1

, ··· , v

}

for

. We want to show that

m+1

U, ··· , v

is a basis

for V/U.

It is easy to see that this spans V /U. If v + U ∈ V/U, then we can write

v =

Then

v + U =

+ U) +

+ U) =

+ U).

So done.

To show that they are linearly independent, suppose that

+ U) = 0 + U = U.

Then this requires

∈ U.

Then we can write this as a linear combination of the u

’s. So

for some

. Since

, ··· , u

, v

n+1

, ··· , v

}

is a basis for

, we must have

= µ

= 0 for all i, j. So {v

+ U} is linearly independent.