Background

Sketch of Theorem 2

If A is
singular (i.e. rank A < n)

If A is
invertible,

Proof of Theorem

Write

QED

September-12-11

9:34 AM

Fields

Basic
theory of vector spaces works over any field.

Other fields if
convenient

Algebraically Closed

Fundamental Theorem of Algebra

Determinants

Determinant is n-linear

Determinant is antisymmetric

⇒ (except if 1+1=0)

Theorem 1

Theorem 2

Linear Transformation and Matrices

Theorem

Eigenvalues

Example

Example

2 is an
eigenvalue

So it is
invertible, so rank is 0, so no more eigenvalues.

Proof of Theorem

Example

Example

Eigenvalues
are 3, 6

Only
2-dimensions of eigenvectors!

Proof of 3rd Corollary

Proof of Proposition

My Proofs

Already
have

Then

This is not
unique, a contradiction, so

QED

His Proof

3⇒ 1

Proof of Corollary

Suppose

■

9:30 AM

Eigenvalue (a.k.a. characteristic value)

Eigenvector

Eigenspace

Theorem

Characteristic Polynomial

The
characteristic polynomial of T is

Note

Monic:
coefficient on highest degree is 1

Spectrum

Corollary

Corollary

Corollary

Similar
transformations have the same spectrum

Direct Sums

Proposition

then TFAE
(the following are equivalent)

Corollary

Diagonalization

Proof of Proposition

(By
Proposition in previous lecture)

Example

Question

Example

Example

Need two
linearly independent eigenvectors to diagonalize T - NOT POSSIBLE.

Proof

1⇒ 2

2⇒ 1

put them together,
get a basis for V consisting of eigenvectors ⇒ diagonalizable

Proof of Corollary

September-16-11

9:29 AM

Proposition

Diagonalizable

is
diagonal.

Note

Nullity

Theorem

TFAE

Corollary

If T has n
distinct eigenvalues, then T is diagonalizable.

Linear
Recursion

Example *

Using
Matlab got

Change of
basis matrix:

Example: Fibonacci Sequence

September-19-11

10:09
AM

Computational Device

If D is the
diagonal matrix of T

Linear Recursion

linear
recursion

Triangular
Forms

Determinant of Upper Triangular

Alternate Proof

Types of Invariant Subspaces

Proof

Already
proved 1⇒ 2, 1⇒ 3, and 3⇒ 1

Express T
in this basis.

September-21-11

9:31 AM

Upper Triangular

A matrix T
is upper triangular if

Triangular Determinant

Invariant Subspace

Theorem

Corollary

Cayley-Hamilton
Theorem

Example

Example

New bases

Proof of Cayley-Hamilton Theorem

Apply
triangular theorem, find basis to triangularize T.

So wlog, T
is triangular

Proceed by
induction on n.

n=1

From the
proof of triangularizability

September-23-11

9:56 AM

Cayley-Hamilton Theorem

Computational Aside

…

Ideals

Principal Ideal

Proof

*monic
generator is unique

Proof of Lemma

Example

Proof of Theorem

Remark

Possible Problem

Better Proof of Theorem

September-26-11

9:31 AM

Ideal

a
subspace

Principal Ideal

A principal
ideal is an ideal of the form

Theorem

Lemma

Corollary

Minimal Polynomial

Theorem

Diag. &
Nilpotent

Proof of Theorem

Rearrange
bases so

Proof of Lemma

Back to Theorem

By
hypothesis

Example of Nilpotent

Chose a
new basis

Example

September-28-11

9:45 AM

Theorem

T is
diagonalizable

Lemma

Nilpotent Matrices

Jordan
Nilpotent

Better Example

Complement Example

Find a Complement

Proof of Extension

Same proof:

Proof of Nimpotence note

Proof of Theorem

⇒

Look at

T is block
upper triangular with diagonal blocks = 0.

Example

September-30-11

9:41 AM

Jordan Nilpotent

The Jordan
nilpotent of order k is

We can get
a lot of nilpotent matrices by taking direct sums of Jordan nilpotents
(Canonical form) :

Complement

Extension

Note: Nimpotence

Theorem

Proof of Theorem

(taken from
Herstein, Intro to Alg)

Claim

U+W=V

Take a
maximal subspace W satisfying

2nd Proof

