Algebra, Topology, Di(cid:11)erential Calculus, and Optimization Theory For Computer Science and Engineering Jean Gallier and Jocelyn Quaintance Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104, USA e-mail: [email protected] c Jean Gallier (cid:13) July 28, 2019 2 Contents Contents 3 1 Introduction 17 2 Groups, Rings, and Fields 19 2.1 Groups, Subgroups, Cosets . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.2 Cyclic Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.3 Rings and Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 I Linear Algebra 43 3 Vector Spaces, Bases, Linear Maps 45 3.1 Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 P 3.2 Indexed Families; the Sum Notation a . . . . . . . . . . . . . . . . . . 47 i I i 3.3 Linear Independence, Subspaces . . . .2 . . . . . . . . . . . . . . . . . . . . 52 3.4 Bases of a Vector Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.5 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.6 Linear Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 3.7 Quotient Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 3.8 Linear Forms and the Dual Space . . . . . . . . . . . . . . . . . . . . . . . . 78 3.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 4 Matrices and Linear Maps 83 4.1 Representation of Linear Maps by Matrices . . . . . . . . . . . . . . . . . . 83 4.2 Change of Basis Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 4.3 Haar Basis Vectors and a Glimpse at Wavelets . . . . . . . . . . . . . . . . 96 4.4 The E(cid:11)ect of a Change of Bases on Matrices . . . . . . . . . . . . . . . . . 113 4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 5 Direct Sums 119 5.1 Sums, Direct Sums, Direct Products . . . . . . . . . . . . . . . . . . . . . . 119 5.2 The Rank-Nullity Theorem; Grassmann’s Relation . . . . . . . . . . . . . . 128 5.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 3 4 CONTENTS 6 Determinants 135 6.1 Permutations, Signature of a Permutation . . . . . . . . . . . . . . . . . . . 135 6.2 Alternating Multilinear Maps . . . . . . . . . . . . . . . . . . . . . . . . . . 139 6.3 De(cid:12)nition of a Determinant . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 6.4 Inverse Matrices and Determinants . . . . . . . . . . . . . . . . . . . . . . . 149 6.5 Systems of Linear Equations and Determinants . . . . . . . . . . . . . . . . 152 6.6 Determinant of a Linear Map . . . . . . . . . . . . . . . . . . . . . . . . . . 153 6.7 The Cayley{Hamilton Theorem . . . . . . . . . . . . . . . . . . . . . . . . . 154 6.8 Permanents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 6.9 Further Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 7 Gaussian Elimination, LU, Cholesky, Echelon Form 163 7.1 Motivating Example: Curve Interpolation . . . . . . . . . . . . . . . . . . . 163 7.2 Gaussian Elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 7.3 Elementary Matrices and Row Operations . . . . . . . . . . . . . . . . . . . 172 7.4 LU-Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 7.5 PA = LU Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 ~ 7.6 Proof of Theorem 7.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 7.7 Dealing with Roundo(cid:11) Errors; Pivoting Strategies . . . . . . . . . . . . . . . 195 7.8 Gaussian Elimination of Tridiagonal Matrices . . . . . . . . . . . . . . . . . 196 7.9 SPD Matrices and the Cholesky Decomposition . . . . . . . . . . . . . . . . 198 7.10 Reduced Row Echelon Form . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 7.11 RREF, Free Variables, Homogeneous Systems . . . . . . . . . . . . . . . . . 213 7.12 Uniqueness of RREF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216 7.13 Solving Linear Systems Using RREF . . . . . . . . . . . . . . . . . . . . . . 218 7.14 Elementary Matrices and Columns Operations . . . . . . . . . . . . . . . . 225 ~ 7.15 Transvections and Dilatations . . . . . . . . . . . . . . . . . . . . . . . . 226 7.16 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 7.17 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 8 Vector Norms and Matrix Norms 245 8.1 Normed Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245 8.2 Matrix Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256 8.3 Subordinate Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261 8.4 Inequalities Involving Subordinate Norms . . . . . . . . . . . . . . . . . . . 268 8.5 Condition Numbers of Matrices . . . . . . . . . . . . . . . . . . . . . . . . . 270 8.6 An Application of Norms: Inconsistent Linear Systems . . . . . . . . . . . . 279 8.7 Limits of Sequences and Series . . . . . . . . . . . . . . . . . . . . . . . . . 280 8.8 The Matrix Exponential . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283 8.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286 8.10 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288 9 Iterative Methods for Solving Linear Systems 295 CONTENTS 5 9.1 Convergence of Sequences of Vectors and Matrices . . . . . . . . . . . . . . 295 9.2 Convergence of Iterative Methods . . . . . . . . . . . . . . . . . . . . . . . . 298 9.3 Methods of Jacobi, Gauss{Seidel, and Relaxation . . . . . . . . . . . . . . . 300 9.4 Convergence of the Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 308 9.5 Convergence Methods for Tridiagonal Matrices . . . . . . . . . . . . . . . . 311 9.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315 9.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316 10 The Dual Space, Duality 319 10.1 The Dual Space E and Linear Forms . . . . . . . . . . . . . . . . . . . . . 319 (cid:3) 10.2 Pairing and Duality Between E and E . . . . . . . . . . . . . . . . . . . . 324 (cid:3) 10.3 The Duality Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329 10.4 Hyperplanes and Linear Forms . . . . . . . . . . . . . . . . . . . . . . . . . 335 10.5 Transpose of a Linear Map and of a Matrix . . . . . . . . . . . . . . . . . . 337 10.6 The Four Fundamental Subspaces . . . . . . . . . . . . . . . . . . . . . . . 345 10.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348 11 Euclidean Spaces 351 11.1 Inner Products, Euclidean Spaces . . . . . . . . . . . . . . . . . . . . . . . . 351 11.2 Orthogonality and Duality in Euclidean Spaces . . . . . . . . . . . . . . . . 360 11.3 Adjoint of a Linear Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367 11.4 Existence and Construction of Orthonormal Bases . . . . . . . . . . . . . . 370 11.5 Linear Isometries (Orthogonal Transformations) . . . . . . . . . . . . . . . . 377 11.6 The Orthogonal Group, Orthogonal Matrices . . . . . . . . . . . . . . . . . 380 11.7 The Rodrigues Formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382 11.8 QR-Decomposition for Invertible Matrices . . . . . . . . . . . . . . . . . . . 385 11.9 Some Applications of Euclidean Geometry . . . . . . . . . . . . . . . . . . . 390 11.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391 11.11 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393 12 QR-Decomposition for Arbitrary Matrices 405 12.1 Orthogonal Re(cid:13)ections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405 12.2 QR-Decomposition Using Householder Matrices . . . . . . . . . . . . . . . . 410 12.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420 12.4 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420 13 Hermitian Spaces 427 13.1 Hermitian Spaces, Pre-Hilbert Spaces . . . . . . . . . . . . . . . . . . . . . 427 13.2 Orthogonality, Duality, Adjoint of a Linear Map . . . . . . . . . . . . . . . 436 13.3 Linear Isometries (Also Called Unitary Transformations) . . . . . . . . . . . 441 13.4 The Unitary Group, Unitary Matrices . . . . . . . . . . . . . . . . . . . . . 443 13.5 Hermitian Re(cid:13)ections and QR-Decomposition . . . . . . . . . . . . . . . . . 446 13.6 Orthogonal Projections and Involutions . . . . . . . . . . . . . . . . . . . . 451 6 CONTENTS 13.7 Dual Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454 13.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461 13.9 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462 14 Eigenvectors and Eigenvalues 467 14.1 Eigenvectors and Eigenvalues of a Linear Map . . . . . . . . . . . . . . . . . 467 14.2 Reduction to Upper Triangular Form . . . . . . . . . . . . . . . . . . . . . . 475 14.3 Location of Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479 14.4 Conditioning of Eigenvalue Problems . . . . . . . . . . . . . . . . . . . . . . 482 14.5 Eigenvalues of the Matrix Exponential . . . . . . . . . . . . . . . . . . . . . 485 14.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487 14.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488 15 Unit Quaternions and Rotations in SO(3) 499 H 15.1 The group SU(2) and the Skew Field of Quaternions . . . . . . . . . . . 499 15.2 Representation of Rotation in SO(3) By Quaternions in SU(2) . . . . . . . 501 15.3 Matrix Representation of the Rotation r . . . . . . . . . . . . . . . . . . . 506 q 15.4 An Algorithm to Find a Quaternion Representing a Rotation . . . . . . . . 508 15.5 The Exponential Map exp: su(2) SU(2) . . . . . . . . . . . . . . . . . . 511 ! ~ 15.6 Quaternion Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . 513 15.7 Nonexistence of a \Nice" Section from SO(3) to SU(2) . . . . . . . . . . . . 515 15.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517 15.9 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 518 16 Spectral Theorems 521 16.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 521 16.2 Normal Linear Maps: Eigenvalues and Eigenvectors . . . . . . . . . . . . . . 521 16.3 Spectral Theorem for Normal Linear Maps . . . . . . . . . . . . . . . . . . . 527 16.4 Self-Adjoint and Other Special Linear Maps . . . . . . . . . . . . . . . . . . 532 16.5 Normal and Other Special Matrices . . . . . . . . . . . . . . . . . . . . . . . 538 16.6 Rayleigh{Ritz Theorems and Eigenvalue Interlacing . . . . . . . . . . . . . 541 16.7 The Courant{Fischer Theorem; Perturbation Results . . . . . . . . . . . . . 546 16.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 549 16.9 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 550 17 Introduction to The Finite Elements Method 557 17.1 A One-Dimensional Problem: Bending of a Beam . . . . . . . . . . . . . . . 557 17.2 A Two-Dimensional Problem: An Elastic Membrane . . . . . . . . . . . . . 568 17.3 Time-Dependent Boundary Problems . . . . . . . . . . . . . . . . . . . . . . 571 18 Graphs and Graph Laplacians; Basic Facts 579 18.1 Directed Graphs, Undirected Graphs, Weighted Graphs . . . . . . . . . . . 582 18.2 Laplacian Matrices of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 589 CONTENTS 7 18.3 Normalized Laplacian Matrices of Graphs . . . . . . . . . . . . . . . . . . . 593 18.4 Graph Clustering Using Normalized Cuts . . . . . . . . . . . . . . . . . . . 597 18.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 599 18.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 600 19 Spectral Graph Drawing 603 19.1 Graph Drawing and Energy Minimization . . . . . . . . . . . . . . . . . . . 603 19.2 Examples of Graph Drawings . . . . . . . . . . . . . . . . . . . . . . . . . . 606 19.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 610 20 Singular Value Decomposition and Polar Form 613 20.1 Properties of f f . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 613 (cid:3) (cid:14) 20.2 Singular Value Decomposition for Square Matrices . . . . . . . . . . . . . . 617 20.3 Polar Form for Square Matrices . . . . . . . . . . . . . . . . . . . . . . . . . 620 20.4 Singular Value Decomposition for Rectangular Matrices . . . . . . . . . . . 623 20.5 Ky Fan Norms and Schatten Norms . . . . . . . . . . . . . . . . . . . . . . 626 20.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 627 20.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 627 21 Applications of SVD and Pseudo-Inverses 631 21.1 Least Squares Problems and the Pseudo-Inverse . . . . . . . . . . . . . . . . 631 21.2 Properties of the Pseudo-Inverse . . . . . . . . . . . . . . . . . . . . . . . . 638 21.3 Data Compression and SVD . . . . . . . . . . . . . . . . . . . . . . . . . . . 643 21.4 Principal Components Analysis (PCA) . . . . . . . . . . . . . . . . . . . . . 645 21.5 Best A(cid:14)ne Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . 656 21.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 659 21.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 660 22 Computing Eigenvalues and Eigenvectors 663 22.1 The Basic QR Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 665 22.2 Hessenberg Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 671 22.3 Making the QR Method More E(cid:14)cient Using Shifts . . . . . . . . . . . . . 677 22.4 Krylov Subspaces; Arnoldi Iteration . . . . . . . . . . . . . . . . . . . . . . 682 22.5 GMRES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 686 22.6 The Hermitian Case; Lanczos Iteration . . . . . . . . . . . . . . . . . . . . . 687 22.7 Power Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 688 22.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 690 22.9 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 691 II A(cid:14)ne and Projective Geometry 693 23 Basics of A(cid:14)ne Geometry 695 8 CONTENTS 23.1 A(cid:14)ne Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 695 23.2 Examples of A(cid:14)ne Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . 704 23.3 Chasles’s Identity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 705 23.4 A(cid:14)ne Combinations, Barycenters . . . . . . . . . . . . . . . . . . . . . . . . 706 23.5 A(cid:14)ne Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 711 23.6 A(cid:14)ne Independence and A(cid:14)ne Frames . . . . . . . . . . . . . . . . . . . . . 717 23.7 A(cid:14)ne Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 723 23.8 A(cid:14)ne Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 730 23.9 A(cid:14)ne Geometry: A Glimpse . . . . . . . . . . . . . . . . . . . . . . . . . . 732 23.10 A(cid:14)ne Hyperplanes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 736 23.11 Intersection of A(cid:14)ne Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . 738 24 Embedding an A(cid:14)ne Space in a Vector Space 741 24.1 The \Hat Construction," or Homogenizing . . . . . . . . . . . . . . . . . . . 741 ^ 24.2 A(cid:14)ne Frames of E and Bases of E . . . . . . . . . . . . . . . . . . . . . . . 748 ^ 24.3 Another Construction of E . . . . . . . . . . . . . . . . . . . . . . . . . . . 751 24.4 Extending A(cid:14)ne Maps to Linear Maps . . . . . . . . . . . . . . . . . . . . . 754 25 Basics of Projective Geometry 759 25.1 Why Projective Spaces? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 759 25.2 Projective Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 764 25.3 Projective Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 769 25.4 Projective Frames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 772 25.5 Projective Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 786 25.6 Finding a Homography Between Two Projective Frames . . . . . . . . . . . 792 25.7 A(cid:14)ne Patches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 805 25.8 Projective Completion of an A(cid:14)ne Space . . . . . . . . . . . . . . . . . . . 808 25.9 Making Good Use of Hyperplanes at In(cid:12)nity . . . . . . . . . . . . . . . . . 813 25.10 The Cross-Ratio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 816 25.11 Fixed Points of Homographies and Homologies . . . . . . . . . . . . . . . . 820 25.12 Duality in Projective Geometry . . . . . . . . . . . . . . . . . . . . . . . . . 834 25.13 Cross-Ratios of Hyperplanes . . . . . . . . . . . . . . . . . . . . . . . . . . . 838 25.14 Complexi(cid:12)cation of a Real Projective Space . . . . . . . . . . . . . . . . . . 840 25.15 Similarity Structures on a Projective Space . . . . . . . . . . . . . . . . . . 842 25.16 Some Applications of Projective Geometry . . . . . . . . . . . . . . . . . . . 851 III The Geometry of Bilinear Forms 857 26 The Cartan{Dieudonn(cid:19)e Theorem 859 26.1 The Cartan{Dieudonn(cid:19)e Theorem for Linear Isometries . . . . . . . . . . . . 859 26.2 A(cid:14)ne Isometries (Rigid Motions) . . . . . . . . . . . . . . . . . . . . . . . . 871 26.3 Fixed Points of A(cid:14)ne Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . 873 CONTENTS 9 26.4 A(cid:14)ne Isometries and Fixed Points . . . . . . . . . . . . . . . . . . . . . . . 875 26.5 The Cartan{Dieudonn(cid:19)e Theorem for A(cid:14)ne Isometries . . . . . . . . . . . . 881 27 Isometries of Hermitian Spaces 885 27.1 The Cartan{Dieudonn(cid:19)e Theorem, Hermitian Case . . . . . . . . . . . . . . . 885 27.2 A(cid:14)ne Isometries (Rigid Motions) . . . . . . . . . . . . . . . . . . . . . . . . 894 28 The Geometry of Bilinear Forms; Witt’s Theorem 899 28.1 Bilinear Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 899 28.2 Sesquilinear Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 907 28.3 Orthogonality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 911 28.4 Adjoint of a Linear Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 916 28.5 Isometries Associated with Sesquilinear Forms . . . . . . . . . . . . . . . . . 918 28.6 Totally Isotropic Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . 922 28.7 Witt Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 928 28.8 Symplectic Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 936 28.9 Orthogonal Groups and the Cartan{Dieudonn(cid:19)e Theorem . . . . . . . . . . . 940 28.10 Witt’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 947 IV Algebra: PID’s, UFD’s, Noetherian Rings, Tensors, Modules over a PID, Normal Forms 953 29 Polynomials, Ideals and PID’s 955 29.1 Multisets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 955 29.2 Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 956 29.3 Euclidean Division of Polynomials . . . . . . . . . . . . . . . . . . . . . . . 962 29.4 Ideals, PID’s, and Greatest Common Divisors . . . . . . . . . . . . . . . . . 964 29.5 Factorization and Irreducible Factors in K[X] . . . . . . . . . . . . . . . . . 972 29.6 Roots of Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 976 29.7 Polynomial Interpolation (Lagrange, Newton, Hermite) . . . . . . . . . . . . 983 30 Annihilating Polynomials; Primary Decomposition 991 30.1 Annihilating Polynomials and the Minimal Polynomial . . . . . . . . . . . . 993 30.2 Minimal Polynomials of Diagonalizable Linear Maps . . . . . . . . . . . . . 995 30.3 Commuting Families of Linear Maps . . . . . . . . . . . . . . . . . . . . . . 998 30.4 The Primary Decomposition Theorem . . . . . . . . . . . . . . . . . . . . . 1001 30.5 Jordan Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1007 30.6 Nilpotent Linear Maps and Jordan Form . . . . . . . . . . . . . . . . . . . . 1010 30.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1016 30.8 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1017 31 UFD’s, Noetherian Rings, Hilbert’s Basis Theorem 1019 10 CONTENTS 31.1 Unique Factorization Domains (Factorial Rings) . . . . . . . . . . . . . . . . 1019 31.2 The Chinese Remainder Theorem . . . . . . . . . . . . . . . . . . . . . . . . 1033 31.3 Noetherian Rings and Hilbert’s Basis Theorem . . . . . . . . . . . . . . . . 1039 31.4 Futher Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1043 32 Tensor Algebras 1045 32.1 Linear Algebra Preliminaries: Dual Spaces and Pairings . . . . . . . . . . . 1047 32.2 Tensors Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1052 32.3 Bases of Tensor Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1064 32.4 Some Useful Isomorphisms for Tensor Products . . . . . . . . . . . . . . . . 1065 32.5 Duality for Tensor Products . . . . . . . . . . . . . . . . . . . . . . . . . . . 1069 32.6 Tensor Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1075 32.7 Symmetric Tensor Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1082 32.8 Bases of Symmetric Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . 1086 32.9 Some Useful Isomorphisms for Symmetric Powers . . . . . . . . . . . . . . . 1089 32.10 Duality for Symmetric Powers . . . . . . . . . . . . . . . . . . . . . . . . . . 1089 32.11 Symmetric Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1093 32.12 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1096 33 Exterior Tensor Powers and Exterior Algebras 1099 33.1 Exterior Tensor Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1099 33.2 Bases of Exterior Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1104 33.3 Some Useful Isomorphisms for Exterior Powers . . . . . . . . . . . . . . . . 1107 33.4 Duality for Exterior Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . 1107 33.5 Exterior Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1111 33.6 The Hodge -Operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1115 (cid:3) ~ 33.7 Left and Right Hooks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1119 ~ 33.8 Testing Decomposability . . . . . . . . . . . . . . . . . . . . . . . . . . . 1129 ~ 33.9 The Grassmann-Plu(cid:127)cker’s Equations and Grassmannians . . . . . . . . . 1132 33.10 Vector-Valued Alternating Forms . . . . . . . . . . . . . . . . . . . . . . . . 1135 33.11 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1139 34 Introduction to Modules; Modules over a PID 1141 34.1 Modules over a Commutative Ring . . . . . . . . . . . . . . . . . . . . . . . 1141 34.2 Finite Presentations of Modules . . . . . . . . . . . . . . . . . . . . . . . . . 1150 34.3 Tensor Products of Modules over a Commutative Ring . . . . . . . . . . . . 1156 34.4 Torsion Modules over a PID; Primary Decomposition . . . . . . . . . . . . . 1159 34.5 Finitely Generated Modules over a PID . . . . . . . . . . . . . . . . . . . . 1165 34.6 Extension of the Ring of Scalars . . . . . . . . . . . . . . . . . . . . . . . . 1181 35 Normal Forms; The Rational Canonical Form 1187 35.1 The Torsion Module Associated With An Endomorphism . . . . . . . . . . 1187 35.2 The Rational Canonical Form . . . . . . . . . . . . . . . . . . . . . . . . . . 1195