Advanced Linear Algebra by Nicholas Loehr

Pages 619
Views 502
Size 4.9 MiB
Downloads 64
Advanced Linear Algebra by Nicholas Loehr

Contents

Preface xvii
I Background on Algebraic Structures 1
1 Overview of Algebraic Systems 3
1.1 Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Rings and Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Subsystems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 Product Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6 Quotient Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.7 Homomorphisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.8 Spanning, Linear Independence, Basis, and Dimension . . . . . . . . . . . . 13
1.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2 Permutations 23
2.1 Symmetric Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2 Representing Functions as Directed Graphs . . . . . . . . . . . . . . . . . . 24
2.3 Cycle Decompositions of Permutations . . . . . . . . . . . . . . . . . . . . 24
2.4 Composition of Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.5 Factorizations of Permutations . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.6 Inversions and Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.7 Signs of Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3 Polynomials 35
3.1 Intuitive Definition of Polynomials . . . . . . . . . . . . . . . . . . . . . . . 35
3.2 Algebraic Operations on Polynomials . . . . . . . . . . . . . . . . . . . . . 36
3.3 Formal Power Series and Polynomials . . . . . . . . . . . . . . . . . . . . . 37
3.4 Properties of Degree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.5 Evaluating Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.6 Polynomial Division with Remainder . . . . . . . . . . . . . . . . . . . . . 41
3.7 Divisibility and Associates . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.8 Greatest Common Divisors of Polynomials . . . . . . . . . . . . . . . . . . 44
3.9 GCDs of Lists of Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.10 Matrix Reduction Algorithm for GCDs . . . . . . . . . . . . . . . . . . . . 46
3.11 Roots of Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.12 Irreducible Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.13 Factorization of Polynomials into Irreducibles . . . . . . . . . . . . . . . . . 51
3.14 Prime Factorizations and Divisibility . . . . . . . . . . . . . . . . . . . . . 52
3.15 Irreducible Polynomials in Q[x] . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.16 Irreducibility in Q[x] via Reduction Mod p . . . . . . . . . . . . . . . . . . 54
3.17 Eisenstein’s Irreducibility Criterion for Q[x] . . . . . . . . . . . . . . . . . . 54
3.18 Kronecker’s Algorithm for Factoring in Q[x] . . . . . . . . . . . . . . . . . 55
3.19 Algebraic Elements and Minimal Polynomials . . . . . . . . . . . . . . . . 56
3.20 Multivariable Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.21 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.22 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
II Matrices 71
4 Basic Matrix Operations 73
4.1 Formal Definition of Matrices and Vectors . . . . . . . . . . . . . . . . . . 73
4.2 Vector Spaces of Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.3 Matrix Operations via Entries . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.4 Properties of Matrix Multiplication . . . . . . . . . . . . . . . . . . . . . . 77
4.5 Generalized Associativity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.6 Invertible Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.7 Matrix Operations via Columns . . . . . . . . . . . . . . . . . . . . . . . . 81
4.8 Matrix Operations via Rows . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.9 Elementary Operations and Elementary Matrices . . . . . . . . . . . . . . 84
4.10 Elementary Matrices and Gaussian Elimination . . . . . . . . . . . . . . . 86
4.11 Elementary Matrices and Invertibility . . . . . . . . . . . . . . . . . . . . . 87
4.12 Row Rank and Column Rank . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.13 Conditions for Invertibility of a Matrix . . . . . . . . . . . . . . . . . . . . 89
4.14 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.15 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5 Determinants via Calculations 101
5.1 Matrices with Entries in a Ring . . . . . . . . . . . . . . . . . . . . . . . . 101
5.2 Explicit Definition of the Determinant . . . . . . . . . . . . . . . . . . . . . 102
5.3 Diagonal and Triangular Matrices . . . . . . . . . . . . . . . . . . . . . . . 103
5.4 Changing Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.5 Transposes and Determinants . . . . . . . . . . . . . . . . . . . . . . . . . 104
5.6 Multilinearity and the Alternating Property . . . . . . . . . . . . . . . . . 106
5.7 Elementary Row Operations and Determinants . . . . . . . . . . . . . . . . 107
5.8 Determinant Properties Involving Columns . . . . . . . . . . . . . . . . . . 109
5.9 Product Formula via Elementary Matrices . . . . . . . . . . . . . . . . . . 109
5.10 Laplace Expansions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
5.11 Classical Adjoints and Inverses . . . . . . . . . . . . . . . . . . . . . . . . . 113
5.12 Cramer’s Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
5.13 Product Formula for Determinants . . . . . . . . . . . . . . . . . . . . . . . 115
5.14 Cauchy–Binet Formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
5.15 Cayley–Hamilton Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
5.16 Permanents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
5.17 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
5.18 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
6 Concrete vs. Abstract Linear Algebra 131
6.1 Concrete Column Vectors vs. Abstract Vectors . . . . . . . . . . . . . . . . 131
6.2 Examples of Computing Coordinates . . . . . . . . . . . . . . . . . . . . . 133
6.3 Concrete vs. Abstract Vector Space Operations . . . . . . . . . . . . . . . . 135
6.4 Matrices vs. Linear Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
6.5 Examples of Matrices Associated with Linear Maps . . . . . . . . . . . . . 138
6.6 Vector Operations on Matrices and Linear Maps . . . . . . . . . . . . . . . 140
6.7 Matrix Transpose vs. Dual Maps . . . . . . . . . . . . . . . . . . . . . . . . 141
6.8 Matrix/Vector Multiplication vs. Evaluation of Maps . . . . . . . . . . . . 142
6.9 Matrix Multiplication vs. Composition of Linear Maps . . . . . . . . . . . 142
6.10 Transition Matrices and Changing Coordinates . . . . . . . . . . . . . . . . 143
6.11 Changing Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
6.12 Algebras of Matrices and Linear Operators . . . . . . . . . . . . . . . . . . 145
6.13 Similarity of Matrices and Linear Maps . . . . . . . . . . . . . . . . . . . . 147
6.14 Diagonalizability and Triangulability . . . . . . . . . . . . . . . . . . . . . 147
6.15 Block-Triangular Matrices and Invariant Subspaces . . . . . . . . . . . . . 149
6.16 Block-Diagonal Matrices and Reducing Subspaces . . . . . . . . . . . . . . 150
6.17 Idempotent Matrices and Projections . . . . . . . . . . . . . . . . . . . . . 151
6.18 Bilinear Maps and Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
6.19 Congruence of Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
6.20 Real Inner Product Spaces and Orthogonal Matrices . . . . . . . . . . . . . 154
6.21 Complex Inner Product Spaces and Unitary Matrices . . . . . . . . . . . . 155
6.22 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
6.23 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
III Matrices with Special Structure 167
7 Hermitian, Positive Definite, Unitary, and Normal Matrices 169
7.1 Conjugate-Transpose of a Matrix . . . . . . . . . . . . . . . . . . . . . . . . 169
7.2 Hermitian Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
7.3 Hermitian Decomposition of a Matrix . . . . . . . . . . . . . . . . . . . . . 172
7.4 Positive Definite Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
7.5 Unitary Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
7.6 Unitary Similarity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
7.7 Unitary Triangularization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
7.8 Simultaneous Triangularization . . . . . . . . . . . . . . . . . . . . . . . . . 178
7.9 Normal Matrices and Unitary Diagonalization . . . . . . . . . . . . . . . . 180
7.10 Polynomials and Commuting Matrices . . . . . . . . . . . . . . . . . . . . . 181
7.11 Simultaneous Unitary Diagonalization . . . . . . . . . . . . . . . . . . . . . 182
7.12 Polar Decomposition: Invertible Case . . . . . . . . . . . . . . . . . . . . . 183
7.13 Polar Decomposition: General Case . . . . . . . . . . . . . . . . . . . . . . 184
7.14 Interlacing Eigenvalues for Hermitian Matrices . . . . . . . . . . . . . . . . 185
7.15 Determinant Criterion for Positive Definite Matrices . . . . . . . . . . . . . 187
7.16 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
7.17 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
8 Jordan Canonical Forms 195
8.1 Examples of Nilpotent Maps . . . . . . . . . . . . . . . . . . . . . . . . . . 196
8.2 Partition Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
8.3 Partition Diagrams and Nilpotent Maps . . . . . . . . . . . . . . . . . . . . 198
8.4 Computing Images via Partition Diagrams . . . . . . . . . . . . . . . . . . 199
8.5 Computing Null Spaces via Partition Diagrams . . . . . . . . . . . . . . . . 200
8.6 Classification of Nilpotent Maps (Stage 1) . . . . . . . . . . . . . . . . . . 201
8.7 Classification of Nilpotent Maps (Stage 2) . . . . . . . . . . . . . . . . . . 202
8.8 Classification of Nilpotent Maps (Stage 3) . . . . . . . . . . . . . . . . . . 203
8.9 Fitting’s Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
8.10 Existence of Jordan Canonical Forms . . . . . . . . . . . . . . . . . . . . . 205
8.11 Uniqueness of Jordan Canonical Forms . . . . . . . . . . . . . . . . . . . . 206
8.12 Computing Jordan Canonical Forms . . . . . . . . . . . . . . . . . . . . . . 207
8.13 Application to Differential Equations . . . . . . . . . . . . . . . . . . . . . 209
8.14 Minimal Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
8.15 Jordan–Chevalley Decomposition of a Linear Operator . . . . . . . . . . . 211
8.16 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
8.17 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
9 Matrix Factorizations 219
9.1 Approximation by Orthonormal Vectors . . . . . . . . . . . . . . . . . . . . 220
9.2 Gram–Schmidt Orthonormalization . . . . . . . . . . . . . . . . . . . . . . 221
9.3 Gram–Schmidt QR Factorization . . . . . . . . . . . . . . . . . . . . . . . . 222
9.4 Householder Reflections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
9.5 Householder QR Factorization . . . . . . . . . . . . . . . . . . . . . . . . . 226
9.6 LU Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
9.7 Example of the LU Factorization . . . . . . . . . . . . . . . . . . . . . . . . 229
9.8 LU Factorizations and Gaussian Elimination . . . . . . . . . . . . . . . . . 230
9.9 Permuted LU Factorizations . . . . . . . . . . . . . . . . . . . . . . . . . . 232
9.10 Cholesky Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
9.11 Least Squares Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . 235
9.12 Singular Value Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . 236
9.13 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
9.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
10 Iterative Algorithms in Numerical Linear Algebra 245
10.1 Richardson’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
10.2 Jacobi’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
10.3 Gauss–Seidel Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
10.4 Vector Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
10.5 Metric Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
10.6 Convergence of Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
10.7 Comparable Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
10.8 Matrix Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
10.9 Formulas for Matrix Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
10.10 Matrix Inversion via Geometric Series . . . . . . . . . . . . . . . . . . . . 255
10.11 Affine Iteration and Richardson’s Algorithm . . . . . . . . . . . . . . . . . 256
10.12 Splitting Matrices and Jacobi’s Algorithm . . . . . . . . . . . . . . . . . . 257
10.13 Induced Matrix Norms and the Spectral Radius . . . . . . . . . . . . . . . 257
10.14 Analysis of the Gauss–Seidel Algorithm . . . . . . . . . . . . . . . . . . . 259
10.15 Power Method for Finding Eigenvalues . . . . . . . . . . . . . . . . . . . . 259
10.16 Shifted and Inverse Power Method . . . . . . . . . . . . . . . . . . . . . . 261
10.17 Deflation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
10.18 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
10.19 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264
IV The Interplay of Geometry and Linear Algebra 271
11 Affine Geometry and Convexity 273
11.1 Linear Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
11.2 Examples of Linear Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . 274
11.3 Characterizations of Linear Subspaces . . . . . . . . . . . . . . . . . . . . . 275
11.4 Affine Combinations and Affine Sets . . . . . . . . . . . . . . . . . . . . . . 276
11.5 Affine Sets and Linear Subspaces . . . . . . . . . . . . . . . . . . . . . . . . 277
11.6 Affine Span of a Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
11.7 Affine Independence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
11.8 Affine Bases and Barycentric Coordinates . . . . . . . . . . . . . . . . . . . 280
11.9 Characterizations of Affine Sets . . . . . . . . . . . . . . . . . . . . . . . . 281
11.10 Affine Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282
11.11 Convex Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
11.12 Convex Hulls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
11.13 Carath´eodory’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
11.14 Hyperplanes and Half-Spaces in Rn . . . . . . . . . . . . . . . . . . . . . . 286
11.15 Closed Convex Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
11.16 Cones and Convex Cones . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
11.17 Intersection Lemma for V-Cones . . . . . . . . . . . . . . . . . . . . . . . 290
11.18 All H-Cones Are V-Cones . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
11.19 Projection Lemma for H-Cones . . . . . . . . . . . . . . . . . . . . . . . . 292
11.20 All V-Cones Are H-Cones . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
11.21 Finite Intersections of Closed Half-Spaces . . . . . . . . . . . . . . . . . . 294
11.22 Convex Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
11.23 Derivative Tests for Convex Functions . . . . . . . . . . . . . . . . . . . . 297
11.24 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
11.25 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
12 Ruler and Compass Constructions 309
12.1 Geometric Constructibility . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
12.2 Arithmetic Constructibility . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
12.3 Preliminaries on Field Extensions . . . . . . . . . . . . . . . . . . . . . . . 312
12.4 Field-Theoretic Constructibility . . . . . . . . . . . . . . . . . . . . . . . . 314
12.5 Proof that GC ⊆ AC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
12.6 Proof that AC ⊆ GC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
12.7 Algebraic Elements and Minimal Polynomials . . . . . . . . . . . . . . . . 320
12.8 Proof that AC = SQC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322
12.9 Impossibility of Geometric Construction Problems . . . . . . . . . . . . . . 323
12.10 Constructibility of the 17-Gon . . . . . . . . . . . . . . . . . . . . . . . . . 324
12.11 Overview of Solvability by Radicals . . . . . . . . . . . . . . . . . . . . . . 326
12.12 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
12.13 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328
13 Dual Spaces and Bilinear Forms 335
13.1 Vector Spaces of Linear Maps . . . . . . . . . . . . . . . . . . . . . . . . . 335
13.2 Dual Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336
13.3 Zero Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
13.4 Annihilators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338
13.5 Double Dual V ∗∗ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
13.6 Correspondence between Subspaces of V and V ∗ . . . . . . . . . . . . . . . 341
13.7 Dual Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342
13.8 Nondegenerate Bilinear Forms . . . . . . . . . . . . . . . . . . . . . . . . . 344
13.9 Real Inner Product Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . 345
13.10 Complex Inner Product Spaces . . . . . . . . . . . . . . . . . . . . . . . . 346
13.11 Comments on Infinite-Dimensional Spaces . . . . . . . . . . . . . . . . . . 348
13.12 Affine Algebraic Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . 349
13.13 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
13.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352
14 Metric Spaces and Hilbert Spaces 359
14.1 Metric Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360
14.2 Convergent Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361
14.3 Closed Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362
14.4 Open Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363
14.5 Continuous Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364
14.6 Compact Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365
14.7 Completeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366
14.8 Definition of a Hilbert Space . . . . . . . . . . . . . . . . . . . . . . . . . . 368
14.9 Examples of Hilbert Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . 369
14.10 Proof of the Hilbert Space Axioms for ℓ2(X) . . . . . . . . . . . . . . . . . 371
14.11 Basic Properties of Hilbert Spaces . . . . . . . . . . . . . . . . . . . . . . . 373
14.12 Closed Convex Sets in Hilbert Spaces . . . . . . . . . . . . . . . . . . . . . 374
14.13 Orthogonal Complements . . . . . . . . . . . . . . . . . . . . . . . . . . . 375
14.14 Orthonormal Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377
14.15 Maximal Orthonormal Sets . . . . . . . . . . . . . . . . . . . . . . . . . . 378
14.16 Isomorphism of H and ℓ2(X) . . . . . . . . . . . . . . . . . . . . . . . . . 379
14.17 Continuous Linear Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
14.18 Dual Space of a Hilbert Space . . . . . . . . . . . . . . . . . . . . . . . . . 382
14.19 Adjoints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
14.20 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384
14.21 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387
V Modules, Independence, and Classification Theorems 395
15 Finitely Generated Commutative Groups 397
15.1 Commutative Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397
15.2 Generating Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399
15.3 Z-Independence and Z-Bases . . . . . . . . . . . . . . . . . . . . . . . . . . 400
15.4 Elementary Operations on Z-Bases . . . . . . . . . . . . . . . . . . . . . . 401
15.5 Coordinates and Z-Linear Maps . . . . . . . . . . . . . . . . . . . . . . . . 402
15.6 UMP for Free Commutative Groups . . . . . . . . . . . . . . . . . . . . . . 403
15.7 Quotient Groups of Free Commutative Groups . . . . . . . . . . . . . . . . 404
15.8 Subgroups of Free Commutative Groups . . . . . . . . . . . . . . . . . . . 405
15.9 Z-Linear Maps and Integer Matrices . . . . . . . . . . . . . . . . . . . . . . 406
15.10 Elementary Operations and Change of Basis . . . . . . . . . . . . . . . . . 408
15.11 Reduction Theorem for Integer Matrices . . . . . . . . . . . . . . . . . . . 411
15.12 Structure of Z-Linear Maps between Free Groups . . . . . . . . . . . . . . 413
15.13 Structure of Finitely Generated Commutative Groups . . . . . . . . . . . 414
15.14 Example of the Reduction Algorithm . . . . . . . . . . . . . . . . . . . . . 415
15.15 Some Special Subgroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417
15.16 Uniqueness Proof: Free Case . . . . . . . . . . . . . . . . . . . . . . . . . . 418
15.17 Uniqueness Proof: Prime Power Case . . . . . . . . . . . . . . . . . . . . . 419
15.18 Uniqueness of Elementary Divisors . . . . . . . . . . . . . . . . . . . . . . 422
15.19 Uniqueness of Invariant Factors . . . . . . . . . . . . . . . . . . . . . . . . 423
15.20 Uniqueness Proof: General Case . . . . . . . . . . . . . . . . . . . . . . . . 424
15.21 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424
15.22 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426
16 Axiomatic Approach to Independence, Bases, and Dimension 437
16.1 Axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437
16.2 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438
16.3 Initial Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438
16.4 Consequences of the Exchange Axiom . . . . . . . . . . . . . . . . . . . . . 439
16.5 Main Theorems: Finite-Dimensional Case . . . . . . . . . . . . . . . . . . . 440
16.6 Zorn’s Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442
16.7 Main Theorems: General Case . . . . . . . . . . . . . . . . . . . . . . . . . 443
16.8 Bases of Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446
16.9 Linear Independence and Linear Bases . . . . . . . . . . . . . . . . . . . . 446
16.10 Field Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 448
16.11 Algebraic Independence and Transcendence Bases . . . . . . . . . . . . . . 449
16.12 Independence in Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452
16.13 Hereditary Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453
16.14 Matroids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454
16.15 Equivalence of Matroid Axioms . . . . . . . . . . . . . . . . . . . . . . . . 455
16.16 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456
16.17 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457
17 Elements of Module Theory 463
17.1 Module Axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463
17.2 Examples of Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465
17.3 Submodules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466
17.4 Submodule Generated by a Subset . . . . . . . . . . . . . . . . . . . . . . . 467
17.5 Direct Products, Direct Sums, and Hom Modules . . . . . . . . . . . . . . 468
17.6 Quotient Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470
17.7 Changing the Ring of Scalars . . . . . . . . . . . . . . . . . . . . . . . . . . 472
17.8 Fundamental Homomorphism Theorem for Modules . . . . . . . . . . . . . 472
17.9 More Module Homomorphism Theorems . . . . . . . . . . . . . . . . . . . 474
17.10 Chains of Submodules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476
17.11 Modules of Finite Length . . . . . . . . . . . . . . . . . . . . . . . . . . . 478
17.12 Free Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479
17.13 Size of a Basis of a Free Module . . . . . . . . . . . . . . . . . . . . . . . . 481
17.14 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483
17.15 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486
18 Principal Ideal Domains, Modules over PIDs, and Canonical Forms 493
18.1 Principal Ideal Domains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494
18.2 Divisibility in Commutative Rings . . . . . . . . . . . . . . . . . . . . . . . 494
18.3 Divisibility and Ideals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495
18.4 Prime and Irreducible Elements . . . . . . . . . . . . . . . . . . . . . . . . 496
18.5 Irreducible Factorizations in PIDs . . . . . . . . . . . . . . . . . . . . . . . 497
18.6 Free Modules over a PID . . . . . . . . . . . . . . . . . . . . . . . . . . . . 498
18.7 Operations on Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 499
18.8 Matrices of Linear Maps between Free Modules . . . . . . . . . . . . . . . 500
18.9 Reduction Theorem for Matrices over a PID . . . . . . . . . . . . . . . . . 502
18.10 Structure Theorems for Linear Maps and Modules . . . . . . . . . . . . . 504
18.11 Minors and Matrix Invariants . . . . . . . . . . . . . . . . . . . . . . . . . 505
18.12 Uniqueness of Smith Normal Form . . . . . . . . . . . . . . . . . . . . . . 506
18.13 Torsion Submodules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507
18.14 Uniqueness of Invariant Factors . . . . . . . . . . . . . . . . . . . . . . . . 508
18.15 Uniqueness of Elementary Divisors . . . . . . . . . . . . . . . . . . . . . . 509
18.16 F[x]-Module Defined by a Linear Operator . . . . . . . . . . . . . . . . . . 510
18.17 Rational Canonical Form of a Linear Map . . . . . . . . . . . . . . . . . . 512
18.18 Jordan Canonical Form of a Linear Map . . . . . . . . . . . . . . . . . . . 513
18.19 Canonical Forms of Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . 514
18.20 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 516
18.21 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 518
VI Universal Mapping Properties and Multilinear Algebra 525
19 Introduction to Universal Mapping Properties 527
19.1 Bases of Free R-Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . 529
19.2 Homomorphisms out of Quotient Modules . . . . . . . . . . . . . . . . . . 529
19.3 Direct Product of Two Modules . . . . . . . . . . . . . . . . . . . . . . . . 531
19.4 Direct Sum of Two Modules . . . . . . . . . . . . . . . . . . . . . . . . . . 532
19.5 Direct Products of Arbitrary Families of R-Modules . . . . . . . . . . . . . 533
19.6 Direct Sums of Arbitrary Families of R-Modules . . . . . . . . . . . . . . . 534
19.7 Solving Universal Mapping Problems . . . . . . . . . . . . . . . . . . . . . 537
19.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539
19.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 541
20 Universal Mapping Problems in Multilinear Algebra 547
20.1 Multilinear Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 547
20.2 Alternating Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 548
20.3 Symmetric Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 549
20.4 Tensor Product of Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . 550
20.5 Exterior Powers of a Module . . . . . . . . . . . . . . . . . . . . . . . . . . 553
20.6 Symmetric Powers of a Module . . . . . . . . . . . . . . . . . . . . . . . . . 555
20.7 Myths about Tensor Products . . . . . . . . . . . . . . . . . . . . . . . . . 557
20.8 Tensor Product Isomorphisms . . . . . . . . . . . . . . . . . . . . . . . . . 558
20.9 Associativity of Tensor Products . . . . . . . . . . . . . . . . . . . . . . . . 560
20.10 Tensor Product of Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . 561
20.11 Bases and Multilinear Maps . . . . . . . . . . . . . . . . . . . . . . . . . . 562
20.12 Bases for Tensor Products of Free R-Modules . . . . . . . . . . . . . . . . 564
20.13 Bases and Alternating Maps . . . . . . . . . . . . . . . . . . . . . . . . . . 565
20.14 Bases for Exterior Powers of Free Modules . . . . . . . . . . . . . . . . . . 566
20.15 Bases for Symmetric Powers of Free Modules . . . . . . . . . . . . . . . . 567
20.16 Tensor Product of Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . 568
20.17 Determinants and Exterior Powers . . . . . . . . . . . . . . . . . . . . . . 569
20.18 From Modules to Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . 571
20.19 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573
20.20 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 577
Appendix: Basic Definitions 583
Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583
Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583
Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584
Partially Ordered Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 585
Further Reading 587
Bibliography 591
Index 595