IB Linear Algebra (Full)

Part IB — Linear Algebra

Based on lectures by S. J. Wadsley

Notes taken by Dexter Chua

Michaelmas 2015

These notes are not endorsed by the lecturers, and I have modified them (often

significantly) after lectures. They are nowhere near accurate representations of what

was actually lectured, and in particular, all errors are almost surely mine.

Definition of a vector space (over

), subspaces, the space spanned by a subset.

Linear independence, bases, dimension. Direct sums and complementary subspaces.

[3]

Linear maps, isomorphisms. Relation between rank and nullity. The space of linear

maps from

, representation by matrices. Change of basis. Row rank and column

rank. [4]

Determinant and trace of a square matrix. Determinant of a product of two matrices

and of the inverse matrix. Determinant of an endomorphism. The adjugate matrix. [3]

Eigenvalues and eigenvectors. Diagonal and triangular forms. Characteristic and

minimal polynomials. Cayley-Hamilton Theorem over

. Algebraic and geometric

multiplicity of eigenvalues. Statement and illustration of Jordan normal form. [4]

Dual of a finite-dimensional vector space, dual bases and maps. Matrix representation,

rank and determinant of dual map. [2]

Bilinear forms. Matrix representation, change of basis. Symmetric forms and their link

with quadratic forms. Diagonalisation of quadratic forms. Law of inertia, classification

by rank and signature. Complex Hermitian forms. [4]

Inner product spaces, orthonormal sets, orthogonal projection,

W ⊕ W

⊥

. Gram-

Schmidt orthogonalisation. Adjoints. Diagonalisation of Hermitian matrices. Orthogo-

nality of eigenvectors and properties of eigenvalues. [4]

Contents

0 Introduction

1 Vector spaces

1.1 Definitions and examples

1.2 Linear independence, bases and the Steinitz exchange lemma

1.3 Direct sums

2 Linear maps

2.1 Definitions and examples

2.2 Linear maps and matrices

2.3 The first isomorphism theorem and the rank-nullity theorem

2.4 Change of basis

2.5 Elementary matrix operations

3 Duality

3.1 Dual space

3.2 Dual maps

4 Bilinear forms I

5 Determinants of matrices

6 Endomorphisms

6.1 Invariants

6.2 The minimal polynomial

6.2.1 Aside on polynomials

6.2.2 Minimal polynomial

6.3 The Cayley-Hamilton theorem

6.4 Multiplicities of eigenvalues and Jordan normal form

7 Bilinear forms II

7.1 Symmetric bilinear forms and quadratic forms

7.2 Hermitian form

8 Inner product spaces

8.1 Definitions and basic properties

8.2 Gram-Schmidt orthogonalization

8.3 Adjoints, orthogonal and unitary maps

8.4 Spectral theory

0 Introduction

In IA Vectors and Matrices, we have learnt about vectors (and matrices) in a

rather applied way. A vector was just treated as a “list of numbers” representing

a point in space. We used these to represent lines, conics, planes and many

other geometrical notions. A matrix is treated as a “physical operation” on

vectors that stretches and rotates them. For example, we studied the properties

of rotations, reflections and shears of space. We also used matrices to express

and solve systems of linear equations. We mostly took a practical approach in

the course.

In IB Linear Algebra, we are going to study vectors in an abstract setting.

Instead of treating vectors as “lists of numbers”, we view them as things we

can add and scalar-multiply. We will write down axioms governing how these

operations should behave, just like how we wrote down the axioms of group

theory. Instead of studying matrices as an array of numbers, we instead look at

linear maps between vector spaces abstractly.

In the course, we will, of course, prove that this abstract treatment of linear

algebra is just “the same as” our previous study of “vectors as a list of numbers”.

Indeed, in certain cases, results are much more easily proved by working with

matrices (as an array of numbers) instead of abstract linear maps, and we don’t

shy away from doing so. However, most of the time, looking at these abstractly

will provide a much better fundamental understanding of how things work.

1 Vector spaces

1.1 Definitions and examples

Notation. We will use F to denote an arbitrary field, usually R or C.

Intuitively, a vector space V over a field F (or an F-vector space) is a space

with two operations:

– We can add two vectors v

, v

∈ V to obtain v

+ v

∈ V .

– We can multiply a scalar λ ∈ F with a vector v ∈ V to obtain λv ∈ V .

Of course, these two operations must satisfy certain axioms before we can

call it a vector space. However, before going into these details, we first look at a

few examples of vector spaces.

Example.

(i) R

{column vectors of length n with coefficients in R}

with the usual

addition and scalar multiplication is a vector space.

m × n

matrix

with coefficients in

can be viewed as a linear map

from R

to R

via v 7→ Av.

This is a motivational example for vector spaces. When confused about

definitions, we can often think what the definition means in terms of

and matrices to get some intuition.

(ii)

Let

be a set and define

X → R}

with addition (

)(

) =

(

) +

(

) and scalar multiplication (

λf

)(

) =

λf

(

). This is a vector

space.

More generally, if

is a vector space,

is a set, we can define

X → V } with addition and scalar multiplication as above.

(iii) Let [a, b] ⊆ R be a closed interval, then

C([a, b], R) = {f ∈ R

[a,b]

: f is continuous}

is a vector space, with operations as above. We also have

∞

([a, b], R) = {f ∈ R

[a,b]

: f is infinitely differentiable}

(iv)

The set of

m × n

matrices with coefficients in

is a vector space, using

componentwise addition and scalar multiplication, is a vector space.

Of course, we cannot take a random set, define some random operations

called addition and scalar multiplication, and call it a vector space. These

operations have to behave sensibly.

Definition

(Vector space)

-vector space is an (additive) abelian group

together with a function F × V → V , written (λ, v) 7→ λv , such that

(i) λ(µv) = λµv for all λ, µ ∈ F, v ∈ V (associativity)

(ii) λ(u + v) = λu + λv for all λ ∈ F, u, v ∈ V (distributivity in V )

(iii) (λ + µ)v = λv + µv for all λ, µ ∈ F, v ∈ V (distributivity in F)

(iv) 1v = v for all v ∈ V (identity)

We always write

for the additive identity in

, and call this the identity.

By abuse of notation, we also write 0 for the trivial vector space {0}.

In a general vector space, there is no notion of “coordinates”, length, angle

or distance. For example, it would be difficult to assign these quantities to the

vector space of real-valued continuous functions in [a, b].

From the axioms, there are a few results we can immediately prove.

Proposition.

In any vector space

, 0

for all

v ∈ V

