Algebra, Topology, Di(cid:11)erential Calculus, and Optimization Theory For Computer Science and Machine Learning 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) August 2, 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 Motivations: Linear Combinations, Linear Independence, Rank . . . . . . . 45 3.2 Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 P 3.3 Indexed Families; the Sum Notation a . . . . . . . . . . . . . . . . . . 60 i I i 3.4 Linear Independence, Subspaces . . . .2 . . . . . . . . . . . . . . . . . . . . 66 3.5 Bases of a Vector Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.6 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 3.7 Linear Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 3.8 Quotient Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 3.9 Linear Forms and the Dual Space . . . . . . . . . . . . . . . . . . . . . . . . 94 3.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 3.11 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 4 Matrices and Linear Maps 107 4.1 Representation of Linear Maps by Matrices . . . . . . . . . . . . . . . . . . 107 4.2 Composition of Linear Maps and Matrix Multiplication . . . . . . . . . . . 112 4.3 Change of Basis Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 4.4 The E(cid:11)ect of a Change of Bases on Matrices . . . . . . . . . . . . . . . . . 120 4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 4.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 5 Haar Bases, Haar Wavelets, Hadamard Matrices 131 3 4 CONTENTS 5.1 Introduction to Signal Compression Using Haar Wavelets . . . . . . . . . . 131 5.2 Haar Matrices, Scaling Properties of Haar Wavelets . . . . . . . . . . . . . . 133 5.3 Kronecker Product Construction of Haar Matrices . . . . . . . . . . . . . . 138 5.4 Multiresolution Signal Analysis with Haar Bases . . . . . . . . . . . . . . . 140 5.5 Haar Transform for Digital Images . . . . . . . . . . . . . . . . . . . . . . . 142 5.6 Hadamard Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 5.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 5.8 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 6 Direct Sums 155 6.1 Sums, Direct Sums, Direct Products . . . . . . . . . . . . . . . . . . . . . . 155 6.2 The Rank-Nullity Theorem; Grassmann’s Relation . . . . . . . . . . . . . . 165 6.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 6.4 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 7 Determinants 181 7.1 Permutations, Signature of a Permutation . . . . . . . . . . . . . . . . . . . 181 7.2 Alternating Multilinear Maps . . . . . . . . . . . . . . . . . . . . . . . . . . 185 7.3 De(cid:12)nition of a Determinant . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 7.4 Inverse Matrices and Determinants . . . . . . . . . . . . . . . . . . . . . . . 197 7.5 Systems of Linear Equations and Determinants . . . . . . . . . . . . . . . . 200 7.6 Determinant of a Linear Map . . . . . . . . . . . . . . . . . . . . . . . . . . 203 7.7 The Cayley{Hamilton Theorem . . . . . . . . . . . . . . . . . . . . . . . . . 203 7.8 Permanents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 7.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 7.10 Further Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 7.11 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 8 Gaussian Elimination, LU, Cholesky, Echelon Form 219 8.1 Motivating Example: Curve Interpolation . . . . . . . . . . . . . . . . . . . 219 8.2 Gaussian Elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 8.3 Elementary Matrices and Row Operations . . . . . . . . . . . . . . . . . . . 228 8.4 LU-Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 8.5 PA = LU Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 ~ 8.6 Proof of Theorem 8.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245 8.7 Dealing with Roundo(cid:11) Errors; Pivoting Strategies . . . . . . . . . . . . . . . 251 8.8 Gaussian Elimination of Tridiagonal Matrices . . . . . . . . . . . . . . . . . 252 8.9 SPD Matrices and the Cholesky Decomposition . . . . . . . . . . . . . . . . 254 8.10 Reduced Row Echelon Form . . . . . . . . . . . . . . . . . . . . . . . . . . . 263 8.11 RREF, Free Variables, Homogeneous Systems . . . . . . . . . . . . . . . . . 269 8.12 Uniqueness of RREF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272 8.13 Solving Linear Systems Using RREF . . . . . . . . . . . . . . . . . . . . . . 274 8.14 Elementary Matrices and Columns Operations . . . . . . . . . . . . . . . . 281 CONTENTS 5 ~ 8.15 Transvections and Dilatations . . . . . . . . . . . . . . . . . . . . . . . . 282 8.16 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287 8.17 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289 9 Vector Norms and Matrix Norms 301 9.1 Normed Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301 9.2 Matrix Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312 9.3 Subordinate Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317 9.4 Inequalities Involving Subordinate Norms . . . . . . . . . . . . . . . . . . . 324 9.5 Condition Numbers of Matrices . . . . . . . . . . . . . . . . . . . . . . . . . 326 9.6 An Application of Norms: Inconsistent Linear Systems . . . . . . . . . . . . 335 9.7 Limits of Sequences and Series . . . . . . . . . . . . . . . . . . . . . . . . . 336 9.8 The Matrix Exponential . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339 9.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342 9.10 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344 10 Iterative Methods for Solving Linear Systems 351 10.1 Convergence of Sequences of Vectors and Matrices . . . . . . . . . . . . . . 351 10.2 Convergence of Iterative Methods . . . . . . . . . . . . . . . . . . . . . . . . 354 10.3 Methods of Jacobi, Gauss{Seidel, and Relaxation . . . . . . . . . . . . . . . 356 10.4 Convergence of the Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 364 10.5 Convergence Methods for Tridiagonal Matrices . . . . . . . . . . . . . . . . 367 10.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372 10.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373 11 The Dual Space and Duality 375 11.1 The Dual Space E and Linear Forms . . . . . . . . . . . . . . . . . . . . . 375 (cid:3) 11.2 Pairing and Duality Between E and E . . . . . . . . . . . . . . . . . . . . 382 (cid:3) 11.3 The Duality Theorem and Some Consequences . . . . . . . . . . . . . . . . 387 11.4 The Bidual and Canonical Pairings . . . . . . . . . . . . . . . . . . . . . . . 393 11.5 Hyperplanes and Linear Forms . . . . . . . . . . . . . . . . . . . . . . . . . 395 11.6 Transpose of a Linear Map and of a Matrix . . . . . . . . . . . . . . . . . . 396 11.7 Properties of the Double Transpose . . . . . . . . . . . . . . . . . . . . . . . 403 11.8 The Four Fundamental Subspaces . . . . . . . . . . . . . . . . . . . . . . . 405 11.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408 11.10 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409 12 Euclidean Spaces 413 12.1 Inner Products, Euclidean Spaces . . . . . . . . . . . . . . . . . . . . . . . . 413 12.2 Orthogonality and Duality in Euclidean Spaces . . . . . . . . . . . . . . . . 422 12.3 Adjoint of a Linear Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429 12.4 Existence and Construction of Orthonormal Bases . . . . . . . . . . . . . . 432 12.5 Linear Isometries (Orthogonal Transformations) . . . . . . . . . . . . . . . . 439 6 CONTENTS 12.6 The Orthogonal Group, Orthogonal Matrices . . . . . . . . . . . . . . . . . 442 12.7 The Rodrigues Formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444 12.8 QR-Decomposition for Invertible Matrices . . . . . . . . . . . . . . . . . . . 447 12.9 Some Applications of Euclidean Geometry . . . . . . . . . . . . . . . . . . . 452 12.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453 12.11 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455 13 QR-Decomposition for Arbitrary Matrices 467 13.1 Orthogonal Re(cid:13)ections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467 13.2 QR-Decomposition Using Householder Matrices . . . . . . . . . . . . . . . . 472 13.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482 13.4 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482 14 Hermitian Spaces 489 14.1 Hermitian Spaces, Pre-Hilbert Spaces . . . . . . . . . . . . . . . . . . . . . 489 14.2 Orthogonality, Duality, Adjoint of a Linear Map . . . . . . . . . . . . . . . 498 14.3 Linear Isometries (Also Called Unitary Transformations) . . . . . . . . . . . 503 14.4 The Unitary Group, Unitary Matrices . . . . . . . . . . . . . . . . . . . . . 505 14.5 Hermitian Re(cid:13)ections and QR-Decomposition . . . . . . . . . . . . . . . . . 508 14.6 Orthogonal Projections and Involutions . . . . . . . . . . . . . . . . . . . . 513 14.7 Dual Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 516 14.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523 14.9 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 524 15 Eigenvectors and Eigenvalues 529 15.1 Eigenvectors and Eigenvalues of a Linear Map . . . . . . . . . . . . . . . . . 529 15.2 Reduction to Upper Triangular Form . . . . . . . . . . . . . . . . . . . . . . 537 15.3 Location of Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 541 15.4 Conditioning of Eigenvalue Problems . . . . . . . . . . . . . . . . . . . . . . 544 15.5 Eigenvalues of the Matrix Exponential . . . . . . . . . . . . . . . . . . . . . 547 15.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 549 15.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 550 16 Unit Quaternions and Rotations in SO(3) 561 H 16.1 The Group SU(2) and the Skew Field of Quaternions . . . . . . . . . . . 561 16.2 Representation of Rotation in SO(3) By Quaternions in SU(2) . . . . . . . 563 16.3 Matrix Representation of the Rotation r . . . . . . . . . . . . . . . . . . . 568 q 16.4 An Algorithm to Find a Quaternion Representing a Rotation . . . . . . . . 570 16.5 The Exponential Map exp: su(2) SU(2) . . . . . . . . . . . . . . . . . . 573 ! ~ 16.6 Quaternion Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . 575 16.7 Nonexistence of a \Nice" Section from SO(3) to SU(2) . . . . . . . . . . . . 577 16.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 579 16.9 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 580 CONTENTS 7 17 Spectral Theorems 583 17.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583 17.2 Normal Linear Maps: Eigenvalues and Eigenvectors . . . . . . . . . . . . . . 583 17.3 Spectral Theorem for Normal Linear Maps . . . . . . . . . . . . . . . . . . . 589 17.4 Self-Adjoint and Other Special Linear Maps . . . . . . . . . . . . . . . . . . 594 17.5 Normal and Other Special Matrices . . . . . . . . . . . . . . . . . . . . . . . 600 17.6 Rayleigh{Ritz Theorems and Eigenvalue Interlacing . . . . . . . . . . . . . 603 17.7 The Courant{Fischer Theorem; Perturbation Results . . . . . . . . . . . . . 608 17.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 611 17.9 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 612 18 Computing Eigenvalues and Eigenvectors 619 18.1 The Basic QR Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 621 18.2 Hessenberg Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 627 18.3 Making the QR Method More E(cid:14)cient Using Shifts . . . . . . . . . . . . . 633 18.4 Krylov Subspaces; Arnoldi Iteration . . . . . . . . . . . . . . . . . . . . . . 638 18.5 GMRES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 642 18.6 The Hermitian Case; Lanczos Iteration . . . . . . . . . . . . . . . . . . . . . 643 18.7 Power Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 644 18.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 646 18.9 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 647 19 Introduction to The Finite Elements Method 649 19.1 A One-Dimensional Problem: Bending of a Beam . . . . . . . . . . . . . . . 649 19.2 A Two-Dimensional Problem: An Elastic Membrane . . . . . . . . . . . . . 660 19.3 Time-Dependent Boundary Problems . . . . . . . . . . . . . . . . . . . . . . 663 20 Graphs and Graph Laplacians; Basic Facts 671 20.1 Directed Graphs, Undirected Graphs, Weighted Graphs . . . . . . . . . . . 674 20.2 Laplacian Matrices of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 681 20.3 Normalized Laplacian Matrices of Graphs . . . . . . . . . . . . . . . . . . . 685 20.4 Graph Clustering Using Normalized Cuts . . . . . . . . . . . . . . . . . . . 689 20.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 691 20.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 692 21 Spectral Graph Drawing 695 21.1 Graph Drawing and Energy Minimization . . . . . . . . . . . . . . . . . . . 695 21.2 Examples of Graph Drawings . . . . . . . . . . . . . . . . . . . . . . . . . . 698 21.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 702 22 Singular Value Decomposition and Polar Form 705 22.1 Properties of f f . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 705 (cid:3) (cid:14) 22.2 Singular Value Decomposition for Square Matrices . . . . . . . . . . . . . . 709 8 CONTENTS 22.3 Polar Form for Square Matrices . . . . . . . . . . . . . . . . . . . . . . . . . 712 22.4 Singular Value Decomposition for Rectangular Matrices . . . . . . . . . . . 715 22.5 Ky Fan Norms and Schatten Norms . . . . . . . . . . . . . . . . . . . . . . 718 22.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 719 22.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 719 23 Applications of SVD and Pseudo-Inverses 723 23.1 Least Squares Problems and the Pseudo-Inverse . . . . . . . . . . . . . . . . 723 23.2 Properties of the Pseudo-Inverse . . . . . . . . . . . . . . . . . . . . . . . . 730 23.3 Data Compression and SVD . . . . . . . . . . . . . . . . . . . . . . . . . . . 735 23.4 Principal Components Analysis (PCA) . . . . . . . . . . . . . . . . . . . . . 737 23.5 Best A(cid:14)ne Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . 748 23.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 752 23.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 753 II A(cid:14)ne and Projective Geometry 757 24 Basics of A(cid:14)ne Geometry 759 24.1 A(cid:14)ne Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 759 24.2 Examples of A(cid:14)ne Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . 768 24.3 Chasles’s Identity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 769 24.4 A(cid:14)ne Combinations, Barycenters . . . . . . . . . . . . . . . . . . . . . . . . 770 24.5 A(cid:14)ne Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 775 24.6 A(cid:14)ne Independence and A(cid:14)ne Frames . . . . . . . . . . . . . . . . . . . . . 781 24.7 A(cid:14)ne Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 787 24.8 A(cid:14)ne Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 794 24.9 A(cid:14)ne Geometry: A Glimpse . . . . . . . . . . . . . . . . . . . . . . . . . . 796 24.10 A(cid:14)ne Hyperplanes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 800 24.11 Intersection of A(cid:14)ne Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . 802 25 Embedding an A(cid:14)ne Space in a Vector Space 805 25.1 The \Hat Construction," or Homogenizing . . . . . . . . . . . . . . . . . . . 805 ^ 25.2 A(cid:14)ne Frames of E and Bases of E . . . . . . . . . . . . . . . . . . . . . . . 812 ^ 25.3 Another Construction of E . . . . . . . . . . . . . . . . . . . . . . . . . . . 815 25.4 Extending A(cid:14)ne Maps to Linear Maps . . . . . . . . . . . . . . . . . . . . . 818 26 Basics of Projective Geometry 823 26.1 Why Projective Spaces? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 823 26.2 Projective Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 828 26.3 Projective Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 833 26.4 Projective Frames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 836 26.5 Projective Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 850 CONTENTS 9 26.6 Finding a Homography Between Two Projective Frames . . . . . . . . . . . 856 26.7 A(cid:14)ne Patches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 869 26.8 Projective Completion of an A(cid:14)ne Space . . . . . . . . . . . . . . . . . . . 872 26.9 Making Good Use of Hyperplanes at In(cid:12)nity . . . . . . . . . . . . . . . . . 877 26.10 The Cross-Ratio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 880 26.11 Fixed Points of Homographies and Homologies . . . . . . . . . . . . . . . . 884 26.12 Duality in Projective Geometry . . . . . . . . . . . . . . . . . . . . . . . . . 898 26.13 Cross-Ratios of Hyperplanes . . . . . . . . . . . . . . . . . . . . . . . . . . . 902 26.14 Complexi(cid:12)cation of a Real Projective Space . . . . . . . . . . . . . . . . . . 904 26.15 Similarity Structures on a Projective Space . . . . . . . . . . . . . . . . . . 906 26.16 Some Applications of Projective Geometry . . . . . . . . . . . . . . . . . . . 915 III The Geometry of Bilinear Forms 921 27 The Cartan{Dieudonn(cid:19)e Theorem 923 27.1 The Cartan{Dieudonn(cid:19)e Theorem for Linear Isometries . . . . . . . . . . . . 923 27.2 A(cid:14)ne Isometries (Rigid Motions) . . . . . . . . . . . . . . . . . . . . . . . . 935 27.3 Fixed Points of A(cid:14)ne Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . 937 27.4 A(cid:14)ne Isometries and Fixed Points . . . . . . . . . . . . . . . . . . . . . . . 939 27.5 The Cartan{Dieudonn(cid:19)e Theorem for A(cid:14)ne Isometries . . . . . . . . . . . . 945 28 Isometries of Hermitian Spaces 949 28.1 The Cartan{Dieudonn(cid:19)e Theorem, Hermitian Case . . . . . . . . . . . . . . . 949 28.2 A(cid:14)ne Isometries (Rigid Motions) . . . . . . . . . . . . . . . . . . . . . . . . 958 29 The Geometry of Bilinear Forms; Witt’s Theorem 963 29.1 Bilinear Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 963 29.2 Sesquilinear Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 971 29.3 Orthogonality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 975 29.4 Adjoint of a Linear Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 980 29.5 Isometries Associated with Sesquilinear Forms . . . . . . . . . . . . . . . . . 982 29.6 Totally Isotropic Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . 986 29.7 Witt Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 992 29.8 Symplectic Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1000 29.9 Orthogonal Groups and the Cartan{Dieudonn(cid:19)e Theorem . . . . . . . . . . . 1004 29.10 Witt’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1011 IV Algebra: PID’s, UFD’s, Noetherian Rings, Tensors, Modules over a PID, Normal Forms 1017 30 Polynomials, Ideals and PID’s 1019 10 CONTENTS 30.1 Multisets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1019 30.2 Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1020 30.3 Euclidean Division of Polynomials . . . . . . . . . . . . . . . . . . . . . . . 1026 30.4 Ideals, PID’s, and Greatest Common Divisors . . . . . . . . . . . . . . . . . 1028 30.5 Factorization and Irreducible Factors in K[X] . . . . . . . . . . . . . . . . . 1036 30.6 Roots of Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1040 30.7 Polynomial Interpolation (Lagrange, Newton, Hermite) . . . . . . . . . . . . 1047 31 Annihilating Polynomials; Primary Decomposition 1055 31.1 Annihilating Polynomials and the Minimal Polynomial . . . . . . . . . . . . 1057 31.2 Minimal Polynomials of Diagonalizable Linear Maps . . . . . . . . . . . . . 1059 31.3 Commuting Families of Linear Maps . . . . . . . . . . . . . . . . . . . . . . 1062 31.4 The Primary Decomposition Theorem . . . . . . . . . . . . . . . . . . . . . 1065 31.5 Jordan Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1071 31.6 Nilpotent Linear Maps and Jordan Form . . . . . . . . . . . . . . . . . . . . 1074 31.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1080 31.8 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1081 32 UFD’s, Noetherian Rings, Hilbert’s Basis Theorem 1085 32.1 Unique Factorization Domains (Factorial Rings) . . . . . . . . . . . . . . . . 1085 32.2 The Chinese Remainder Theorem . . . . . . . . . . . . . . . . . . . . . . . . 1099 32.3 Noetherian Rings and Hilbert’s Basis Theorem . . . . . . . . . . . . . . . . 1105 32.4 Futher Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1109 33 Tensor Algebras 1111 33.1 Linear Algebra Preliminaries: Dual Spaces and Pairings . . . . . . . . . . . 1113 33.2 Tensors Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1118 33.3 Bases of Tensor Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1130 33.4 Some Useful Isomorphisms for Tensor Products . . . . . . . . . . . . . . . . 1131 33.5 Duality for Tensor Products . . . . . . . . . . . . . . . . . . . . . . . . . . . 1135 33.6 Tensor Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1141 33.7 Symmetric Tensor Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1148 33.8 Bases of Symmetric Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . 1152 33.9 Some Useful Isomorphisms for Symmetric Powers . . . . . . . . . . . . . . . 1155 33.10 Duality for Symmetric Powers . . . . . . . . . . . . . . . . . . . . . . . . . . 1155 33.11 Symmetric Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1159 33.12 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1162 34 Exterior Tensor Powers and Exterior Algebras 1165 34.1 Exterior Tensor Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1165 34.2 Bases of Exterior Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1170 34.3 Some Useful Isomorphisms for Exterior Powers . . . . . . . . . . . . . . . . 1173 34.4 Duality for Exterior Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . 1173