Math 344 Notes Fall '08 August 2008: This page uses MathML. It is viewed best with either Mozilla/Firefox/Netscape 7+ or Internet Explorer 6+ MathPlayer .
>
Martin Flashman's Courses
MATH 344 Linear Algebra Fall, 2008
Currently based on  Fall, 2003
Class Notes and Summaries
 week1 8-27 8-29 week 2 9-1 No Class 9-3 9-5 week 3 9-8 9-10 9-12 week 4 9-15 9-17 9-19 week 5 9-22 9-24 9-26 week 6 9-29 10-1 10-3 week 7 10-6 10-8 10-10 week 8 10-13 10-15 10-17 week 9[exam!] 10-20 10-22 10-24 week 10 10-27 10-29 10-31 week 11 11-3 11-5 11-7 week 12 11-10 11-12 11-14 week 13 11-17 11-19 11-21 week 14 NoClasses week 15 12-1 12-3 12-5 week 16 12-8 12-10 12-12

8-27 Completed discussion of course organization.
• Other texts in Linear Algebra:

• Finite Dimensional Vector Spaces by Paul Halmos
Linear algebra by Kenneth Hoffman and Ray Kunze.
Linear Algebra by Friedberg, Insel, and Spence
Linear Algebra by  Lang
Applied linear algebra by Ben Noble.
Linear Algebra and Its Applications by G. Strang
Topics in Abstract Algebra by I. Herstein
HSU Library Holdings
• On Proofs:

• How to Read and Do Proofs by D.Solow
The Keys to Advanced Mathematics by D. Solow
How to Solve It by G. Polya

• Motivational Question I:
• What can we say about powers of a square 2 by 2 matrix A and AX , where X is `(x,y)^{tr}`.
• What is the geometric interpretation of AX when X is  `(1,0)^{tr}` or `(0,1)^{tr}`?
• Examples:

A= (
 0 1 1 0

)
`A^n = I `  if `n` is even
`A^n =A` if `n` is odd.

A= (
 1 1 0 1

)

`A^n `  =
(
 1 n 0 1

)
Prove? [Use induction]

A  =
(
 r 0 0 s

)

1. r = 1/2 s= 1/2   Discussion: Same if  0< |r|, |s| < 1

`A^n`  `->`
(
 0 0 0 0

)
2. r= 2, s = 1/2  Discussion: ....
3. r= 1, s = -1   Discussion: `A^n = I `  if `n` is even; `A^n =A` if  `n `is odd

8-29
• Warm up:  Find the eigenvalues for

A= (

 0 1 1 0

)
• Complex numbers: C = { z = a+bi, where a and b are real numbers}

• The arithmetic of C. `||z|| = sqrt(a^2 + b^2) `
z = ||z||(cos(t) +i sin(t))    [called the "polar form" of the complex number]

The geometry of complex arithmetic:

If z = a+bi = ||z||(cos(t) +i sin(t)) and w  = c+di = ||w||(cos(s) +i sin(s)) then

z+w = (a+c)+(b+d)i which corresponds geometrically to the "vector " sum  of z and w in the plane, and

zw = ||z||(cos(t) +i sin(t)) ||w||(cos(s) +i sin(s))=  ||z|| ||w|| (cos(t) +i sin(t))(cos(s) +i sin(s))
= ||z|| ||w|| (cos(t) cos(s) - sin(t)sin(s) + (sin(t) cos(s) + sin(s)cos(t)) i)
= ||z|| ||w|| (cos(t+s) + sin(t+s) i)

So you use the product of the magnitudes of z and w to determine the magnitude of the product and use the sum of the angles to determine the angle of the product.

Powers of complex numbers.
Based on the previous result on products,
`z^n =  ||z||^n  (cos(nt) + sin(nt) i) `
If ||z||<1, then the powers of z will spiral into 0. If ||z||>1, then the powers of z will spiral outward without bound. If ||z||=1 and z is not 1, the the powers of Z will oscillate around the circle of radius 1 without having any limit.

Notation: cos(t) + i sin(t) is somtimes written as cis(t).
Note: If we consider the series for ex = 1 + x + x2/2! +x3/3! + ...
then eix = 1 + ix + (ix)2/2! +(ix)3/3! + ... = 1 + ix -  x2/2! - ix3/3! + ...
... = cos(x) + i sin(x)
Thus ei*pi = cos(pi) + i sin(pi)= -1.  So ln(-1) = i *pi.
Furthermore:
`e^{a+bi} = e^a*e^{bi} = e^a ( cos (b) + sin(b) i) `

Matrices with complex number entries.
If r and s are complex numbers in the matrix A, then as n get large if ||r|| < 1 and ||s|| < 1 the powers of A will get close to the zero matrix ,  if r=s=1 the powers of A will always be A,  and otherwise the powers of A will diverge .

Polynomials with complex coefficients.
Because multiplication and addition make sense for complex numbers, we can consider polynomials with coefficients that are complex numbers and use a complex number for the variable, making a complex polynomial a function from the complex numbers to the complex numbers.
This can be visualized using one plane for the domain of the polynomial and a second plane for the co-domain, target, or range of the polynomial.

The Fundamental Theorem of Algebra: If f is a non constant  polynomial with complex number coefficients then there is at least on complex number z*  where f(z*) = 0.

For more on complex numbers see: Dave's Short Course on Complex Numbers,

9-3
• Fields: The structure used for "solving linear equations," finding inverses for matrices, and doing other parts of matrix algebra.

• Definition- Axioms See Fields.
Examples: R, Q, C, Z2, Zp, where p is a prime number, F4, {f where f is a rational function defined on all but a finite number of real numbers}, algebraic numbers = {z: z is a complex number which is the root of a polynomial with integer coefficients}.
• Polynomials with coefficients in a field. [We will study these in some detail later].
• Matrices with entries in a field.

• Discussion of the properties of a field with 4 elements- from the homework assignment.
• A few more properties of Fields:
• Suppose F is a field.
• If  a and b are in F and ab = 0 then either a =0 or b=0.

• Proof: Case 1. If a=0 then we are done.
Case 2. If a is not 0, then a has an inverse... c where ca=1. Then b=1b= (ca)b=  c(ab) = c0 = 0.
Thus either  a =0 or b=0. IRMC   [I rest my case.]
• If  a, b and c are in F a+b = a+c implies b=c.

• Proof: Let k be the element of the field where k + a = 0 Then
b = 0 + b = (k +a)+b =k +(a+b)= k +(a+c) =(k +a)+c = 0 + c = c.
• If  a, b and c are in F with  a not equal to 0 ab = ac implies b=c.

• Proof: Similar to the last result.
• Let  n·1 stand for  1 + 1 + 1 + ... + 1 with n summands. Either (i) for all n,  n·1 is not 0 in which case we say the field has "characteristic 0" , or (ii) for some n, n·1=0. In the case n·1=0, there is a smallest n for which n·1=0, in which case we say the field has "characteristic n". For example: R, Q, and C all have characteristic 0, while Z2, Zp, where p is a prime number, and any finite field such as  F4, all have a non zero characteristic.
• If the characteristic of F is not zero, then it is a prime number.

• Proof: If n is not a prime, n = rs with 1<r,s<n. Let a = 1+1+...+1 r times and b= 1+1+...+1 s times. Then ab=n·1=0, so either a = 0 or b = 0, contradicting the fact the n was supposed to be the SMALLEST natural number for which n·1=0. IRMC.
9-12
• Solving equations with fields:
Suppose F is a field and `alpha` and `beta` are elements of F and X is a variable. We say that the equation `alpha` X = `beta` has a solution in F if there is an element of F, `gamma` where `alpha gamma = beta`.
Proposition: If `alpha \ne 0` then  there is an element of F, `gamma`,  where `alpha gamma = beta`.
Preface: We did some work on the side to "solve" the equation.
This analysis did the work of finding the candidate for `gamma` and seeing it was in F.
Proof: Suppose `alpha  in F and alpha  \ne 0.`
Then by the field axioms, there is an element of F, `alpha^{-1}` where `alpha^{-1} alpha = 1`.
Let  `gamma = alpha^{-1} beta`. Then `alpha gamma = alpha (alpha^{-1} beta) = (alpha alpha^{-1}) beta = 1 beta = beta`. IRMC!
• Systems of linear equations:
One linear equation with n unknowns with coefficients in a field F:
`alpha_1,alpha_2,...,alpha_n , and beta in F`
`alpha_1X_1 + alpha_2X_2 + ... + alpha_nX_n = beta `
k linear equationswith n unknowns with coefficients in a field F:
`alpha_{11}X_1 + alpha_{12}X_2 + ... + alpha_{1n}X_n = beta_1 `
`alpha_{21}X_1 + alpha_{22}X_2 + ... + alpha_{2n}X_n = beta _2`
.
.
.
`alpha_{k1}X_1 + alpha_{k2}X_2 + ... + alpha_{kn}X_n = beta _k`
The techniques learned in your previous linear algebra course can still be used for F since those techniques relied solely on the arithmetic that makes sense in any field.
• Motivation Question II

• Coke or Pepsi?
• Initial Sample: out of 1000 people.... 600 liked coke, 400 liked pepsi. ... v0 = (600,400)

• A. First resample: 500 of 600 stayed loyal to Coke, 100 switched to Pepsi.
300 of 400 stayed loyal to Pepsi , 100 switched to Coke.  so  v1 = (600,400)
• B. Alternative Resample: 400 of 600 stayed loyal to Coke, 200 switched to Pepsi.
•                       300 of 400 stayed loyal to Pepsi , 100 switched to Coke.  so  v1 = (500,500)

• Example A.
v0TA = v1 where

TA= (
 5/6 1/6 1/4 3/4

)

Example B.
v0TB = v1 where

TB= (
 2/3 1/3 1/4 3/4

)

Questions: If the pattern in case B continues with the proportions of those switching remaining the same:
what can we say about vn  when n is large?
Does the distribution of vn when n is large depend on v_0?
Is there some initial distribution that would remain unchanged under the pattern of switching in B?
i.e. is there a distribution v*0 = (c*,p*)  where v*0 = v*1 =  ... = v*n.
Solve the equation:  (c*, 1000-c*) TB = (c*, 1000-c*).

How are these questions related to Motivation Question I?

v0Tn = vn.

9-15
Vectors and vector spaces.
• Traditional vectors: vectors in R2, R2, and Rn.
• Lists. Definition: A list is an ordered collection of a finite number of n-objects, separated by comma and surrounded by parentheses.

• A list is also called an n-tuple.

Examples: (3,5) is a list of 2 real numbers,  (3,4,5,3,5) is a list of 5 real numbers. ((2,3,5,2), (2,3), ( )) is a list of 3 lists.
The length of a list is the number n of places for objects in the list.
If v and w are lists, we say v = w if v and w have the same length n, v = (v , v , ..., v ), w = (w ,w , ..., w ) and vi = w for each i, where i = 1,2,...,n.
Example. Visualize R2, R3, and R4.
• Definition: If S is a set, Sn = {lists of length n with entries from the set S}

• = { v = (v , v , ..., v ) where  vis a member of S for each i, where i = 1,2,...,n..}
• Definition: Suppose F is a field.  We define an internal operation on Fn+, and an external operation between  F and Fn, * , by the following:

• If v =  (v , v , ..., v ) and w =  (w ,w , ..., w ) are in Fn  and a is in F then v + w = (v + w1, v2 + w , ..., vn+w ) and
a*v =  (av , av , ..., av ) using the addition and multiplication of F for the operations on the individual elements of F.
• Proposition: With the operations just defined on F the following properties are true:
• If v, w, and z are in F and a and b are in F, then v+w and a*v are in F [closure] ;
• (v+w)+z = v+(w+z)  [Associativity 1]
• If we let 0 denote (0,0,...0) then 0+v=v+0 = v [Additive identity]
• For each v, there is a list in Fn , v', so that v+v' = v' + v =0. [Additive inverse]
• v+w=w+v [commutativity]
• 1*v = v
• a*( v + w) = (a*v) + (a*w) [distributive 1]
• (a+b)*v = (a*v) + (b*v)    [distributive 2]
• (ab)*v = a*(b*v)   [associativity 2]

• Abstract Vector Spaces
• Definition: Suppose V is a non empty set, F is a field, and there is an internal operation on V, +, and an external operation between  F and V, * .

• We say that V is a vector space over F,  " V is a vs/F", and we call the elements of V, "vectors", if the following properties are true:
• If v,w,and z are in V  and a and b are in F, then v+w and a*v are in V  [closure] ;
• (v+w)+z = v+(w+z)  [Associativity 1]
• If there is an element of V, denoted 0 so that 0+v=v+0 = v [Additive identity]
• For each v, there is an element of V, v', so that v+v' = v' + v =0. [Additive inverse]
• v+w=w+v [commutativity]
• 1*v = v [scalar identity]
• a*( v + w) = (a*v) + (a*w) [distributive 1]
• (a+b)*v = (a*v) + (b*v)    [distributive 2]
• (ab)*v = a*(b*v)   [associativity 2]

• Vectors in a more general context:
• Functions: Suppose S is a set. We define V(S,F) = { f:S -> F, the functions with domain S and target F}.
Note that if f and g are in V(S,F) then f=g means that for all s in S, f(s) = g(s).

• Note: When S = {1,2,...,n} we can give a 1 to 1 correspondence between V(S,F) and Fn by letting  f (k) = vk when v =(v , v , ..., v ) is in Fn .
Note: If S is the empty set, then V(S,F) is the empty set.
• Definition: Suppose S is a non empty set and F is a field.  We define an internal operation on V(S,F), +, and an external operation between  F and V(S,F), * , by the following:

• If v and w are in V(S,F) and a is in F then v + w is the function defined by (v+w)(s) = v(s) + w(s)  for all s in S and
a*v is the function defined by (a*v)(s) =  a v(s)  for all s in S using the addition and multiplication of F for the operations on the elements of F as appropriate.
• Proposition: With the operations just defined on V(S,F) is a vs/F, i.e., the following properties are true:
• If v,w,and z are in V(S,F)  and a and b are in F, then v+w and a*v are in V(S,F)  [closure] ;
• (v+w)+z = v+(w+z)  [Associativity 1]
• If we let 0 denote the function 0(s) = 0 for all in S then 0+v=v+0 = v [Additive identity]
• For each v, there is a function v' in V(S,F), v', so that v+v' = v' + v =0. [Additive inverse]
• v+w=w+v [commutativity]
• 1*v = v  [scalar identity]
• a*( v + w) = (a*v) + (a*w) [distributive 1]
• (a+b)*v = (a*v) + (b*v)    [distributive 2]
• (ab)*v = a*(b*v)   [associativity 2]

9-17
• Examples:
• S = N, the natural numbers = {0,1,2,3,...}. V(S,F) = F can be identified with infinite sequences of elements from the field.
• S= { (i,j): i=1,2,...n; j= 1,2,...,m} then we can give a one to one correspondence between V(S,F) and the collection of n by m matrices with entries in the field F. A matrix M coresponds to the function where f ((i,j)) = M i,j the entry in row i, column j of M.
• S = F. Then V(S,F) = V(F,F).
• S=F=R. Then V(S,F) = V(R,R)= {f:R->R}
• P(F) = { f in V(F,F) where f (x) = a0 + a1x + a2x2 + ...+ anxn with ai is in F for each i} = the polynomial functions from F to F.
• F[X] = { f in F, where f(n) = 0 for all but a finite number of n.}   X = (0,1,0,0,0,...).
• C0(R) = {f in V(R,R) where f is continuous}.
• C1(R) = {f in V(R,R) where f is continuously differentiable}.
• C(R) = {f in V(R,R) where f is n times differentiable for any n}.

• Simple properties of Vector spaces
• is unique.
Proof: Suppose z is in V and z+v= v+z = v for all v in V.  Then 0 = 0 + z = z !
• -v is unique. Proof: Exercise.
• 0*v= 0. [0 is the zero vector, 0 is the zero scalar.]
Proof:  0*v = (0+0) * v = 0*v + 0*v .
Thus 0 =
0*v + -(0*v) =  (0*v + 0*v) + -( 0*v)  =0*v + (0*v + -( 0*v)) = 0*v + 0 = 0*v
• a*0 = 0.  Proof: Exercise.
• (-1)v = -v. Proof: Exercise.
• If v+z = w + z then v=w. [cancellation] Proof: Exercise.
• If a*v = 0, then either a = 0 or v = 0.
Proof: If a = 0, then the statement is correct.
Suppose a is not 0. Then there is a  in F where ba = 1.
Then v = 1*v = (ba)* v =  b*(
a*v) = b *0 = 0.