, and (

−

−v

where −v is the additive inverse of v.

Proof is left as an exercise.

In mathematics, whenever we define “something”, we would also like to define

a “sub-something”. In the case of vector spaces, this is a subspace.

Definition

(Subspace)

is an

-vector space, then

U ⊆ V

is an (

-linear)

subspace if

(i) u, v ∈ U implies u + v ∈ U .

(ii) u ∈ U, λ ∈ F implies λu ∈ U .

(iii) 0 ∈ U .

These conditions can be expressed more concisely as “

is non-empty and if

λ, µ ∈ F, u, v ∈ U , then λu + µv ∈ U”.

Alternatively,

is a subspace of

if it is itself a vector space, inheriting the

operations from V .

We sometimes write U ≤ V if U is a subspace of V .

Example.

(i) {(x

, x

) ∈ R

: x

+ x

= t} is a subspace of R

iff t = 0.

(ii)

Let

be a set. We define the support of

to be

supp

(

) =

{x ∈ X

(

)

= 0

}

. Then the set of functions with finite support

forms a vector subspace. This is since

supp

(

)

⊆ supp

(

)

∪ supp

(

supp(λf) = supp(f) (for λ 6= 0) and supp(0) = ∅.

If we have two subspaces

and

, there are several things we can do with

them. For example, we can take the intersection

U ∩ V

. We will shortly show

that this will be a subspace. However, taking the union will in general not

produce a vector space. Instead, we need the sum:

Definition

(Sum of subspaces)

Suppose

U, W

are subspaces of an

vector

space V . The sum of U and V is

U + W = {u + w : u ∈ U, w ∈ W }.

Proposition.

Let

U, W

be subspaces of

. Then

and

U ∩ W

are

subspaces.

Proof. Let u

+ w

∈ U + W , λ, µ ∈ F. Then

λ(u

+ w

) + µ(u

+ w

) = (λu

+ µu

) + (λw

+ µw

) ∈ U + W.

Similarly, if

∈ U ∩ W

, then

λv

µv

∈ U

and

λv

µv

∈ W

. So

λv

+ µv

∈ U ∩ W .

Both U ∩ W and U + W contain 0, and are non-empty. So done.

In addition to sub-somethings, we often have quotient-somethings as well.

Definition

(Quotient spaces)

Let

be a vector space, and

U ⊆ V

a subspace.

Then the quotient group

V/U

can be made into a vector space called the quotient

space, where scalar multiplication is given by (λ, v + U ) = (λv) + U.

This is well defined since if

U ∈ V /U

, then

v − w ∈ U

. Hence

for λ ∈ F, we have λv − λw ∈ U. So λv + U = λw + U .

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.

1.3 Direct sums

We are going to define direct sums in many ways in order to confuse students.

Definition

((Internal) direct sum)

Suppose

is a vector space over

and

U, W ⊆ V

are subspaces. We say that

is the (internal) direct sum of

and

W if

(i) U + W = V

(ii) U ∩ W = 0.

We write V = U ⊕ W .

Equivalently, this requires that every

v ∈ V

can be written uniquely as

with u ∈ U, w ∈ W . We say that U and W are complementary subspaces of V .

You will show in the example sheets that given any subspace

U ⊆ V

must

have a complementary subspace in V .

Example.

Let

, and





. Then





and





are both

complementary subspaces to U in V .

Definition

((External) direct sum)

U, W

are vector spaces over

, the

(external) direct sum is

U ⊕ W = {(u, w) : u ∈ U, w ∈ W },

with addition and scalar multiplication componentwise:

, w

) + (u

, w

) = (u

+ u

, w

+ w

), λ(u, w) = (λu, λw).

The difference between these two definitions is that the first is decomposing

into smaller spaces, while the second is building a bigger space based on two

spaces.

Note, however, that the external direct sum

U ⊕ W

is the internal direct

sum of

and

viewed as subspaces of

U ⊕ W

, i.e. as the internal direct sum

{

(

u, 0

) :

u ∈ U}

and

{

(

0, v

) :

v ∈ V }

. So these two are indeed compatible

notions, and this is why we give them the same name and notation.

Definition

((Multiple) (internal) direct sum)

, ··· , U

⊆ V

are subspaces

of V , then V is the (internal) direct sum

V = U

⊕ ··· ⊕ U

i=1

if every v ∈ V can be written uniquely as v =

with u

∈ U

This can be extended to an infinite sum with the same definition, just noting

that the sum v =

has to be finite.

For more details, see example sheet 1 Q. 10, where we prove in particular

that dim V =

dim U

Definition

((Multiple) (external) direct sum)

, ··· , U

are vector spaces

over F, the external direct sum is

⊕ ··· ⊕ U

i=1

= {(u

, ··· , u

) : u

∈ U

with pointwise operations.

This can be made into an infinite sum if we require that all but finitely many

of the u

have to be zero.

2 Linear maps

In mathematics, apart from studying objects, we would like to study functions

between objects as well. In particular, we would like to study functions that

respect the structure of the objects. With vector spaces, the kinds of functions

we are interested in are linear maps.

2.1 Definitions and examples

Definition

(Linear map)

Let

U, V

be vector spaces over

. Then

U → V

is a linear map if

(i) α(u

+ u

) = α(u

) + α(u

) for all u

∈ U .

(ii) α(λu) = λα(u) for all λ ∈ F, u ∈ U.

We write L(U, V ) for the set of linear maps U → V .

There are a few things we should take note of:

–

If we are lazy, we can combine the two requirements to the single require-

ment that

α(λu

+ µu

) = λα(u

) + µα(u

–

It is easy to see that if

is linear, then it is a group homomorphism (if we

view vector spaces as groups). In particular, α(0) = 0.

–

If we want to stress the field

, we say that

-linear. For example,

complex conjugation is a map C → C that is R-linear but not C -linear.

Example.

(i)

Let

be an

n×m

matrix with coefficients in

. We will write

A ∈ M

n,m

(

Then α : F

→ F

defined by v → Av is linear.

Recall matrix multiplication is defined by: if A

is the ijth coefficient of

A, then the ith coefficient of Av is A

. So we have

α(λu + µv)

j=1

(λu + µv)

= λ

j=1

+ µ

j=1

= λα(u)

+ µα(v)

So α is linear.

(ii)

Let

be a set and

g ∈ F

. Then we define

→ F

(

)(

) =

g(x)f(x). Then m

is linear. For example, f (x) 7→ 2x

f(x) is linear.

(iii)

Integration

: (

([

a, b

])

, R

)

→

(

([

a, b

])

, R

) defined by

f 7→

(

) d

linear.

(iv) Differentiation D : (C

∞

([a, b]), R) → (C

∞

([a, b]), R) by f 7→ f

is linear.

(v)

α, β ∈ L

(

U, V

), then

defined by (

)(

) =

(

) +

(

) is linear.

Also, if λ ∈ F, then λα defined by (λα)(u) = λ(α(u)) is also linear.

In this way, L(U, V ) is also a vector space over F.

(vi)

Composition of linear maps is linear. Using this, we can show that many

things are linear, like differentiating twice, or adding and then multiplying

linear maps.

Just like everything else, we want to define isomorphisms.

Definition

(Isomorphism)

We say a linear map

U → V

is an isomorphism

if there is some β : V → U (also linear) such that α ◦ β = id

and β ◦ α = id

If there exists an isomorphism

U → V

, we say

and

are isomorphic, and

write U

∼

V .

Lemma.

and

are vector spaces over

and

U → V

, then

is an

isomorphism iff α is a bijective linear map.

Proof.

is an isomorphism, then it is clearly bijective since it has an inverse

function.

Suppose

is a linear bijection. Then as a function, it has an inverse

V → U

. We want to show that this is linear. Let

, v

∈ V

λ, µ ∈ F

. We

have

αβ(λv

+ µv

) = λv

+ µv

= λαβ(v

) + µαβ(v

) = α(λβ(v

) + µβ(v

)).

Since α is injective, we have

β(λv

+ µv

) = λβ(v

) + µβ(v

So β is linear.

Definition

(Image and kernel)

Let

U → V

be a linear map. Then the

image of α is

im α = {α(u) : u ∈ U }.

The kernel of α is

ker α = {u : α(u) = 0}.

It is easy to show that these are subspaces of V and U respectively.

Example.

(i)

Let

A ∈ M

m,n

(

) and

→ F

be the linear map

v 7→ Av

. Then the

system of linear equations

j=1

= b

, 1 ≤ i ≤ n

has a solution iff (b

, ··· , b

) ∈ im α.

The kernel of α contains all solutions to

= 0.

(ii) Let β : C

∞

(R, R) → C

∞

(R, R) that sends

β(f )(t) = f

(t) + p(t)f

(t) + q(t)f (t).

for some p, q ∈ C

∞

(R, R).

Then if

(

)

∈ im β

, then there is a solution (in

∞

(

R, R

)) to the differential

equation

(t) + p(t)f

(t) + q(t)f (t) = y(t).

Similarly, ker β contains the solutions to the homogeneous equation

(t) + p(t)f

(t) + q(t)f (t) = 0.

If two vector spaces are isomorphic, then it is not too surprising that they

have the same dimension, since isomorphic spaces are “the same”. Indeed this is

what we are going to show.

Proposition. Let α : U → V be an F-linear map. Then

(i)

is injective and

S ⊆ U

is linearly independent, then

(

) is linearly

independent in V .

(ii) If α is surjective and S ⊆ U spans U, then α(S) spans V .

(iii) If α is an isomorphism and S ⊆ U is a basis, then α(S) is a basis for V .

Here (iii) immediately shows that two isomorphic spaces have the same

dimension.

Proof.

(i)

We prove the contrapositive. Suppose that

is injective and

(

) is linearly

dependent. So there are

, ··· , s

∈ S

distinct and

, ··· , λ

∈ F

not all

zero such that

α(s

) =

i=1

α(s

) = α

i=1

Since α is injective, we must have

i=1

This is a non-trivial relation of the s

in U . So S is linearly dependent.

(ii)

Suppose

is surjective and

spans

. Pick

v ∈ V

. Then there is some

u ∈ U

such that

(

) =

. Since

spans

, there is some

, ··· , s

∈ S

and λ

, ··· , λ

∈ F such that

u =

I=1

Then

v = α(u) =

i=1

α(s

So α(S) spans V .

(iii) Follows immediately from (i) and (ii).

Corollary.

and

are finite-dimensional vector spaces over

and

U → V

is an isomorphism, then dim U = dim V .

Note that we restrict it to finite-dimensional spaces since we’ve only shown

that dimensions are well-defined for finite dimensional spaces. Otherwise, the

proof works just fine for infinite dimensional spaces.

Proof.

Let

be a basis for

. Then

(

) is a basis for

. Since

is injective,

|S| = |α(S)|. So done.

How about the other way round? If two vector spaces have the same di-

mension, are they necessarily isomorphic? The answer is yes, at least for

finite-dimensional ones.

However, we will not just prove that they are isomorphic. We will show that

they are isomorphic in many ways.

Proposition.

Suppose

is a

-vector space of dimension

n < ∞

. Then writing

, ··· , e

for the standard basis of F

, there is a bijection

Φ : {isomorphisms F

→ V } → {(ordered) basis(v

, ··· , v

) for V },

defined by

α 7→ (α(e

), ··· , α(e

)).

Proof.

We first make sure this is indeed a function — if

is an isomorphism,

then from our previous proposition, we know that it sends a basis to a basis. So

(α(e

), ··· , α(e

)) is indeed a basis for V .

We now have to prove surjectivity and injectivity.

Suppose

α, β

→ V

are isomorphism such that Φ(

) = Φ(

). In other

words, α(e

) = β(e

) for all i. We want to show that α = β. We have

























= α

i=1

α(e

) =

β(e

) = β

























Hence α = β.

Next, suppose that (v

, ··· , v

) is an ordered basis for V . Then define

























It is easy to check that this is well-defined and linear. We also know that

injective since (

, ··· , v

) is linearly independent. So if

, then

. Also,

is surjective since (

, ··· , v

) spans

. So

is an isomorphism,

and by construction Φ(α) = (v

, ··· , v

2.2 Linear maps and matrices

Recall that our first example of linear maps is matrices acting on

. We will

show that in fact, all linear maps come from matrices. Since we know that all

vector spaces are isomorphic to

, this means we can represent arbitrary linear

maps on vector spaces by matrices.

This is a useful result, since it is sometimes easier to argue about matrices

than linear maps.

Proposition.

Suppose

U, V

are vector spaces over

and

, ··· , e

}

is a

basis for

. Then every function

S → V

extends uniquely to a linear map

U → V .

The slogan is “to define a linear map, it suffices to define its values on a

basis”.

Proof.

For uniqueness, first suppose

α, β

U → V

are linear and extend

S →

V . We have sort-of proved this already just now.

If u ∈ U, we can write u =

i=1

with u

∈ F since S spans. Then

α(u) = α





α(e

) =

f(e

Similarly,

β(u) =

f(e

So α(u) = β(u) for every u. So α = β.

For existence, if

u ∈ U

, we can write

in a unique way. So defining

α(u) =

f(e

)

is unambiguous. To show linearity, let λ, µ ∈ F, u, v ∈ U. Then

α(λu + µv) = α



(λu

+ µv



(λu

+ µv

)f(e

)

= λ



f(e

)



+ µ



f(e

)



= λα(u) + µα(v).

Moreover, α does extend f.

Corollary.

and

are finite-dimensional vector spaces over

with bases

, ··· , e

) and (f

, ··· , f

) respectively, then there is a bijection

Mat

n,m

(F) → L(U, V ),

sending A to the unique linear map α such that α(e

) =

We can interpret this as follows: the

th column of

tells us how to write

α(e

) in terms of the f

We can also draw a fancy diagram to display this result. Given a basis

, ··· , e

, by our bijection, we get an isomorphism

(

) :

U → F

. Similarly,

we get an isomorphism s(f

) : V → F

Since a matrix is a linear map

→ F

, given a matrix

, we can

produce a linear map α : U → V via the following composition

U F

s(e

)

s(f

)

−1

We can put this into a square:

U V

s(e

)

s(f

)

Then the corollary tells us that every

gives rise to an

, and every

corresponds

to an A that fit into this diagram.

Proof.

is a linear map

U → V

, then for each 1

≤ i ≤ m

, we can write

(

)

uniquely as

α(e

) =

j=1

for some

∈ F

. This gives a matrix

= (

). The previous proposition tells

us that every matrix A arises in this way, and α is determined by A.

Definition

(Matrix representation)

We call the matrix corresponding to a

linear map

α ∈ L

(

U, V

) under the corollary the matrix representing

with

respect to the bases (e

, ··· , e

) and (f

, ··· , f

It is an exercise to show that the bijection

Mat

n,m

(

)

→ L

(

U, V

) is an iso-

morphism of the vector spaces and deduce that

dim L

(

U, V

) = (

dim U

)(

dim V

Proposition.

Suppose

U, V, W

are finite-dimensional vector spaces over

with

bases R = (u

, ··· , u

) , S = (v

, .., v

) and T = (w

, ··· , w

) respectively.

U → V

and

V → W

are linear maps represented by

and

respectively (with respect to

and

), then

βα

is linear and represented by

BA with respect to R and T .

U V W

A B

s(R)

s(S)

s(T )

Proof.

Verifying

βα

is linear is straightforward. Next we write

βα

(

) as a linear

combination of w

, ··· , w

βα(u

) = β

β(v

)

(BA)

2.3 The first isomorphism theorem and the rank-nullity

theorem

The main theorem of this section is the rank-nullity theorem, which relates the

dimensions of the kernel and image of a linear map. This is in fact an easy

corollary of a stronger result, known as the first isomorphism theorem, which

directly relates the kernel and image themselves. This first isomorphism is an

exact analogy of that for groups, and should not be unfamiliar. We will also

provide another proof that does not involve quotients.

Theorem

(First isomorphism theorem)

Let

U → V

be a linear map. Then

ker α

and

im α

are subspaces of

and

respectively. Moreover,

induces an

isomorphism

¯α : U/ ker α → im α

(u + ker α) 7→ α(u)

Note that if we view a vector space as an abelian group, then this is exactly

the first isomorphism theorem of groups.

Proof. We know that 0 ∈ ker α and 0 ∈ im α.

Suppose u

, u

∈ ker α and λ

, λ

∈ F. Then

α(λ

+ λ

) = λ

α(u

) + λ

α(u

) = 0.

So λ

+ λ

∈ ker α. So ker α is a subspace.

Similarly, if

(

)

, α

(

)

∈ im α

, then

λα

(

) =

(

)

∈

im α. So im α is a subspace.

Now by the first isomorphism theorem of groups,

¯α

is a well-defined isomor-

phism of groups. So it remains to show that

¯α

is a linear map. Indeed, we

have

¯α(λ(u + ker α)) = α(λu) = λα(u) = λ(¯α(u + ker α)).

So ¯α is a linear map.

Definition

(Rank and nullity)

U → V

is a linear map between finite-

dimensional vector spaces over

(in fact we just need

to be finite-dimensional),

the rank of

is the number

(

) =

dim im α

. The nullity of

is the number

n(α) = dim ker α.

Corollary

(Rank-nullity theorem)

U → V

is a linear map and

finite-dimensional, then

r(α) + n(α) = dim U.

Proof.

By the first isomorphism theorem, we know that

U/ ker α

∼

im α

. So we

have

dim im α = dim(U/ ker α) = dim U − dim ker α.

So the result follows.

We can also prove this result without the first isomorphism theorem, and

say a bit more in the meantime.

Proposition.

U → V

is a linear map between finite-dimensional vector

spaces over

, then there are bases (

, ··· , e

) for

and (

, ··· , f

) for

such that α is represented by the matrix



0 0



where r = r(α) and I

is the r × r identity matrix.

In particular, r(α) + n(α) = dim U.

Proof.

Let

k+1

, ··· , e

be a basis for the kernel of

. Then we can extend this

to a basis of the (e

, ··· , e

Let

(

) for 1

≤ i ≤ k

. We now show that (

, ··· , f

) is a basis for

im α

(and thus

). We first show that it spans. Suppose

v ∈ im α

. Then we

have

v = α

i=1

for some λ

∈ F. By linearity, we can write this as

v =

i=1

α(e

) =

i=1

+ 0.

So v ∈ hf

, ··· , f

To show linear dependence, suppose that

i=1

= 0.

So we have

i=1

= 0.

i=1

∈ ker α. Since (e

k+1

, ··· , e

) is a basis for ker α, we can write

i=1

i=k+1

for some

(

+ 1

, ··· , m

). Since (

, ··· , e

) is a basis, we must have

= 0 for all i. So they are linearly independent.

Now we extend (f

, ··· , f

) to a basis for V , and

α(e

) =

(

1 ≤ i ≤ k

0 k + 1 ≤ i ≤ m

Example. Let

W = {x ∈ R

: x

+ x

= 0 = x

− x

What is dim W ? Well, it clearly is 3, but how can we prove it?

We can consider the map α : R

→ R

given by













7→



+ x

− x



Then

ker α

. So

dim W

= 5

− r

(

). We know that

0) = (1

and α(0, 0, 1, 0, 0) = (0, 1). So r(α) = dim im α = 2. So dim W = 3.

More generally, the rank-nullity theorem gives that

linear equations in

have a space of solutions of dimension at least n − m.

Example.

Suppose that

and

are subspaces of

, all of which are finite-

dimensional vector spaces of F. We let

α : U ⊕ W → V

(u, w) 7→ u + w,

where the ⊕ is the external direct sum. Then im α = U + W and

ker α = {(u, −u) : u ∈ U ∩ W }

∼

dim(U ∩ W ).

Then we have

dim U + dim W = dim(U ⊕ W ) = r(α) + n(α) = dim(U + W ) + dim(U ∩ W ).

This is a result we’ve previously obtained through fiddling with basis and horrible

stuff.

Corollary.

Suppose

U → V

is a linear map between vector spaces over

both of dimension n < ∞. Then the following are equivalent

(i) α is injective;

(ii) α is surjective;

(iii) α is an isomorphism.

Proof.

It is clear that, (iii) implies (i) and (ii), and (i) and (ii) together implies

(iii). So it suffices to show that (i) and (ii) are equivalent.

Note that

is injective iff

(

) = 0, and

is surjective iff

(

) =

dim V

By the rank-nullity theorem,

(

) +

(

) =

. So the result follows immediately.

Lemma.

Let

A ∈ M

n,n

(

) =

(

) be a square matrix. The following are

equivalent

(i) There exists B ∈ M

(F) such that BA = I

(ii) There exists C ∈ M

(F) such that AC = I

If these hold, then

. We call

invertible or non-singular, and write

−1

= B = C.

Proof.

Let

α, β, γ, ι

→ F

be the linear maps represented by matrices

A, B, C, I

respectively with respect to the standard basis.

We note that (i) is equivalent to saying that there exists

such that

βα

This is true iff

is injective, which is true iff

is an isomorphism, which is true

iff α has an inverse α

−1

Similarly, (ii) is equivalent to saying that there exists

such that

αγ

This is true iff

is injective, which is true iff

is isomorphism, which is true iff

α has an inverse α

−1

So these are the same things, and we have β = α

−1

= γ.

2.4 Change of basis

Suppose we have a linear map

U → V

. Given a basis

}

for

, and a basis

} for V , we can obtain a matrix A.

U V

) (f

)

We now want to consider what happens when we have two different basis

}

and

}

. These will then give rise to two different maps from

to our

space

, and the two basis can be related by a change-of-basis map

. We can

put them in the following diagram:

U U

) (e

)

where

is the identity map. If we perform a change of basis for both

and

we can stitch the diagrams together as

U U V V

U α

)

) (f

)

Then if we want a matrix representing the map

U → V

with respect to bases

) and (v

), we can write it as the composition

B = Q

−1

AP.

We can write this as a theorem:

Theorem.

Suppose that (

, ··· , e

) and (

, ··· , u

) are basis for a finite-

dimensional vector space

over

, and (

, ··· , f

) and (

, ··· , v

) are basis

of a finite-dimensional vector space V over F.

Let

U → V

be a linear map represented by a matrix

with respect to

) and (f

) and by B with respect to (u

) and (v

). Then

B = Q

−1

AP,

where P and Q are given by

k=1

, v

k=1

Note that one can view

as the matrix representing the identity map

from

with basis (

) to

with basis (

), and similarly for

. So both are

invertible.

Proof. On the one hand, we have

α(u

) =

j=1

[QB]

On the other hand, we can write

α(u

) = α

k=1

[AP ]

Since the f

are linearly independent, we conclude that

QB = AP.

Since Q is invertible, we get B = Q

−1

AP .

Definition

(Equivalent matrices)

We say

A, B ∈ Mat

n,m

(

) are equivalent if

there are invertible matrices

P ∈ Mat

(

Q ∈ Mat

(

) such that

−1

Since

(

) =

{A ∈ Mat

(

) :

A is invertible}

is a group, for each

k ≥

this is indeed an equivalence relation. The equivalence classes are orbits under

the action of GL

(F) × GL

(F), given by

(F) × GL

(F) × Mat

n,m

(F) → Mat(F)

(P, Q, A) 7→ QAP

−1

Two matrices are equivalent if and only if they represent the same linear map

with respect to different basis.

Corollary.

A ∈ Mat

n,m

(

), then there exists invertible matrices

P ∈

(F), Q ∈ GL

(F) so that

−1

AP =



0 0



for some 0 ≤ r ≤ min(m, n).

This is just a rephrasing of the proposition we had last time. But this tells

us there are min(m, n) + 1 orbits of the action above parametrized by r.

Definition (Column and row rank). If A ∈ Mat

n,m

(F), then

–

The column rank of

, written

(

), is the dimension of the subspace of

spanned by the columns of A.

–

The row rank of

, written

(

), is the dimension of the subspace of

spanned by the rows of A. Alternatively, it is the column rank of A

There is no a priori reason why these should be equal to each other. However,

it turns out they are always equal.

Note that if

→ F

is the linear map represented by

(with respect to

the standard basis), then

(

) =

(

), i.e. the column rank is the rank. Moreover,

since the rank of a map is independent of the basis, equivalent matrices have

the same column rank.

Theorem.

A ∈ Mat

n,m

(

), then

(

) =

(

), i.e. the row rank is equivalent

to the column rank.

Proof. We know that there are some invertible P, Q such that

−1

AP =



0 0



where r = r(A). We can transpose this whole equation to obtain

−1

AP )

= P

)

−1



0 0



So r(A

) = r.

2.5 Elementary matrix operations

We are now going to re-prove our corollary that we can find

P, Q

such that

−1



0 0



in a way that involves matrices only. This will give a

concrete way to find P and Q, but is less elegant.

To do so, we need to introduce elementary matrices.

Definition

(Elementary matrices)

We call the following matrices of

(

)

elementary matrices:







0 1

1 0







This is called a reflection, where the rows we changed are the ith and jth row.

(λ) =







1 λ







This is called a shear, where λ appears at the i, jth entry.

(λ) =













This is called a shear, where λ 6= 0 appears at the ith column.

Observe that if A is a m × n matrix, then

(i) AS

is obtained from A by swapping the i and j columns.

(ii) AE

(λ) is obtained by adding λ× column i to column j.

(iii) AT

(λ) is obtained from A by rescaling the ith column by λ.

Multiplying on the left instead of the right would result in the same operations

performed on the rows instead of the columns.

Proposition.

A ∈ Mat

n,m

(

), then there exists invertible matrices

P ∈

(F), Q ∈ GL

(F) so that

−1

AP =



0 0



for some 0 ≤ r ≤ min(m, n).

We are going to start with

, and then apply these operations to get it into

this form.

Proof.

We claim that there are elementary matrices

, ··· , E

and

, ··· , F

(these E are not necessarily the shears, but any elementary matrix) such that

···E

···F



0 0



This suffices since the

∈ GL

(

) and

∈ GL

(

). Moreover, to prove the

claim, it suffices to find a sequence of elementary row and column operations

reducing A to this form.

= 0, then done. If not, there is some

i, j

such that

= 0. By swapping

row 1 and row

; and then column 1 and column

, we can assume

= 0. By

rescaling row 1 by

, we can further assume A

= 1.

Now we can add

−A

times column 1 to column

for each

j 6

= 1, and then

add −A

times row 1 to row i 6= 1. Then we now have

A =







1 0 ··· 0

. B







Now

is smaller than

. So by induction on the size of

, we can reduce

a matrix of the required form, so done.

It is an exercise to show that the row and column operations do not change

the row rank or column rank, and deduce that they are equal.

3 Duality

Duality is a principle we will find throughout mathematics. For example, in IB

Optimisation, we considered the dual problems of linear programs. Here we will

look for the dual of vector spaces. In general, we try to look at our question in a

“mirror” and hope that the mirror problem is easier to solve than the original

mirror.

At first, the definition of the dual might see a bit arbitrary and weird. We

will try to motivate it using what we will call annihilators, but they are much

more useful than just for these. Despite their usefulness, though, they can be

confusing to work with at times, since the dual space of a vector space

will be

constructed by considering linear maps on

, and when we work with maps on

dual spaces, things explode.

3.1 Dual space

To specify a subspace of

, we can write down linear equations that its elements

satisfy. For example, if we have the subspace









i ⊆ F

, we can specify

this by saying









∈ U if and only if

− x

= 0

− x

= 0.

However, characterizing a space in terms of equations involves picking some

particular equations out of the many possibilities. In general, we do not like

making arbitrary choices. Hence the solution is to consider all possible such

equations. We will show that these form a subspace in some space.

We can interpret these equations in terms of linear maps

→ F

. For

example

− x

= 0 if and only if









∈ ker θ

, where

→ F

is defined









7→ x

− x

This works well with the vector space operations. If

, θ

→ F

vanish on

some subspace of

, and

λ, µ ∈ F

, then

λθ

µθ

also vanishes on the subspace.

So the set of all maps F

→ F that vanishes on U forms a vector space.

To formalize this notion, we introduce dual spaces.

Definition

(Dual space)

Let

be a vector space over

. The dual of

defined as

∗

= L(V, F) = {θ : V → F : θ linear}.

Elements of V

∗

are called linear functionals or linear forms.

By convention, we use Roman letters for elements in

, and Greek letters

for elements in V

∗

Example.

– If V = R

and θ : V → R that sends









7→ x

− x

, then θ ∈ V

∗

–

Let

. Then for any fixed

V → F

defined by

f 7→ f

(

) is in

∗

– Let V = C([0, 1], R). Then f 7→

f(t) dt ∈ V

∗

– The trace tr : M

(F) → F defined by A 7→

i=1

is in M

(F)

∗

It turns out it is rather easy to specify how the dual space looks like, at least

in the case where V is finite dimensional.

Lemma.

is a finite-dimensional vector space over

with basis (

, ··· , e

then there is a basis (

, ··· , ε

) for

∗

(called the dual basis to (

, ··· , e

))

such that

) = δ

Proof.

Since linear maps are characterized by their values on a basis, there exists

unique choices for ε

, ··· , ε

∈ V

∗

. Now we show that (ε

, ··· , ε

) is a basis.

Suppose

θ ∈ V

∗

. We show that we can write it uniquely as a combination of

, ··· , ε

. We have

i=1

if and only if

(

) =

i=1

(

) (for all

j) if and only if λ

= θ(e

). So we have uniqueness and existence.

Corollary. If V is finite dimensional, then dim V = dim V

∗

When

is not finite dimensional, this need not be true. However, we

know that the dimension of

∗

is at least as big as that of

, since the above

gives a set of

dim V

many independent vectors in

∗

. In fact for any infinite

dimensional vector space,

dim V

∗

is strictly larger than

dim V

, if we manage to

define dimensions for infinite-dimensional vector spaces.

It helps to come up with a more concrete example of how dual spaces look

like. Consider the vector space

, where we treat each element as a column

vector (with respect to the standard basis). Then we can regard elements of

∗

as just row vectors (

, ··· , a

) =

j=1

with respect to the dual basis. We

have





i,j

i=1



··· a















This is exactly what we want.

Now what happens when we change basis? How will the dual basis change?

Proposition.

Let

be a finite-dimensional vector space over

with bases

, ··· , e

) and (f

, ··· , f

), and that P is the change of basis matrix so that

k=1

Let (ε

, ··· , ε

) and (η

, ··· , η

) be the corresponding dual bases so that

) = δ

= η