More
constructive

As first
proof, they are linearly independent

Claim

Proof

Claim

Proof

Our formula
was

Nilpotent
Jordan Canonical Form

October-03-11

9:37 AM

Theorem

Moreover,

The Algebra
of Nilpotent Transformation

October-05-11

10:05 AM

Equivalence Class

Algebra of Nilpotent Transformation Explanation

map is
linear, preserves product

Proof

Proof 1:

Proof 2:

General
case

Homomorphism

Modulo Polynomials

Check that
this is well-defined.

Algebra

An algebra
is a set A which is

Has an associative
multiplication

Distributive law

Algebra of Nilpotent Transformation

There is a
map from

This is a
homomorphism. i.e.

Lemma

Jordan
Forms

Proof of Corollary

Goal

Then T is
similar to

Proof of Lemma

October-07-11

10:09
AM

Jordan Block

Jordan Form

A Jordan
form is a direct sum of Jordan blocks

From the
nilpotent case, we get

Corollary

Moreover,

Lemma

Jordan Form
Theorem

Proof of Lemma

Example

Proof of Lemma

Claim

Proof of Lemma

Proof of Theorem

(Because of
direct sum, both terms are 0)

By
induction Hypothesis

October-12-11

9:32 AM

Lemma

Lemma

Lemma

Theorem

Corollary

Applications
of Jordan Forms

Proof of Jordan Form Theorem

Already
been done

Example

Look for
similarity classes of solutions

Count
similar classes:

= 10

Example

Example

Gives

or

The
similarity classes of these are the solutions

Example

Which
matrices have square roots?

So if A is
a square, the nilpotent part of A must come in pairs of size differing by 0
or 1

Is a square

October-14-11

9:43 AM

Jordan Form Theorem

Then T is
similar to

Note

Jordan
blocks can be used to answer similarity-invariant questions.

The Algebra
A(T)

The Algebra A(T) Description

by
induction.

Proof 1 of Proposition

Proof 2 of Proposition

Example of CRT

0

[0]

(0,0)

1

[1]

(1, 1)

2

[2]

(0, 2)

3

[3]

(1, 0)

4

[4]

(0, 1)

5

[5]

(1, 2)

Proof 3 of Proposition

October-17-11

9:30 AM

Generalized Eigenspace

Idempotent

Projections
are idempotent

Proposition

Chinese Remainder Theorem

CRT says

is a
bijection.

Chinese Remainder Theorem for Polynomials

Theorem

Jordan Form
Application

Example use of Jordan Form

Proof of Proposition

D is
diagonalizable

Uniqueness

Cyclic Vectors

Claim: v is
cyclic for T

October-19-11

9:25 AM

Proposition

Cyclic Vectors

T is cyclic if it has a cyclic vector.

Theorem

T is
cyclic

T has a single
Jordan block for each eigenvalue

Remark

Linear
Recursion Revisited

October-21-11

9:31 AM

Linear Recursion Formulae

Note

Case 2

Repeated
roots:

General
Solution

Solution
space is spanned by

Markov
Chains

Example

A
microorganism has 3 possible reproductive states: Male, Female, and Neuter.

Male one
day → M 2/3 time, N 1/3 time next day

Female one
day → F 1/2 time, N 1/2 time next day

Neuter one
day → M 1/6, F 1/2, N 1/3

Proof of Lemma

Proof of Theorem

On the
other hand

Proof of Corollary

Write

Similarly,

So each row
of L has all entries the same.

October-24-11

11:25
AM

Discrete State Space

A discrete process provides probabilities for
transition between states at discrete time intervals.

A process
is stationary if the transition
probabilities are time independent.

A discrete
stationary process is called a Markov process.

Regular Markov Process

i.e. It is
possible over time to move from any state to any other.

Lemma

Theorem

Euclidean Norm

Claim

Proof

By
Cauchy-Schwarz inequality

Corollary

Markov
Chain Example

Example: Hardy-Weinberg Law

Assume:

The
distribution is the same for both sexes

This gene
does not affect reproductive capability

GG
Gg         gg

GG
Gg         gg

Total
probability:

To find the
new probability distribution for the next generation, apply this to the
probability distribution of females.

So the new
transition matrix

In 2nd
generation, new probabilities:

Stabilizes
after 1 generation.