• Subspaces.
• Definition. W is a subspace of V, W < V, if  W is a subset of V and using the operations of V, W is also a vector space.
• Simple testing. Is W a subspace of V?
• Hard way: check all the axioms again!  :(
• Easier: Since the operation is the same, you don't need to check scalar identity, associativity, commutativity, or distributivity.
• Fact: If W<V and 0v is the zero for V and 0w is the zero for W then, 0v=0w.
Proof:
0v+0w = 0w but 0w+0w = 0w, so by cancellation: 0w=0w.
9-19
• Test 1: (3 steps) If W is non empty and closed under addition and scalar multiplication, then W < V.
• Proof: (i) Since w is not empty, choose w in W. Then 0w= 0, so 0 is in W and so W satisfies the additive identity property.

• (ii) If w is in W, then (-1)w =-w is also in W, so W satisfies the additive inverse property. IRMC.
• Easiest: (2 step) If W is non empty and if for any w and z in W and a in F, w+az is W  [super closure] then W<V.
• Proof: (i) Use a=1, so W is closed under addition.

• (ii)Use a= -1, w= z, then z + (-1)z = 0 is in W.
(iii) 0 + az = az is in W, so W is closed under scalar multiplication.  Now apply the previous test.  IRMC.

• Do Examples
• F[X] = { f in F, where f(n) = 0 for all but a finite number of n.} < F
• Note: When F = R or C, F[X] can be identified with P(F).
Proof: Assume f and g are in F, and a is in F.  We need to show f+ a g is also in F . So consider  [ f+ ag](n). Since f and g are not 0 except at a finite number of n, [ f+ a g](n) will also be zero at all but a finite number of n.
• Suppose A is an n by k matrix with entries in F.
• N(A) ="the null space of A" = { v in Fn where vA= (0,0,...0) in Fk } <  Fn
• N(A) can be considered the subspace of solutions to the system of k homogenous linear equations in n unknowns determined by vA=(0,0,...,0 ).
• Proof: Clearly... 0A = 0, so 0 is in N(A). Suppose v and w are in N(A) and a is in F, then consider (v+aw)A = vA+(aw)A=vA+a(wA) = 0 +0 = 0, so (v+aw) is in N(A).
• R(A) = "the range space of A" = { w in Fk where for some v in Fn, vA= w  } <  Fk
• Proof:  Clearly... 0A = 0, so 0 is in N(A).Suppose z and w are in R(A) and a is in F, then there are v and u in  in Fk where vA=w and uA=z.  So (v+au)A = vA+(au)A=vA+a(uA) =w+az, so w+az is also in R(A).
• R(A) can be considered the collection of k dimensional vectors, w, for which the system of k linear equations in n unknowns determined by vA=w has a solution.

• {f in C(R) where f ''(x) - f(x) = 0} < C(R).
• Example: Solutions `( x_1, x_2, ... x_n)` to a single  homogenous linear equation  for am subspace of `R^n`.
• Theorem: "The Intersection of a family of subspaces is a subspace."
Suppose V is a v.s. over a field F.
If U is a nonempty family of subspaces of V ,
then
`nnn U = {v in W`  for all `W in U}` is a subspace of V
Proof: (i) O is a member of every subspace of V, so O is a member of `nnn U`.
(ii) Suppose v and w are vectors in `nnn U` and `alpha in F`. Then v and w are vectors in  every subspace W that is in the family U. But since W is a subspace, v + `alpha` w is also a vector in all the subspaces W that are members of U. Hence
v + `alpha` w  is member  of `nnn U`. So `nnn U` is a subspace of V.
• Application of Theorem: N(A) Fn .
• Example: {f in C(R) where f is a solution to a homgeneous linear differential equation of order n} < C(R). And this holds for a family of homogeneous linear diff'l equations as well.

9-24

• Motivation:  Reconsider R(A)- the range space of a matrix A.
Suppose A is an n by k matrix with entries in F. v in Fn, vA is a vector in Fk which is a linear combination of the row  vectors of the matrix A determined by the entries of v.
This leads to considering the set of linear combinations of a collection of vectors (like the row vectors or column vectors of a matrix)- often described as the span of the set of vectors or the subspace generated by a set of vectors.  Unfortunately this characterization of "span" is not as clear when the set of vectors is empty!
We will develop a more general definition of span that includes the empty set.
• Definion: Suppose S is a set of vectors in a v.s. V over the field F.
SPAN (S) =
`nnn` {all W < V  where S `subset` W}.
Facts : 1. SPAN(S) < V.
2. S `subset` SPAN(S).
3. If  S  `subset`  W and W < V then  SPAN(S) <W.

• Fact: If U<W and W <V, then U<V.

• Proof:The operation on U is the same operation for W and V.

• (Internal) Sums , Intersections,  and Direct Sums of Subspaces

• Suppose U1, U2,  ... , Un are all subspaces of V.
• Definition:  U1+ U2+  ... + Un = {v in V where v = u1+ u2+  ... + un for  uk in Uk , k = 1,2,...,n} called the (internal) sum of the subspaces.

• Facts: (i) U1+ U2+  ... + Un < V.
(ii)  Uk < U1+ U2+  ... + Un for each k, k= 1,2,...,n.
(iii) If W<V and Uk < W for each k, k= 1,2,...,n, then U1+ U2+  ... + Un <W.
So ...
U1+ U2+  ... + Un is the smallest subspace of V that contains Uk for each k, k= 1,2,...,n.
• Examples:

• U1 = {(x,y,z): x+y+2z=0} U2 = {(x,y,z): 3x+y-z=0}. U1 + U2 = R3.

Let Uk = {f in P(F): f(x) = akxk  where ak is in F} . Then U0+ U1+ U2+  ... + Un = {f : f (x) = a0 + a1x + a2x2 + ...+ anxn where a0 ,a1 ,a2,...,an are in F}.

• Definition:  U1 `cap` U2`cap`  ... `cap` Un = {v in V where v is in Uk , for all k = 1,2,...,n} called the intersection of the subspaces.

• Facts:(i) U1`cap` U2`cap`  ... `cap` Un < V.
(ii)   U1`cap`U2`cap`  ... `cap` Un < Uk for each k, k= 1,2,...,n.
(iii) If W<V and W < Uk for each k, k= 1,2,...,n, then W<U1`cap` U2`cap`  ... `cap` Un .
So ...
U1`cap` U2`cap`  ... `cap` Un is the largest subspace of V that is contained  in Uk for each k, k= 1,2,...,n.
Examples: U1 = {(x,y,z): x+y+2z=0} U2 = {(x,y,z): 3x+y-z=0}. U1 `cap` U2 = {(x,y,z): x+y+2z=0 and 3x+y-z=0}= ...
Let Uk = {f in P(F): f(x) = akxk  where ak is in F} then Uj`cap`Uk = {0} for j not equal to k.

...
9-26
Suppose V is a v.s over F and  `U_1` and `U_2` are subspaces of V. We say that V is the direct sum of  U1 and U2 and we write
V = `U_1` `oplus` `U_2` if (1) `U_1` + `U_2` and (2) U1`cap` U2 = {0}.

Prop: Suppose V = `U_1` `oplus` `U_2`  and `v in V`, v = `u_1 + u_2 = w_1 + w_2 ` with `u_i` and `w_i` are in `U_i` for i = 1 and 2.
Then  `u_i = w_i` for i = 1,2.
Conversely,  if V = `U_1` + and  `U_2` and if v = `u_1 + u_2 =  w_1 + w_2 ` with `u_i` and `w_i` are in `U_i` for i = 1 and 2.
implies  `u_i = w_i` for i = 1,2 then V = `U_1`  `oplus`  `U_2`.

Proof:  From the hypothesis, `u_1 _ (- w_1) =  w_2 + (- u_2) in U_1` and `U_2`, so it is in `U_1 cap U_2` = {0}. Thus ... `u_i = w_i` for i = 1, 2.
Conversely: if `v  in  U_1 nn U_2`  then v =  v + 0  = 0 + v, so v = 0. Thus V = ` U_1` `oplus` `U_2`.

To generalize the direct sum  to U1, U2,  ... , Un, we would start by assuming V = U1 + U2 +  ... + Un.
We might try to generalize the intersection property by assuming that `U_i` `oplus` `U_j` = {0} for  all i and j that are not equal. This won't work .

9-29
Discuss Exercise: If U and W are subspaces of V and U `uu` W  is also a subspace of V, then either U < W or W < U.

Direct Sums:
Suppose U1, U2,  ... , Un are all subspaces of V and U1+ U2+  ... + Un = V, we say V is the direct sum of U1, U2,  ... , Un if for any v in V, the expression of v as v = u1+ u2+  ... + un for  uk in Uk is unique, i.e., if v = u1'+ u2'+  ... + un' for  uk' in Uk then u1 = u1', u2=u2', ... , un=un'. In these notes we will write
V = U1
`oplus` U2 `oplus`...`oplus` Un
Examples:Uk = {v in Fn: v = (0,... 0,a,0, ... 0) where a is in F is in the kth place on the list.} Then U1`oplus` U2`oplus`  ... `oplus` Un = V.

Theorem:  V =  U1`oplus` U2`oplus`  ... `oplus` Un if and only if (i)U1+ U2+  ... + Un = V AND 0=u1+ u2+  ... + un for  uk in Uk implies u1=u2=...=un=0.
Theorem: V = U`oplus`W if and only if V = U+W and U`cap`W={0}.

Examples using subspaces and direct sums in appplications:
Suppose A is a square matrix (n by n) with entries in the field F.
For c in F, let Wc = { v in Fn where vA = cv}.
Fact: For any A and any c,  Wc< Fn . [Comment: for most c, Wc= {0}. ]
Definition: If Wc is not the trivial subspace, then c is called an eigenvalue or characteristic value for the matrix A and nonzero elements of Wc  are called eigen vectors or characteristic vectors for A.

Application 1 : Consider the coke and pepsi matrices:

Example A.
vA = cv? where

A=(
 5/6 1/6 1/4 3/4

)

Example B.
vB = cv where

B=(
 2/3 1/3 1/4 3/4

)

Questions: For which c is Wc non-trivial?
To answer this question we need to find (x,y) [not (0,0)] so that

Example A

(x,y)(
 5/6 1/6 1/4 3/4

)= c(x,y)

Example B

(x,y)(
 2/3 1/3 1/4 3/4

)= c(x,y)

Is R2 = Wc1 + Wc2 for these subspaces? Is this sum direct?

Focusing on Example B we consider for which will the matrix equation have a nontrivial solution (x,y)?
We consider the  equations:  2/3 x +1/4 y = cx and 1/3 x+3/4 y = cy.
Multiplying by 12 to get rid of the fractions and bringing the cx and cy to the left side we find that
(8-12
c)x + 3 y = 0 and 4x + (9-12c)y = 0

Multiplying by 4 and (8-12c) then subtracting the first equation from the second we have
((8-12c)(9-12c)  - 12 )y = 0. For this system to have a nontrivial  solution, it must be that
((8-12c)(9-12)
c  - 12 ) = 0 or  `72 - (108+96)  c+144c^2 -12 = 0`  or
`60 -204c +144c^2 = 0`.
Clearly one root of this equation is 1, so factoring we have (1-c)(60-144c) = 0 and c = 1 and c = 5/12 are the two solutions... so there are exactly two distinct eigenvalues for example B,
c= 1 and c = 5/12  and two non trivial eigenspaces
W1  and W5/12 .

General Claim: If c is different from k, then Wc `cap` Wk = {0}
Proof:?
Generalize?
What does this mean for  vn  when n is large?
Does the distribution of vn when n is large depend on v0?

Application 2: For c a real number let
Wc = {f in C(R) where f '(x)=c f(x)} < C(R).
What is this subspace explicitly?
Let V={f in C(R) where f ''(x) - f(x) = 0} < C(R).
Claim: V = W1 `oplus` W-1
Begin?
We'll come back to this later in the course!

If c is different for k, then Wc `cap` Wk = {0}
Proof:...

Back to looking at things from the point of view of individual vectors:
Linear combinations:

Def'n.
Suppose S is a set of vectors in a vector space V over the field F. We say that a vector v in V is a linear combination of vectors in S if there are vectors u1, u2,  ... , un in S  and scalars a1, a2,  ..., an in F where v = a1u1+ a2u2+  ... + anun .
Comment: For many introductory textbooks: S is a finite set.

Recall. Span (S) = {v in V where v is a linear combination of vectors in S}
If S is finite and Span (S) = V we say that S spans V and V is a "finite dimensional" v.s.

Linear Independence.
Def'n. A set of vectors S is linearly dependent
if there are vectors u1, u2,  ... , un in S  and scalars
`alpha_1, alpha_2,  ..., alpha_n in F` NOT ALL 0 where `0 = alpha_1u_1+ alpha_2u_2+  ... + alpha_n u_n` .
A set of vectors S is linearly independent  if it is not linearly dependent.

Other ways to characterize linearly independent.
A set of vectors S is linearly independent  if  whenever there are vectors u1, u2,  ... , un in S  and scalars
`alpha_1, alpha_2,  ..., alpha_n in F` in F where `0 = alpha_1u_1+ alpha_2u_2+  ... + alpha_n u_n` , the scalars are all 0, i.e. `alpha_1, alpha_2,  ..., alpha_n = 0` .

Examples: Suppose A is an n by m matrix: the row space of A= span ( row vectors of A) , the column space of A = Span(column vectors of A).
Relate to R(A)

Recall R(A) = "the range space of A" = { w in Fk where for some v in Fn, vA= w  } <  Fk
.
w is in R(A) if and only if w is a linear combination of the row vectors, i.e., R(A) = the row space of A.
If you consider  Av instead of vA, the R*(A) = the column space of A.

"Infinite dimensional" v.s. examples: P(F), F, C (R)
F[X] was shown to be infinite dimensional. [ If  p is in SPAN(p1,....,pn) then the degree of p is no larger than the maximum of the degrees of {p1,...pn}. So F[X] cannot equal SPAN(p1,...,pn) for any finite set of polynomials- i.e, F[X] is NOT finite dimensional.

Some Standard examples.

Bases- def'n.

Definition: A set B is called a basis for the vector space V over F if (i) B is linearly independent and (ii) SPAN( B)  = V.

Bases and representation of vectors in a f.d.v.s.

10-8
Suppose B is a finite basis for V with its elements in a list, (u1, u2,  ... , un) .
If v is in V, then
there are unique vectors
scalars
`alpha_1, alpha_2,  ..., alpha_n` in F where  v = ` alpha_1u_1+ alpha_2u_2+  ... + alpha_n u_n` .

The scalars are called the coordinates of v w.r.t. B, and we will write

v = [`alpha_1, alpha_2,  ..., alpha_n`]B.

Linear Independence Theorems
Theorem 1 : Suppose S is a
linearly independent set and  v1  is not an element of Span(S), then
S `cup` v1 is also linearly independent.
Proof Outline:
Suppose vectors u1, u2,  ... , un in S  and scalars `alpha_1, alpha_2,  ..., alpha_n, alpha in F` where `0 = alpha_1u_1+ alpha_2u_2+  ... + alpha_n u_n + alpha` v1 . If `alpha` is not 0 then
`v1= -alpha^{-1}( alpha_1u_1+ alpha_2u_2+  ... + alpha_n u_n) in` Span(S), contradicting the hypothesis. So `alpha = 0`. Buth then `0 = alpha_1u_1+ alpha_2u_2+  ... + alpha_n u_n ` and since S is linearly independent,
`alpha_1, alpha_2,  ..., alpha_n = 0`. Thus  S `cup` v1 is linearly independent.   EOP.

Theorem 2: Suppose S is a finite set of vectors with V = Span (S) and T is a subset of vectors in V. If  n( T) > n(S) then T is linearly dependent.
Proof Outline: Suppose n(S) = N. Then by the assumption  ... [Proof  works by finding N homogeneous linear equations with N+1 unknowns.]

10-10
Theorem 3:
Every finite dimensional vector space has a basis.
Proof outline:
• How to constuct a basis, B, for a non trivial finite dimensional v.s., V. Since V is finite dimensional it has a subset S that is finite with Span (S) = V.
• Start with the empty set. This is linearly independent. Call this B0.  If span(B0) = V then you are done. B0 is a basis.
• If Span(B0) is not V then there is a vector v1 in V where v1 is not in Span(B0). Apply Theorem 1 to obtain `B1 = B0 cup {v1}` which is linearly independent. If Span(B1) then B1 is a basis for V. Otherwise continue using Theorem 1 repeatedly until the resulting set of vectors has more then the number of sets in the spanning set. But by Theorem 2, this is a contradiction. So at some stage of the process, Span(Bk) = V, and Bk is a basis for V.

Comment:The proof of the Theorem  also shows that given T, a  linearly independent subset of V and V a finite dimensional vector space, one can step by step add elements to  T, so that eventually you have a new set S where S is lineary independent with Span(S) = V and T   contained in  S. In other words we can construct a set B that is a basis for V with T contained in B.  This proves

Corollary: Every Linearly independent subset of a finite dimensional vector space can be extended to a basis of the vector space.

Theorem 4. If V is finite dimensional vs  and B and B' are bases for V, then n(B) = n(B').

Proof: fill in ... based on the Theorem 2. n(B) <= n(B')  and n(B') <= n(B)  so...

Definition: The dimension of a finite dimensional v.s. over F is the number of elements in a(ny) basis for V.

Discuss dim({0}).
What is Span of the empty set? Characterize SPAN(S) = the intersection of all subspaces that contain S. Then Span (empty set) = Intersection of all subspaces= {0}.

The empty set is linearly independent!... so The empty set is a basis for {0} and the dimension of {0} is 0!

10-13
More Dimension Results:

Prop: A Subspace of a finite dimensional vs is finite dimensional.

Suppose Dim(V) = n, S  a set of vectors with N(S) = n. Then
(1) If S is Linearly independent, then S is a basis.
(2) If Span(S) = V, then S is a basis.

Proof: (1) S is contained is a basis, B. If B is larger than S, then B has more than n elements, which contradicts that fact that any basis for V has exactly n elements. So B = S and S is a basis.
(2) Outline:V has a basis of n elements, B.  Suppose S in linearly dependent and show that there is a set with less than n elemnets that spans V. Hence B cannot be a basis. This,
S is a basis.
IRMC

Theorem: Sums, intersections and dimension: If U, W <V  are finite dimensional, then so is U+W and
dim(U+W) = Dim(U) + Dim(W)  - Dim(U`cap`W).
Proof: (idea) build up bases of U and W from U`cap`W.... then check  that  the union of these bases is a basis for U+W

Problem 2.12: Suppose p0,...,pm are in Pm(F) and pi(2) = 0 for all i.
Prove {p0,...,pm} is linearly dependent.

Proof: Suppose {p0,...,pm} is linearly independent.
Notice that by the assumption for any coefficients

(a0p0+..+ampm )(2) = a0p0(2)+..+ampm(2) = 0
and since u(x)= 1 has u(2) = 1, u (= 1) is not in the SPAN(p0,...,pm).
Thus
SPAN(p0,...,pm)
is not Pm(F).

But SPAN ( 1,x, ..., xm) = Pm(F) .
By repeatedly applying the Lemma to these two sets of m+1 polynomials as in Theorem 2.6, we have SPAN (p0,...,pm)=P
m(F)
. So {p0,...,pm} is not linearly independent.
End of proof.

Examples: In R2, P4(R).

Connect to Coke and Pepsi example: find a basis of eigen vectors using the B example for R2.  [Use the on-line technology]

Example B

(x,y)(
 2/3 1/3 1/4 3/4

)= c(x,y)

We considered the  equations:  2/3 x +1/4 y = cx and 1/3 x+3/4 y = cy and showed that
there are exactly two distinct eigenvalues for example B,
c= 1 and c = 5/12  and two non trivial eigenspaces
W1  and W5/12 .
Now we can use technology to find eigenvectors in each of these subspaces.
Matrix calculator
, gave as a result that the eignevalue 1 had an eigenvector (1,4/3)  while 5/12 had an eigenvector (1,-1). These two vectors are a basis for R2.

Linear Transformations: V and W vector spaces over F.
Definition: A function T:V ` ->`  W is a linear transformation if for any x,y in V and in F, T(x+y) = T(x) + T(y) and T(ax) = a T(x).

Examples: T(x,y) = (3x+2y,x-3y) is a linear transformation T: R2  -> R2.
G(x,y) = (3x+2y, x^2 -2y) is not a linear trasnformation.
G(1,1) = (5, -1) , G(2,2) = (10, 0)... 2*(1,1) = (2,2) but 2* (5,-1) is not (10,0)!
Notice that T(x,y)can be thought of as the result of a matric multiplication

(x,y) (
 3 1 2 -2

)
So the two key properties are the direct consequence of the properties of matrix multiplication.... (v+w)A= vA+wA and (cv)A = c(vA).
For A a k by n matrix :  TA  (left argument) and
AT (right) are linear transformations on Fk and Fn.
TA  (x) = x A for x in Fk and AT(y) = A[y]tr for y in Fn and [y]tr indicates the entries of the vector treated as a one column matrix.

The set of all linear transformations from V to W is denoted L(V,W).

V = U `oplus` W if and only if V = U+W  and U`cap`W={0}.
Proof:
=> suppose v is in U`cap`W, then v=u in U and v=w in W, so 0 = u-v. But since V= U`oplus`W, this means u=w = 0 so v=0, so U`cap`W={0}.
Note: This argument extends to V as the direct sum of any family of subspaces.

<= Suppose u is in U and w is in W and u+w = 0. Then, u = -w so u is also in W, and thus u is is U`cap`W={0}. So u=0 and then w= 0 . Since V=U+W, we have by 1.8, V=U`oplus`W. EOP

2.19 If V is f.d.v.s.  and U1, ...Un are subspaces with  V = U1 +...+ Un and
dim(V) = dim(U1)+...+ dim(Un) then
V = U1 `oplus`...`oplus` Un

Proof outline: Choose bases for U1, ..., Un and let B be the union of these setes. Since V = U1 +...+ Un every vector in v is a linear combination of elements from B. But B has exactly dim(U1)+...+ dim(Un) = dim(V) elements in it, B is a basis for V. Now suppose  0=u1+ u2+  ... + un for  uk in Uk. Then each ui =can be expressed as a linear combination of the basis vectors for Ui, and the entire linear combination is 0 implies that each coefficient is 0 because B is a basis. So u1=...=un=0 and V = U1 `oplus`...`oplus` UnEOP

How do you find a basis for the SPAN(S) in Rn?
Outline of use of row operations...

10-17
Back to linear transformations:

Consequences of the definition: If T:V->W is a linear transformation, then for any x and y in V and a in F,

(i) T(0) = 0.

(ii) T(-x) = -T(x)

(iii) T(x+ay) = T(x) + aT(y).

Quick test: If T:V->W is a function and (iii) holds for any x and y in V and a in F, then the function is a linear transformation.

D... Differentiation is a linear transformation: on polynomials, on ...

Example: (D(f))(x) = f' (x) or D(f) = f'.
(D(f + `alpha` g))(x) = (f+`alpha`g)' (x) = f'(x) + `alpha`g'(x) = (f'+`alpha`g') (x)  or
D(f+
`alpha`g) = f'+ `alpha`g'= D(f) +`alpha` D(g).

Theorem: T : V->W  linear, B a basis, gives S(T):B ->W.
Suppose S:B -> W, then there is a unique linear transformation T(S):V->W such that S(T(S))=S.
Proof:
Let T(S)(v) be defined as follows: Suppose v is expressed (uniquely) as a linear combination of elements of B, ie.
v =
a1u1+ a2u2+  ... + anun
... then let T(v)  = a1S(u1)+ a2S(u2)+  ... + anS(un) ....
This is well defined since the representation of v is unique. Left to show T is linear.  Clearly... if u is in B then S(T(S))(u) = S(u).
Example: T: P(F) `->` P(F).... S(xn) = nx n-1.
Or another example:
S(xn) = 1/(n+1) x n+1.

Key Spaces related to T:V->W
Null Space of T= kernel of T = {v in V where T(v) = 0 [ in W] }= N(T) < V
Range of T = Image of T = T(V) = {w in W where w = T(v) for some v in V} <W.

10-20
Major result of the day: Suppose T:V->W and V is a finite dimensional v.s. over F. Then N(T) and R(T) are also finite dimensional and Dim(V) = Dim (N(T)) + Dim(R(T)).
Proof:
Done in class- see text: Outline: start with a basis C for N(T) and extend this to a basis B for V.  Show that  T(B-C) is a basis for R(T).

Visualize with Winplot?

10-22
Algebraic stucture on L(V,W)

Definition of the sum and scalar multiplication:
T, U in L(V,W), a in F, (T+U)(v) = T(v) + U(v).
Fact:T+U is also linear.
(aT)(v) = a T(v) .
Fact:aT is also Linear.
Check: L(V,W) is a vector space over F.

Composition: T:V -> W and U : W -> Z both linear, then  UT:V->Z where UT(v) = U(T(v)) is linear.

Note: If T':V-> W and U':W->Z are also linear, then  U(T+T') = UT + UT' and (U+U') T = UT + UT'. If S:Z->Y is also linear then S(TU) = (ST)U.

Key focus: L(V,V) , the set of linear "operators" on V.... also called L(V).
If T and U are in L(V) then UT is also in L(V).  This is the key example of what is called a "Linear Algebra"... a vector space with an extra internal operation usually described as the product. That satisfies the distributive and associative properties and has an "identity"- namely Id(v) = v for all v `in V`. [Id T = T Id = T for all T  `in  L(V)`.

If T `in` L(V), then `T^n in` L(V).

Example: V = `C^{oo}`(R). D: V `->` V is defined by D(f )= f '. Then `D^2 +4D + Id` = (D + 3Id)(D + Id) = T `in` L(V).  Finding N(T) is solving the "homogenous linear differential equation" f ''(x) + 4f '(x) + f (x) = 0.

10-24
Linear Transformations and Bases
We proved that if V and W are finite dimensional then so is L(V,W) and dim(L(V,W)) = dim(V) Dim(W).
We did this using bases for V and W to find a basis for L(V,W). That basis for L(V,W) also established  a function from L(V,W
) to the matrices that is a linear transformation! More details will be supplied for this lecture later.

Matrices  and Linear transformations.

Footnote on notation for Matrices: If the basis for V is B and for W is C and T:V->W,
the matrix of T with respect to those bases can be denoted MBC(T). Note - this follows a convention on the representation of a transformation.
The matrix for a vector V is denoted
MB(v). If we treat this as a row vector we have MC(T(v))=
MB(v)MBC(T).
This can be transposed using column vectors for the matrix of the vectors and we have with this transposed view:
MC(T(v))=MBC(T)MB(v)

The function M : L(V,W) -> Mat (m,n; F) is a linear transformation.

10-27
Recall definition of "injective" or "1:1" function.
Recall definition of "surjective" or "onto" function.

Theorem: T is 1:1 (injective) if and only if N(T) = {0}
Proof: =>  Suppose T is 1:1.  We now that T(0)=0 , so if T(v) = 0, then v = 0. Thus 0 is the only element of N(T) or N(T) = {0}.
<=  Suppose N(T) = {0}. If T (v) = T(w) then T(v-w) =T(v)-T(w) = 0 so v-w is in N(T).... ok, than must mean that v-w = 0,  so v=w and T is 1:1.

Theorem: T is onto if and only of the Range of T = W.
Theorem: T is onto if and only if for any (some) basis, B, of V, Span(T(B)) = W.
Theorem: If V and W are finite dimensional v.s. / F, dimV = dim W,  T : V `->` W is linear, then T is 1:1 if and only if T is onto.
Proof: We know that dim V = dim N(T) + dim R(T).
=>  If T is 1:1, then  dim N(T) = 0, so dim V = dim R(T)  . Thus dim R(T) = dim W and T is onto.
<=   If T is onto, then dimR(T) = dim W. So dim N(T) = 0 and thus N(T) = {0} and T is 1:1.

10-29

The importance of the Null Space of T, N(T), is understanding what T does in general.

Example 1. D:P(R) -> P(R)... D(f) = f'. Then N(D) = { f: f(x) = C for some constant C.} [from calculus 109!]
Notice: If f'(x) = g'(x)  the f(x) = g(x) + C for some C.
Proof: consider D(f(x) - g(x)) = Df(x) - Dg(x) = 0, so f(x) -g(x) is in N(T).

Example 2: Solving  a system of homogeneous  linear equations. This was connected to finding the null space of a linear trasnformation connected to a matrix. Then what about a non- homogeneous system with the same matrix. Result: If z is a solution of the non- homogeneous system of linear equations and z ' is another solution, then z' = z + n where n is a solution to the homogeneous system.

General Proposition: T:V->W. If b is a vector in W and a is in V with T(a) = b, then T-1({b}) = {v in V: v = a +n where n is in  N(T)} = a + N(T)

Comment: a + N(T) is called the coset of a mod N(T)...these are analogous to lines in R2. More on this later in the course.

10-31
Note:Why this called a "linear" transformation:
The geometry of linear: A line in R2 is {(x,y): Ax +By = C where A and B are not both 0} = {(x,y): (x,y) = (a,b) + t(u,v)}= L, line through (a,b) in direction of (u,v).

Suppose T is a linear transformation :
Let T(L) = L' = {(x'y'): (x',y')= T(x,y)}
T(x,y) = T(a,b) + t T(u,v).
If T(u,v) = (0,0) then L' = T(L) = {T(a,b)}.
If not then L' is also a line though T(a,b) in the direction of T(u,v).
[View this in winplot?]

Coke/Pepsi example B: T(x,y) =(2/3 x +1/4 y, 1/3 x+3/4 y)
T(v0) = v
1, T(v1) = v2.... T(vk)=T(vk+1).
T(v*)=v* means a nonzero v* is an eigenvector with eigenvalue 1. T(1, 4/3) = (1,4/3). Also T(3/7, 4/7) = T
[(3/7)(1,4/3)] = 3/7T(1,4/3) =3/7(1,4/3) =(3/7,4/7).
T(1,-1) =(5/12,-5/12 )= (5/12)(1,-1) means that (1,-1) is an eigenvector with eigenvalue 5/12.

Invertibility of Linear Transformations:
Def'n: T:V -> W is invertible if and only if
there is a linear transformation S :W -> V where TS = IdW and ST = IdV .

Fact:
If T is invertible then the S :W->V used in the definition is also invertible!
S is unique:  If S' satsifies the same properties as s, then
S = S Id = S(TS')  =(ST)S' = Id S' = S'
S is called "the inverse of T".
Prop: T is invertible iff  T is 1:1 and onto  (injective and surjective).
Outline of Proof:
(i) =>  Assume S... (a)show T is 1:1. [This uses ST = Id].(b) show T is onto [This uses TS = Id].
(ii) <=  Assume T is 1:1 and onto. Define S. [This uses that T is onto and 1:1] Show S is linear [This uses T is linear.] and TS =I and ST = I

11-3 and 5
Def:
If there is a T:V->W that is invertible, we say W is isomorphic with V. (V=T W)
(i)V=Id V (ii)If V=T W then W=S V  (iii)If V=T W and W=U Z then V=UT Z.

Theorem: Suppose V and W are finite dimensional v.s./F. Then
V=T W if and only if dim(V) = dim(W).
Proof: =>: Suppose
V=T W. Then since there is a T: V`->` W that is an isomorphism, dim (V) = dim N(T) + dim R(T). But R(T) = W and N(T) = {0} so dim N(T) = 0 and dim(V) = dim(W).
<= (outline) Assume dim(V) = dim ( W) = n. Choose a basis B for V, B = {v1,v2,...,vn} and a basis C for W, C  = {w1,w2,...,wn}. Then use T defined by T(vi) = wi and show this is invertible.

Theorem: Suppose B= (v1,...,vn) and C=(w1,...,wm)  are finite bases  (lists) for V and W respectively. The linear transformation M: L(V,W) -> Mat(m,n,F) is an isomorphism.
Proof: Show injective by Null(M)= {Z} -where Z is the zero transformation.
Show M is onto by giving TA where M(
TA ) = A based on knowing A.
[OR use dimensions of these vector spaces are equal proved previously.]

Cor. [if isomorphism is established directly]: Dim L(V,W) = Dim(V) Dim(W).

Prop. V a f.d.v.s.  If T is in L(V) then the following are equivalent:
(i) T is invertible.
(ii) T is 1:1.
(iii) T is onto.
Proof: (i) =>(ii). Immediate.
(ii)=>(iii) . Dim V = Dim(N(T)) + Dim(R(T)). Since T is 1:1, N(T)={0}, so Dim(N(T))= 0 and thus Dim V = Dim (R(T)) so R(T) = V and T is onto.
(iii) =>(i)
Dim V = Dim(N(T)) + Dim(R(T)) Since T is onto, R(T) = V... so Dim(N(T)) = 0. ... so N(T) = {0} and T is 1:1, so T is invertible.

Connection to square matrices:
A is invertible  is equivalent to....Systems of equations statements.

[Motivation]
Look at Coke/Pepsi example B: T(x,y) =
(2/3 x +1/4 y, 1/3 x+3/4 y)= (x,y)A
T(v0) = v
1, T(v1) = v2.... T(vk)=T(vk+1).
v2=T(v1) = TT(v0);... T(vk)=Tk(v0) = (x0,v0)Ak.
We considerd the  equations:  2/3 x +1/4 y = cx and 1/3 x+3/4 y = cy and showed that
there are exactly two distinct eigenvalues for example B,
c= 1 and c = 5/12  and two non trivial eigenspaces
W1  and W5/12 .
Now we can use technology to find eigenvectors in each of these subspaces.
Matrix calculator
, gave as a result that the eigenvalue 1 had an eigenvector (1,4/3)=v1  while 5/12 had an eigenvector (1,-1)=v2. These two vectors are a basis for R2.
B=(v1,v2)
What is the matrix of T using this basis.
`M_B^B(T) =((1,0),(0,5/12))`
Using this basis and matrix makes it easy to see what happens when the transformation is applied repeatedly:
`M_B^B(T^n) = [M_B^B(T)]^n =((1,0),(0,5/12))^n=((1,0),(0,{5/12}^n))`

Change of basis:
So ... What is the rel
ationship between this very nice matrix for T that results from using the basis B of eigenvectors and the matrix for T that uses the standard basis, E = (e1,e2)?
`M_E^E(Id) =((2/3,1/4),(1/3,3/4)).

The key to understanding the relationship between these is the identity map!
We consider the matrix for the identity operator using B for the source and
E for the target.
`M_B^E(Id) =((1,1),(4/3,-1))`
And for the identity operator using E for the source and B for the target, MEB(Id).
Notice that
MEB(Id) MBE(Id) =MBB(Id* Id)=MBB(Id)= In the n by n identity matrix, and similarly MBE(Id) MEB(Id) =MEE(Id) = In . Thus both these matrices are invertible and each is the inverse of the other!
Furthermore:
`M_B^B(T) =((1,0),(0,5/12))`

MBE(Id)MBB(T)MEB(Id)=MEE(IdTId)=MEE(T)
and
MEB(Id)MEE(T)MBE(Id)=MBB(IdTId)=MBB(T).

If we let P =MEB(Id) and L = MBE(Id) = P-1, then we have

LMBB(T)P =P-1MBB(T)P=MEE(T)
or

M
BB
(T)P= PMEE(T)
and
PMEE(T)L=MBB(T).

11/5
Change of  Basis, Invertibility and similar matrices.
The previous example works in general:
The Change of Basis Theorem:
Suppose V is a f.d.v.s over F, dim(V) = n, and B and E are two bases for V. Suppose T:V -> V is a linear operator, then
MBE(Id)MBB(T)MEB(Id)=MEE(T)
and
MEB(Id)MEE(T)MBE(Id)=MBB(T).

If we let P =MEB(Id) and L = MBE(Id) = P-1
[
LP =MBE(Id)MEB(Id) = MEE(Id)= In ]
then we have
LMBB(T)P =P-1MBB(T)P=MEE(T)
or
MBB(T)P= PMEE(T)
and likewise  PMEE(T)L=MBB(T).

Def'n: We say that two matrices A and B are similar if there is an invertible matrix P so that
B = P-1AP.

Cor.Suppose V is a f.d.v.s over F, dim(V) = n, and B and E are two bases for V. Suppose T:V -> V is a linear operator, then MBB(T) and MEE(T) are similar matrices.

11-7
There is a "converse" to the theorem based on the following
Proposition: If P is an invertible n by n matrix, then TP:Fn ->
Fn defined by the matrix P where MEE(TP) =P maps every basis B of Fn to a basis, TP(B)= B' .

Eigenvectors, Eigenvalues, Eigenspaces, Matrices, Diagonalizability, and Polynomials!

Definition:Suppose T is a linear operator on V, then a is an eigenvalue for T if there is a non-zero vector v where T(v) = av. The vector v is called an eignevector for T.
Proposition: a is an eignevalue for T  if and only if Null(T-aId)  is non-trivial.]

Def'n:T is diagonalizable if V has a basis of eigenvectors.
T is diagonalizable if and only if M(T) is similar to a diagonal matrix, i.e., a matrix A where Ai,j=0 for indices i, j where i is not equal to j.
Fact: If T is diagonalizable with distinct eigenvalues  a1,...,ak , then S = (T-
a1Id)(T-a2Id).... (T-akId) = 0.
Proof: It suffices to show that for any v in a basis for V, T(v) = 0.  Choose a basis for V of eigenvectors, and suppose v is an element of this basis with T(v) =
aj v. Then S(v)= (T-a1Id)(T-a2Id).... (T-akId)(v) = (T-a1Id)(T-a2Id).... (T-ajId)... (T-akId)(T-ajId)(v) = 0.

What about the Converse? If  there are distinct scalars a1,...,ak where S(v) = (T-a1Id)(T-a2Id).... (T-akId)(v) = 0 for any v in V, is T diagonalizable? we will return to this later....!

A Quick trip into High School/Precalculus Algebra and Formal Polynomials: Recall... F[X]
F[X] = { f in F, where f(n) = 0 for all but a finite number of n}
=
{ formal polynomials with coefficients in F using the "variable" X}
<
F.
X = (0,1,0,0,....). example: 2+X + 5X2 +7 X4 = (2,1,5,0,7,0,0,...)

Notice: F[X] is an algebra over F... that is it has a multiplication defined on its elements... in fact it has a multiplicative unity, 1 =(1,0,0,0...), and furthermore, this algebra has a commutative multiplication: if f,g are in F[X] the f*g = g*f.

Notice:
If f is not 0, then deg(f) = ...., and
Theorem: If f
and g are not 0 = (0,0,0...),  then f*g is also non-zero, with deg(f*g) = deg(f) + deg(g).

11-10
If A is any algebra over F with unity, and `f` is in F[X],
f  = (a1 , a2, ... ,an, 0 , 0 , ...) then we have a function, f :A`->`A defined by
f
(t) =
a1 I + a2t+ ... +antn  where I  is the unity for A.

In particular (i)A can be the field F itself, so f is in P(F).
Example: F = Z2. f  = X2 + X in F[X]. Then f is not (0,0,0....) but f(t) = 0 for all t in F.

(ii) A can be L(V) where Vis a finite dimensional vector space over F.
Then f (T) is also in L(V).
(iii) A can be M(n;F), the n by n matrices with entries from F.

Then f (M) is also in M(n;F).

The Division Algorithm, [proof?]
If g is not zero, for any f there exist unique q , r in F[X] where f  = q*g +r and either (i) r = 0 or (ii) deg(r) < deg(g).
The Remainder and Factor Theorems [Based on the DA]
Suppose c is in F,
for any f there exist unique q , r in F[X]
where f  = q*(X-c) +r and  r = f(c).

Suppose c is in F ,then  f (c) = 0 if and only if f = (X-c)*q for some q in F[X].

Roots and degree.
If c is in F and f (c) = 0, then c is called a root of f.
If f is not 0, and deg(f) = n then there can be at n distinct roots of f in F.

Factoring polynomials. A polynomial in F[X] is called reducible if there exist polynomials p and q, with deg(p)>0 and deg(q)>0 where f=p*q.
If deg(f )>0 and f is not reducible it is called irreducible (over F).
Example:
X2 + 1 is irreducible over R but Reducible over C.

11-12
(I)The FTof Alg for C[X].
Theorem: If f is non-zero in C[X] with deg(f)>0, then there is a complex number r where f (r) = 0

(II) The FT of Alg for R[X].

Theorem:
If f is non-zero in R[X] andis irreducible, then deg(f)= 1 or 2.

Proof  of II assuming (I):
If f is in R[X] and deg(f)>2, then f is in C[X].
If r is a root of f and r is a real number then f is reducible by the factor theorem.
If r=a +ib is not a real number, then because the complex conjugate of a sum(product) of complex numbers is the sum (product) of the conjugates of the numbers, and the complex conjugate of a real number is the same real number, we can show that f(a+bi) =0 = f(a-bi).  Now by the factor theorem (applied twice)
f = (X-(a+bi))*(X-(a-bi))*q=((X-a)2 + b2 )*q
and deg(q) = deg(f ) -2 >0. Thus f is reducible.

Back to Linear Algebra, Eigenvalues  and "the Minimal Polynomial for a Linear Operator":
Theorem: Suppose V is nontrivial f.d.v.s / C.  T in L(V). Then T has an eigenvalue.
Comment: First consider this with the
Coke/Pepsi example B:
T(x,y) =
(2/3 x +1/4 y, 1/3 x+3/4 y).
Consider ( e1= (1,0), T(
e1) = (2/3,1/3), T(T(e1 ))=  (4/9+1/12, 2/9+3/16) ). This must be linearly dependent because it has 3 vectors in R2. This gives some coefficients in R not all zero, where a0 Id(v) + a1T(v) + a2T2(v)=0. Thus we have f in R[X] , f =  a0  + a1X + a2X2
and  f(T)(e1) = 0. In fact, we can use f =(X-1)(X-5/12) . f(T)(e1)=(T-Id)(T-5/12Id)(e1)= (T-Id)((T-5/12Id)(e1))=(T-Id)(2/3-5/12,1/3) = 0 Thus we find that (T-Id) (1/3,1/3)= 0, so (1/3,1/3) is an eigenvector for T with eigenvalue 1.
Now here is a
Proof (outline): Suppose dim V = n >0.
Consider v, a nonzero element of V, and the set (v, T(v), T2(v),
T3(v)....Tn(v)).
Since this set has n+1 vectors it must be linearly dependent. ...
...
This means there is a non-zero polynomial, f,  in C[X] where f (T)(v) = 0.
Let m = deg(f ).
Using the FT of Alg for C we have that f = a (X-c1)... (X-cm).
Now apply this to T as a product and ....
for some i and w (not 0), (T-ciId) (w) = 0. Thus T has an eigenvalue.

Theorem:V, T as usual. Then there is some non-zero polynomial f in F[X] where f  (T) = 0, i.e., for all v in V, f  (T)(v)= 0.
Proof (outline).
Suppose dim(V)=n. Consider the set (Id, T, T2,T3....Tn*n).
Since this set has n*n+1 vectors in L(V) where dim(L(V))= n*n, so it must be linearly dependent. ...
...
This means there is a non-zero polynomial, f,  in C[X] where f (T) = 0, i.e., f(T)(v) = 0 for all v  in V.

Definition: Ann(T)={f in F[X] : f  (T) = 0}.  The previous Theorem shows Ann(T) has a non trival element.
Prop: f, g in Ann(T), h in F[X] then f+g and h*f are in Ann(T).

Theorem (The minimal polynomial): There is a non zero monic polynomial in Ann(T) of smallest degree. This polynomial is unique and any polynomial in Ann(T) has this polynomial as a factor.

Proof: The previous theorem has shown Ann(T) has a nonzero polynomial element. Considering the degrees of the non-zero polynomials in Ann(T) there is a smallest positive degree, call it m and a polynomial g in Ann(T) with deg(g) = m. If g = bXm +....terms of lower degree, where b is not 0,
then f = 1/b*g is also in Ann(T) and f  is a monic polynomial.

Now suppose h is also in Ann(T) , then by the division algorithm, h = q*f + r where either r = 0 or deg(r)< m. But since h and f are in Ann(T), h - q*f = r is also in Ann(T). Since deg(f )=m, which is the lowest degree for an element of Ann(T), it must be that r = 0, so h =q*f. Now if h is also monic and deg(h) = m, then deg(q) = 0, and since h and f are both monic, q = 1, and h = f. Thus the non zero monic polynomial in Ann(T) of smallest degree is unique!
11-14
Prop. (Min'l Poly meets eigenvalues)
Suppose m in F[X] is the mininal polynomial for T.
Then T has eigenvalues c if and only if X-c is a factor of m.
Proof: =>  Suppose  c is an eigenvalue for T.
Then W
=Null(T-c) is a nontrivial subspace of V and for w in Wc
T(w) = cw is also in Wc . Let S(w)=T(w) for w in Wc .Notice that S is in L(W).
As a linear operator on
Wc ,(X-c)(S) = 0, so X-c is the minimal polynomial for S.
But for any w in
Wc (and thus in V), m(S)(w) = m(T)(w) = 0, so m is in Ann(S), and X-c is a factor of m.

<=  Suppose
X-c is a factor of m.  m= (X-c)*q. Since m is the minimal polynomial for T and deg(q)= deg(m)-1, q(T) is not the 0 operator. Thus there is some v in V where w =q(T)(v) is not 0.
But
m(T)(v)=...=(T-cId)(q(T)(v))=(T-cId)(w) = 0. So c is an eigenvalue for T.   EOP

Cor. T is invertible if and only if the constant for = m(0) is not 0.
Cor. If T is invertible then T-1 = -1/
m(0) (( m-m(0))/X)(T))

Invariant Subspaces: V, T as usual.
Def'n:W is called an invariant subspace for T if for all w in W, T(w) is also in W... i.e. T(W)<W.
If W is an invariant subspace of T, then T:W->W is a linear operator as well, denoted T|W.
If W is an invariant subspace of T, then the minimal polyonmial of
T|W is a factor of the minimal polynomial of T.

Invariant Subspaces, Diagonal and Block Matrices:
If
V is a fdvs / F and T is in L(V)  with W1 ,W2 ,...,Wk invariant subspaces for T and V = W1 `oplus`W2 `oplus`...`oplus` Wk .
and if the basis for V is B is composed of bases for each
W1 ,W2 ,... ,Wk in order, then M(T)  is composed of matrix blocks - each of which is M(T|Wi). Furthermore if m1 ,m2 ,... , mk is the minimal polynomial for T restricted to W1 ,W2 ,... ,Wk then the minimal polynomial for T is the lowest common multiple of the polynomials m1 ,m2 ,... , mk.

11-19
Examples of Matrices, characteristics values and minimal polynomials.
[Some references here to the characteristic polynomial from previous course work in Linear algebra.]
Example 1. `((3,0,0),(0,3,0), (0,0,2))` is a diagonal matrix that has characteristic polynomial `(x-3)^2 (x-2)` but minimal polynomial `(x-3)(x-2)`.
Example 2.
`((3,1),(0,3))` is not diagonalizable. It has characteristic polynomial and minimal polynomial `(x-3)^2`.
These examples are relevant because of the following

Prop. Suppose m in F[X] is the mininal polynomial for T.
T is diagonalizable
if and only if there are distinct c1,...,cm in F where m =  (X-c1)... (X-cm)

Proof :
=> Suppose T is diagonalizable and T has eigenvalues c1,...,cm. By the preceeding Proposition,  for each c1,...,cm each (X-c1),...,(X-cm) is a factor of the minimal polynomial, and by our previous work, S=(X-c1)*...*(X-cm) is in Ann(T) so m = S.

<=
[ Modified from proof in Hoffman and Kunze- Linear algebra 2nd Ed]
Suppose
there are distinct c1,...,cm in F where m = (X-c1)*...*(X-cm).
Let W be the subspace spanned by all the characteristic vectors of  T. So W =
W1 +W2 +...+ Wm  where Wk = Null(T-ck).
We will show that V = W indirectly. Suppose V is not W.

Lemma: There is a vector v* not in W and a characteristic value cj  where w*=(T-cj Id)(v*) is in W. [Proof is below.]

Now express w* in terms of vectors in
Wk
Then for any polynomial h,
h(T)(w*) = h(c1)w1 +  ... +h(ck) wk.
Now
m = (X-cj )q and q-q(cj ) = (X-cj )k.

THUS...
q(T)(v*)-q(cj )(v*) = k(T)(T-cj Id)(v*)= k(T)(w*) which is in W!

BUT 0 = m(T)(v*)=(T-cj Id)(qT)(v*).... so q(T)(v*) is in W.

Thus q(cj )(v*)=q(T)(v*)- k(T)(w*) is in W.

But we assumed v* is not in W, so q(cj ) = 0. So the factor (X-cj ) appeared twice in m!  A Contradiction!
Proof of Lemma: We must find a vector v* not in W and a characteristic value cj  where w*=(T-cj Id)(v*) is in W.

Suppose b is in V but not in W.
Consider C={ all polynomials f where f (T) (
b) is in W}.
[There are some non-trivial elements of C since m(T)(b) = 0, so is in C.]
Of all the elements of C, there is a unique non-zero monic polynomial of least degree which we will call g.
[Proof left as exercise for Friday]
Then g is a factor of m. [Proof left as exercise for Friday.] Since b is not in W,  g is not a constant, and so deg( g ) >0.
Since we know all the factors of m, for some
cj ,
(X- cj  ) is a  factor of g.

So g= (X- cj  ) * h, and because g was of minimal degree for polynomials where  f (T) (b) is in W,
h(T)(b)=v* is not in W.

But  w* = g(T)(b) = (T-cj Id)h(T)(b) =  (T-cj Id)(v*) is in W.
End of lemma's proof.

11-21
Remark: Every monic polynomial is the minimal polynomial for some linear operator:
Suppose `f` is the polynomial and degree of `f` is `n`, `f = a_0 + a_1 X + a_2 X^2 + ... + a_{n-1}X^{n-1} + X^n`.
Let T: `R^n -> R^n` be defined by  T(`e_i`) = `e_{i+1}` for `i = 1,2,...n-1` and
T(`e_n`) =
`- (a_0e_1 + a_1e_2 + a_2 e_3 + ... + a_{n-1}e_n)`. Then the minimal polynomial of T is `f`.

Example:
`f = (X-2)(X-1)^2 = (X-2) (X^2 -2X +1) = X^3  -4X^2  -3X -2 `. Then using the standard basis T has matrix:
`((0,0, 2),(1,0,3), (0,1, 4))` and  `f` is the minimal polynomial for T.

Nilpotent Operators and Jordan Canonical Form.

Now what about operators where the minimal polynomial splits into powers of linears? or where the minimal polynomial has non-linear irreducible factors?

First Consider the case of powers of linear factors.
The simplest is just a power of X.  (or (X-c)).

Example: D: P3(R) -> P3(R), the derivative. Then the minimal polynomial for D is X4.

Definition:
In general, an operator N is called nilpotent if  for some k>0, Nk =0. The smallest such k is called the index of nilpotency for N, and  if  k is the index of nilpotency for N, then the minimal polynomial for N is Xk .

Proposition: If N is nilpotent of index k and dim V = k, then there is a basis for V , {b1,b2,...bk} where N(bk)= 0 and N(bi) = bi+1 for all i <k.
Proof: Since
the minimal polynomial for N is Xk, there is some vector v* in V where Nk-1 (v*) is not zero but Nk (v*)=0. Let b1 = v* and b2 = N(b1), b3 = N(b2), ...,bk = N(bk-1).
Then clearly N(
bk )= Nk (v*)=0. It suffices to show that (b1,b2,...bk) is linearly independent. Suppose a1b1 + a2b2+...+ akbk= 0. Then a1v* + a2N(v*)+...+ akNk-1 (v*)= 0. Now apply N to obtain Nk-1(a1b1 + a2b2+...+ akbk)= 0 or a1Nk-1b1 + a2Nk-1b2+...+ akNk-1bk= 0. But Nk-1bj =0 for  j>1, so a1Nk-1b1=0. But Nk-1 (v*) is not zero, so a1 = 0.  Now by using Nk-2(a2b2+...+ akbk)= 0 a similar analysis shows that a2 =0. Continuing we can show that a3 =0, ..., ak-1
= 0. But that leaves ak bk = 0 and thus ak = 0, so {b1,b2,...bk} is linearly independent.

Alternatively: Let f = (
a1, a2,...,ak) the polynomial of degree k-1 with a1, a2,...,afor coefficients. If is not the zero polynomial and f(N)(v*)=0 then  f  must be a factor of  Xk . But the assumption is that Nk-1 (v*) is not zero, so f must be the zero polynomial and all of the coefficients are 0. Hence, (b1,b2,...bk) is linearly independent.

12-1
Example: Find the basis for
D: P3(R) -> P3(R).
• Using the basis (b1,b2,...bk) the matrix for N, M(N) has 0 everywhere except for 1's that are below the main diagonal.
• If  T is an operator on a vector space V with dim V= k and the minimal polynomial for T is (X-c)k .
Then let N = T-cId and  so
Nk =0. So N is nilpotent with index of nilpotency k. Using the basis for V determined in the last proposition we have M(T-cId ) = M(T) - cM(Id), So the matrix of T  , M(T) = M(T-cId) + cM(Id). This matrix is called the Jordan Block matrix of dimension k for the characteristic value c. J(c;k)
• The BIG Picture.
• Theorem (Jordan Canonical Form): Suppose T is a linear operator on V and m is the minimal polynomial for T.
If m =
(X-c1)p1... (X-cm)pm then
there are
T- invariant subspaces W1,....,Wq with V = W1`oplus`... `oplus`Wq. Furthermore the minimal polynomial for T restricted to each subspace Wi is of the form (X-cj)riwhere dim(Wi) =ri and ri=<pj and ri= pj for at least one i and each j.

• Thus there is a basis for V so that using that basis, M(T) is a block matrix where each block has the form of the J(cj ; ri). This matrix is called the Jordan Canonical Form for T.
Fill in examples of possible matrices for T when m =
(X- 2)3(X+3)2X3 (X-1)
where dim (V) =12. Discuss uniqueness.

• 12-3

• By the Fundamental Theorem of Algebra, If V is a finite dimensional vector space over C,  then any linear operator on V has a basis for which M(T) is a Jordan Canonical Form.

• Corollary: For T a linear operator on V, a finite dimensional vs over R or C,  the degree of the minimal polynomial for T is not greater than the dimension of V.
Proof: By the Jordan Theorem, the degree of m is p1 + p2+ ....+ pm which is no greater than the r1+r2+ ... +rq = dim(V).

• Application to powers of matrices:
Suppose A is a n by n matrix with complex coefficients. Then there is a linear operator T on C
n that has A for it's matrix using the standard basis for Cn . By the Jordan Theorem, there is a basis for Cn where M(T)=J is in Jordan form. Thus there is an inverible matrix S where A =S-1 J S.
Now consider A
n = (S-1 J S )n = S-1J n S.
So we can determine the behavior of
An by studying powers of the Jordan blocks.
Do an example  with J( 1/2;3),
J( 1;3), J(2;3) , and J( i ;3).
What conclusions can we infer about the convergence of
An  for large n based on the eigenvalues of A?
If any eigenvalue ,c, has  |c|>1 then the sequence diverges. If |c| = 1 and c is not 1, then the sequence will not converge, c= 1 and the block is J(1;k) with k > 1, then the sequence diverges.
Otherwise, the sequence will converge!
• Look at J(c;3) and J(c;4) to see with examples... using technology.

• Application to Markov Chains:
A markov chain consist of a finite number, n, of states and a matrix T where T(i,j) = the probability that something currently in state j will move to state i after one period of transition. Thus 0 <= T(i,j)  <= 1 for all 1 <= i,j <= n. It is assumed the only possible changes of state from j to i are listed, so T(1,j) + T(2,j) +... +T(n,j) = 1 for any j. If v = (v1, v
2, ... ,vn) gives the initial distribution of objects in the various states, then T(v) is the likely distribution of objects after one period  of transition.
• T(v) i = T(i,1)v1 + T(i,2)v2 +... +T(i,n)vn , so T gives a linear operator on Rn and Cn. Notice that using the standard basis, M(T) = T. If we assume that the probabilities of T remain the same for every period of transition, then T is called a  Markov transition matrix. Given the initial distribution v, the distribution after k periods of transition is T(...(T(v))...) = Tk(v).  Treating T as a linear operator on Cn, there is a basis for Cn that is composed of Jordan blocks. Thus, the question of what happens to the distribution between the states in the long run is determined by the eigen values of T. T is called a regular Markov process, if  for some k, all the entries of Tk are positive.
• DO example to illustrate how this works on graph.

12-5
Theorem: If T is a regular Markov p
rocess, then 1 is an eigenvalue for T and all other eigenvalues of T have magnitude less than 1. Furthermore: Dim Null(T-Id)=1 and the power of X-1 in the minimal polynomial of T is 1.
• Corollary: For k large, Tk(v) is close to the unique vector v*in Cn where
T(v*)=v* and v1 + v2 +... +vn =v*1 + v*2 +... +v*n.
Illustrate this with example... and technology.
• Use the result to find long run for a 5 state markov process using graph  of transitions and technology to find the limit as the solution to T(v*)=v* or (T-Id)(v*)=0.

• Proof (outline ..based in part on Friedberg, Insel, Spence): Suppose T is a regular Markov process and let J be the Jordan matrix for T.
Fact: If c is an eigenvalue for T, then c is an eigenvalue for the transpose of T, Tt.
Proof of fact (outline): check: f (T)t = f(Tt), so T and Tt have the same minimal polynomial, hence the same eigenvalues.

Lemma 1: If c is an eigenvalue for T, then |c| ≤ 1.
Proof of Lemma 1:  Consider c as an eigenvalue for Tt. Suppose x be an eigenvector with eigenvalue c for Tt.
• Then (Tt(x))i =T(1,i)x1 + T(2,i)x2 +... +T(n,i)xn = cxi for each i. Let b = Max{|x1|,|x2|,...,|xn|}
Then for some k,
|c| b = |c xk| = |T(1,k)x1 + T(2,k)x2 +... +T(n,k)xn|
|T(1,k)x1|+ |T(2,k)x2 |+... +|T(n,k)xn|   [triangle inequality}
|T(1,k)||x1| + |T(2,k)||x2| +... +|T(n,k)||xn|          [  |ab|=|a| |b|  ]
|T(1,k)|b + |T(2,k)|b +... +|T(n,k)|b    [ b =Max{|x1|,|x2|,...,|xn|}]
≤ [|T(1,k)| + |T(2,k)| +... +|T(n,k)|]b = b
since T(1,j) + T(2,j) +... +T(n,j) = 1  and 0 T(i,j).
• Lemma 2: 1 is an eigenvalue for T.
Proof: 1 an eigenvalue for
Tt: T(1,j)1 + T(2,j)1 +... +T(n,j)1 = 1 so Tt has an eigenvector of (1,...,1) = u.
• Lemma 3: J has single blocks for c=1, of the form J(1;1).
Powers of T have real number entries that are never larger than 1. [Prove as exercise.]
But if there is a Jordan block in J  with J(1;k) with k>1, the powers will get much larger than 1.

• Lemma 4: If c is an eigenvalue for T with |c|=1, then c = 1 and Dim(Null(T-Id))= 1.
Proof: Since T is a regular Markov process, we may assume that all entries of T are positive.
First, since |c| = 1, all the previous inequalities in Lemma 1 are actually equalities for any eigenvector x for the eigenvalue c.

b =|c| b = |c xk| = |T(1,k)x1 + T(2,k)x2 +... +T(n,k)xn|
=|T(1,k)x1|+ |T(2,k)x2 |+... +|T(n,k)xn|     (*)
=|T(1,k)||x1| + |T(2,k)||x2| +... +|T(n,k)||xn|
=|T(1,k)|b + |T(2,k)|b +... +|T(n,k)|b   (**)
=[|T(1,k)| + |T(2,k)| +... +|T(n,k)|]b = b .
T(1,k) + T(2,k) +... +T(n,k) = 1
• Notice that for any complex numbers a and b,  |a+b| = |a| + |b|  only if a and b are "colinear", that is, there is some complex number z with |z| = 1 and non-negative real numbers r and where a = rz and b = sz.
Using this fact for  (*)  there must be some complex number z*  with |z*| = 1  and real numbers rj where

rj z* =T(j,k)xfor all j.
• From (**) ,  since b > 0, either T(j,k) = 0  or |xj|=b, but the assumption of regularity is that T(j,k)>0, so |xj|= b > 0  for all j. But then rj z*/T(j,k)=xso
b
=
|xj| = |rj z* /T(j,k) | =  rj |z*| /T(j,k) = rj/T(j,k) for all j. Thus b z* =xfor all j.
SO.... x = bz*(1,1,...,1) and c = 1.
Thus if If c is an eigenvalue for T with |c|=1, then c = 1 and if x is an eigenvector with eigenvalue 1 then x is a scalar multiple of (1,1,...,1), so Dim(Null(T-Id))= 1
EOP for Lemma.

• To Finish the Proof of the Theorem- note that since Dim(Null(T-Id))= 1, the factor of the minimal polynomial that corresponds to the eigenvalue 1 can only be (X-1), since all blocks in the Jordan matrix from the eigenvalu 1 are of the form J(1,1).

Proof of the Corollary:
By the Jordan Theorem, there is a basis for Cn where M(T)=J is in Jordan form. Thus there is an inverible matrix S where T =S-1 J S.
Now consider T
n = (S-1 J S )n = S-1J n S.
Since T has only 1 for a complex eigenvalue of magnitude 1, and all other eigenvalues have magnitude less than 1, and since there is only one block ( J(1,1) ) for the eigenvalue 1. For k large Tk, is close to the matrix  S-1 K S where K(1,1) = 1 and K(i,j) = 0 for (i,j) different from (1,1).
Now one can show that
S-1 K S is the square matrix which has each column equal to the eigenvector with eigenvalue  1and with the sum of its components equal to one.
From this it can be shown that for any v,
Tk(v) is close to the unique vector v*in Cn where
T(v*)=v* and v1 + v2 +... +vn =v*1 + v*2 +... +v*n.

• Do Example. We looked at a 3 by 3 example of a regular Markov chain matrix modelling the movement of rental cars between SF, LA, and Vegas. We assumed there are 400 cars in the fleet. To find the v* suggested by the Theorem, we need to solve Tv* = v* and 400=v*1 + v*2 +v*3 . This is equivalent to solving the system of equations (T-I)v* = 0 with 400=v*1 + v*2 +v*3 . Since the columns of T add to 1, the matrix T-I has linearly dependent rows (they add to 0). replacing the final row with 1 1 1  and  0 with (0,0,400) the equations had a unique solution, 400(3/11,6/11, 2/11). Obviously, if the total number of cars were N, then the result would be N(3/11,6/11, 2/11).  The proportions  are fixed then by  the characteristic vector  (3/11,6/11, 2/11).  Furthermore, this result is independent of the starting distribution, so  if all cars started in SF, the result would be the same, and similarly for LA or Vegas. So for n large Tn is approximately the matrix with each column equal to the transpose of (3/11,6/11, 2/11).

• Notice that T n -> T* where each column of T* is v* with  v*1+... + v*n = 1

Proof of JCF Theorem:  ?? Outline

• Miscellaneous topics:

• The determinant: An axiomatic approach with multilinearity.

Definition: V a fdvs  over F. A Function T: V n -> F is called a multilinear function on V if
T
(v1,..., vn) is a linear function for variable vector, i.e. for all i,

T(v1,. ,avi+v'i,.., vn)= aT(v1,.., vi,..., vn) + T(v1,..,v'i,..., vn)
Prop.: If T is multilinear then T
(v1,...,0,..., vn)=0.
• T is called alternating if
T(v1,.
..,vi ,..., vj, ..., vn) = -T(v1,... ,vj,...,vi,..., vn)
• Prop: If 1+1 is not 0, then T is alternating if and only if T(v1,..,vi ,...,vi,.., vn)= 0
• Assume for the remainder of this topic that  1+1 is not 0 in F.
• If T is alternating and multilinear then   (v1,. ,vi,...,avi+vj,.., vn)= T(v1,..,vi ,...,vj,..., vn)
• Theorem: There is a unique alternating multilinear function D on Fn  satisfying the property that D(e1,...,en) = 1.
Furthermore when considered as a function on the n by n matrices with coefficients in F,
D(M) = 0 if and only if M is singular.
• Start of Proof: Every square matrix is row equivalent to an upper triangular matrix. [Math 241.]
Lemma: If M is an upper triangular matrix, then D(M) is the product of the entries along the main diagonal.
Proof:Let the product be denoted p. Then D(M) = pD(M') where M' is upper triangular with 1's along the main diagonal. Then since D is alternating and multilinear, D(M') = D(I) = 1.
• D(MP) = D(M)D(P) ..... Proof : If D(P) = 0 then P is singular and so is MP, so D(MP) = D(M)*D(P).
Suppose D(P) is not 0. Let D* be defined on M by D*(M) =1/D(P)* D(MP). Show D* is multilinear, alternating and D*(I)=1.
• Cor. If M is invertible with inverse P then D(P) = 1/D(M).
• Cor. If T is a linear operator on a fdvs / F then D(T) = D(M(T)) is well defined using any basis.

• Prop: If N is the transpose of M, then D(M)=D(N).
Proof: Let D* be defined on M by D*(M) = D(
Mt
). Then show D* is multilinear, alternating and D*(I)=1.
• Cor. : If M is in O(n), then D(M)= +1 or - 1.
• Construction of D using permutations.
What is a permutation?
What is the sign of a permutation?
If p is a permutation and  t is a transposition then sign(tp) =  - sign(p)
Definition. D(M) =
Σ
sign(p) M1,p(1) * M2,p(2) * ...*Mn,p(n)
• D is multilinear, alternating and D(I) = 1.
• Applications of deteminants:
• D is a multivariable polynomial  on the n2 entries of a matrix.
• The collection of non-invertible matrices correspond to points in an n2 dimensional euclidean space where a single  polynomial equation  D(....) = 0. These matrices form a "hypersurface" in n2 euclidean space.
Thus the invertible matrices are an
n2  dimensional .."manifold"... in  n2 euclidean space, composed of all those points not on the hypersurface of non-invertible matrices.
These matrices are also a group under multiplication... in fact with a little more exploration of the properties it can be shown that the multiplication is a continuous (differentiable) function and so this group (called the "general linear group"  GL(n) ) is a special type of group called a Lie Group. [Pronounced "Lee"  named after Sophus Lie.]
• Area ,Volume, and generalized volume.
The rows of  M span P= {v in V where v is a linear combination of the row vectors of R with coefficients
in [0,1]}, a parallelogram, parallelpiped, ... in R2, R3, .....
Then |D(M)| = area P  or volume of P...
Geometry of the row operations and its effect on area and volume, etc
• The cross product in R3 and the determinant. Notice that the definition of D makes sense as long as the multiplication does, so  we can use one row of vectors and still compute D. Use (e1,e2, e3) for the first row and we can define v× w  using the matrix with v and w in the second and third rows.
Generalized "cross product" of n-1 vectors in Rn.
• What about eigenvalues, eigenvectors and determinants?
If c is an eigenvalue then A- cI or T-cId is singular.
Thus c is an eigenvalue for A (or T) if and only if D(A-cI) = 0 or D(T-cId) = 0
The characteristic polynomial! Notice that the definition of D make sense as long as the terms in the matrix can be  multiplied. So this will work for  polynomials in  F[X].  In particular, D(A-XI)  makes sense and is a polynomial of degree n. This polynomial is called the characteristic polynomial of A or T.  Sometimes this uses the letter χ.
The characteristic values of A or T are precisely the roots (zeroes) of its characteristic polynomial.

• Theorem: ( Cayley -Hamilton for C or R)  For any A (or T) , χ(A) = 0.
Proof: For Complex matrices. Use the Jordan Theorem and the Jordan matrix. Then the minimal polynomial of A is a factor of D(A-XI).  IRMC! For a matrix with real entries the result follows by considering the matrix as a matrix with complex entries.
• Comment: The minimal polynomial is a factor of the characteristic polynomial and has exactly the same roots-- which makes it a little easier to find the minimal polynomial.

Linear Programming; See  Waner - Costenoble's treatment of Linear Programming
or LINEAR PROGRAMMING:A Concise Introduction by Thomas S. Ferguson  (.pdf file)

• Inner Products:  Unit vectors ("normal"). Orthogonal vectors.
• V... finite dimensional i.p.s.  Notation: If  w = x+ yi then use ~w to denote the conjugate of w, so ~w = x - yi.
Orthonormal basis: ||vj||=<vk,vk> = 1. <vk,vj> = 0 for  k and j different.
• Suppose B = (v1,v2 ... vn) is an orthonormal basis for Fn.  Let A be the matrix that has each row  determined as the coordinates of the basis B in terms of the standard basis. Let A* be the matrix that is the conjugate of the transpose of A. Then AA* = I.

• If  B = (v1,v2 ... vn) is an orthonormal basis for V then v = sum <v,vj>vj .
Proof: v = Σ
ajvj so <v,vi> = <Σ ajvj , vi> = Σ aj <vj,vi> = ai
• Proposition: If S is an orthonormal set of vectors then S is linearly independent.
Proof: If 0=
Σ ajvj then 0=<0,vi> = <Σ ajvj , vi> = Σ aj <vj,vi> = ai for each i, so the vectors are linearly independent..
• How to find an orthonormal basis for a finite dimensional vector space.
Convert a basis C=
(w1,w2 ... wn). [Called the Gram-Schmidt process]: Start: v1= w1 / ||w1||.

Next: Let
z2= w2 - <w2,v1>v1, so <z2,v1 > =0. Now let v2= z2 / ||z2||. Then <v1,v2 > = 0 and Span(v1, v2 ) = Span (w1,w2 ).
• Continue....Let  z3= w3 - (<w3,v1>v1 + <w3,v2>v2), so <z3,v1 >=<z3,v2>  =0. Now let v3= z3 / ||z3||. Then <v3,v1 >=<v3,v2 > = 0 and Span(v1,v2,v3>) = Span (w1,w2 ,w3).  and so on.... until we are done.
• An Alternative: v3= w3 - (<w3,v1>/ ||v1||2 v1 + <w3,v2>/||v2||2 v2) , etc.
• <>Do an example  in R 3; discuss the geometry of this.
Orthogonal Linear Operators:
Def. T:V-> V in L(V) is called an orthogonal if ||T(v)|| = ||v|| for all v in V.
Relation to Inner Products, angles:
Prop: T is orthogonal if and only if <T(v),T(w)> =
<v,w> for all v and w in V.
An Orthonormal operator is 1:1 and "preserves the angles between vectors", in particular it transforms a set of orthonormal vectors to a set of orthonormal vectors.
An Orthonormal operator will transform an orthonormal basis to an orthonormal basis.
O(n): If V = Rn with the usual inner product, then O(n) = { T in L(V): T is orthonormal}
Prop: If T and S are in O(n) then , so TS and T-1 are also in O(n).
Comment: Since Multiplication of operators is associative, and clearly, Id is in O(n), O(n) forms a "group".... called the "orthogonal group."

Relation to matrices: A square matrix defines a linear operator by multiplication.  If T is the operator from the matrix M then using the standard basis, M(T) = M. Then T is orthogonal if and only if Mt*M = I.  Thus O(n) = {n by n matrices M | Mt*M = I}
• Upper triangular representations. The following gives an example of a proof  by mathematical induction on the dimension of a vector space. The proof of the Jordan theorem is another result that usually is  proven by some form of  mathematical induction.

Theorem 5.13  Vfdvs / C. T in L(V) then V has a basis B=(v1,..., vn)  where T(vk) is in Span(v1,..., vk). Thus M(T) is a matrix with M(T)ij = 0 for j<= i.

Proof: By induction on the dimension of V. When n = 1, the statement is true obviously. (!)

Now assume that dim(V) = n > 1 and the statement is true for all vector spaces of dimension less than n.
Since V isa complex vector space, T has an eigenvalue c.  Consider  S = T -cId. Then dim(Null(S))>0 making dim(R(S)) = m <n.  Let U = Range(S) and consider T(u) where u is in U.  T(u) = T(u) - cId(u) + cu= (T-cId) u + cu and clearly (T-cId) (u) is in U and cu is in U so T(u) is in U. Now we can apply the induction hypothesis to U to find a basis B'= (u1,..., um) for U so that T(uk) is in Span
(u1,..., um). Extend B' to a basis for V, B =(u1,..., um, v1,...vn-m) . Then  T(vk) = T(vk) - cId(vk) + cvk= (T-cId) vk + cvk . But (T-cId)vk is in U  so T(vk) is in the span(u1,..., um ,v1,...vk).

Cor. (5.16)V fdvs/ C, t in L(V). T is invertible iff all entries of the diagonal of an upper triangular matrix representing T are non-zero.