Then the change of basis matrix from (

, ··· , ε

) to (

, ··· , η

) is (

−1

)

, i.e.

`=1

Proof. For convenience, write Q = P

−1

so that

k=1

So we can compute

`=1

) =

`=1

k=1

k,`

= [P Q]

= δ

So ε

`=1

Now we’ll return to our original motivation, and think how we can define

subspaces of V

∗

in terms of subspaces of V , and vice versa.

Definition (Annihilator). Let U ⊆ V . Then the annihilator of U is

= {θ ∈ V

∗

: θ(u) = 0, ∀u ∈ U}.

If W ⊆ V

∗

, then the annihilator of W is

= {v ∈ V : θ(v) = 0, ∀θ ∈ W }.

One might object that

should be a subset of

∗∗

and not

. We will

later show that there is a canonical isomorphism between

∗∗

and

, and this

will all make sense.

Example.

Consider

with standard basis

, e

; (

)

∗

with dual basis

(

, ε

). If

+ 2

and

hε

− ε

, then

and W

= U.

We see that the dimension of

and

add up to three, which is the

dimension of R

. This is typical.

Proposition. Let V be a vector space over F and U a subspace. Then

dim U + dim U

= dim V.

We are going to prove this in many ways.

Proof.

Let (

, ··· , e

) be a basis for

and extend to (

, ··· , e

) a basis for

V . Consider the dual basis for V

∗

, say (ε

, ··· , ε

). Then we will show that

= hε

k+1

, ··· , ε

dim U

n −k

as required. This is easy to prove — if

j > k

, then

(

) = 0

for all

i ≤ k

. So

k+1

, ··· , ε

∈ U

. On the other hand, suppose

θ ∈ U

. Then

we can write

θ =

j=1

But then 0 = θ(e

) = λ

for i ≤ k. So done.

Proof.

Consider the restriction map

∗

→ U

∗

, given by

θ 7→ θ|

. This is

obviously linear. Since every linear map

U → F

can be extended to

V → F

, this

is a surjection. Moreover, the kernel is U

. So by rank-nullity theorem,

dim V

∗

= dim U

+ dim U

∗

Since dim V

∗

= dim V and dim U

∗

= dim U, we’re done.

Proof.

We can show that

(

V/U

)

∗

, and then deduce the result. Details are

left as an exercise.

3.2 Dual maps

Since linear algebra is the study of vector spaces and linear maps between them,

after dualizing vector spaces, we should be able to dualize linear maps as well.

If we have a map

V → W

, then after dualizing, the map will go the other

direction, i.e.

∗

→ V

∗

. This is a characteristic common to most dualization

processes in mathematics.

Definition

(Dual map)

Let

V, W

be vector spaces over

and

V → W ∈

(

V, W

). The dual map to

, written

∗

→ V

∗

is given by

θ 7→ θ ◦ α

Since the composite of linear maps is linear,

∗

(

)

∈ V

∗

. So this is a genuine

map.

Proposition.

Let

α ∈ L

(

V, W

) be a linear map. Then

∗

∈ L

(

∗

, V

∗

) is a

linear map.

This is not the same as what we remarked at the end of the definition of

the dual map. What we remarked was that given any

∗

(

) is a linear map.

What we want to show here is that α

∗

itself as a map W

∗

→ V

∗

is linear.

Proof. Let λ, µ ∈ F and θ

, θ

∈ W

∗

. We want to show

∗

(λθ

+ µθ

) = λα

∗

(θ

) + µα

∗

(θ

To show this, we show that for every

v ∈ V

, the left and right give the same

result. We have

∗

(λθ

+ µθ

)(v) = (λθ

+ µθ

)(αv)

= λθ

(α(v)) + µθ

(α(v))

= (λα

∗

(θ

) + µα

∗

(θ

))(v).

So α

∗

∈ L(W

∗

, V

∗

What happens to the matrices when we take the dual map? The answer is

that we get the transpose.

Proposition.

Let

V, W

be finite-dimensional vector spaces over

and

V →

be a linear map. Let (

, ··· , e

) be a basis for

and (

, ··· , f

) be a basis

for W ; (ε

, ··· , ε

) and (η

, ··· , η

) the corresponding dual bases.

Suppose

is represented by

with respect to (

) and (

) for

and

Then α

∗

is represented by A

with respect to the corresponding dual bases.

Proof. We are given that

α(e

) =

k=1

We must compute α

∗

(η

). To do so, we evaluate it at e

. We have

∗

(η

)(e

) = η

(α(e

)) = η

k=1

= A

We can also write this as

∗

(η

)(e

) =

k=1

Since this is true for all j, we have

∗

(η

)

k=1

So done.

Note that if α : U → V and β : V → W , θ ∈ W

∗

, then

(βα)

∗

(θ) = θβα = α

∗

(θβ) = α

∗

(β

∗

(θ)).

So we have (

βα

)

∗

. This is obviously true for the finite-dimensional case,

since that’s how transposes of matrices work.

Similarly, if α, β : U → V , then (λα + µβ)

∗

= λα

∗

+ µβ

∗

What happens when we change basis? If

−1

for some invertible

and Q, then

= (Q

−1

AP )

= P

−1

)

= ((P

−1

)

−1

)

So in the dual space, we conjugate by the dual of the change-of-basis matrices.

As we said, we can use dualization to translate problems about a vector space

to its dual. The following lemma gives us some good tools to do so:

Lemma.

Let

α ∈ L

(

V, W

) with

V, W

finite dimensional vector spaces over

Then

(i) ker α

∗

= (im α)

(ii) r

(

) =

(

∗

) (which is another proof that row rank is equal to column

rank).

(iii) im α

∗

= (ker α)

At first sight, (i) and (iii) look quite similar. However, (i) is almost trivial to

prove, but (iii) is rather hard.

Proof.

(i) If θ ∈ W

∗

, then

θ ∈ ker α

∗

⇔ α

∗

(θ) = 0

⇔ (∀v ∈ V ) θα(v) = 0

⇔ (∀w ∈ im α) θ(w) = 0

⇔ θ ∈ (im α)

(ii) As im α ≤ W , we’ve seen that

dim im α + dim(im α)

= dim W.

Using (i), we see

n(α

∗

) = dim(im α)

r(α) + n(α

∗

) = dim W = dim W

∗

By the rank-nullity theorem, we have r(α) = r(α

∗

(iii)

The proof in (i) doesn’t quite work here. We can only show that one

includes the other. To draw the conclusion, we will show that the two

spaces have the dimensions, and hence must be equal.

Let θ ∈ im α

∗

. Then θ = φα for some φ ∈ W

∗

. If v ∈ ker α, then

θ(v) = φ(α(v)) = φ(0) = 0.

So im α

∗

⊆ (ker α)

But we know

dim(ker α)

+ dim ker α = dim V,

So we have

dim(ker α)

= dim V − n(α) = r(α) = r(α

∗

) = dim im α

∗

Hence we must have im α

∗

= (ker α)

Not only do we want to get from

∗

, we want to get back from

∗

We can take the dual of

∗

to get a

∗∗

. We already know that

∗∗

is isomorphic

, since

∗

is isomorphic to

already. However, the isomorphism between

∗

and

are not “natural”. To define such an isomorphism, we needed to pick

a basis for

and consider a dual basis. If we picked a different basis, we would

get a different isomorphism. There is no natural, canonical, uniquely-defined

isomorphism between V and V

∗

However, this is not the case when we want to construct an isomorphism

V → V

∗∗

. The construction of this isomorphism is obvious once we think hard

what

∗∗

actually means. Unwrapping the definition, we know

∗∗

(

∗

, F

Our isomorphism has to produce something in

∗∗

given any

v ∈ V

. This is

equivalent to saying given any

v ∈ V

and a function

θ ∈ V

∗

, produce something

in F.

This is easy, by definition

θ ∈ V

∗

is just a linear map

V → F

. So given

and θ, we just return θ(v). We now just have to show that this is linear and is

bijective.

Lemma.

Let

be a vector space over

. Then there is a linear map

V →

∗

)

∗

given by

ev(v)(θ) = θ(v).

We call this the evaluation map.

We call this a “canonical” map since this does not require picking a particular

basis of the vector spaces. It is in some sense a “natural” map.

Proof.

We first show that

(

)

∈ V

∗∗

for all

v ∈ V

, i.e.

(

) is linear for any

v. For any λ, µ ∈ F, θ

, θ

∈ V

∗

, then for v ∈ V , we have

ev(v)(λθ

+ µθ

) = (λθ

+ µθ

)(v)

= λθ

(v) + µθ

(v)

= λ ev(v)(θ

) + µ ev(v)(θ

So done. Now we show that

itself is linear. Let

λ, µ ∈ F

, v

∈ V

. We

want to show

ev(λv

+ µv

) = λ ev(v

) + µ ev(v

To show these are equal, pick θ ∈ V

∗

. Then

ev(λv

+ µv

)(θ) = θ(λv

+ µv

)

= λθ(v

) + µθ(v

)

= λ ev(v

)(θ) + µ ev(v

)(θ)

= (λ ev(v

) + µ ev(v

))(θ).

So done.

In the special case where V is finite-dimensional, this is an isomorphism.

Lemma. If V is finite-dimensional, then ev : V → V

∗∗

is an isomorphism.

This is very false for infinite dimensional spaces. In fact, this is true only

for finite-dimensional vector spaces (assuming the axiom of choice), and some

(weird) people use this as the definition of finite-dimensional vector spaces.

Proof.

We first show it is injective. Suppose

(

) =

for some

v ∈ V

. Then

(

) =

(

)(

) = 0 for all

θ ∈ V

∗

. So

dimhvi

dim V

∗

dim V

. So

dimhvi

= 0. So

is injective. Since

and

∗∗

have the same

dimension, this is also surjective. So done.

From now on, we will just pretend that

and

∗∗

are the same thing, at

least when V is finite dimensional.

Note that this lemma does not just say that

is isomorphic to

∗∗

(we

already know that since they have the same dimension). This says there is a

completely canonical way to choose the isomorphism.

In general, if

is infinite dimensional, then

is injective, but not surjective.

So we can think of V as a subspace of V

∗∗

in a canonical way.

Lemma.

Let

V, W

be finite-dimensional vector spaces over

after identifying

(V and V

∗∗

) and (W and W

∗∗

) by the evaluation map. Then we have

(i) If U ≤ V , then U

= U.

(ii) If α ∈ L(V, W ), then α

∗∗

= α.

Proof.

(i)

Let

u ∈ U

. Then

(

) =

(

) = 0 for all

θ ∈ U

. So

annihilates

everything in U

. So u ∈ U

. So U ⊆ U

. We also know that

dim U = dim V − dim U

= dim V − (dim V −dim U

) = dim U

So we must have U = U

(ii)

The proof of this is basically — the transpose of the transpose is the

original matrix. The only work we have to do is to show that the dual of

the dual basis is the original basis.

Let (

, ··· , e

) be a basis for

and (

, ··· , f

) be a basis for

, and let

(

, ··· , ε

) and (

, ··· , η

) be the corresponding dual basis. We know

that

(ε

) = δ

= ε

), f

(η

) = δ

= η

So (e

, ··· , e

) is dual to (ε

, ··· , ε

), and similarly for f and η.

is represented by

, then

∗

is represented by

. So

∗∗

is represented

by (A

)

= A. So done.

Proposition.

Let

be a finite-dimensional vector space

and

are

subspaces of V . Then we have

(i) (U

+ U

)

= U

∩ U

(ii) (U

∩ U

)

= U

+ U

Proof.

(i) Suppose θ ∈ V

∗

. Then

θ ∈ (U

+ U

)

⇔ θ(u

+ u

) = 0 for all u

∈ U

⇔ θ(u) = 0 for all u ∈ U

∪ U

⇔ θ ∈ U

∩ U

(ii) We have

∩ U

)

= ((U

)

∩ (U

)

= (U

+ U

)

= U

+ U

So done.

4 Bilinear forms I

So far, we have been looking at linear things only. This can get quite boring.

For a change, we look at bilinear maps instead. In this chapter, we will look at

bilinear forms in general. It turns out there isn’t much we can say about them,

and hence this chapter is rather short. Later, in Chapter 7, we will study some

special kinds of bilinear forms which are more interesting.

Definition

(Bilinear form)

Let

V, W

be vector spaces over

. Then a function

V × W → F

is a bilinear form if it is linear in each variable, i.e. for each

v ∈ V , φ(v, ·) : W → F is linear; for each w ∈ W , φ( ·, w) : V → F is linear.

Example. The map defined by

V × V

∗

→ F

(v, θ) 7→ θ(v) = ev(v)(θ)

is a bilinear form.

Example.

Let

. Then the function (

v, w

) =

i=1

is bilinear.

Example. If V = W = C([0, 1], R), then

(f, g) 7→

fg dt

is a bilinear form.

Example. Let A ∈ Mat

m,n

(F). Then

φ : F

× F

→ F

(v, w) 7→ v

is bilinear. Note that the (real) dot product is the special case of this, where

n = m and A = I.

In fact, this is the most general form of bilinear forms on finite-dimensional

vector spaces.

Definition

(Matrix representing bilinear form)

Let (

, ··· , e

) be a basis for

and (

, ··· , f

) be a basis for

, and

V × W → F

. Then the matrix

representing ψ with respect to the basis is defined to be

= ψ(e

, f

Note that if v =

and w =

, then by linearity, we get

ψ(v, w) = ψ



, w



ψ(e

, w)





i,j

ψ(e

, f

)

= λ

Aµ.

So ψ is determined by A.

We have identified linear maps with matrices, and we have identified bilinear

maps with matrices. However, you shouldn’t think linear maps are bilinear maps.

They are, obviously, two different things. In fact, the matrices representing

matrices and bilinear forms transform differently when we change basis.

Proposition.

Suppose (

, ··· , e

) and (

, ··· , v

) are basis for

such that

for all i = 1, ··· , n;

and (f

, ··· , f

) and (w

, ··· , w

) are bases for W such that

for all j = 1, ··· , m.

Let

V × W → F

be a bilinear form represented by

with respect to

(

, ··· , e

) and (

, ··· , f

), and by

with respect to the bases (

, ··· , v

)

and (w

, ··· , w

). Then

B = P

AQ.

The difference with the transformation laws of matrices is this time we are

taking transposes, not inverses.

Proof. We have

= φ(v

, w

)

= φ





φ(e

, f

)

k,`

= (P

AQ)

Note that while the transformation laws for bilinear forms and linear maps

are different, we still get that two matrices are representing the same bilinear

form with respect to different bases if and only if they are equivalent, since if

B = P

−1

AQ, then B = ((P

−1

)

AQ.

If we are given a bilinear form

V ×W → F

, we immediately get two linear

maps:

: V → W

∗

, ψ

: W → V

∗

defined by ψ

(v) = ψ(v, ·) and ψ

(w) = ψ( ·, w).

For example, if

V × V

∗

→ F

, is defined by (

v, θ

)

7→ θ

(

), then

V →

∗∗

is the evaluation map. On the other hand,

∗

→ V

∗

is the identity

map.

Lemma.

Let (

, ··· , ε

) be a basis for

∗

dual to (

, ··· , e

) of

; (

, ··· , η

)

be a basis for W

∗

dual to (f

, ··· , f

) of W .

represents

with respect to (

, ··· , e

) and (

, ··· , f

), then

also

represents

with respect to (

, ··· , f

) and (

, ··· , ε

); and

represents

with respect to (e

, ··· , e

) and (η

, ··· , η

Proof. We just have to compute

)(f

) = A





So we get

) =

So A

represents ψ

We also have

)(e

) = A

) =

Definition

(Left and right kernel)

The kernel of

is left kernel of

, while

the kernel of ψ

is the right kernel of ψ.

Then by definition, v is in the left kernel if ψ(v, w) = 0 for all w ∈ W .

More generally, if T ⊆ V , then we write

⊥

= {w ∈ W : ψ(t, w) = 0 for all t ∈ T }.

Similarly, if U ⊆ W , then we write

⊥

U = {v ∈ V : ψ(v, u) = 0 for all u ∈ U}.

In particular, V

⊥

= ker ψ

and

⊥

W = ker ψ

If we have a non-trivial left (or right) kernel, then in some sense, some

elements in V (or W ) are “useless”, and we don’t like these.

Definition

(Non-degenerate bilinear form)

. ψ

is non-degenerate if the left and

right kernels are both trivial. We say ψ is degenerate otherwise.

Definition

(Rank of bilinear form)

V → W

is a bilinear form

on a

finite-dimensional vector space

, then the rank of

is the rank of any matrix

representing

. This is well-defined since

(

) =

(

) if

and

are

invertible.

Alternatively, it is the rank of ψ

(or ψ

Lemma.

Let

and

be finite-dimensional vector spaces over

with bases

, ··· , e

) and (f

, ··· , f

) be their basis respectively.

Let

V ×W → F

be a bilinear form represented by

with respect to these

bases. Then

is non-degenerate if and only if

is (square and) invertible. In

particular, V and W have the same dimension.

We can understand this as saying if there are too many things in

