Linear Algebra As an Introduction to Abstract Mathematics Lecture Notes for MAT67 University of California, Davis written Fall 2007, last updated January 2, 2016 Isaiah Lankham Bruno Nachtergaele Anne Schilling Copyright (cid:13)c 2007 by the authors. These lecture notes may be reproduced in their entirety for non-commercial purposes. Contents 1 What is Linear Algebra? 1 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 What is Linear Algebra? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Systems of linear equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3.1 Linear equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3.2 Non-linear equations . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3.3 Linear transformations . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3.4 Applications of linear equations . . . . . . . . . . . . . . . . . . . . . 7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2 Introduction to Complex Numbers 11 2.1 Definition of complex numbers . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2 Operations on complex numbers . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2.1 Addition and subtraction of complex numbers . . . . . . . . . . . . . 12 2.2.2 Multiplication and division of complex numbers . . . . . . . . . . . . 13 2.2.3 Complex conjugation . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2.4 The modulus (a.k.a. norm, length, or magnitude) . . . . . . . . . . . 16 2.2.5 Complex numbers as vectors in R2 . . . . . . . . . . . . . . . . . . . 18 2.3 Polar form and geometric interpretation for C . . . . . . . . . . . . . . . . . 19 2.3.1 Polar form for complex numbers . . . . . . . . . . . . . . . . . . . . . 19 2.3.2 Geometric multiplication for complex numbers . . . . . . . . . . . . . 20 2.3.3 Exponentiation and root extraction . . . . . . . . . . . . . . . . . . . 21 2.3.4 Some complex elementary functions . . . . . . . . . . . . . . . . . . . 22 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 ii 3 The Fundamental Theorem of Algebra and Factoring Polynomials 26 3.1 The Fundamental Theorem of Algebra . . . . . . . . . . . . . . . . . . . . . 26 3.2 Factoring polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4 Vector Spaces 36 4.1 Definition of vector spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.2 Elementary properties of vector spaces . . . . . . . . . . . . . . . . . . . . . 39 4.3 Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.4 Sums and direct sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 5 Span and Bases 48 5.1 Linear span . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 5.2 Linear independence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 5.3 Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 5.4 Dimension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 6 Linear Maps 64 6.1 Definition and elementary properties . . . . . . . . . . . . . . . . . . . . . . 64 6.2 Null spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 6.3 Range . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 6.4 Homomorphisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 6.5 The dimension formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 6.6 The matrix of a linear map . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 6.7 Invertibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 7 Eigenvalues and Eigenvectors 85 7.1 Invariant subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 7.2 Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 7.3 Diagonal matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 7.4 Existence of eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 iii 7.5 Upper triangular matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 7.6 Diagonalization of 2×2 matrices and applications . . . . . . . . . . . . . . . 96 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 8 Permutations and the Determinant of a Square Matrix 102 8.1 Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 8.1.1 Definition of permutations . . . . . . . . . . . . . . . . . . . . . . . . 102 8.1.2 Composition of permutations . . . . . . . . . . . . . . . . . . . . . . 105 8.1.3 Inversions and the sign of a permutation . . . . . . . . . . . . . . . . 107 8.2 Determinants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 8.2.1 Summations indexed by the set of all permutations . . . . . . . . . . 110 8.2.2 Properties of the determinant . . . . . . . . . . . . . . . . . . . . . . 112 8.2.3 Further properties and applications . . . . . . . . . . . . . . . . . . . 115 8.2.4 Computing determinants with cofactor expansions . . . . . . . . . . . 116 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 9 Inner Product Spaces 120 9.1 Inner product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 9.2 Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 9.3 Orthogonality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 9.4 Orthonormal bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 9.5 The Gram-Schmidt orthogonalization procedure . . . . . . . . . . . . . . . . 129 9.6 Orthogonal projections and minimization problems . . . . . . . . . . . . . . 132 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 10 Change of Bases 139 10.1 Coordinate vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 10.2 Change of basis transformation . . . . . . . . . . . . . . . . . . . . . . . . . 141 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 11 The Spectral Theorem for Normal Linear Maps 147 11.1 Self-adjoint or hermitian operators . . . . . . . . . . . . . . . . . . . . . . . 147 11.2 Normal operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 11.3 Normal operators and the spectral decomposition . . . . . . . . . . . . . . . 151 iv 11.4 Applications of the Spectral Theorem: diagonalization . . . . . . . . . . . . 153 11.5 Positive operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 11.6 Polar decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 11.7 Singular-value decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . 159 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 List of Appendices A Supplementary Notes on Matrices and Linear Systems 164 A.1 From linear systems to matrix equations . . . . . . . . . . . . . . . . . . . . 164 A.1.1 Definition of and notation for matrices . . . . . . . . . . . . . . . . . 165 A.1.2 Using matrices to encode linear systems . . . . . . . . . . . . . . . . 168 A.2 Matrix arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 A.2.1 Addition and scalar multiplication . . . . . . . . . . . . . . . . . . . . 171 A.2.2 Multiplication of matrices . . . . . . . . . . . . . . . . . . . . . . . . 175 A.2.3 Invertibility of square matrices . . . . . . . . . . . . . . . . . . . . . . 179 A.3 Solving linear systems by factoring the coefficient matrix . . . . . . . . . . . 181 A.3.1 Factorizing matrices using Gaussian elimination . . . . . . . . . . . . 182 A.3.2 Solving homogeneous linear systems . . . . . . . . . . . . . . . . . . . 192 A.3.3 Solving inhomogeneous linear systems . . . . . . . . . . . . . . . . . . 195 A.3.4 Solving linear systems with LU-factorization . . . . . . . . . . . . . . 199 A.4 Matrices and linear maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204 A.4.1 The canonical matrix of a linear map . . . . . . . . . . . . . . . . . . 204 A.4.2 Using linear maps to solve linear systems . . . . . . . . . . . . . . . . 205 A.5 Special operations on matrices . . . . . . . . . . . . . . . . . . . . . . . . . . 211 A.5.1 Transpose and conjugate transpose . . . . . . . . . . . . . . . . . . . 211 A.5.2 The trace of a square matrix . . . . . . . . . . . . . . . . . . . . . . . 212 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 B The Language of Sets and Functions 218 B.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 B.2 Subset, union, intersection, and Cartesian product . . . . . . . . . . . . . . . 220 B.3 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 v B.4 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 C Summary of Algebraic Structures Encountered 226 C.1 Binary operations and scaling operations . . . . . . . . . . . . . . . . . . . . 226 C.2 Groups, fields, and vector spaces . . . . . . . . . . . . . . . . . . . . . . . . . 229 C.3 Rings and algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 D Some Common Math Symbols and Abbreviations 236 E Summary of Notation Used 243 F Movie Scripts 246 vi Chapter 1 What is Linear Algebra? 1.1 Introduction This book aims to bridge the gap between the mainly computation-oriented lower division undergraduate classes and the abstract mathematics encountered in more advanced mathe- matics courses. The goal of this book is threefold: 1. You will learn Linear Algebra, which is one of the most widely used mathematical theories around. Linear Algebra finds applications in virtually every area of mathe- matics, including multivariate calculus, differential equations, and probability theory. It is also widely applied in fields like physics, chemistry, economics, psychology, and engineering. You are even relying on methods from Linear Algebra every time you use an internet search like Google, the Global Positioning System (GPS), or a cellphone. 2. You will acquire computational skills to solve linear systems of equations, perform operations on matrices, calculate eigenvalues, and find determinants of matrices. 3. In the setting of Linear Algebra, you will be introduced to abstraction. As the theory of Linear Algebra is developed, you will learn how to make and use definitions and how to write proofs. The exercises for each Chapter are divided into more computation-oriented exercises and exercises that focus on proof-writing. 1 2 CHAPTER 1. WHAT IS LINEAR ALGEBRA? 1.2 What is Linear Algebra? Linear Algebra is the branch of mathematics aimed at solving systems of linear equations with a finite number of unknowns. In particular, one would like to obtain answers to the following questions: • Characterization of solutions: Are there solutions to a given system of linear equations? How many solutions are there? • Finding solutions: How does the solution set look? What are the solutions? Linear Algebra is a systematic theory regarding the solutions of systems of linear equations. Example 1.2.1. Let us take the following system of two linear equations in the two un- knowns x and x : 1 2 (cid:41) 2x +x = 0 1 2 . x −x = 1 1 2 This system has a unique solution for x ,x ∈ R, namely x = 1 and x = −2. 1 2 1 3 2 3 The solution can be found in several different ways. One approach is to first solve for one of the unknowns in one of the equations and then to substitute the result into the other equation. Here, for example, we might solve to obtain x = 1+x 1 2 from the second equation. Then, substituting this in place of x in the first equation, we 1 have 2(1+x )+x = 0. 2 2 From this, x = −2/3. Then, by further substitution, 2 (cid:18) (cid:19) 2 1 x = 1+ − = . 1 3 3 Alternatively, we can take a more systematic approach in eliminating variables. Here, for example, we can subtract 2 times the second equation from the first equation in order to obtain 3x = −2. It is then immediate that x = −2 and, by substituting this value for x 2 2 3 2 in the first equation, that x = 1. 1 3 1.2. WHAT IS LINEAR ALGEBRA? 3 Example 1.2.2. Take the following system of two linear equations in the two unknowns x 1 and x : 2 (cid:41) x +x = 1 1 2 . 2x +2x = 1 1 2 We can eliminate variables by adding −2 times the first equation to the second equation, whichresultsin0 = −1. Thisisobviouslyacontradiction, andhencethissystemofequations has no solution. Example 1.2.3. Letustakethefollowingsystemofonelinearequationinthetwounknowns x and x : 1 2 x −3x = 0. 1 2 In this case, there are infinitely many solutions given by the set {x = 1x | x ∈ R}. You 2 3 1 1 can think of this solution set as a line in the Euclidean plane R2: x 2 x = 1x 1 2 3 1 x 1 −3 −2 −1 1 2 3 −1 In general, a system of m linear equations in n unknowns x ,x ,...,x is a collec- 1 2 n tion of equations of the form  a x +a x +···+a x = b 11 1 12 2 1n n 1   a x +a x +···+a x = b  21 1 22 2 2n n 2 . . , (1.1) . . . .     a x +a x +···+a x = b  m1 1 m2 2 mn n m wherethea ’sarethecoefficients(usuallyrealorcomplexnumbers)infrontoftheunknowns ij x , and the b ’s are also fixed real or complex numbers. A solution is a set of numbers j i s ,s ,...,s such that, substituting x = s ,x = s ,...,x = s for the unknowns, all of 1 2 n 1 1 2 2 n n the equations in System (1.1) hold. Linear Algebra is a theory that concerns the solutions and the structure of solutions for linear equations. As we progress, you will see that there is a lot of subtlety in fully understanding the solutions for such equations. 4 CHAPTER 1. WHAT IS LINEAR ALGEBRA? 1.3 Systems of linear equations 1.3.1 Linear equations Before going on, let us reformulate the notion of a system of linear equations into the language of functions. This will also help us understand the adjective “linear” a bit better. A function f is a map f : X → Y (1.2) from a set X to a set Y. The set X is called the domain of the function, and the set Y is called the target space or codomain of the function. An equation is f(x) = y, (1.3) where x ∈ X and y ∈ Y. (If you are not familiar with the abstract notions of sets and functions, please consult Appendix B.) Example 1.3.1. Let f : R → R be the function f(x) = x3 −x. Then f(x) = x3 −x = 1 is an equation. The domain and target space are both the set of real numbers R in this case. In this setting, a system of equations is just another kind of equation. Example 1.3.2. Let X = Y = R2 = R × R be the Cartesian product of the set of real numbers. Then define the function f : R2 → R2 as f(x ,x ) = (2x +x ,x −x ), (1.4) 1 2 1 2 1 2 and set y = (0,1). Then the equation f(x) = y, where x = (x ,x ) ∈ R2, describes the 1 2 system of linear equations of Example 1.2.1. The next question we need to answer is, “What is a linear equation?”. Building on the definition of an equation, a linear equation is any equation defined by a “linear” function f that is defined on a “linear” space (a.k.a. a vector space as defined in Section 4.1). We will elaborate on all of this in later chapters, but let us demonstrate the main features of a “linear” space in terms of the example R2. Take x = (x ,x ),y = (y ,y ) ∈ R2. There are 1 2 1 2