AAA Part IB of the Mathematical Tripos of the University of Cambridge Michaelmas 2012 Linear Algebra Lectured by: Notes by: Prof. I. Grojnowski Alex Chan Please send comments and corrections to [email protected]. The most recent copy of these notes can be downloaded from alexwlchan.net/maths These notes are licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License. The following resources are not endorsed by the University of Cambridge. Printed Tuesday, 7 May 2013. Course schedule Denition of a vector space (over R or C), subspaces, the space spanned by a subset. Linear independence, bases, dimension. Direct sums and complementary subspaces. [3] Linear maps, isomorphisms. Relation between rank and nullity. The space of linear maps from U to V, representation by matrices. Change of basis. Row rank and column rank. [4] Determinant and trace of a square matrix. Determinant of a product of two matrices and of the inverse matrix. Determinant of an endomorphism. The adjugate matrix. [3] Eigenvalues and eigenvectors. Diagonal and triangular forms. Characteristic and min- imal polynomials. Cayley-Hamilton Theorem over C. Algebraic and geometric multi- plicity of eigenvalues. Statement and illustration of Jordan normal form. [4] Dual of a nite-dimensional vector space, dual bases and maps. Matrix representation, rank and determinant of dual map. [2] Bilinear forms. Matrix representation, change of basis. Symmetric forms and their link with quadratic forms. Diagonalisation of quadratic forms. Law of inertia, classification by rank and signature. Complex Hermitian forms. [4] Inner product spaces, orthonormal sets, orthogonal projection, V = W ⊕W⊥. Gram- Schmidt orthogonalisation. Adjoints. Diagonalisation of Hermitian matrices. Orthogo- nality of eigenvectors and properties of eigenvalues. [4] Appropriate books C.W. Curtis Linear Algebra: an Introductory Approach. Springer 1984 (38.50 hardback) P.R. Halmos Finite-Dimensional Vector Spaces. Springer 1974 (31.50 hardback) K. Hoffman and R. Kunze Linear Algebra. Prentice-Hall 1971 (72.99 hardback) Contents 1 Vector spaces 3 1.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 Linear maps and matrices . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.5 Conservation of dimension: the rank-nullity theorem . . . . . . . . . . . 17 1.6 Sums and intersections of subspaces . . . . . . . . . . . . . . . . . . . . 21 2 Endomorphisms 25 2.1 Determinants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3 Jordan normal form 35 3.1 Eigenvectors and eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . 35 3.2 Cayley-Hamilton theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.3 Combinatorics of nilpotent matrices . . . . . . . . . . . . . . . . . . . . 45 3.4 Applications of JNF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4 Duals 53 5 Bilinear forms 57 5.1 Symmetric forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 5.2 Anti-symmetric forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 6 Hermitian forms 69 6.1 Inner product spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 6.2 Hermitian adjoints for inner products . . . . . . . . . . . . . . . . . . . 74 Vector spaces | 3 1 Vector spaces 1.1 Definitions Lecture 1 We start by fixing a field, F. We say that F is a field if: • F is an abelian group under an operation called addition, (+), with additive iden- tity 0; • F\{0} is an abelian group under an operation called multiplication, (·), with mul- tiplicative identity 1; • Multiplication is distributive over addition; that is, a(b+c) = ab + ac for all a,b,c ∈ F. Fields we’ve encountered before include the reals R, the complex numbers C, the ring of √ √ integers modulo p, Z/p = F , the rationals Q, as well as Q[ 3] = {a+b 3 : a,b ∈ Q}. p Everything we will discuss works over any field, but it’s best to have R and C in mind, since that’s what we’re most familiar with. Definition. A vector space over F is a tuple (V,+,·) consisting of a set V, opera- tions + : V ×V → V (vector addition) and · : F×V → V (scalar multiplication) such that (i) (V,+) is an abelian group, that is: • Associative: for all v ,v ,v ∈ V, (v +v )+v = v +(v +v ); 1 2 3 1 2 3 1 2 3 • Commutative: for all v ,v ∈ V, v +v = v +v ; 1 2 1 2 2 1 • Identity: there is some (unique) 0 ∈ V such that, for all v ∈ V, 0+v = v = v+0; • Inverse: for all v ∈ V, there is some u ∈ V with u+v = v+u = 0. This inverse is unique, and often denoted −v. (ii) Scalar multiplication satisfies • Associative: for all λ ,λ ∈ F, v ∈ V, λ ·(λ ·v) = (λ λ )·v; 1 2 1 2 1 2 • Identity: for all v ∈ V, the unit 1 ∈ F acts by 1·v = v; • ·distributesover+ : forallλ ∈ F,v ,v ∈ V,λ·(v +v ) = λ·v +λ·v ; V 1 2 1 2 1 2 • +F distributesover·: forallλ1,λ2 ∈ F,v ∈ V,(λ1+λ2)·v = λ1·v+λ2·v; We usually say “the vector space V” rather than (V,+,·). 4 | IB Linear Algebra Examples 1.1. (i) {0} is a vector space. (ii) Vectors in the plane under vector addition form a vector space. (iii) The space of n-tuples with entries in F, denoted Fn = (cid:8)(a ,...,a ) : a ∈ F(cid:9) 1 n i with component-wise addition (a ,...,a )+(b ,...,b ) = (a +b ,...,a +b ) 1 n 1 n 1 1 n n and scalar multiplication λ·(a ,...,a ) = (λa ,...,λa ). 1 n 1 n Proving that this is a vector space is an exercise. It is also a special case of the next example. (iv) Let X be any set, and FX = {f : X → F} be the set of all functions X → F. This is a vector space, with addition defined pointwise: (f +g)(x) = f(x)+g(x) and multiplication also defined pointwise: (λ·f)(x) = λf(x) if λ ∈ F, f,g ∈ FX, x ∈ X. If X = {1,...,n}, then FX = Fn and we have the previous example. Proof that FX is a vector space. • As + in F is commutative, we have (f +g)(x) = f(x)+g(x) = g(x)+f(x) = (g+f)(x), so f +g = g +f. Similarly, f in F associative implies f + (g +h) = (f +g)+h, and that (−f)(x) = −f(x) and 0(x) = 0. • Axioms for scalar multiplication follow from the relationship between · and + in F. Check this yourself! (v) C is a vector space over R. Lemma 1.2. Let V be a vector space over F. (i) For all λ ∈ F, λ·0 = 0, and for all v ∈ V, 0·v = 0. (ii) Conversely, if λ·v = 0 and λ ∈ F has λ (cid:54)= 0, then v = 0. (iii) For all v ∈ V, −1·v = −v. Proof. (i) λ·0 = λ·(0+0) = λ·0+λ·0 =⇒ λ·0 = 0. 0·v = (0+0)·v = 0·v+0·v =⇒ 0·v = 0. (ii) As λ ∈ F, λ (cid:54)= 0, there exists λ−1 ∈ F such that λ−1λ = 1, so v = (λ−1λ)·v = λ−1(λ·v), hence if λ·v = 0, we get v = λ−1·0 = 0 by (i). (iii) 0 = 0·v = (1+(−1))·v = 1·v+(−1·v) = v+(−1·v) =⇒ −1·v = −v. We will write λv rather than λ·v from now on, as the lemma means this will not cause any confusion. Vector spaces | 5 1.2 Subspaces Definition. Let V be a vector space over F. A subset U ⊆ V is a vector subspace (or just a subspace), written U ≤ V, if the following holds: (i) 0 ∈ U; (ii) If u ,u ∈ U, then u +u ∈ U; 1 2 1 2 (iii) If u ∈ U, λ ∈ F, then λu ∈ U. Equivalently, U is a subspace if U ⊆ V, U (cid:54)= ∅ (U is non-empty) and for all u,v ∈ U, λ,µ ∈ F, λu+µv ∈ U. Lemma 1.3. If V is a vector space over F and U ≤ V, then U is a vector space over F under the restriction of the operations + and · on V to U. (Proof is an exercise.) Examples 1.4. (i) {0} and V are always subspaces of V. (ii) (cid:8)(r ,...,r ,0,...,0) : r ∈ R(cid:9) ⊆ Rn+m is a subspace of Rn+m. 1 n i (iii) The following are all subspaces of sets of functions: C1(R) = (cid:8)f : R → R | f continuously differentiable(cid:9) ⊆ C(R) = (cid:8)f : R → R | f continuous(cid:9) ⊆ RR = {f : R → R}. Consider: f,g continuous implies that f +g is, and λf is, for λ ∈ R; the zero function is continuous, so C(R) is a subspace of RR, similarly for C1(R). (iv) Let X be any set, and write F[X] = (FX) = (cid:8)f : X → F | f(x) (cid:54)= 0 for only finitely many x ∈ X(cid:9). fin This is the set of finitely supported functions, which is is a subspace of FX. Consider: if f(x) = 0, then λf(x) = 0, so if f ∈ (FX) , then so is λf. fin Similarly, (f +g)−1(F\{0}) ⊆ f−1(F\{0})∪g−1(F\{0}) and if these two are finite, then so is the LHS. Now consider the special case X = N: F[N] = (FN) = (cid:8)(λ ,λ ,...) | only finitely many λ are non-zero(cid:9). fin 0 1 i We write xi for the function which sends i (cid:55)→ 1, j (cid:55)→ 0 if j (cid:54)= i; that is, for the tuple (0,...,0,1,0,...) in the ith place. Thus F[N] = (cid:8)(cid:80)λ | only finitely many λ non-zero(cid:9). i i We can do better than a vector space here: define multiplication by (cid:0)(cid:80)λ xi(cid:1)(cid:0)(cid:80)µ xj(cid:1) = (cid:80)λ µ ·xi+j. i j i j This is still in F[N]. It is more usual to denote this by F[x], the polynomials in x over F (and this is a formal definition of the polynomial ring). 6 | IB Linear Algebra 1.3 Bases Lecture 2 Definition. SupposeV is a vector space over F, andS ⊆ V is a subset of V. Then v isalinear combination ofelementsofS ifthereissomen > 0andλ ,...,λ ∈ F, 1 n v ,...,v ∈ S such that v = λ v +···+λ v or if v = 0. 1 n 1 1 n n We write (cid:104)S(cid:105) for the span of S, the set of all linear combinations of elements of S. Notice that it is important in the definition to use only finitely many elements – infinite sums do not make sense in arbitrary vector spaces. We will see later why it is convenient notation to say that 0 is a linear combination of n = 0 elements of S. (cid:10) (cid:11) Example 1.5. ∅ = {0}. Lemma 1.6. (i) (cid:104)S(cid:105) is a subspace of V. (ii) If W ≤ V is a subspace, and S ⊆ W, then (cid:104)S(cid:105) ≤ W; that is, (cid:104)S(cid:105) is the smallest subset of V containing S. Proof. (i) is immediate from the definition. (ii) is immediate, by (i) applied to W. Definition. We say that S spans V if (cid:104)S(cid:105) = V. Example 1.7. The set {(1,0,0),(0,1,0),(1,1,0),(7,8,0)} spans (cid:8)(x,y,0)(cid:9) ≤ R3. Definition. Letv ,...,v beasequenceofelementsinV. Wesaytheyarelinearly 1 n dependent if there exist λ ,...,λ ∈ F, not all zero, such that 1 n n (cid:88) λ v = 0, i i i=1 which we call a linear relation among the v . We say that v ,...,v are linearly i 1 n independent if they are not linearly dependent; that is, if there is no linear relation among them, or equivalently if n (cid:88) λ v = 0 =⇒ λ = 0 for all i. i i i i=1 We say that a subset S ⊆ V is linearly independent if every finite sequence of distinct elements in S is linearly independent. Vector spaces | 7 Notethatifv ,...,v islinearlyindependent,thensoiseveryreorderingv ,...,v . 1 n π(1) π(n) • If v ,...,v are linearly independent, and v ,...,v is a subsequence, then the 1 n i1 ik subsequence is also linearly independent. • If some v = 0, then 1 · 0 = 0 is a linear relation, so v ,...,v is not linearly i 1 n independent. • If v = v for some i (cid:54)= j, then 1 · v + (−1)v = 0 is a linear relation, so the i j i j sequence isn’t linearly independent. • If |S| < ∞, say S = {v ,...,v }, then S is linearly independent if and only if 1 n v ,...,v are linearly independent. 1 n        1 0    Example 1.8. Let V = R3, S = 0,1 , and then  0 0        1 0 λ 1 λ10+λ21 = λ2 0 0 0 is zero if and only if λ = λ = 0, and so S is linearly independent. 1 2 Exercises 1.9. (i) Show that v ,v ∈ V are linearly dependent if and only if v = 0 or v = λv 1 2 1 2 1 for some λ ∈ F.          1 1 2    (ii) Let S = 0,2,1 , then  1 0 0           1 1 2 1 1 2 λ 1 λ10+λ22+λ31 = 0 2 1λ2, 1 0 0 1 0 0 λ 3 (cid:124) (cid:123)(cid:122) (cid:125) A so linear independence of S is the same as Aλ = 0 =⇒ λ = 0. Show that in this example, there are no non-zero solutions. (iii) If S ⊆ Fn, S = {v ,...,v }, then show that finding a relation of linear 1 m dependence(cid:80)m λ v isequivalenttosolvingAλ = 0, whereA = (v ... v ) i=1 i i 1 m is an n×m matrix whose columns are the v . i (iv) Hence show that every collection of four vectors in R3 has a relation of linear dependence. Definition. The set S ⊆ V is a basis for V if (i) S is linearly independent and; (ii) S spans V. Remark. This is slightly the wrong notion. We should order S, but we’ll deal with this later. 8 | IB Linear Algebra Examples 1.10. (i) By convention, the vector space {0} has ∅ as a basis. (ii) S = {e ,...,e }, where e is a vector of all zeroes except for a one in the ith 1 n i position, is a basis of Fn called the standard basis. (iii) F[x] = F[N] = (FN) has basis (cid:8)1,x,x2,...(cid:9). fin More generally, F[X] has (cid:8)δ | x ∈ X(cid:9) as a basis, where x (cid:40) 1 if x = y, δ (y) = x 0 otherwise, so F[X] is, formally, the set of linear combinations of elements of X. For amusement: F[N] ≤ FN, and 1,x,x2,... are linearly independent in FN as they are linearly independent in F[N], but they do not span FN, as (1,1,1,...) (cid:54)∈ F[N]. Show that if a basis of FN exists, then it is uncountable. Lemma 1.11. A set S is a basis of V if and only if every vector v ∈ V can be written uniquely as a linear combination of elements of S. Proof. (⇐) Writing v as a linear combination of elements of S for every v ∈ V means that (cid:104)S(cid:105) = V. Uniquely means that, in particular, 0 can be written uniquely, and so S is linearly independent. (⇒)Ifv = (cid:80)n λ v = (cid:80)n µ v ,wherev ∈ S andi = 1,...,n,then(cid:80)n (λ −µ )v = i=1 i i i=1 i i i i=1 i i i 0, and since the v are linearly independent, λ = µ for all i. i i i Observe: if S is a basis of V, |S| = d and |F| = q < ∞ (for example, F = Z/pZ, and q = p), then the lemma gives |V| = qd, which implies that d is the same, regardless of choice of basis for V, that is every basis of V has the same size. In fact, this is true when F = R or indeed when F is arbitrary, which means we must give a proof without counting. We will now slowly show this, showing that the language of vector spaces reduces the proof to a statement about matrices – Gaussian elimination (row reduction) – we’re already familiar with. Definition. V is finite dimensional if there exists a finite set S which spans V. Lecture 3 Theorem 1.12 Let V be a vector space over F, and let S span V. If S is finite, then S has a subset which is a basis for V. In particular, if V is finite dimensional, then V has a basis. Proof. If S is linearly independent, then we’re done. Otherwise, there exists a relation of linear dependence, (cid:80)n c v = 0, where not all c are zero (for c ∈ F). Sup- i=1 i i i i (cid:80) (cid:80) pose c (cid:54)= 0, then we get c v = − c v , so v = − c v /c , and hence we i0 (cid:10) i0 i0 j(cid:54)=i0 j j(cid:11) i0 j j i0 claim(cid:104)v ,...,v (cid:105) = v ,...,v ,v ,...,v (proofisanexercise). Soremovingv 1 m 1 i0−1 i0+1 m i0 doesn’t change the span. We repeat this process, continuing to remove elements until we have a basis. Remark. If S = {0}, say with V = {0}, then the proof says remove 0 from the set S to get ∅, which is why it is convenient to say that ∅ is a basis of {0}.