(or

then some of them are bound to be useless.

Proof.

Since

and

are represented by

and

(in some order), they both

have trivial kernel if and only if

(

) =

(

) = 0. So we need

(

) =

dim V

and

(

) =

dim W

. So we need

dim V

dim W

and

have full rank, i.e. the

corresponding linear map is bijective. So done.

Example. The map

× F

→ F









7→ ad − bc

is a bilinear form. This, obviously, corresponds to the determinant of a 2-by-2

matrix. We have ψ(v, w) = −ψ(w, v) for all v, w ∈ F

5 Determinants of matrices

We probably all know what the determinant is. Here we are going to give a

slightly more abstract definition, and spend quite a lot of time trying motivate

this definition.

Recall that

is the group of permutations of

{

, ··· , n}

, and there is a

unique group homomorphism

→ {±

}

such that

(

) = 1 if

can be

written as a product of an even number of transpositions;

(

) =

−

1 if

can be

written as an odd number of transpositions. It is proved in IA Groups that this

is well-defined.

Definition (Determinant). Let A ∈ Mat

n,n

(F). Its determinant is

det A =

σ∈S

ε(σ)

i=1

iσ(i)

This is a big scary definition. Hence, we will spend the first half of the

chapter trying to understand what this really means, and how it behaves. We

will eventually prove a formula that is useful for computing the determinant,

which is probably how you were first exposed to the determinant.

Example. If n = 2, then S

= {id, (1 2)}. So

det A = A

− A

When n = 3, then S

has 6 elements, and

det A = A

+ A

− A

We will first prove a few easy and useful lemmas about the determinant.

Lemma. det A = det A

Proof.

det A

σ∈S

ε(σ)

i=1

σ(i)i

σ∈S

ε(σ)

j=1

jσ

−1

(j)

τ ∈S

ε(τ

−1

)

j=1

jτ (j)

Since ε(τ ) = ε(τ

−1

), we get

τ ∈S

ε(τ)

j=1

jτ (j)

= det A.

Lemma. If A is an upper triangular matrix, i.e.

A =







··· a

0 a

··· a

0 0 ··· a







Then

det A =

i=1

Proof. We have

det A =

σ∈S

ε(σ)

i=1

iσ( i)

But A

iσ( i)

= 0 whenever i > σ(i). So

i=1

iσ( i)

= 0

if there is some i ∈ {1, ··· , n} such that i > σ(i).

However, the only permutation in which

i ≤ σ

(

) for all

is the identity. So

the only thing that contributes in the sum is σ = id. So

det A =

i=1

To motivate this definition, we need a notion of volume. How can we define

volume on a vector space? It should be clear that the “volume” cannot be

uniquely determined, since it depends on what units we are using. For example,

saying the volume is “1” is meaningless unless we provide the units, e.g.

So we have an axiomatic definition for what it means for something to denote a

“volume”.

Definition

(Volume form)

A volume form on

is a function

×···×F

→

F that is

(i) Multilinear, i.e. for all i and all v

, ··· , v

i−1

, v

i+1

, ··· , v

∈ F

, we have

d(v

, ··· , v

i−1

, ·, v

i+1

, ··· , v

) ∈ (F

)

∗

(ii) Alternating, i.e. if v

= v

for some i 6= j, then

d(v

, ··· , v

) = 0.

We should think of

(

, ··· , v

) as the

-dimensional volume of the paral-

lelopiped spanned by v

, ··· , v

We can view

A ∈ Mat

(

) as

-many vectors in

by considering its columns

A = (A

(1)

(2)

··· A

(n)

), with A

(i)

∈ F

. Then we have

Lemma. det A is a volume form.

Proof. To see that det is multilinear, it is sufficient to show that each

i=1

iσ(i)

is multilinear for all

σ ∈ S

, since linear combinations of multilinear forms are

multilinear. But each such product is contains precisely one entry from each

column, and so is multilinear.

To show it is alternating, suppose now there are some

k, `

distinct such that

(k)

(`)

. We let