October-28-11

9:30 AM

Inner
Product Space

Conjugate in 2nd Variable

Conjugate
linear in second variable.

Sesquilinear
form (1/2 linear)

Examples

Check properties:

Linear in
1st variable

Symmetric

Linear in
1st variable

Symmetric

Proof of Theorem

1,2 easy

Example

Example

October-28-11

9:55 AM

Inner Product

Linear in first variable

Positive Definite

2 ⇒

Norm

Theorem

Cauchy-Schwarz
inequality

Triangle
inequality

Orthogonality

Proof of Lemma

Example

Fourier
Series

Proof of Lemma

Proof of Lemma

Proof of Theorem(Projection)

1.

2.

Proof of Corollary

If S is
finite, not problem

October-31-11

9:35 AM

Orthogonal

Orthonormal

Remarks

Pythagorean Law

Lemma

Note

Gram-Schmidt Process

Build an
o.n. set with the same span.

…

Lemma

Lemma

Projection

Theorem (Projection)

Then:

Corollary - Bessel's Inequality

Corollary

Canonical
Forms in Inner Product Spaces

November-02-11

9:33 AM

Proof of Theorem

What is T*?

Conjugate
transpose of T

So we can
define a linear transformation

Proof of Proposition

1.

2.

3.

4.

Proof of Theorem

Proof of Corollary

Theorem

Adjoint

Proposition

Hermitian (Self-Adjoint)

Reason:

This is
basis independent.

Theorem

Corollary

then there is an orthonormal basis ξ such that

Unitary
Maps

Proof of Theorem

1 ⇒ 2a By
definition

2a ⇒ 2b

2b ⇒ 2a

Assignment
5 #5a

2a ⇒ 3a

3a ⇒ 3b
Obvious

3b ⇒ a

Proof of Proposition

3nd and 2rd
statements are clearly equivalent.

U is
invertible and

November-04-11

Unitary and Orthogonal Maps

Theorem

U is
unitary

U
preserves inner product

U is isometric
(preserves norm)

U sends
every orthonormal basis of V to an orthonormal basis for W

U sends some
orthonormal basis of V to an orthonormal basis of W

Remark

Proposition

Unitarily Equivalent

Corollary

Then U is
unitary (takes one orthonormal basis to another) and

Normal Maps

Example of Normal Maps

If D is diagonal
w.r.t an orthonormal basis

Proof of Theorem

Proof of Corollary

Proof of Corollary

Proof of Corollary

Example

November-07-11

9:40 AM

Definition

Theorem

There is an
orthonormal basis which diagonalizes T.

Corollary

If T is
normal and

Corollary

If U is
unitary, then

and U is
diagonalizable w.r.t. some o.n. basis.

Corollary

Corollary

Rank 1 Matrices

Polar
Decomposition

Proof of Proposition

Proof of Proposition

1⇒2

Claim:

Claim

Proof of Claim

4⇒ 2

Proof of Polar Decomposition Theorem

Claim

Proof

Claim

Remark

November-09-11

9:30 AM

Complex

Positive

Proposition

Square Root

Fact (Homework)

Partial Isometry

Examples

Proposition

Theorem (Polar Decomposition)

S-Numbers

Geometry of
how T acts

If
considering the action on a unit sphere, T stretches it onto an ellipsoid
(axis length defined by s-numbers). U is a partial rotation in space.

Least
Square Approximation

Example

y

ax

7

3

1.6

1.86

9

2

2.1

1.94

5

5

2.0

2.02

4

6

2.2

2.10

3

1

0.8

0.73

3

2

1.1

0.98

November-11-11

9:30 AM

…

...

...

...

Problem
becomes

Claim

Proof

Sesquilinear
Forms

Proof

Proof of Principal Axis Theorem

A is
diagonalizable w.r.t orthonormal basis

November-11-11

10:09
AM

Sesquilinear Form

Definitions

Theorem

Principal Axis Theorem

Symmetric Quadratic Form

Diagonalization

Again, this
quadratic form can be diagonalized

Conics

Formula of an Ellipse

General Conic

Diagonalize
w.r.t. orthonormal basis:

So

The
equation

becomes

Translate
to eliminate constants

Rotate by U
to get

November-14-11

10:07
AM

Ellipse

Hyperbola

