Linear Algebra As an Introduction to Abstract Mathematics Lecture Notes for MAT67 University of California, Davis written Fall 2007, last updated February 10, 2012 Isaiah Lankham Bruno Nachtergaele Anne Schilling Copyright c 2007 by the authors. (cid:13) These lecture notes may be reproduced in their entirety for non-commercial purposes. Contents 1 What is Linear Algebra? 1 1.1 Introduction to MAT 67 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 . . . . . . . . . . . . . . . . . . . . . . . . . . 6 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 . . . . . . . . . . . . . . . . . . . . . 38 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 Ranges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 . . . . . . . . . . . . . . . . . . . . . . 106 8.1.3 Inversions and the sign of a permutation . . . . . . . . . . . . . . . . 108 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 9.4 Orthonormal bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 9.5 The Gram-Schmidt orthogonalization procedure . . . . . . . . . . . . . . . . 129 9.6 Orthogonal projections and minimization problems . . . . . . . . . . . . . . 131 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 Supplementary Notes on Matrices and Linear Systems 164 12.1 From linear systems to matrix equations . . . . . . . . . . . . . . . . . . . . 164 12.1.1 Definition of and notation for matrices . . . . . . . . . . . . . . . . . 165 12.1.2 Using matrices to encode linear systems . . . . . . . . . . . . . . . . 168 12.2 Matrix arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 12.2.1 Addition and scalar multiplication . . . . . . . . . . . . . . . . . . . . 171 12.2.2 Multiplying and matrices . . . . . . . . . . . . . . . . . . . . . . . . . 175 12.2.3 Invertibility of square matrices . . . . . . . . . . . . . . . . . . . . . . 179 12.3 Solving linear systems by factoring the coefficient matrix . . . . . . . . . . . 181 12.3.1 Factorizing matrices using Gaussian elimination . . . . . . . . . . . . 181 12.3.2 Solving homogenous linear systems . . . . . . . . . . . . . . . . . . . 191 12.3.3 Solving inhomogeneous linear systems . . . . . . . . . . . . . . . . . . 194 12.3.4 Solving linear systems with LU-factorization . . . . . . . . . . . . . . 198 12.4 Matrices and linear maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 12.4.1 The canonical matrix of a linear map . . . . . . . . . . . . . . . . . . 203 12.4.2 Using linear maps to solve linear systems . . . . . . . . . . . . . . . . 204 12.5 Special operations on matrices . . . . . . . . . . . . . . . . . . . . . . . . . . 210 12.5.1 Transpose and conjugate transpose . . . . . . . . . . . . . . . . . . . 210 12.5.2 The trace of a square matrix . . . . . . . . . . . . . . . . . . . . . . . 211 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 List of Appendices A The Language of Sets and Functions 217 A.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 A.2 Subset, union, intersection, and Cartesian product . . . . . . . . . . . . . . . 219 A.3 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 v A.4 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 B Summary of Algebraic Structures Encountered 225 B.1 Binary operations and scaling operations . . . . . . . . . . . . . . . . . . . . 225 B.2 Groups, fields, and vector spaces . . . . . . . . . . . . . . . . . . . . . . . . . 228 B.3 Rings and algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 C Some Common Math Symbols & Abbreviations 235 D Summary of Notation Used 242 E Movie Scripts 245 vi Chapter 1 What is Linear Algebra? 1.1 Introduction to MAT 67 This class may well be one of your first mathematics classes that bridges the gap between the mainly computation-oriented lower division classes and the abstract mathematics en- countered in more advanced mathematics courses. The goal of this class 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 areaof mathemat- ics, 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. We will develop the theory of Linear Algebra together, and you will learn to write proofs. The lectures will mainly develop the theory of Linear Algebra, and the discussion sessions will focus on the computational aspects. The lectures and the discussion sections go hand in hand, and it is important that you attend both. The exercises for each Chapter are divided into more computation-oriented exercises and exercises that focus on proof-writing. There 1 2 CHAPTER 1. WHAT IS LINEAR ALGEBRA? are also some very short webwork homework sets to make sure you have some basic skills. You can already try the first one that introduces some logical concepts by clicking below: Background Webwork Problems 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 2x +x = 0 1 2 . x1 x2 = 1 ) − This system has a unique solution for x ,x R, namely x = 1 and x = 2. 1 2 ∈ 1 3 2 −3 This 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 − 2 1 x = 1+ = . 1 −3 3 (cid:18) (cid:19) 1.2. WHAT IS LINEAR ALGEBRA? 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 Example 1.2.2. Take the following system of two linear equations in the two unknowns x 1 and x : 2 x +x = 1 1 2 . 2x1 +2x2 = 1 ) Here, wecaneliminatevariablesbyadding 2timesthefirstequationtothesecondequation, − whichresultsin0 = 1. Thisisobviouslyacontradiction, andhencethissystemofequations − has no solution. Example 1.2.3. Letustakethefollowingsystem ofonelinearequationinthetwo unknowns 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 4 CHAPTER 1. WHAT IS LINEAR ALGEBRA? 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 this course progresses, you will see that there is a lot of subtlety in fully understanding the solutions for such equations. 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, then please consult Appendix A.) 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