be the transposition (

k `

). By Lagrange’s theorem, we

can write

= A

q τ A

where A

= ker ε and q is the disjoint union. We also know that

σ∈A

i=1

iσ( i)

σ∈A

i=1

i,τ σ(i)

since if

(

) is not

, then

does nothing; if

(

) is

, then

just swaps

them around, but A

(k)

= A

(l)

. So we get

σ∈A

i=1

iσ(i)

∈τ A

i=1

iσ

(i)

But we know that

det A = LHS − RHS = 0.

So done.

We have shown that determinants are volume forms, but is this the only

volume form? Well obviously not, since 2

det A

is also a valid volume form.

However, in some sense, all volume forms are “derived” from the determinant.

Before we show that, we need the following

Lemma.

Let

be a volume form on

. Then swapping two entries changes

the sign, i.e.

d(v

, ··· , v

) = −d(v

, ··· , v

Proof. By linearity, we have

0 = d(v

, ··· , v

+ v

, ··· , v

+ v

, ··· , v

)

= d(v

, ··· , v

)

+ d(v

, ··· , v

)

+ d(v

, ··· , v

)

+ d(v

, ··· , v

)

= d(v

, ··· , v

)

+ d(v

, ··· , v

So done.

Corollary. If σ ∈ S

, then

d(v

σ(1)

, ··· , v

σ(n)

) = ε(σ)d(v

, ··· , v

)

for any v

∈ F

Theorem.

Let

be any volume form on

, and let

= (

(1)

··· A

(n)

)

∈

Mat

(F). Then

d(A

(1)

, ··· , A

(n)

) = (det A)d(e

, ··· , e

where {e

, ··· , e

} is the standard basis.

Proof. We can compute

d(A

(1)

, ··· , A

(n)

) = d

i=1

, A

(2)

, ··· , A

(n)

i=1

d(e

, A

(2)

, ··· , A

(n)

)

i,j=1

d(e

, e

, A

(3)

, ··· , A

(n)

)

,··· ,i

d(e

, ··· , e

)

j=1

We know that lots of these are zero, since if

for some

k, j

, then the term

is zero. So we are just summing over distinct tuples, i.e. when there is some

such that i

= σ(j). So we get

d(A

(1)

, ··· , A

(n)

) =

σ∈S

d(e

σ(1)

, ··· , e

σ(n)

)

j=1

σ(j)j

However, by our corollary up there, this is just

d(A

(1)

, ··· , A

(n)

) =

σ∈S

ε(σ)d(e

, ··· , e

)

j=1

σ(j)j

= (det A)d(e

, ··· , e

So done.

We can rewrite the formula as

d(Ae

, ··· , Ae

) = (det A)d(e

, ··· , e

It is not hard to see that the same proof gives for any v

, ··· , v

, we have

d(Av

, ··· , Av

) = (det A)d(v

, ··· , v

So we know that

det A

is the volume rescaling factor of an arbitrary parallelopiped,

and this is true for any volume form d.

Theorem. Let A, B ∈ Mat

(F). Then det(AB) = det(A) det(B).

Proof.

Let

be a non-zero volume form on

(e.g. the “determinant”). Then

we can compute

d(ABe

, ··· , ABe

) = (det AB)d(e

, ··· , e

but we also have

d(ABe

, ··· , ABe

) = (det A)d(Be

, ··· , Be

) = (det A)(det B)d(e

, ··· , e

Since d is non-zero, we must have det AB = det A det B.

Corollary.

A ∈ Mat

(

) is invertible, then

det A 6

= 0. In fact, when

invertible, then det(A

−1

) = (det A)

−1

Proof. We have

1 = det I = det(AA

−1

) = det A det A

−1

So done.

Definition

(Singular matrices)

A matrix

is singular if

det A

= 0. Otherwise,

it is non-singular.

We have just shown that if

det A

= 0, then

is not invertible. Is the converse

true? If

det A 6

= 0, then can we conclude that

is invertible? The answer is

yes. We are now going to prove it in an abstract and clean way. We will later

prove this fact again by constructing an explicit formula for the inverse, which

involves dividing by the determinant. So if the determinant is non-zero, then we

know an inverse exists.

Theorem. Let A ∈ Mat

(F). Then the following are equivalent:

(i) A is invertible.

(ii) det A 6= 0.

(iii) r(A) = n.

Proof.

We have proved that (i)

⇒

(ii) above, and the rank-nullity theorem implies

(iii)

⇒

(i). We will prove (ii)

⇒

(iii). In fact we will show the contrapositive.

Suppose

(

)

< n

. By rank-nullity theorem,

(

)

0. So there is some

x =













such that Ax = 0. Suppose λ

6= 0. We define B as follows:

B =







1 λ

k−1

k+1







has the

th column identically zero. So

det

(

) = 0. So it is sufficient

to prove that det(B) 6= 0. But det B = λ

6= 0. So done.

We are now going to come up with an alternative formula for the determinant

(which is probably the one you are familiar with). To do so, we introduce the

following notation:

Notation.

Write

for the matrix obtained from

by deleting the

th row

and jth column.

Lemma. Let A ∈ Mat

(F). Then

(i) We can expand det A along the jth column by

det A =

i=1

(−1)

i+j

det

(ii) We can expand det A along the ith row by

det A =

j=1

(−1)

i+j

det

We could prove this directly from the definition, but that is messy and scary,

so let’s use volume forms instead.

Proof.

Since

det A

, (i) and (ii) are equivalent. So it suffices to prove

just one of them. We have

det A = d(A

(1)

, ··· , A

(n)

where d is the volume form induced by the determinant. Then we can write as

det A = d

(1)

, ··· ,

i=1

, ··· , A

(n)

i=1

d(A

(1)

, ··· , e

, ··· , A

(n)

)

The volume form on the right is the determinant of a matrix with the

th column

replaced with

. We can move our columns around so that our matrix becomes

B =



stuff 1



We get that

det B

det

, since the only permutations that give a non-zero

sum are those that send

. In the row and column swapping, we have made

n − j column transpositions and n − i row transpositions. So we have

det A =

i=1

(−1)

n−j

(−1)

n−i

det B

i=1

(−1)

i+j

det

This is not only useful for computing determinants, but also computing

inverses.

Definition

(Adjugate matrix)

Let

A ∈ Mat

(

). The adjugate matrix of

written adj A, is the n × n matrix such that (adj A)

= (−1)

i+j

det

The relevance is the following result:

Theorem.

A ∈ Mat

(

), then

(

adj A

) = (

det A

)

= (

adj A

)

. In particu-

lar, if det A 6= 0, then

−1

det A

adj A.

Note that this is not an efficient way to compute the inverse.

Proof. We compute

[(adj A)A]

i=1

(adj A)

i=1

(−1)

i+j

det

. (∗)

So if j = k, then [(adj A)A]

= det A by the lemma.

Otherwise, if

j 6

, consider the matrix

obtained from

by replacing the

th column by the

th column. Then the right hand side of (

∗

) is just

det B

the lemma. But we know that if two columns are the same, the determinant is

zero. So the right hand side of (∗) is zero. So

[(adj A)A]

= det Aδ

The calculation for [

A adj A

] = (

det A

)

can be done in a similar manner, or by

considering (A adj A)

= (adj A)

= (adj(A

))A

= (det A)I

Note that the coefficients of (

adj A

) are just given by polynomials in the

entries of

, and so is the determinant. So if

is invertible, then its inverse is

given by a rational function (i.e. ratio of two polynomials) in the entries of A.

This is very useful theoretically, but not computationally, since the polyno-

mials are very large. There are better ways computationally, such as Gaussian

elimination.

We’ll end with a useful tricks to compute the determinant.

Lemma. Let A, B be square matrices. Then for any C, we have

det



A C

0 B



= (det A)(det B).

Proof. Suppose A ∈ Mat

(F), and B ∈ Mat

(F), so C ∈ Mat

k,`

(F). Let

X =



A C

0 B



Then by definition, we have

det X =

σ∈S

k+`

ε(σ)

k+`

i=1

iσ(i)

j ≤ k

and

i > k

, then

= 0. We only want to sum over permutations

such

that

(

)

> k

i > k

. So we are permuting the last

things among themselves,

and hence the first

things among themselves. So we can decompose this into

, where

is a permutation of

{

, ··· , k}

and fixes the remaining things,

while σ

fixes {1, ··· , k}, and permutes the remaining. Then

det X =

σ=σ

ε(σ

)

i=1

iσ

(i)

j=1

k+j σ

(k+j)

∈S

ε(σ

)

i=1

iσ

(i)





∈S

ε(σ

)

j=1

jσ

(j)





= (det A)(det B)

Corollary.

det







stuff

0 A







i=1

det A

6 Endomorphisms

Endomorphisms are linear maps from a vector space

to itself. One might

wonder — why would we want to study these linear maps in particular, when

we can just work with arbitrary linear maps from any space to any other space?

When we work with arbitrary linear maps, we are free to choose any basis

for the domain, and any basis for the co-domain, since it doesn’t make sense to

require they have the “same” basis. Then we proved that by choosing the right

bases, we can put matrices into a nice form with only 1’s in the diagonal.

However, when working with endomorphisms, we can require ourselves to use

the same basis for the domain and co-domain, and there is much more we can

say. One major objective is to classify all matrices up to similarity, where two

matrices are similar if they represent the same endomorphism under different

bases.

6.1 Invariants

Definition.

is a (finite-dimensional) vector space over

. An endomorphism

is a linear map

V → V

. We write

End

(

) for the

-vector space of all

such linear maps, and I for the identity map V → V .

When we think about matrices representing an endomorphism of

, we’ll

use the same basis for the domain and the range. We are going to study some

properties of these endomorphisms that are not dependent on the basis we pick,

known as invariants.

Lemma.

Suppose (

, ··· , e

) and (

, ··· , f

) are bases for

and

α ∈ End

(

represents

with respect to (

, ··· , e

) and

represents

with respect

to (f

, ··· , f

), then

B = P

−1

AP,

where P is given by

j=1

Proof.

This is merely a special case of an earlier more general result for arbitrary

maps and spaces.

Definition

(Similar matrices)

We say matrices

and

are similar or conjugate

if there is some P invertible such that B = P

−1

AP .

Recall that

(

), the group of invertible

n × n

matrices.

(

) acts on

Mat

(F) by conjugation:

(P, A) 7→ P AP

−1

We are conjugating it this way so that the associativity axiom holds (otherwise

we get a right action instead of a left action). Then

and

are similar iff they

are in the same orbit. Since orbits always partition the set, this is an equivalence

relation.

Our main goal is to classify the orbits, i.e. find a “nice” representative for

each orbit.

Our initial strategy is to identify basis-independent invariants for endomor-

phisms. For example, we will show that the rank, trace, determinant and

characteristic polynomial are all such invariants.

Recall that the trace of a matrix

A ∈ Mat

(

) is the sum of the diagonal

elements:

Definition (Trace). The trace of a matrix of A ∈ Mat

(F) is defined by

tr A =

i=1

We want to show that the trace is an invariant. In fact, we will show a

stronger statement (as well as the corresponding statement for determinants):

Lemma.

(i) If A ∈ Mat

m,n

(F) and B ∈ Mat

n,m

(F), then

tr AB = tr BA.

(ii) If A, B ∈ Mat

(F) are similar, then tr A = tr B.

(iii) If A, B ∈ Mat

(F) are similar, then det A = det B.

Proof.

(i) We have

tr AB =

i=1

(AB)

i=1

j=1

i=1

= tr BA.

(ii) Suppose B = P

−1

AP . Then we have

tr B = tr(P

−1

(AP )) = tr((AP )P

−1

) = tr A.

(iii) We have

det(P

−1

AP ) = det P

−1

det A det P = (det P )

−1

det A det P = det A.

This allows us to define the trace and determinant of an endomorphism.

Definition

(Trace and determinant of endomorphism)

Let

α ∈ End

(

), and

be a matrix representing

under any basis. Then the trace of

tr α

tr A

and the determinant is det α = det A.

The lemma tells us that the determinant and trace are well-defined. We

can also define the determinant without reference to a basis, by defining more

general volume forms and define the determinant as a scaling factor.

The trace is slightly more tricky to define without basis, but in IB Analysis

II example sheet 4, you will find that it is the directional derivative of the

determinant at the origin.

To talk about the characteristic polynomial, we need to know what eigenvalues

are.

Definition

(Eigenvalue and eigenvector)

Let

α ∈ End

(

). Then

λ ∈ F

is an

eigenvalue (or E-value) if there is some v ∈ V \ {0} such that αv = λv.

v is an eigenvector if α(v) = λv for some λ ∈ F.

When

λ ∈ F

, the

-eigenspace, written

(

) or

(

) is the subspace of

containing all the λ-eigenvectors, i.e.

(λ) = ker(λι − α).

where ι is the identity function.

Definition

(Characteristic polynomial)

The characteristic polynomial of

defined by

(t) = det(tι − α).

You might be used to the definition

(

) =

det

(

α − tι

) instead. These two

definitions are obviously equivalent up to a factor of

−

1, but this definition

has an advantage that

(

) is always monic, i.e. the leading coefficient is 1.

However, when doing computations in reality, we often use

det

(

α − tι

) instead,

since it is easier to negate tι than α.

We know that

is an eigenvalue of

iff

(

α −λι

)

0 iff

(

α −λι

)

< dim V

iff

(

) =

det

(

λι − α

) = 0. So the eigenvalues are precisely the roots of the

characteristic polynomial.

If A ∈ Mat

(F), we can define χ

(t) = det(tI − A).

Lemma.

and

are similar, then they have the same characteristic polyno-

mial.

Proof.

det(tI − P

−1

AP ) = det(P

−1

(tI − A)P ) = det(tI − A).

Lemma. Let α ∈ End(V ) and λ

, ··· , λ

distinct eigenvalues of α. Then

E(λ

) + ··· + E(λ

) =

i=1

E(λ

)

is a direct sum.

Proof. Suppose

i=1

with

, y

∈ E

(

). We want to show that they are equal. We are going to find

some clever map that tells us what

and

are. Consider

∈ End

(

) defined

r6=j

(α − λ

ι).

Then

i=1

r6=j

(α − λ

ι)(x

)

i=1

r6=j

(λ

− λ

)(x

Each summand is zero, unless i 6= j. So this is equal to

i=1

r6=j

(λ

− λ

)(x

Similarly, we obtain

i=1

r6=j

(λ

− λ

)(y

Since we know that

, we must have

r6=j

(λ

− λ

r6=j

(λ

− λ

Since we know that

r6=j

(λ

− λ

) 6= 0, we must have x

= y

for all i.

So each expression for

is unique.

The proof shows that any set of non-zero eigenvectors with distinct eigenvalues

is linearly independent.

Definition

(Diagonalizable)

We say

α ∈ End

(

) is diagonalizable if there is

some basis for

such that

is represented by a diagonal matrix, i.e. all terms

not on the diagonal are zero.

These are in some sense the nice matrices we like to work with.

Theorem.

Let

α ∈ End

(

) and

, ··· , λ

be distinct eigenvalues of

. Write

for E(λ

). Then the following are equivalent:

(i) α is diagonalizable.

(ii) V has a basis of eigenvectors for α.

(iii) V =

i=1

(iv) dim V =

i=1

dim E

Proof.

– (i) ⇔ (ii): Suppose (e

, ··· , e

) is a basis for V . Then

α(e

) = A

where

represents

. Then

is diagonal iff each

is an eigenvector. So

done

–

(ii)

⇔

(iii): It is clear that (ii) is true iff

, but we know that this

must be a direct sum. So done.

–

(iii)

⇔

(iv): This follows from example sheet 1 Q10, which says that

i=1

iff the bases for

are disjoint and their union is a basis of

V .

6.2 The minimal polynomial

6.2.1 Aside on polynomials

Before we talk about minimal polynomials, we first talk about polynomials in

general.

Definition (Polynomial). A polynomial over F is an object of the form

f(t) = a

+ a

m−1

+ ··· + a

t + a

with m ≥ 0, a

, ··· , a

∈ F.

We write F[t] for the set of polynomials over F.

Note that we don’t identify a polynomial

with the corresponding function

it represents. For example, if

Z/pZ

, then

and

are different polynomials,

even though they define the same function (by Fermat’s little theorem/Lagrange’s

theorem). Two polynomials are equal if and only if they have the same coeffi-

cients.

However, we will later see that if

, then polynomials are equal

if and only if they represent the same function, and this distinction is not as

important.

Definition

(Degree)

Let

f ∈ F

[

]. Then the degree of

, written

deg f

is the

largest n such that a

6= 0. In particular, deg 0 = −∞.

Notice that deg fg = deg f + deg g and deg f + g ≤ max{deg f, deg g}.

Lemma

(Polynomial division)

f, g ∈ F

[

] (and

g 6

= 0), then there exists

q, r ∈ F[t] with deg r < deg g such that

f = qg + r.

Proof is omitted.

Lemma. If λ ∈ F is a root of f, i.e. f (λ) = 0, then there is some g such that

f(t) = (t − λ)g(t).

Proof. By polynomial division, let

f(t) = (t − λ)g(t) + r(t)

for some

(

)

, r

(

)

∈ F

[

] with

deg r < deg

(

t − λ

) = 1. So

has to be constant,

i.e. r(t) = a

for some a

∈ F. Now evaluate this at λ. So

0 = f(λ) = (λ − λ)g(λ) + r(λ) = a

So a

= 0. So r = 0. So done.

Definition

(Multiplicity of a root)

Let

f ∈ F

[

] and

a root of

. We say

has multiplicity k if (t − λ)

is a factor of f but (t − λ)

k+1

is not, i.e.

f(t) = (t − λ)

g(t)

for some g(t) ∈ F[t] with g(λ) 6= 0.

We can use the last lemma and induction to show that any non-zero

f ∈ F

[

]

can be written as

f = g(t)

i=1

(t − λ

)

where

, ··· , λ

are all distinct,

1, and

is a polynomial with no roots in

Hence we obtain the following:

Lemma.

A non-zero polynomial

f ∈ F

[

] has at most

deg f

roots, counted with

multiplicity.

Corollary.

Let

f, g ∈ F

[

] have degree

< n

. If there are

, ··· , λ

distinct such

that f (λ

) = g(λ

) for all i, then f = g.

Proof.

Given the lemma, consider

f − g

. This has degree less than

, and

(

f − g

)(

) = 0 for

= 1

, ··· , n

. Since it has at least

n ≥ deg

(

f − g

) roots, we

must have f − g = 0. So f = g.

Corollary.

is infinite, then

and

are equal if and only if they agree on

all points.

More importantly, we have the following:

Theorem

(The fundamental theorem of algebra)

Every non-constant polyno-

mial over C has a root in C.

We will not prove this.

We say C is an algebraically closed field.

It thus follows that every polynomial over

of degree

n >

0 has precisely

roots, counted with multiplicity, since if we write

(

) =

(

)

(

t − λ

)

and

has no roots, then

is constant. So the number of roots is

deg f

counted with multiplicity.

It also follows that every polynomial in

factors into linear polynomials and

quadratic polynomials with no real roots (since complex roots of real polynomials

come in complex conjugate pairs).

6.2.2 Minimal polynomial

Notation.

Given

(

) =

i=0

∈ F

[

A ∈ Mat

(

) and

α ∈ End

(

), we

can write

f(A) =

i=0

, f (α) =

i=0

where A

= I and α

= ι.

Theorem

(Diagonalizability theorem)

Suppose

α ∈ End

(

). Then

is diago-

nalizable if and only if there exists non-zero

(

)

∈ F

[

] such that

(

) = 0, and

p(t) can be factored as a product of distinct linear factors.

Proof.

Suppose

is diagonalizable. Let

, ··· , λ

be the distinct eigenvalues

of α. We have

V =

i=1

E(λ

So each v ∈ V can be written (uniquely) as

v =

i=1

with α(v

) = λ

Now let

p(t) =

i=1

(t − λ

Then for any v, we get

p(α)(v) =

i=1

p(α)(v

) =

i=1

p(λ

= 0.

So p(α) = 0. By construction, p has distinct linear factors.

Conversely, suppose we have our polynomial

p(t) =

i=1

(t − λ

with

, ··· , λ

∈ F

distinct, and

(

) = 0 (we can wlog assume

is monic, i.e.

the leading coefficient is 1). We will show that

V =

i=1

(λ

In other words, we want to show that for all

v ∈ V

, there is some

∈ E

(

)

for i = 1, ··· , k such that v =

To find these v

out, we let

(t) =

i6=j

t − λ

− λ

This is a polynomial of degree k − 1, and q

(λ

) = δ

Now consider

q(t) =

i=1

(t).

We still have

deg q ≤ k −

1, but

(

) = 1 for any

. Since

and 1 agree on

points, we must have q = 1.

Let π

: V → V be given by π

= q

(α). Then the above says that

j=1

= ι.

Hence given v ∈ V , we know that v =

We now check that π

v ∈ E

(λ

). This is true since

(α − λ

ι)π

v =

i6=j

(λ

− λ

)

i=1

(α − λ

)(v) =

i6=j

(λ

− λ

)

p(α)(v) = 0.

αv

= λ

So done.

In the above proof, if

v ∈ E

(

), then

(

) =

. So

is a projection

onto the E

(λ

Definition

(Minimal polynomial)

The minimal polynomial of

α ∈ End

(

) is

the non-zero monic polynomial M

(t) of least degree such that M

(α) = 0.

The monic requirement is just for things to look nice, since we can always

divide by the leading coefficient of a polynomial to get a monic version.

Note that if

represents

, then for all

p ∈ F

[

(

) represents

(

Thus

(

) is zero iff

(

) = 0. So the minimal polynomial of

is the minimal

polynomial of A if we define M

analogously.

There are two things we want to know — whether the minimal polynomial

exists, and whether it is unique.

Existence is always guaranteed in finite-dimensional cases. If

dim V

n < ∞

then

dim End

(

) =

. So

ι, α, α

, ··· , α

are linearly dependent. So there are

some λ

, ··· , λ

∈ F not all zero such that

i=0

= 0.

So deg M

≤ n

. So we must have a minimal polynomial.

To show that the minimal polynomial is unique, we will prove the following

stronger characterization of the minimal polynomial:

Lemma.

Let

α ∈ End

(

), and

p ∈ F

[

]. Then

(

) = 0 if and only if

(

) is

a factor of p(t). In particular, M

is unique.

Proof.

For all such

, we can write

(

) =

(

)

(

) +

(

) for some

of degree

less than deg M

. Then

p(α) = q(α)M

(α) + r(α).

So if

(

) = 0 iff

(

) = 0. But

deg r < deg M

. By the minimality of

, we

must have r(α) = 0 iff r = 0. So p(α) = 0 iff M

(t) | p(t).

So if

and

are both minimal polynomials for

, then

| M

and

| M

. So

is just a scalar multiple of

. But since

and

are

monic, they must be equal.

Example. Let V = F

, and consider the following matrices:

A =



1 0

0 1



, B =



1 1

0 1



Consider the polynomial

(

) = (

t −

. We can compute

(

) =

(

) = 0. So

(

) and

(

) are factors of (

t −

. There aren’t many factors of (

t −

So the minimal polynomials are either (

t −

1) or (

t −

. Since

A − I

= 0 and

B − I 6

= 0, the minimal polynomial of

t −

1 and the minimal polynomial of

B is (t − 1)

We can now re-state our diagonalizability theorem.

Theorem

(Diagonalizability theorem 2.0)

Let

α ∈ End

(

). Then

is diago-

nalizable if and only if M

(t) is a product of its distinct linear factors.

Proof. (⇐) This follows directly from the previous diagonalizability theorem.

(

⇒

) Suppose

is diagonalizable. Then there is some

p ∈ F

[

] non-zero such

that

(

) = 0 and

is a product of distinct linear factors. Since

divides

also has distinct linear factors.

Theorem.

Let

α, β ∈ End

(

) be both diagonalizable. Then

and

are

simultaneously diagonalizable (i.e. there exists a basis with respect to which

both are diagonal) if and only if αβ = βα.

This is important in quantum mechanics. This means that if two operators

do not commute, then they do not have a common eigenbasis. Hence we have

the uncertainty principle.

Proof.

(

⇒

) If there exists a basis (

, ··· , e

) for

such that

and

are repre-

sented by

and

respectively, with both diagonal, then by direct computation,

AB = BA. But AB represents αβ and BA represents βα. So αβ = βα.

(

⇐

) Suppose

αβ

βα

. The idea is to consider each eigenspace of

individu-

ally, and then diagonalize

in each of the eigenspaces. Since

is diagonalizable,

we can write

V =

i=1

(λ

where

are the eigenvalues of

. We write

for

(

). We want to show

that

sends

to itself, i.e.

(

)

⊆ E

. Let

v ∈ E

. Then we want

(

) to be

in E

. This is true since

α(β(v)) = β(α(v)) = β(λ

v) = λ

β(v).

So β(v) is an eigenvector of α with eigenvalue λ

Now we can view β|

∈ End(E

). Note that

(β|

) = M

(β)|

= 0.

Since

(

) is a product of its distinct linear factors, it follows that

β|

diagonalizable. So we can choose a basis

of eigenvectors for

β|

. We can do

this for all i.

Then since

is a direct sum of the

’s, we know that

i=1

is a

basis for V consisting of eigenvectors for both α and β. So done.

6.3 The Cayley-Hamilton theorem

We will first state the theorem, and then prove it later.

Recall that

(

) =

det

(

tι − α

) for

α ∈ End

(

). Our main theorem of the

section (as you might have guessed from the title) is

Theorem

(Cayley-Hamilton theorem)

Let

be a finite-dimensional vector

space and

α ∈ End

(

). Then

(

) = 0, i.e.

(

)

| χ

(

). In particular,

deg M

≤ n.

We will not prove this yet, but just talk about it first. It is tempting to prove

this by substituting

into

det

(

tι − α

) and get

det

(

α − α

) = 0, but this is

meaningless, since what the statement

(

) =

det

(

tι − α

) tells us to do is to

expand the determinant of the matrix







t − a

··· a

t − a

··· a

··· t − a







to obtain a polynomial, and we clearly cannot substitute

in this expression.

However, we can later show that we can use this idea to prove it, but just be a

bit more careful.

Note also that if ρ(t) ∈ F[t] and

A =













then

ρ(A) =







ρ(λ

)

ρ(λ

)







Since

(

) is defined as

i=1

(

t − λ

), it follows that

(

) = 0. So if

diagonalizable, then the theorem is clear.

This was easy. Diagonalizable matrices are nice. The next best thing we can

look at is upper-triangular matrices.

Definition

(Triangulable)

An endomorphism

α ∈ End

(

) is triangulable if

there is a basis for V such that α is represented by an upper triangular matrix







··· a

0 a

··· a

0 0 ··· a







We have a similar lemma telling us when matrices are triangulable.

Lemma.

An endomorphism

is triangulable if and only if

(

) can be written

as a product of linear factors, not necessarily distinct. In particular, if

(or any algebraically closed field), then every endomorphism is triangulable.

Proof. Suppose that α is triangulable and represented by







∗ ··· ∗

0 λ

··· ∗

0 0 ··· λ







Then

(t) = det







t − λ

∗ ··· ∗

0 t − λ

··· ∗

0 0 ··· t − λ







i=1

(t − λ

So it is a product of linear factors.

We are going to prove the converse by induction on the dimension of our

space. The base case

dim V

= 1 is trivial, since every 1

1 matrix is already

upper triangular.

Suppose

α ∈ End

(

) and the result holds for all spaces of dimensions

< dim V

, and

is a product of linear factors. In particular,

(

) has a root,

say λ ∈ F.

Now let

(

)

= 0, and let

be a complementary subspace to

i.e.

U ⊕ W

. Let

, ··· , u

be a basis for

and

r+1

, ··· , w

be a basis

for

so that

, ··· , u

, w

r+1

, ··· , w

is a basis for

, and

is represented by



λI

stuff

0 B



We know

(

) = (

t −λ

)

(

). So

(

) is also a product of linear factors. We

let β : W → W be the map defined by B with respect to w

r+1

, ··· , w

(Note that in general,

is not

α|

in general, since

does not necessarily

map

. However, we can say that (

α−β

)(

)

∈ U

for all

w ∈ W

. This can

be much more elegantly expressed in terms of quotient spaces, but unfortunately

that is not officially part of the course)

Since

dim W < dim V

, there is a basis

r+1

, ··· , v

for

such that

represented by C, which is upper triangular.

For j = 1, ··· , n − r, we have

α(v

j+r

) = u +

n−r

k=1

k+r

for some u ∈ U. So α is represented by



λI

stuff

0 C



with respect to (u

, ··· , u

, v

r+1

, ··· , v

), which is upper triangular.

Example. Consider the real rotation matrix



cos θ sin θ

−sin θ cos θ



This is not similar to a real upper triangular matrix (if

is not an integer

multiple of

). This is since the eigenvalues are

±iθ

and are not real. On the

other hand, as a complex matrix, it is triangulable, and in fact diagonalizable

since the eigenvalues are distinct.

For this reason, in the rest of the section, we are mostly going to work in

We can now prove the Cayley-Hamilton theorem.

Theorem

(Cayley-Hamilton theorem)

Let

be a finite-dimensional vector

space and

α ∈ End

(

). Then

(

) = 0, i.e.

(

)

| χ

(

). In particular,

deg M

≤ n.

Proof.

In this proof, we will work over

. By the lemma, we can choose a basis

, ··· , e

} is represented by an upper triangular matrix.

A =







∗ ··· ∗

0 λ

··· ∗

0 0 ··· λ







We must prove that

(α) = χ

(α) =

i=1

(α − λ

ι) = 0.

Write V

= he

, ··· , e

i. So we have the inclusions

= 0 ⊆ V

⊆ ··· ⊆ V

n−1

⊆ V

= V.

We also know that dim V

= j. This increasing sequence is known as a flag.

Now note that since A is upper-triangular, we get

α(e

) =

k=1

∈ V

So α(V

) ⊆ V

for all j = 0, ··· , n.

Moreover, we have

(α − λ

ι)(e

) =

j−1

k=1

⊆ V

j−1

for all

= 1

, ··· , n

. So every time we apply one of these things, we get to a

smaller space. Hence by induction on n − j, we have

i=j

(α − λ

ι)(V

) ⊆ V

j−1

In particular, when j = 1, we get

i=1

(α − λ

ι)(V ) ⊆ V

= 0.

So χ

(α) = 0 as required.

Note that if our field

is not

but just a subfield of

, say

, we can just

pretend it is a complex matrix, do the same proof.

We can see this proof more “visually” as follows: for simplicity of expression,

we suppose

= 4. In the basis where

is upper-triangular, the matrices

A −λ

look like this

A − λ

I =







0 ∗ ∗ ∗

0 0 ∗ ∗

0 0 0 ∗







A − λ

I =







∗ ∗ ∗ ∗

0 0 ∗ ∗

0 0 0 ∗







A − λ

I =







∗ ∗ ∗ ∗

0 ∗ ∗ ∗

0 0 0 ∗







A − λ

I =







∗ ∗ ∗ ∗

0 ∗ ∗ ∗

0 0 ∗ ∗

0 0 0 0







Then we just multiply out directly (from the right):

i=1

(A − λ

I) =







0 ∗ ∗ ∗

0 0 ∗ ∗

0 0 0 ∗













∗ ∗ ∗ ∗

0 0 ∗ ∗

0 0 0 ∗













∗ ∗ ∗ ∗

0 ∗ ∗ ∗

0 0 0 ∗













∗ ∗ ∗ ∗

0 ∗ ∗ ∗

0 0 ∗ ∗

0 0 0 0













0 ∗ ∗ ∗

0 0 ∗ ∗

0 0 0 ∗













∗ ∗ ∗ ∗

0 0 ∗ ∗

0 0 0 ∗













∗ ∗ ∗ ∗

0 ∗ ∗ ∗

0 0 0 0













0 ∗ ∗ ∗

0 0 ∗ ∗

0 0 0 ∗













∗ ∗ ∗ ∗

0 0 0 0













0 0 0 0







This is exactly what we showed in the proof — after multiplying out the first

elements of the product (counting from the right), the image is contained in the

span of the first n − k basis vectors.

Proof.

We’ll now prove the theorem again, which is somewhat a formalization

of the “nonsense proof” where we just substitute t = α into det(α − tι).

Let α be represented by A, and B = tI − A. Then

B adj B = det BI

= χ

(t)I

But we know that

adj B

is a matrix with entries in

[

] of degree at most

n −

So we can write

adj B = B

n−1

+ B

n−2

+ ··· + B

with B

∈ Mat

(F). We can also write

(t) = t

+ a

n−1

+ ··· + a

Then we get the result

(tI

− A)(B

n−1

+ B

n−2

+ ··· + B

) = (t

+ a

n−1

+ ··· + a

We would like to just throw in

, and get the desired result, but in all these

derivations, t is assumed to be a real number, and, tI

− A is the matrix







t − a

··· a

t − a

··· a

··· t − a







It doesn’t make sense to put our A in there.

However, what we can do is to note that since this is true for all values of

the coefficients on both sides must be equal. Equating coefficients in

, we have

−AB

= a

− AB

= a

n−2

− AB

n−1

= a

n−1

− 0 = I

We now multiply each row a suitable power of A to obtain

−AB

= a

− A

= a

n−1

n−2

− A

n−1

= a

n−1

− 0 = A

Summing this up then gives χ

(A) = 0.

This proof suggests that we really ought to be able to just substitute in

and be done. In fact, we can do this, after we develop sufficient machinery. This

will be done in the IB Groups, Rings and Modules course.

Lemma. Let α ∈ End(V ), λ ∈ F. Then the following are equivalent:

(i) λ is an eigenvalue of α.

(ii) λ is a root of χ

(t).

(iii) λ is a root of M

(t).

Proof.

–

(i)

⇔

(ii):

is an eigenvalue of

if and only if (

α − λι

)(

) = 0 has a

non-trivial root, iff det(α − λι) = 0.

– (iii) ⇒ (ii): This follows from Cayley-Hamilton theorem since M

| χ

–

(i)

⇒

(iii): Let

be an eigenvalue, and

be a corresponding eigenvector.

Then by definition of M

, we have

(α)(v) = 0(v) = 0.

We also know that

(α)(v) = M

(λ)v.

Since v is non-zero, we must have M

(λ) = 0.

–

(iii)

⇒

(i): This is not necessary since it follows from the above, but

we could as well do it explicitly. Suppose

is a root of

(

). Then

(

) = (

t − λ

)

(

) for some

g ∈ F

[

]. But

deg g < deg M

. Hence by

minimality of

, we must have

(

)

= 0. So there is some

v ∈ V

such

that g(α)(v) 6= 0. Then

(α − λι)g(α)(v) = M

(α)v = 0.

So we must have

(

)(

)) =

λg

(

)(

). So

(

)(

)

∈ E

(

)

}

. So (i)

holds.

Example. What is the minimal polynomial of

A =





1 0 −2

0 1 1

0 0 2





We can compute

(

) = (

t−

(

t−

2). So we know that the minimal polynomial

is one of (t − 1)

(t − 2) and (t − 1)(t − 2).

By direct and boring computations, we can find (

A − I

)(

A −

) = 0. So we

know that M

(t) = (t − 1)(t − 2). So A is diagonalizable.

6.4 Multiplicities of eigenvalues and Jordan normal form

We will want to put our matrices in their “Jordan normal forms”, which is

a unique form for each equivalence class of similar matrices. The following

properties will help determine which Jordan normal form a matrix can have.

Definition

(Algebraic and geometry multiplicity)

Let

α ∈ End

(

) and

eigenvalue of α. Then

(i)

The algebraic multiplicity of

, written

, is the multiplicity of

as a

root of χ

(t).

(ii)

The geometric multiplicity of

, written

, is the dimension of the corre-

sponding eigenspace, dim E

(λ).

(iii) c

is the multiplicity of λ as a root of the minimal polynomial m

(t).

We will look at some extreme examples:

Example.

– Let

A =







λ 1 ··· 0

0 λ

0 0 ··· λ







We will later show that a

= n = c

and g

= 1.

– Consider A = λI. Then a

= g

= n, c

= 1.

Lemma. If λ is an eigenvalue of α, then

(i) 1 ≤ g

≤ a

(ii) 1 ≤ c

≤ a

Proof.

(i)

The first inequality is easy. If

is an eigenvalue, then

(

)

= 0. So

dim E

(

)

≥

1. To prove the other inequality, if

, ··· , v

is a basis

for

(

), then we can extend it to a basis for

, and then

is represented



λI

∗

0 B



So χ

(t) = (t − λ)

(t). So a

> g = g

(ii)

This is straightforward since

(

) = 0 implies 1

≤ c

, and since

(

)

(t), we know that c

≤ α

Lemma. Suppose F = C and α ∈ End(V ). Then the following are equivalent:

(i) α is diagonalizable.

(ii) g

= a

for all eigenvalues of α.

(iii) c

= 1 for all λ.

Proof.

–

(i)

⇔

(ii):

is diagonalizable iff

dim V

dim E

(

). But this is

equivalent to

dim V =

≤

= deg χ

= dim V.

So we must have

. Since each

is at most

, they must

be individually equal.

–

(i)

⇔

(iii):

is diagonalizable if and only if

(

) is a product of distinct

linear factors if and only if c

= 1 for all eigenvalues λ.

Definition

(Jordan normal form)

We say

A ∈ Mat

(

) is in Jordan normal

form if it is a block diagonal of the form







(λ

) 0

(λ

)

0 J

(λ

)







where

k ≥

, ··· , n

∈ N

such that

, ··· , λ

not necessarily

distinct, and

(λ) =







λ 1 ··· 0

0 λ

0 0 ··· λ







is an m × m matrix. Note that J

(λ) = λI

+ J

(0).

For example, it might look something like













with all other entries zero.

Then we have the following theorem:

Theorem

(Jordan normal form theorem)

Every matrix

A ∈ Mat

(

) is similar

to a matrix in Jordan normal form. Moreover, this Jordan normal form matrix

is unique up to permutation of the blocks.

This is a complete solution to the classification problem of matrices, at least

. We will not prove this completely. We will only prove the uniqueness part,

and then reduce the existence part to a special form of endomorphisms. The

remainder of the proof is left for IB Groups, Rings and Modules.

We can rephrase this result using linear maps. If

α ∈ End

(

) is an endo-

morphism of a finite-dimensional vector space

over

, then the theorem says

there exists a basis such that

is represented by a matrix in Jordan normal

form, and this is unique as before.

Note that the permutation thing is necessary, since if two matrices in Jordan

normal form differ only by a rearrangement of blocks, then they are similar, by

permuting the basis.

Example.

Every 2

2 matrix in Jordan normal form is one of the three types:

Jordan normal form χ



λ 0

0 λ



(t − λ)



λ 0

0 µ



(t − λ)(t − µ) (t − λ)(t − µ)



λ 1

0 λ



(t − λ)

with

λ, µ ∈ C

distinct. We see that

determines the Jordan normal form of

A, but χ

does not.

Every 3

3 matrix in Jordan normal form is one of the six types. Here

, λ

and λ

are distinct complex numbers.

Jordan normal form χ





0 0

0 λ

0 0 λ





(t − λ

)(t − λ

) (t − λ

)(t − λ

)





0 0

0 λ

0 0 λ





(t − λ

)

(t − λ

) (t − λ

)(t − λ

)





1 0

0 λ

0 0 λ





(t − λ

)

(t − λ

) (t − λ

)

(t − λ

)





0 0

0 λ

0 0 λ





(t − λ

)

(t − λ

)





1 0

0 λ

0 0 λ





(t − λ

)

(t − λ

)





1 0

0 λ

0 0 λ





(t − λ

)

(t − λ

)

Notice that

and

together determine the Jordan normal form of a 3

complex matrix. We do indeed need

in the second case, since if we are given

= (t − λ

)(t − λ

), we know one of the roots is double, but not which one.

In general, though, even χ

and M

together does not suffice.

We now want to understand the Jordan normal blocks better. Recall the

definition

(λ) =







λ 1 ··· 0

0 λ

0 0 ··· λ







= λI

+ J

(0).

If (e

, ··· , e

) is the standard basis for C

, we have

(0)(e

) = 0, J

(0)(e

) = e

i−1

for 2 ≤ i ≤ n.

Thus we know

(0)

) =

(

0 i ≤ k

i−k

k < i ≤ n

In other words, for k < n, we have

(λ) − λI)

= J

(0)



0 I

n−k

0 0



If k ≥ n, then we have (J

(λ) − λI)

= 0. Hence we can summarize this as

n((J

(λ) − λI

)

) = min{r, m}.

Note that if

(

), then

(

) =

(

) = (

t − λ

)

. So

is the only

eigenvalue of

. So

. We also know that

(

A−λI

) =

n−r

(

A−λI

) =

1. So g

= 1.

Recall that a general Jordan normal form is a block diagonal matrix of Jordan

blocks. We have just studied individual Jordan blocks. Next, we want to look at

some properties of block diagonal matrices in general. If

is the block diagonal

matrix

A =













then

(t) =

i=1

(k).

Moreover, if ρ ∈ F[t], then

ρ(A) =







ρ(A

)

ρ(A

)

ρ(A

)







Hence

(t) = lcm(M

(t), ··· , M

(t)).

By the rank-nullity theorem, we have

n(ρ(A)) =

i=1

n(ρ(A

)).

Thus if A is in Jordan normal form, we get the following:

– g

is the number of Jordan blocks in A with eigenvalue λ.

– a

is the sum of sizes of the Jordan blocks of A with eigenvalue λ.

– c

is the size of the largest Jordan block with eigenvalue λ.

We are now going to prove the uniqueness part of Jordan normal form

theorem.

Theorem.

Let

α ∈ End

(

), and

in Jordan normal form representing

. Then

the number of Jordan blocks J

(λ) in A with n ≥ r is

n((α − λι)

) − n((α − λι)

r−1

This is clearly independent of the choice of basis. Also, given this information,

we can figure out how many Jordan blocks of size exactly

by doing the right

subtraction. Hence this tells us that Jordan normal forms are unique up to

permutation of blocks.

Proof. We work blockwise for

A =







(λ

)

(λ

)

(λ

)







We have previously computed

n((J

(λ) − λI

)

) =

(

r r ≤ m

m r > m

Hence we know

n((J

(λ) − λI

)

) − n((J

(λ) − λI

)

r−1

) =

(

1 r ≤ m

0 otherwise.

It is also easy to see that for µ 6= λ,

n((J

(µ) − λI

)

) = n(J

(µ − λ)

) = 0

Adding up for each block, for r ≥ 1, we have

n((α−λι)

)−n((α−λι)

r−1

) = number of Jordan blocks J

(λ) with n ≥ r.

We can interpret this result as follows: if

r ≤ m

, when we take an additional

power of

(

)

−λI

, we get from



0 I

m−r

0 0





0 I

m−r−1

0 0



. So we kill off

one more column in the matrix, and the nullity increase by one. This happens

until (

(

)

− λI

)

= 0, in which case increasing the power no longer affects

the matrix. So when we look at the difference in nullity, we are counting the

number of blocks that are affected by the increase in power, which is the number

of blocks of size at least r.

We have now proved uniqueness, but existence is not yet clear. To show

this, we will reduce it to the case where there is exactly one eigenvalue. This

reduction is easy if the matrix is diagonalizable, because we can decompose the

matrix into each eigenspace and then work in the corresponding eigenspace. In

general, we need to work with “generalized eigenspaces”.

Theorem

(Generalized eigenspace decomposition)

Let

be a finite-dimensional

vector space C such that α ∈ End(V ). Suppose that

(t) =

i=1

(t − λ

)

with λ

, ··· , λ

∈ C distinct. Then

V = V

⊕ ··· ⊕ V

where V

= ker((α − λ

ι)

) is the generalized eigenspace.

This allows us to decompose

into a block diagonal matrix, and then each

block will only have one eigenvalue.

Note that if

···

= 1, then we recover the diagonalizability theorem.

Hence, it is not surprising that the proof of this is similar to the diagonalizability

theorem. We will again prove this by constructing projection maps to each of

the V

Proof. Let

(t) =

i6=j

(t − λ

)

Then

, ··· , p

have no common factors, i.e. they are coprime. Thus by Euclid’s

algorithm, there exists q

, ··· , q

∈ C[t] such that

= 1.

We now define the endomorphism

= q

(α)p

(α)

for j = 1, ··· , k.

Then

= ι. Since M

(α) = 0 and M

(t) = (t − λ

ι)

(t), we get

(α − λ

ι)

= 0.

So im π

⊆ V

Now suppose v ∈ V . Then

v = ι(v) =

j=1

(v) ∈

V =

To show this is a direct sum, note that

= 0, since the product contains

(α) as a factor. So

= ιπ





= π

So π is a projection, and π

= ι

. So if v =

, then applying π

to both

sides gives

(

). Hence there is a unique way of writing

as a sum of

things in V

. So V =

as claimed.

Note that we didn’t really use the fact that the vector space is over

, except

to get that the minimal polynomial is a product of linear factors. In fact, for

arbitrary vector spaces, if the minimal polynomial of a matrix is a product of

linear factors, then it can be put into Jordan normal form. The converse is also

true — if it can be put into Jordan normal form, then the minimal polynomial

is a product of linear factors, since we’ve seen that a necessary and sufficient

condition for the minimal polynomial to be a product of linear factors is for

there to be a basis in which the matrix is upper triangular.

Using this theorem, by restricting

to its generalized eigenspaces, we can

reduce the existence part of the Jordan normal form theorem to the case

(

) =

(

t − λ

)

. Further by replacing

α − λι

, we can reduce this to the case where

0 is the only eigenvalue.

Definition

(Nilpotent)

We say

α ∈ End

(

) is nilpotent if there is some

such

that α

= 0.

Over

is nilpotent if and only if the only eigenvalue of

is 0. This is

since α is nilpotent if the minimal polynomial is t

for some r.

We’ve now reduced the problem of classifying complex endomorphisms to the

classifying nilpotent endomorphisms. This is the point where we stop. For the

remainder of the proof, see IB Groups, Rings and Modules. There is in fact an

elementary proof of it, and we’re not doing it not because it’s hard, but because

we don’t have time.

Example. Let

A =





3 −2 0

1 0 0

1 0 1





We know we can find the Jordan normal form by just computing the minimal

polynomial and characteristic polynomial. But we can do better and try to find

a P such that P

−1

AP is in Jordan normal form.

We first compute the eigenvalues of A. The characteristic polynomial is

det





t − 3 −2 0

1 t 0

1 0 t − 1





= (t − 1)((t − 3)t + 2) = (t − 1)

(t − 2).

We now compute the eigenspaces of A. We have

A − I =





2 −2 0

1 −1 0

1 0 0





We see this has rank 2 and hence nullity 1, and the eigenspace is the kernel

(1) =









We can also compute the other eigenspace. We have

A − 2I =





1 −2 0

1 0 −1





This has rank 2 and

(2) =









Since

dim E

(1) + dim E

(2) = 2 < 3,

this is not diagonalizable. So the minimal polynomial must also be

(

) =

(

) = (

t −

(

t −

2). From the classificaion last time, we know that

similar to





1 1 0

0 1 0

0 0 2





We now want to compute a basis that transforms

to this. We want a basis

, v

) of C

such that

= v

, Av

= v

+ v

, Av

= 2v

Equivalently, we have

(A − I)v

= 0, (A − I)v

= v

, (A − 2I)v

= 0.

There is an obvious choices v

, namely the eigenvector of eigenvalue 2.

To find

and

, the idea is to find some

such that (

A − I

)

but

(A − I)

= 0. Then we can let v

= (A − I)v

We can compute the kernel of (A − I)

. We have

(A − I)





2 −2 0

1 −1 0

2 −2 0





The kernel of this is

ker(A − I)

















We need to pick our

that is in this kernel but not in the kernel of

A − I

(which is the eigenspace E

we have computed above). So we have









, v









, v









Hence we have

P =





0 1 2

0 1 1

1 0 2





and

−1

AP =





1 1 0

0 1 0

0 0 2





7 Bilinear forms II

In Chapter 4, we have looked at bilinear forms in general. Here, we want to look

at bilinear forms on a single space, since often there is just one space we are

interested in. We are also not looking into general bilinear forms on a single

space, but just those that are symmetric.

7.1 Symmetric bilinear forms and quadratic forms

Definition

(Symmetric bilinear form)

Let

is a vector space over

. A bilinear

form φ : V ×V → F is symmetric if

φ(v, w) = φ(w, v)

for all v, w ∈ V .

Example.

S ∈ Mat

(

) is a symmetric matrix, i.e.

, the bilinear form

φ : F

× F

→ F defined by

φ(x, y) = x

Sx =

i,j=1

is a symmetric bilinear form.

This example is typical in the following sense:

Lemma.

Let

be a finite-dimensional vector space over

, and

V ×V → F

is a symmetric bilinear form. Let (

, ··· , e

) be a basis for

, and let

the matrix representing

with respect to this basis, i.e.

(

, e

). Then

φ is symmetric if and only if M is symmetric.

Proof. If φ is symmetric, then

= φ(e

, e

) = φ(e

, e

) = M

So M

= M. So M is symmetric.

If M is symmetric, then

φ(x, y) = φ





i,j

= φ(y, x).

We are going to see what happens when we change basis. As in the case of

endomorphisms, we will require to change basis in the same ways on both sides.

Lemma.

Let

is a finite-dimensional vector space, and

V × V → F

bilinear form. Let (e

, ··· , e

) and (f

, ··· , f

) be bases of V such that

k=1

represents

with respect to (

) and

represents

with respect to (

then

B = P

AP.

Proof. Special case of general formula proven before.

This motivates the following definition:

Definition

(Congruent matrices)

Two square matrices

A, B

are congruent if

there exists some invertible P such that

B = P

AP.

It is easy to see that congruence is an equivalence relation. Two matrices

are congruent if and only if represent the same bilinear form with respect to

different bases.

Thus, to classify (symmetric) bilinear forms is the same as classifying (sym-

metric) matrices up to congruence.

Before we do the classification, we first look at quadratic forms, which are

something derived from bilinear forms.

Definition

(Quadratic form)

A function

V → F

is a quadratic form if there

exists some bilinear form φ such that

q(v) = φ(v, v)

for all v ∈ V .

Note that quadratic forms are not linear maps (they are quadratic).

Example.

Let

and

be represented by

with respect to the standard

basis. Then







x y









= A

+ (A

+ A

)xy + A

Notice that if A is replaced the symmetric matrix

(A + A

then we get a different φ, but the same q. This is in fact true in general.

Proposition

(Polarization identity)

Suppose that

char F 6

= 2, i.e. 1 + 1

= 0

(e.g. if

). If

V → F

is a quadratic form, then there exists a

unique symmetric bilinear form φ : V × V → F such that

q(v) = φ(v, v).

Proof.

Let

V × V → F

be a bilinear form such that

(

v, v

) =

(

). We

define φ : V ×V → F by

φ(v, w) =

(ψ(v, w) + ψ(w, v))

for all

v, w ∈ F

. This is clearly a bilinear form, and it is also clearly symmetric

and satisfies the condition we wants. So we have proved the existence part.

To prove uniqueness, we want to find out the values of

(

v, w

) in terms of

what q tells us. Suppose φ is such a symmetric bilinear form. We compute

q(v + w) = φ(v + w, v + w)

= φ(v, v) + φ(v, w) + φ(w, v) + φ(w, w)

= q(v) + 2φ(v, w) + q(w).

So we have

φ(v, w) =

(q(v + w) − q(v) − q(w)).

So it is determined by q, and hence unique.

Theorem.

Let

be a finite-dimensional vector space over

, and

V ×V → F

a symmetric bilinear form. Then there exists a basis (

, ··· , e

) for

such

that φ is represented by a diagonal matrix with respect to this basis.

This tells us classifying symmetric bilinear forms is easier than classifying

endomorphisms, since for endomorphisms, even over

, we cannot always make

it diagonal, but we can for bilinear forms over arbitrary fields.

Proof.

We induct over

dim V

. The cases

= 0 and

= 1 are trivial, since

all matrices are diagonal.

Suppose we have proven the result for all spaces of dimension less than

First consider the case where

(

v, v

) = 0 for all

v ∈ V

. We want to show that

we must have

= 0. This follows from the polarization identity, since this

induces the zero quadratic form, and we know that there is a unique bilinear

form that induces the zero quadratic form. Since we know that the zero bilinear

form also induces the zero quadratic form, we must have

= 0. Then

will

be represented by the zero matrix with respect to any basis, which is trivially

diagonal.

If not, pick e

∈ V such that φ(e

, e

) 6= 0. Let

U = ker φ(e

, ·) = {u ∈ V : φ(e

, u) = 0}.

Since

(

, ·

)

∈ V

∗

\ {

}

, we know that

dim U

n −

1 by the rank-nullity

theorem.

Our objective is to find other basis elements

, ··· , e

such that

(

, e

) = 0

for all j > 1. For this to happen, we need to find them inside U.

Now consider

φ|

U×U

U × U → F

, a symmetric bilinear form. By the

induction hypothesis, we can find a basis

, ··· , e

for

such that

φ|

U×U

represented by a diagonal matrix with respect to this basis.

Now by construction,

(

, e

) = 0 for all 1

≤ i 6

j ≤ n

and (

, ··· , e

) is

a basis for V . So we’re done.

Example. Let q be a quadratic form on R

given by

















= x

+ y

+ z

+ 2xy + 4yz + 6xz.

We want to find a basis f

, f

for R

such that q is of the form

q(af

+ bf

+ cf

) = λa

+ µb

+ νc

for some λ, µ, ν ∈ R.

There are two ways to do this. The first way is to follow the proof we just had.

We first find our symmetric bilinear form. It is the bilinear form represented by

the matrix

A =





1 1 3

1 1 2

3 2 1





We then find

such that

(

, f

)

= 0. We note that

(

) = 1

= 0. So we pick

= e









Then

φ(e

, v) =



1 0 0







1 1 3

1 1 2

3 2 1













= v

+ v

+ 3v

Next we need to pick our

. Since it is in the kernel of

(

, ·

), it must satisfy

φ(f

, f

) = 0.

To continue our proof inductively, we also have to pick an f

such that

φ(f

, f

) 6= 0.

For example, we can pick





−1





Then we have q(f

) = −8.

Then we have

φ(f

, v) =



3 0 −1







1 1 3

1 1 2

3 2 1













= v

+ 8v

Finally, we want φ(f

, f

) = φ(f

, f

) = 0. Then





−8





works. We have q(f

) = 8.

With these basis elements, we have

q(af

+ bf

+ cf

) = φ(af

+ bf

+ cf

, af

+ bf

+ cf

)

= a

q(f

) + b

q(f

) + c

q(f

)

= a

− 8b

+ 8c

Alternatively, we can solve the problem by completing the square. We have

+ y

+ z

+ 2xy + 4yz + 6xz = (x + y + 3z)

− 2yz − 8z

= (x + y + 3z)

− 8



z +



We now see

























= (x + y + 3z)(x

+ y

+ 3z

) −8



z +







Why do we know this? This is clearly a symmetric bilinear form, and this also

clearly induces the

given above. By uniqueness, we know that this is the right

symmetric bilinear form.

We now use this form to find our f

, f

such that φ(f

, f

) = δ

To do so, we just solve the equations

x + y + 3z = 1

z +

y = 0

y = 0.

This gives our first vector as









We then solve

x + y + 3z = 0

z +

y = 1

y = 0.

So we have





−3





Finally, we solve

x + y + 3z = 0

z +

y = 0

y = 1.

This gives





−5/8

−1/8.





Then we can see that the result follows, and we get

q(af

+ bf

+ cf

) = a

− 8b

We see that the diagonal matrix we get is not unique. We can re-scale our

basis by any constant, and get an equivalent expression.

Theorem. Let φ be a symmetric bilinear form over a complex vector space V .

Then there exists a basis (v

, ··· , v

) for V such that φ is represented by



0 0



with respect to this basis, where r = r(φ).

Proof.

We’ve already shown that there exists a basis (

, ··· , e

) such that

(

, e

) =

for some

. By reordering the

, we can assume that

, ··· , λ

6= 0 and λ

r+1

, ··· , λ

= 0.

For each 1

≤ i ≤ r

, there exists some

such that

. For

+ 1

≤ r ≤ n

we let µ

= 1 (or anything non-zero). We define

Then

φ(v

, v

) =

φ(e

, e

) =

(

0 i 6= j or i = j > r

1 i = j < r.

So done.

Note that it follows that for the corresponding quadratic form q, we have

i=1

Corollary.

Every symmetric

A ∈ Mat

(

) is congruent to a unique matrix of

the form



0 0



Now this theorem is a bit too strong, and we are going to fix that next lecture,

by talking about Hermitian forms and sesquilinear forms. Before that, we do

the equivalent result for real vector spaces.

Theorem.

Let

be a symmetric bilinear form of a finite-dimensional vector

space over

. Then there exists a basis (

, ··· , v

) for

such that

represented





−I





with

(

p, q ≥

0. Equivalently, the corresponding quadratic forms is

given by

i=1

−

p+q

j=p+1

Note that we have seen these things in special relativity, where the Minkowski

inner product is given by the symmetric bilinear form represented by







−1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1







in units where c = 1.

Proof.

We’ve already shown that there exists a basis (

, ··· , e

) such that

φ(e

, e

) = λ

for some λ

, ··· , λ

∈ R. By reordering, we may assume











> 0 1 ≤ i ≤ p

< 0 p + 1 ≤ i ≤ r

= 0 i > r

We let µ

be defined by











√

1 ≤ i ≤ p

√

−λ

p + 1 ≤ i ≤ r

1 i > r

Defining

we find that φ is indeed represented by





−I





We will later show that this form is indeed unique. Before that, we will have

a few definitions, that really only make sense over R.

Definition

(Positive/negative (semi-)definite)

Let

be a symmetric bilinear

form on a finite-dimensional real vector space V . We say

(i) φ is positive definite if φ(v, v) > 0 for all v ∈ V \{0}.

(ii) φ is positive semi-definite if φ(v, v) ≥ 0 for all v ∈ V .

(iii) φ is negative definite if φ(v, v) < 0 for all v ∈ V \{0}.

(iv) φ is negative semi-definite if φ(v, v) ≤ 0 for all v ∈ V .

We are going to use these notions to prove uniqueness. It is easy to see that

= 0 and

, then we are negative definite; if

= 0 and

q 6

, then we

are negative semi-definite etc.

Example. Let φ be a symmetric bilinear form on R

represented by



0 0

n−p



Then φ is positive semi-definite. φ is positive definite if and only if n = p.

If instead φ is represented by



−I

0 0

n−p



then φ is negative semi-definite. φ is negative definite precisely if n = q.

We are going to use this to prove the uniqueness part of our previous theorem.

Theorem

(Sylvester’s law of inertia)

Let

be a symmetric bilinear form on a

finite-dimensional real vector space

. Then there exists unique non-negative

integers p, q such that φ is represented by





0 0

0 −I

0 0 0





with respect to some basis.

Proof.

We have already proved the existence part, and we just have to prove

uniqueness. To do so, we characterize

and

in a basis-independent way. We

already know that

(

) does not depend on the basis. So it suffices to

show p is unique.

To see that

is unique, we show that

is the largest dimension of a subspace

P ⊆ V such that φ|

P ×P

is positive definite.

First we show we can find such at P . Suppose φ is represented by





0 0

0 −I

0 0 0





with respect to (

, ··· , e

). Then

restricted to

, ··· , e

is represented by

with respect to e

, ··· , e

. So φ restricted to this is positive definite.

Now suppose

is any subspace of

such that

φ|

P ×P

is positive definite. To

show

has dimension at most

, we find a subspace complementary to

with

dimension n − p.

Let Q = he

p+1

, ··· , e

i. Then φ restricted to Q × Q is represented by



−I

0 0



Now if

v ∈ P ∩Q \{

}

, then

(

v, v

)

0 since

v ∈ P \{

}

and

(

v, v

)

≤

0 since

v ∈ Q, which is a contradiction. So P ∩ Q = 0.

We have

dim V ≥ dim(P + Q) = dim P + dim Q = dim P + (n − p).

Rearranging gives

dim P ≤ p.

A similar argument shows that

is the maximal dimension of a subspace

Q ⊆ V

such that φ|

Q×Q

is negative definite.

Definition

(Signature)

The signature of a bilinear form

is the number

p −q

where p and q are as above.

Of course, we can recover p and q from the signature and the rank of φ.

Corollary.

Every real symmetric matrix is congruent to precisely one matrix

of the form





0 0

0 −I

0 0 0





7.2 Hermitian form

The above result was nice for real vector spaces. However, if

is a bilinear form

on a

-vector space

, then

(

iv, iv

) =

−φ

(

v, v

). So there can be no good

notion of positive definiteness for complex bilinear forms. To make them work

for complex vector spaces, we need to modify the definition slightly to obtain

Hermitian forms.

Definition

(Sesquilinear form)

Let

V, W

be complex vector spaces. Then a

sesquilinear form is a function φ : V ×W → C such that

(i) φ(λv

+ µv

, w) =

λφ(v

, w) + ¯µφ(v

, w).

(ii) φ(v, λw

+ µw

) = λφ(v, w

) + µφ(vw

for all v, v

, v

∈ V , w, w

, w

∈ W and λ, µ ∈ C.

Note that some people have an opposite definition, where we have linearity

in the first argument and conjugate linearity in the second.

These are called sesquilinear since “sesqui” means “one and a half”, and this

is linear in the second argument and “half linear” in the first.

Alternatively, to define a sesquilinear form, we can define a new complex

vector space

V structure on V by taking the same abelian group (i.e. the same

underlying set and addition), but with the scalar multiplication

C ×

V →

defined as

(λ, v) 7→

λv.

Then a sesquilinear form on

V × W

is a bilinear form on

V × W

. Alternatively,

this is a linear map W →

∗

Definition

(Representation of sesquilinear form)

Let

V, W

be finite-dimensional

complex vector spaces with basis (

, ··· , v

) and (

, ··· , w

) respectively,

and

V × W → C

be a sesquilinear form. Then the matrix representing

with respect to these bases is

= φ(v

, w

for 1 ≤ i ≤ n, 1 ≤ j ≤ m.

As usual, this determines the whole sesquilinear form. This follows from

the analogous fact for the bilinear form on

V ×W → C

. Let

and

W =

. Then we have

φ(v, w) =

i,j

φ(v

, w

) = λ

†

Aµ.

We now want the right definition of symmetric sesquilinear form. We cannot

just require

(

v, w

) =

(

w, v

), since

is linear in the second variable and

conjugate linear on the first variable. So in particular, if

(

v, w

)

= 0, we have

φ(iv, w) 6= φ(v, iw).

Definition

(Hermitian sesquilinear form)

A sesquilinear form on

V × V

Hermitian if

φ(v, w) = φ(w, v).

Note that if

is Hermitian, then

(

v, v

) =

φ(v, v) ∈ R

for any

v ∈ V

. So

it makes sense to ask if it is positive or negative. Moreover, for any complex

number λ, we have

φ(λv, λv) = |λ|

φ(v, v).

So multiplying by a scalar does not change the sign. So it makes sense to talk

about positive (semi-)definite and negative (semi-)definite Hermitian forms.

We will prove results analogous to what we had for real symmetric bilinear

forms.

Lemma.

Let

V × V → C

be a sesquilinear form on a finite-dimensional

vector space over

, and (

, ··· , e

) a basis for

. Then

is Hermitian if and

only if the matrix A representing φ is Hermitian (i.e. A = A

†

Proof. If φ is Hermitian, then

= φ(e

, e

) = φ(e

, e

) = A

†

If A is Hermitian, then





= λ

†

Aµ = µ

†

λ = φ





So done.

Proposition

(Change of basis)

Let

be a Hermitian form on a finite di-

mensional vector space

; (

, ··· , e

) and (

, ··· , v

) are bases for

such

that

k=1

;

and

A, B

represent

with respect to (

, . . . , e

) and (

, ··· , v

) respectively.

Then

B = P

†

AP.

Proof. We have

= φ(v

, v

)

= φ





k,`=1

= (P

†

AP )

Lemma

(Polarization identity (again))

A Hermitian form

is determined

by the function ψ : v 7→ φ(v, v).

The proof this time is slightly more involved.

Proof. We have the following:

ψ(x + y) = φ(x, x) + φ(x, y) + φ(y, x) + φ(y, y)

−ψ(x − y) = −φ(x, x) + φ(x, y) + φ(y, x) − φ(y, y)

iψ(x − iy) = iφ(x, x) + φ(x, y) − φ(y, x) + iφ(y, y)

−iψ(x + iy) = −iφ(x, x) + φ(x, y) − φ(y, x) − iφ(y, y)

φ(x, y) =

(ψ(x + y) − ψ(x − y) + iψ(x − iy) − iψ(x + iy)).

Theorem

(Hermitian form of Sylvester’s law of inertia)

Let

be a finite-

dimensional complex vector space and

a hermitian form on

. Then there

exists unique non-negative integers p and q such that φ is represented by





0 0

0 −I

0 0 0





with respect to some basis.

Proof. Same as for symmetric forms over R.

8 Inner product spaces

Welcome to the last chapter, where we discuss inner products. Technically, an

inner product is just a special case of a positive-definite symmetric bilinear or

hermitian form. However, they are usually much more interesting and useful.

Many familiar notions such as orthogonality only make sense when we have an

inner product.

In this chapter, we will adopt the convention that

always means either

or C, since working with other fields doesn’t make much sense here.

8.1 Definitions and basic properties

Definition

(Inner product space)

Let

be a vector space. An inner product

is a positive-definite symmetric bilinear/hermitian form. We usually write

(x, y) instead of φ(x, y).

A vector space equipped with an inner product is an inner product space.

We will see that if we have an inner product, then we can define lengths and

distances in a sensible way.

Example.

(i) R

or C

with the usual inner product

(x, y) =

i=1

¯x

forms an inner product space.

In some sense, this is the only inner product on finite-dimensional spaces,

by Sylvester’s law of inertia. However, we would not like to think so, and

instead work with general inner products.

(ii)

Let

([0

, F

) be the vector space of real/complex valued continuous

functions on [0, 1]. Then the following is an inner product:

(f, g) =

f(t)g(t) dt.

(iii)

More generally, for any

: [0

→ R

continuous, we can define the inner

product on C([0, 1], F) as

(f, g) =

w(t)

f(t)g(t) dt.

If V is an inner product space, we can define a norm on V by

kvk =

(v, v).

This is just the usual notion of norm on

and

. This gives the notion of

length in inner product spaces. Note that

kvk >

0 with equality if and only if

v = 0.

Note also that the norm

k · k

determines the inner product by the polarization

identity.

We want to see that this indeed satisfies the definition of a norm, as you might

have seen from Analysis II. To prove this, we need to prove the Cauchy-Schwarz

inequality.

Theorem

(Cauchy-Schwarz inequality)

Let

be an inner product space and

v, w ∈ V . Then

|(v, w)| ≤ kvkkwk.

Proof.

= 0, then this is trivial. Otherwise, since the norm is positive

definite, for any λ, we get

0 ≤ (v − λw, v − λw) = (v, v) −

λ(w, v) − λ(v, w) + |λ|

(w, w).

We now pick a clever value of λ. We let

λ =

(w, v)

(w, w)

Then we get

0 ≤ (v, v) −

|(w, v)|

(w, w)

−

|(w, v)|

(w, w)

|(w, v)|

(w, w)

So we get

|(w, v)|

≤ (v, v)(w, w).

So done.

With this, we can prove the triangle inequality.

Corollary

(Triangle inequality)

Let

be an inner product space and

v, w ∈ V

Then

kv + wk ≤ kv k + kwk.

Proof. We compute

kv + wk

= (v + w, v + w)

= (v, v) + (v, w) + (w, v) + (w, w)

≤ kvk

+ 2kvkkwk + kwk

= (kvk + kwk)

So done.

The next thing we do is to define orthogonality. This generalizes the notion

of being “perpendicular”.

Definition

(Orthogonal vectors)

Let

be an inner product space. Then

v, w ∈ V are orthogonal if (v, w) = 0.

Definition

(Orthonormal set)

Let

be an inner product space. A set

i ∈ I} is an orthonormal set if for any i, j ∈ I, we have

, v

) = δ

It should be clear that an orthonormal set must be linearly independent.

Definition

(Orthonormal basis)

Let

be an inner product space. A subset of

V is an orthonormal basis if it is an orthonormal set and is a basis.

In an inner product space, we almost always want orthonormal basis only. If

we pick a basis, we should pick an orthonormal one.

However, we do not know there is always an orthonormal basis, even in the

finite-dimensional case. Also, given an orthonormal set, we would like to extend

it to an orthonormal basis. This is what we will do later.

Before that, we first note that given an orthonormal basis, it is easy to find

the coordinates of any vector in this basis. Suppose

is a finite-dimensional

inner product space with an orthonormal basis v

, ··· , v

. Given

v =

i=1

we have

, v) =

i=1

, v

) = λ

So v ∈ V can always be written as

i=1

, v)v

Lemma

(Parseval’s identity)

Let

be a finite-dimensional inner product space

with an orthonormal basis v

, ··· , v

, and v, w ∈ V . Then

(v, w) =

i=1

, v)(v

, w).

In particular,

kvk

i=1

|(v

, v)|

This is something we’ve seen in IB Methods, for infinite dimensional spaces.

However, we will only care about finite-dimensional ones now.

Proof.

(v, w) =





i=1

, v)v

j=1

, w)v





i,j=1

, v)(v

, w)(v

, v

)

i,j=1

, v)(v

, w)δ

i=1

, v)(v

, w).

8.2 Gram-Schmidt orthogonalization

As mentioned, we want to make sure every vector space has an orthonormal

basis, and we can extend any orthonormal set to an orthonormal basis, at least

in the case of finite-dimensional vector spaces. The idea is to start with an

arbitrary basis, which we know exists, and produce an orthonormal basis out of

it. The way to do this is the Gram-Schmidt process.

Theorem

(Gram-Schmidt process)

Let

be an inner product space and

, e

, ···

a linearly independent set. Then we can construct an orthonormal set

, v

, ··· with the property that

, ··· , v

i = he

, ··· , e

for every k.

Note that we are not requiring the set to be finite. We are just requiring it

to be countable.

Proof.

We construct it iteratively, and prove this by induction on

. The base

case k = 0 is contentless.

Suppose we have already found v

, ··· , v

that satisfies the properties. We

define

k+1

= e

k+1

−

i=1

, e

i+1

We want to prove that this is orthogonal to all the other

’s for

i ≤ k

. We have

, u

k+1

) = (v

, e

k+1

) −

i=1

, e

k+1

)δ

= (v

, e

k+1

) − (v

, e

k+1

) = 0.

So it is orthogonal.

We want to argue that u

k+1

is non-zero. Note that

, ··· , v

, u

k+1

i = hv

, ··· , v

, e

k+1

since we can recover

k+1

from

, ··· , v

and

k+1

by construction. We also

know

, ··· , v

, e

k+1

i = he

, ··· , e

, e

k+1

by assumption. We know

, ··· , e

, e

k+1

has dimension

+ 1 since the

are

linearly independent. So we must have

k+1

non-zero, or else

, ··· , v

will

be a set of size

spanning a space of dimension

+ 1, which is clearly nonsense.

Therefore, we can define

k+1

Then

, ··· , v

k+1

is orthonormal and

, ··· , v

k+1

, ··· , e

k+1

as re-

quired.

Corollary.

is a finite-dimensional inner product space, then any orthonor-

mal set can be extended to an orthonormal basis.

Proof.

Let

, ··· , v

be an orthonormal set. Since this is linearly independent,

we can extend it to a basis (v

, ··· , v

, x

k+1

, ··· , x

We now apply the Gram-Schmidt process to this basis to get an orthonormal

basis of

, say (

, ··· , u

). Moreover, we can check that the process does not

modify our v

, ··· , v

, i.e. u

= v

for 1 ≤ i ≤ k. So done.

Definition

(Orthogonal internal direct sum)

Let

be an inner product space

and

, V

≤ V

. Then

is the orthogonal internal direct sum of

and

if it

is a direct sum and V

and V

are orthogonal. More precisely, we require

(i) V = V

+ V

(ii) V

∩ V

= 0

(iii) (v

, v

) = 0 for all v

∈ V

and v

∈ V

Note that condition (iii) implies (ii), but we write it for the sake of explicitness.

We write V = V

⊥ V

Definition

(Orthogonal complement)

W ≤ V

is a subspace of an inner

product space V , then the orthogonal complement of W in V is the subspace

⊥

= {v ∈ V : (v, w) = 0, ∀w ∈ W }.

It is true that the orthogonal complement is a complement and orthogonal,

i.e. V is the orthogonal direct sum of W and W

⊥

Proposition.

Let

be a finite-dimensional inner product space, and

W ≤ V

Then

V = W ⊥ W

⊥

Proof.

There are three things to prove, and we know (iii) implies (ii). Also, (iii)

is obvious by definition of W

⊥

. So it remains to prove (i), i.e. V = W + W

⊥

Let w

, ··· , w

be an orthonormal basis for W , and pick v ∈ V . Now let

w =

i=1

, v)w

Clearly, we have

w ∈ W

. So we need to show

v − w ∈ W

⊥

. For each

, we can

compute

, v − w) = (w

, v) −

i=1

, v)(w

, w

)

= (w

, v) −

i=1

, v)δ

= 0.

Hence for any λ

, we have



, v − w



= 0.

So we have v − w ∈ W

⊥

. So done.

Definition

(Orthogonal external direct sum)

Let

, V

be inner product spaces.

The orthogonal external direct sum of

and

is the vector space

⊕V

with

the inner product defined by

+ v

, w

+ w

) = (v

, w

) + (v

, w

with v

, w

∈ V

, v

, w

∈ V

Here we write v

+ v

∈ V

⊕ V

instead of (v

, v

) to avoid confusion.

This external direct sum is equivalent to the internal direct sum of

{

(

, 0

) :

∈ V

} and {(0, v

) : v

∈ V

Proposition.

Let

be a finite-dimensional inner product space and

W ≤ V

Let (

, ··· , e

) be an orthonormal basis of

. Let

be the orthonormal

projection of

onto

, i.e.

V → W

is a function that satisfies

ker π

⊥

π|

= id. Then

(i) π is given by the formula

π(v) =

i=1

, v)e

(ii) For all v ∈ V, w ∈ W , we have

kv − π(v)k ≤ kv − wk,

with equality if and only if

(

) =

. This says

(

) is the point on

that is closest to v.

⊥

π(v)

Proof.

(i) Let v ∈ V , and define

w =

i=1

, v)e

We want to show this is

(

). We need to show

v − w ∈ W

⊥

. We can

compute

, v − w) = (e

, v) −

i=1

, v)(e

, e

) = 0.

So v − w is orthogonal to every basis vector in w, i.e. v − w ∈ W

⊥

.So

π(v) = π(w) + π(v − w) = w

as required.

(ii)

This is just Pythagoras’ theorem. Note that if

and

are orthogonal,

then

kx + yk

= (x + y, x + y)

= (x, x) + (x, y) + (y, x) + (y.y)

= kxk

+ kyk

We apply this to our projection. For any w ∈ W , we have

kv − wk

= kv − π(v)k

+ kπ(v) − wk

≥ kv − π(v)k

with equality if and only if kπ(v) − wk = 0, i.e. π(v) = w.

8.3 Adjoints, orthogonal and unitary maps

Adjoints

Lemma.

Let

and

be finite-dimensional inner product spaces and

V →

is a linear map. Then there exists a unique linear map

∗

W → V

such that

(αv, w) = (v, α

∗

w) (∗)

for all v ∈ V , w ∈ W .

Proof.

There are two parts. We have to prove existence and uniqueness. We’ll

first prove it concretely using matrices, and then provide a conceptual reason of

what this means.

Let (

, ··· , v

) and (

, ··· , w

) be orthonormal basis for

and

Suppose α is represented by A.

To show uniqueness, suppose

∗

W → V

satisfies (

αv, w

) = (

v, α

∗

) for

all v ∈ V , w ∈ W , then for all i, j, by definition, we know

, α

∗

)) = (α(v

), w

)

, w

) =

So we get

∗

) =

, α

∗

))v

Hence α

∗

must be represented by A

†

. So α

∗

is unique.

To show existence, all we have to do is to show

†

indeed works. Now let

∗

be represented by

†

. We can compute the two sides of (

∗

) for arbitrary

v, w

We have





i,j

(α(v

), w

)

i,j

, w

i,j

We can compute the other side and get



, α

∗





i,j

†

i,j

So done.

What does this mean, conceptually? Note that the inner product

defines

an isomorphism

V →

∗

v 7→

(

·, v

). Similarly, we have an isomorphism

W →

∗

. We can then put them in the following diagram:

V W

∗

∼

∗

Then

∗

is what fills in the dashed arrow. So

∗

is in some sense the “dual” of

the map α.

Definition (Adjoint). We call the map α

∗

the adjoint of α.

We have just seen that if

is represented by

with respect to some or-

thonormal bases, then α

∗

is represented by A

†

Definition

(Self-adjoint)

Let

be an inner product space, and

α ∈ End

(

Then α is self-adjoint if α = α

∗

, i.e.

(α(v), w) = (v, α(w))

for all v, w.

Thus if

with the usual inner product, then

A ∈ Mat

(

) is self-

adjoint if and only if it is symmetric, i.e.

. If

with the usual

inner product, then

A ∈ Mat

(

) is self-adjoint if and only if

is Hermitian,

i.e. A = A

†

Self-adjoint endomorphisms are important, as you may have noticed from IB

Quantum Mechanics. We will later see that these have real eigenvalues with an

orthonormal basis of eigenvectors.

Orthogonal maps

Another important class of endomorphisms is those that preserve lengths. We

will first do this for real vector spaces, since the real and complex versions have

different names.

Definition

(Orthogonal endomorphism)

Let

be a real inner product space.

Then α ∈ End(V ) is orthogonal if

(α(v), α(w)) = (v, w)

for all v, w ∈ V .

By the polarization identity,

is orthogonal if and only if

kα

(

)

kvk

for

all v ∈ V .

A real square matrix (as an endomorphism of

with the usual inner product)

is orthogonal if and only if its columns are an orthonormal set.

There is also an alternative way of characterizing these orthogonal maps.

Lemma.

Let

be a finite-dimensional space and

α ∈ End

(

). Then

orthogonal if and only if α

−1

= α

∗

Proof. (⇐) Suppose α

−1

= α

∗

. If α

−1

= α

∗

, then

(αv, αv) = (v, α

∗

αv) = (v, α

−1

αv) = (v, v).

(

⇒

) If

is orthogonal and (

, ··· , v

) is an orthonormal basis for

, then for

1 ≤ i, j ≤ n, we have

= (v

, v

) = (αv

, αv

) = (v

, α

∗

αv

So we know

∗

α(v

) =

i=1

, α

∗

αv

))v

= v

So by linearity of α

∗

α, we know α

∗

α = id

. So α

∗

= α

−1

Corollary. α ∈ End

(

) is orthogonal if and only if

is represented by an

orthogonal matrix, i.e. a matrix

such that

, with respect to

any orthonormal basis.

Proof.

Let (

, ··· , e

) be an orthonormal basis for

. Then suppose

represented by

. So

∗

is represented by

. Then

∗

−1

if and only if

= A

A = I.

Definition

(Orthogonal group)

Let

be a real inner product space. Then the

orthogonal group of V is

O(V ) = {α ∈ End(V ) : α is orthogonal}.

It follows from the fact that

∗

−1

that

is invertible, and it is clear

from definition that O(

) is closed under multiplication and inverses. So this is

indeed a group.

Proposition.

Let

be a finite-dimensional real inner product space and

, ··· , e

) is an orthonormal basis of V . Then there is a bijection

O(V ) → {orthonormal basis for V }

α 7→ (α(e

, ··· , e

)).

This is analogous to our result for general vector spaces and general bases,

where we replace O(V ) with GL(V ).

Proof. Same as the case for general vector spaces and general bases.

Unitary maps

We are going to study the complex version of orthogonal maps, known as unitary

maps. The proofs are almost always identical to the real case, and we will not

write the proofs again.

Definition

(Unitary map)

Let

be a finite-dimensional complex vector space.

Then α ∈ End(V ) is unitary if

(α(v), α(w)) = (v, w)

for all v, w ∈ V .

By the polarization identity,

is unitary if and only if

kα

(

)

kvk

for all

v ∈ V .

Lemma.

Let

be a finite dimensional complex inner product space and

α ∈

End(V ). Then α is unitary if and only if α is invertible and α

∗

= α

−1

Corollary. α ∈ End

(

) is unitary if and only if

is represented by a unitary

matrix A with respect to any orthonormal basis, i.e. A

−1

= A

†

Definition

(Unitary group)

Let

be a finite-dimensional complex inner prod-

uct space. Then the unitary group of V is

U(V ) = {α ∈ End(V ) : α is unitary}.

Proposition.

Let

be a finite-dimensional complex inner product space. Then

there is a bijection

U(V ) → {orthonormal basis of V }

α 7→ {α(e

), ··· , α(e

)}.

8.4 Spectral theory

We are going to classify matrices in inner product spaces. Recall that for general

vector spaces, what we effectively did was to find the orbits of the conjugation

action of

(

) on

Mat

(

). If we have inner product spaces, we will want to

look at the action of

(

) or

(

) on

Mat

(

). In a more human language,

instead of allowing arbitrary basis transformations, we only allow transforming

between orthonormal basis.

We are not going to classify all endomorphisms, but just self-adjoint and

orthogonal/unitary ones.

Lemma.

Let

be a finite-dimensional inner product space, and

α ∈ End

(

)

self-adjoint. Then

(i) α has a real eigenvalue, and all eigenvalues of α are real.

(ii) Eigenvectors of α with distinct eigenvalues are orthogonal.

Proof. We are going to do real and complex cases separately.

(i)

Suppose first

is a complex inner product space. Then by the fundamental

theorem of algebra,

has an eigenvalue, say

. We pick

v ∈ V \ {

}

such

that αv = λv. Then

λ(v, v) = (λv, v) = (αv, v) = (v, αv) = (v, λv) = λ(v, v).

Since v 6= 0, we know (v, v) 6= 0. So λ =

λ.

For the real case, we pretend we are in the complex case. Let

, ··· , e

an orthonormal basis for

. Then

is represented by a symmetric matrix

(with respect to this basis). Since real symmetric matrices are Hermitian

viewed as complex matrices, this gives a self-adjoint endomorphism of

By the complex case,

has real eigenvalues only. But the eigenvalues of

A are the eigenvalues of α and M

(t) = M

(t). So done.

Alternatively, we can prove this without reducing to the complex case. We

know every irreducible factor of

(

) in

[

] must have degree 1 or 2,

since the roots are either real or come in complex conjugate pairs. Suppose

f(t) were an irreducible factor of degree 2. Then





(α) 6= 0

since it has degree less than the minimal polynomial. So there is some

v ∈ V such that





(α)(v) 6= 0.

So it must be that

(

)(

) =

. Let

hv, α

(

)

. Then this is an

α-invariant subspace of V since f has degree 2.

Now

α|

∈ End

(

) is self-adjoint. So if (

, e

) is an orthonormal basis of

U, then α is represented by a real symmetric matrix, say



a b

b a



But then

α|

(

) = (

t − a

)

−b

, which has real roots, namely

a ± b

. This

is a contradiction, since M

α|

= f, but f is irreducible.

(ii)

Now suppose

αv

λv

αw

µw

and

λ 6

. We need to show (

v, w

) = 0.

We know

(αv, w) = (v, αw)

by definition. This then gives

λ(v, w) = µ(v, w)

Since λ 6= µ, we must have (v, w) = 0.

Theorem.

Let

be a finite-dimensional inner product space, and

α ∈ End

(

)

self-adjoint. Then V has an orthonormal basis of eigenvectors of α.

Proof.

By the previous lemma,

has a real eigenvalue, say

. Then we can find

an eigenvector v ∈ V \{0} such that αv = λv.

Let U = hvi

⊥

. Then we can write

V = hvi ⊥ U.

We now want to prove α sends U into U. Suppose u ∈ U . Then

(v, α(u)) = (αv, u) = λ(v, u) = 0.

So α(u) ∈ hvi

⊥

= U. So α|

∈ End(U ) and is self-adjoint.

By induction on

dim V

has an orthonormal basis (

, ··· , v

) of

eigen-

vectors. Now let

kvk

Then (v

, v

, ··· , v

) is an orthonormal basis of eigenvectors for α.

Corollary.

Let

be a finite-dimensional vector space and

self-adjoint. Then

V is the orthogonal (internal) direct sum of its α-eigenspaces.

Corollary.

Let

A ∈ Mat

(

) be symmetric. Then there exists an orthogonal

matrix P such that P

AP = P

−1

AP is diagonal.

Proof.

Let (

·, ·

) be the standard inner product on

. Then

is self-adjoint

as an endomorphism of

. So

has an orthonormal basis of eigenvectors for

A, say (v

, ··· , v

). Taking P = (v

··· v

) gives the result.

Corollary.

Let

be a finite-dimensional real inner product space and

V × V → R

a symmetric bilinear form. Then there exists an orthonormal basis

(

, ··· , v

) for

with respect to which

is represented by a diagonal matrix.

Proof.

Let (

, ··· , u

) be any orthonormal basis for

. Then

is represented

by a symmetric matrix

. Then there exists an orthogonal matrix

such that

is diagonal. Now let

. Then (

, ··· , v

) is an orthonormal

basis since

, v

) =





, u

= [P

P ]

= δ

Also, ψ is represented by P

AP with respect to (v

, ··· , v

Note that the diagonal values of

are just the eigenvalues of

. So the

signature of

is just the number of positive eigenvalues of

minus the number

of negative eigenvalues of A.

Corollary.

Let

be a finite-dimensional real vector space and

φ, ψ

symmetric

bilinear forms on

such that

is positive-definite. Then we can find a basis

(

, ··· , v

) for

such that both

and

are represented by diagonal matrices

with respect to this basis.

Proof.

We use

to define an inner product. Choose an orthonormal basis for

(equipped with

) (

, ··· , v

) with respect to which

is diagonal. Then

represented by I with respect to this basis, since ψ(v

, v

) = δ

. So done.

Corollary.

A, B ∈ Mat

(

) are symmetric and

is positive definitive (i.e.

Av >

0 for all

v ∈ R

\ {

}

). Then there exists an invertible matrix

such

that Q

AQ and Q

BQ are both diagonal.

We can deduce similar results for complex finite-dimensional vector spaces,

with the same proofs. In particular,

Proposition.

(i)

A ∈ Mat

(

) is Hermitian, then there exists a unitary matrix

U ∈

Mat

−1

AU = U

†

is diagonal.

(ii)

is a Hermitian form on a finite-dimensional complex inner product

space V , then there is an orthonormal basis for V diagonalizing ψ.

(iii)

φ, ψ

are Hermitian forms on a finite-dimensional complex vector space

and

is positive definite, then there exists a basis for which

and

are

diagonalized.

(iv)

Let

A, B ∈ Mat

(

) be Hermitian, and

positive definitive (i.e.

†

Av >

for

v ∈ V \{

}

). Then there exists some invertible

such that

†

and

†

BQ are diagonal.

That’s all for self-adjoint matrices. How about unitary matrices?

Theorem.

Let

be a finite-dimensional complex vector space and

α ∈ U

(

)

be unitary. Then V has an orthonormal basis of α eigenvectors.

Proof.

By the fundamental theorem of algebra, there exists

v ∈ V \ {

}

and

λ ∈ C such that αv = λv. Now consider W = hvi

⊥

. Then

V = W ⊥ hvi.

We want to show

restricts to a (unitary) endomorphism of

. Let

w ∈ W

We need to show α(w) is orthogonal to v. We have

(αw, v) = (w, α

−1

v) = (w, λ

−1

v) = 0.

(

)

∈ W

and

α|

∈ End

(

). Also,

α|

is unitary since

is. So by

induction on

dim V

has an orthonormal basis of

eigenvectors. If we add

v/kvk

to this basis, we get an orthonormal basis of

itself comprised of

eigenvectors.

This theorem and the analogous one for self-adjoint endomorphisms have a

common generalization, at least for complex inner product spaces. The key fact

that leads to the existence of an orthonormal basis of eigenvectors is that

and

∗

commute. This is clearly a necessary condition, since if

is diagonalizable, then

∗

is diagonal in the same basis (since it is just the transpose (and conjugate)),

and hence they commute. It turns out this is also a sufficient condition, as you

will show in example sheet 4.

However, we cannot generalize this in the real orthogonal case. For example,



cos θ sin θ

−sin θ cos θ



∈ O(R

)

cannot be diagonalized (if

θ 6∈ πZ

). However, in example sheet 4, you will find a

classification of

(

), and you will see that the above counterexample is the

worst that can happen in some sense.