Parabola

Focus and
line. The set of points equidistant to focus and line.

Duality

Dual Space Basis

Proof of Proposition

Proof of Theorem

November-16-11

10:00
AM

Dual Space

Kronecker Delta

Proposition

Note

Thus there
is a natural linear map

This is
linear.

Theorem

Remark

This fails
dramatically for infinite dimensional vectors spaces.

Example

Isomorphism

V is reflexive

Duality on
Inner Product Spaces

Proof

Proof of Corollary

So get:

To get
equality, take

Proof of Proposition

1.

2.

3.

Claim:

November-18-11

9:31 AM

Theorem

Corollary

Notation

Definition

Let V be a
finite dimensional vector space.

This is the
annihilator of S

Proposition

Relationship between perps.

H inner
product space

Transpose

Proof of Claim

Proof of Claim

Proof of Theorem

1

The matrix
of the transpose is the transpose of the matrix.

2

3

4

Since

November-21-11

9:39 AM

Transpose Map

Claim

Claim

"transpose"
is a linear map

Theorem

Quotient
Spaces

Proof of Well Definition

Proof of Proposition

Proof of Theorem

The
connection is given by :

November-21-11

10:02
AM

Quotient Space

Proposition

Theorem

Relations

Convex Sets

Proof of Proposition

1.

2.

Claim

Suppose

If true for
k then

So the
convex combination of two convex combination of two convex combinations of
points in S is a convex combinations of points in S

Proof of Theorem

Claim

Proof of Corollary

f is
continuous

The
continuous image of a compact set is compact (by EVT)

November-23-11

9:33 AM

Convexity

Hyperplane

Proposition

The
intersection of convex sets is convex.

Theorem (Carathéodory)

Remark

Corollary

Remark: From Calculus

Heine-Bore Theorem

Extreme Value theorem

Convexity

November-25-11

9:32 AM

Theorem

Separation Theorem

Corollary

If C is a closed subset of V then C is the intersection of
all closed half spaces which contain it.

Proof

So f
achieves its minimum value by the extreme value theorem.

Uniqueness

Alternatively

Inequality
is Cauchy-Schwartz and must hold with equality

So the
closest point is unique.,

Claim

Proof of Separation Theorem

Proof of Corollary

Normed
Vector Spaces

Examples

1

2

Satisfies
1, 2

3

Satisfies
1, 2

4

Satisfies
1, 2

Satisfies 3
but hard to prove

Does not
satisfy 3

Proof of Proposition

Balanced
follows from 2

Convex
follows from 3, 2

Proof of Lemma

This is a
Lipschitz function.

Proof of Theorem

T is
continuous, S is compact so by Extreme Value Theorem the minimum values is
attained:

Proof of Corollary

November-28-11

9:30 AM

Norm

Unit Ball

Proposition

Example

1)

2)

3)

Special Cases

Lemma

V finite
dimensional normal space.

Then T is
uniformly continuous

Theorem

V finite
dimensional normal vector space

Equivalent

Corollary

If V is a
finite dimensional normed vector space then any two norms on V are
equivalent.

Convergence

Corollary
says that convergence in a finite dimensional normal space is independent of
choice of the norm.

Norms

Proof of Theorem

Proof of Corollary

Proof of Quotient Norm

Proof of Lemma

Proof of Theorem

So we have
an isometric isomorphism

Proof of Corollary

November-30-11

9:30 AM

V normed
vector space

Theorem

Corollary

Quotient Norm

Proposition

The
quotient norm is a norm.

Question

These are
linear isomorphisms.

Are they
isometric when V is normed?

Lemma

Theorem

Corollary

Norms in
Matrices

Examples

In
particular, this definition does not depend on choice of o.n. basis.

Proof of Lemma 1

Proof of Corollary

Proof of Lemma 2

Proof of Corollary

Other side
is similar.

Proof of Corollary2

Other side
is similar

Proof of Theorem

Proof of Remark 1

December-02-11

9:53 AM

Matrix Norm

Trace Norm

Polar
decomposition

Lemma 1

Corollary

Lemma 2

Corollary

Corollary2

Remark

Same
argument shows that

Theorem

Remark 1

Remark 2

Ky Fan Norms

is a
unitarily invariant matrix norm

Theorem (Ky Fan)