Advanced Linear Algebra

Designed for advanced undergraduate and beginning graduate students in linear or abstract algebra, Advanced Linear Algebra covers theoretical aspects of the subject, along with examples, computations, and proofs. It explores a variety of advanced topics in linear algebra that highlight the rich interconnections of the subject to geometry, algebra, analysis, combinatorics, numerical computation, and many other areas of mathematics. The author begins with chapters introducing basic notation for vector spaces, permutations, polynomials, and other algebraic structures. The following chapters are designed to be mostly independent of each other, so that readers with different interests can jump directly to the topic they want. This is an unusual organization compared to many abstract algebra textbooks, which require readers to follow the order of chapters. Each chapter consists of a mathematical vignette devoted to the development of one specific topic. Some chapters look at introductory material from a sophisticated or abstract viewpoint while others provide elementary expositions of more theoretical concepts. Several chapters offer unusual perspectives or novel treatments of standard results. A wide array of topics is included, ranging from concrete matrix theory (basic matrix computations, determinants, normal matrices, canonical forms, matrix factorizations, and numerical algorithms) to more abstract linear algebra (modules, Hilbert spaces, dual vector spaces, bilinear forms, principal ideal domains, universal mapping properties, and multilinear algebra). The book provides a bridge from elementary computational linear algebra to more advanced, abstract aspects of linear algebra needed in many areas of pure and applied mathematics. Cover Half Title Series Page Title Page Copyright Page Dedication Contents Preface Part I: Background on Algebraic Structures 1. Overview of Algebraic Systems 1.1. Groups 1.2. Rings and Fields 1.3. Vector Spaces 1.4. Subsystems 1.5. Product Systems 1.6. Quotient Systems 1.7. Homomorphisms 1.8. Spanning, Linear Independence, Basis, and Dimension 1.9. Summary 1.10. Exercises 2. Permutations 2.1. Symmetric Groups 2.2. Representing Functions as Directed Graphs 2.3. Cycle Decompositions of Permutations 2.4. Composition of Cycles 2.5. Factorizations of Permutations 2.6. Inversions and Sorting 2.7. Signs of Permutations 2.8. Summary 2.9. Exercises 3. Polynomials 3.1. Intuitive Definition of Polynomials 3.2. Algebraic Operations on Polynomials 3.3. Formal Power Series and Polynomials 3.4. Properties of Degree 3.5. Evaluating Polynomials 3.6. Polynomial Division with Remainder 3.7. Divisibility and Associates 3.8. Greatest Common Divisors of Polynomials 3.9. GCDs of Lists of Polynomials 3.10. Matrix Reduction Algorithm for GCDs 3.11. Roots of Polynomials 3.12. Irreducible Polynomials 3.13. Unique Factorization of Polynomials 3.14. Prime Factorizations and Divisibility 3.15. Irreducible Polynomials in Q[x] 3.16. Testing Irreducibility in Q[x] via Reduction Modulo a Prime 3.17. Eisenstein’s Irreducibility Criterion for Q[x] 3.18. Lagrange’s Interpolation Formula 3.19. Kronecker’s Algorithm for Factoring in Q[x] 3.20. Algebraic Elements and Minimal Polynomials 3.21. Multivariable Polynomials 3.22. Summary 3.23. Exercises Part II: Matrices 4. Basic Matrix Operations 4.1. Formal Definition of Matrices and Vectors 4.2. Vector Spaces of Functions 4.3. Matrix Operations via Entries 4.4. Properties of Matrix Multiplication 4.5. Generalized Associativity 4.6. Invertible Matrices 4.7. Matrix Operations via Columns 4.8. Matrix Operations via Rows 4.9. Elementary Operations and Elementary Matrices 4.10. Elementary Matrices and Gaussian Elimination 4.11. Elementary Matrices and Invertibility 4.12. Row Rank and Column Rank 4.13. Conditions for Invertibility of a Matrix 4.14. Block Matrix Multiplication 4.15. Tensor Product of Matrices 4.16. Summary 4.17. Exercises 5. Determinants via Calculations 5.1. Matrices with Entries in a Ring 5.2. Explicit Definition of the Determinant 5.3. Diagonal and Triangular Matrices 5.4. Changing Variables 5.5. Transposes and Determinants 5.6. Multilinearity and the Alternating Property 5.7. Elementary Row Operations and Determinants 5.8. Determinant Properties Involving Columns 5.9. Product Formula via Elementary Matrices 5.10. Laplace Expansions 5.11. Classical Adjoints and Inverses 5.12. Cramer’s Rule 5.13. Product Formula via Computations 5.14. Cauchy–Binet Formula 5.15. Cayley–Hamilton Theorem 5.16. Permanents 5.17. Summary 5.18. Exercises 6. Comparing Concrete Linear Algebra to Abstract Linear Algebra 6.1. Column Vectors versus Abstract Vectors 6.2. Examples of Computing Coordinates 6.3. Operations on Column Vectors versus Abstract Vectors 6.4. Matrices versus Linear Maps 6.5. Examples of Matrices Associated with Linear Maps 6.6. Vector Operations on Matrices and Linear Maps 6.7. Matrix Transpose versus Dual Maps 6.8. Matrix/Vector Multiplication versus Evaluation of Maps 6.9. Matrix Multiplication versus Composition of Linear Maps 6.10. Transition Matrices and Changing Coordinates 6.11. Changing Bases 6.12. Algebras of Matrices versus Algebras of Linear Operators 6.13. Similarity of Matrices versus Similarity of Linear Maps 6.14. Diagonalizability and Triangulability 6.15. Block-Triangular Matrices and Invariant Subspaces 6.16. Block-Diagonal Matrices and Reducing Subspaces 6.17. Idempotent Matrices and Projections 6.18. Bilinear Maps and Matrices 6.19. Congruence of Matrices 6.20. Real Inner Product Spaces and Orthogonal Matrices 6.21. Complex Inner Product Spaces and Unitary Matrices 6.22. Summary 6.23. Exercises Part III: Matrices with Special Structure 7. Hermitian, Positive Definite, Unitary, and Normal Matrices 7.1. Conjugate-Transpose of a Matrix 7.2. Hermitian Matrices 7.3. Hermitian Decomposition of a Matrix 7.4. Positive Definite Matrices 7.5. Unitary Matrices 7.6. Unitary Similarity 7.7. Unitary Triangularization 7.8. Simultaneous Triangularization 7.9. Normal Matrices and Unitary Diagonalization 7.10. Polynomials and Commuting Matrices 7.11. Simultaneous Unitary Diagonalization 7.12. Polar Decomposition: Invertible Case 7.13. Polar Decomposition: General Case 7.14. Interlacing Eigenvalues for Hermitian Matrices 7.15. Determinant Criterion for Positive Definite Matrices 7.16. Summary 7.17. Exercises 8. Jordan Canonical Forms 8.1. Examples of Nilpotent Maps 8.2. Partition Diagrams 8.3. Partition Diagrams and Nilpotent Maps 8.4. Computing Images via Partition Diagrams 8.5. Computing Null Spaces via Partition Diagrams 8.6. Classification of Nilpotent Maps (Stage 1) 8.7. Classification of Nilpotent Maps (Stage 2) 8.8. Classification of Nilpotent Maps (Stage 3) 8.9. Fitting’s Lemma 8.10. Existence of Jordan Canonical Forms 8.11. Uniqueness of Jordan Canonical Forms 8.12. Computing Jordan Canonical Forms 8.13. Application to Differential Equations 8.14. Minimal Polynomials 8.15. Jordan–Chevalley Decomposition of a Linear Operator 8.16. Summary 8.17. Exercises 9. Matrix Factorizations 9.1. Approximation by Orthonormal Vectors 9.2. Gram–Schmidt Orthonormalization Algorithm 9.3. Gram–Schmidt QR Factorization 9.4. Householder Reflections 9.5. Householder QR Factorization 9.6. LU Factorization 9.7. Example of the LU Factorization 9.8. LU Factorizations and Gaussian Elimination 9.9. Permuted LU Factorizations 9.10. Cholesky Factorization 9.11. Least Squares Approximation 9.12. Singular Value Decomposition 9.13. Summary 9.14. Exercises 10. Iterative Algorithms in Numerical Linear Algebra 10.1. Richardson’s Algorithm 10.2. Jacobi’s Algorithm 10.3. Gauss–Seidel Algorithm 10.4. Vector Norms 10.5. Metric Spaces 10.6. Convergence of Sequences 10.7. Comparable Norms 10.8. Matrix Norms 10.9. Formulas for Matrix Norms 10.10. Matrix Inversion via Geometric Series 10.11. Affine Iteration and Richardson’s Algorithm 10.12. Splitting Matrices and Jacobi’s Algorithm 10.13. Induced Matrix Norms and the Spectral Radius 10.14. Analysis of the Gauss–Seidel Algorithm 10.15. Power Method for Finding Eigenvalues 10.16. Shifted and Inverse Power Method 10.17. Deflation 10.18. Summary 10.19. Exercises Part IV: The Interplay of Geometry and Linear Algebra 11. Affine Geometry and Convexity 11.1. Linear Subspaces 11.2. Examples of Linear Subspaces 11.3. Characterizations of Linear Subspaces 11.4. Affine Combinations and Affine Sets 11.5. Affine Sets and Linear Subspaces 11.6. The Affine Span of a Set 11.7. Affine Independence 11.8. Affine Bases and Barycentric Coordinates 11.9. Characterizations of Affine Sets 11.10. Affine Maps 11.11. Convex Sets 11.12. Convex Hulls 11.13. Carathéodory’s Theorem on Convex Hulls 11.14. Hyperplanes and Half-Spaces in Rn 11.15. Closed Convex Sets 11.16. Cones and Convex Cones 11.17. Intersection Lemma for V-Cones 11.18. All H-Cones Are V-Cones 11.19. Projection Lemma for H-Cones 11.20. All V-Cones Are H-Cones 11.21. Finite Intersections of Closed Half-Spaces 11.22. Convex Functions 11.23. Derivative Tests for Convex Functions 11.24. Summary 11.25. Exercises 12. Ruler and Compass Constructions 12.1. Geometric Constructibility 12.2. Arithmetic Constructibility 12.3. Preliminaries on Field Extensions 12.4. Field-Theoretic Constructibility 12.5. Proof that GC ⊆ AC 12.6. Proof that AC ⊆ GC 12.7. Algebraic Elements and Minimal Polynomials 12.8. Proof that AC = SQC 12.9. Impossibility of Geometric Construction Problems 12.10. Constructibility of a Regular 17-Sided Polygon 12.11. Overview of Solvability by Radicals 12.12. Summary 12.13. Exercises 13. Dual Vector Spaces 13.1. Vector Spaces of Linear Maps 13.2. Dual Bases 13.3. The Zero-Set Operator 13.4. The Annihilator Operator 13.5. The Double Dual V∗∗ 13.6. Correspondence between Subspaces of V and V∗ 13.7. Dual Maps 13.8. Bilinear Pairings of Vector Spaces 13.9. Theorems on Bilinear Pairings 13.10. Real Inner Product Spaces 13.11. Complex Inner Product Spaces 13.12. Duality for Infinite-Dimensional Spaces 13.13. A Preview of Affine Algebraic Geometry 13.14. Summary 13.15. Exercises 14. Bilinear Forms 14.1. Definition of Bilinear Forms 14.2. Examples of Bilinear Forms 14.3. Matrix of a Bilinear Form 14.4. Congruence of Matrices 14.5. Orthogonality in Bilinear Spaces 14.6. Bilinear Forms and Dual Spaces 14.7. Theorem on Orthogonal Complements 14.8. Radical of a Bilinear Form 14.9. Diagonalization of Symmetric Bilinear Forms 14.10. Structure of Alternate Bilinear Forms 14.11. Totally Isotropic Subspaces 14.12. Orthogonal Maps 14.13. Reflections 14.14. Writing Orthogonal Maps as Compositions of Reflections 14.15. Witt’s Cancellation Theorem 14.16. Uniqueness Property of Witt Decompositions 14.17. Summary 14.18. Exercises 15. Metric Spaces and Hilbert Spaces 15.1. Metric Spaces 15.2. Convergent Sequences 15.3. Closed Sets 15.4. Open Sets 15.5. Continuous Functions 15.6. Compact Sets 15.7. Completeness 15.8. Definition of a Hilbert Space 15.9. Examples of Hilbert Spaces 15.10. Proof of the Hilbert Space Axioms for l2(X) 15.11. Basic Properties of Hilbert Spaces 15.12. Closed Convex Sets in Hilbert Spaces 15.13. Orthogonal Complements 15.14. Orthonormal Sets 15.15. Maximal Orthonormal Sets 15.16. Isomorphism of H and l2(X) 15.17. Continuous Linear Maps 15.18. Dual Space of a Hilbert Space 15.19. Adjoints 15.20. Summary 15.21. Exercises Part V: Modules and Classification Theorems 16. Finitely Generated Commutative Groups 16.1. Commutative Groups 16.2. Generating Sets for Commutative Groups 16.3. Z-Independence and Z-Bases 16.4. Elementary Operations on Z-Bases 16.5. Coordinates and Z-Linear Maps 16.6. UMP for Free Commutative Groups 16.7. Quotient Groups of Free Commutative Groups 16.8. Subgroups of Free Commutative Groups 16.9. Z-Linear Maps and Integer Matrices 16.10. Elementary Operations and Change of Basis 16.11. Reduction Theorem for Integer Matrices 16.12. Structure of Z-Linear Maps of Free Commutative Groups 16.13. Structure of Finitely Generated Commutative Groups 16.14. Example of the Reduction Algorithm 16.15. Some Special Subgroups 16.16. Uniqueness Proof: Free Case 16.17. Uniqueness Proof: Prime Power Case 16.18. Uniqueness of Elementary Divisors 16.19. Uniqueness of Invariant Factors 16.20. Uniqueness Proof: General Case 16.21. Summary 16.22. Exercises 17. Introduction to Modules 17.1. Module Axioms 17.2. Examples of Modules 17.3. Submodules 17.4. Submodule Generated by a Subset 17.5. Direct Products and Direct Sums 17.6. Homomorphism Modules 17.7. Quotient Modules 17.8. Changing the Ring of Scalars 17.9. Fundamental Homomorphism Theorem for Modules 17.10. More Module Isomorphism Theorems 17.11. Free Modules 17.12. Finitely Generated Modules over a Division Ring 17.13. Zorn’s Lemma 17.14. Existence of Bases for Modules over Division Rings 17.15. Basis Invariance for Modules over Division Rings 17.16. Basis Invariance for Free Modules over Commutative Rings 17.17. Jordan–Hölder Theorem for Modules 17.18. Modules of Finite Length 17.19. Summary 17.20. Exercises 18. Principal Ideal Domains, Modules over PIDs, and Canonical Forms 18.1. Principal Ideal Domains 18.2. Divisibility in Commutative Rings 18.3. Divisibility and Ideals 18.4. Prime and Irreducible Elements 18.5. Irreducible Factorizations in PIDs 18.6. Free Modules over a PID 18.7. Operations on Bases 18.8. Matrices of Linear Maps between Free Modules 18.9. Reduction Theorem for Matrices over a PID 18.10. Structure Theorems for Linear Maps and Modules 18.11. Minors and Matrix Invariants 18.12. Uniqueness of Smith Normal Form 18.13. Torsion Submodules 18.14. Uniqueness of Invariant Factors 18.15. Uniqueness of Elementary Divisors 18.16. F[x]-Module Defined by a Linear Operator 18.17. Rational Canonical Form of a Linear Map 18.18. Jordan Canonical Form of a Linear Map 18.19. Canonical Forms of Matrices 18.20. Summary 18.21. Exercises Part VI: Universal Mapping Properties and Multilinear Algebra 19. Introduction to Universal Mapping Properties 19.1. Bases of Free R-Modules 19.2. Homomorphisms out of Quotient Modules 19.3. Direct Product of Two Modules 19.4. Direct Sum of Two Modules 19.5. Direct Products of Arbitrary Families of R-Modules 19.6. Direct Sums of Arbitrary Families of R-Modules 19.7. Solving Universal Mapping Problems 19.8. Summary 19.9. Exercises 20. Universal Mapping Problems in Multilinear Algebra 20.1. Multilinear Maps 20.2. Alternating Maps 20.3. Symmetric Maps 20.4. Tensor Product of Modules 20.5. Exterior Powers of a Module 20.6. Symmetric Powers of a Module 20.7. Myths about Tensor Products 20.8. Tensor Product Isomorphisms 20.9. Associativity of Tensor Products 20.10. Tensor Product of Maps 20.11. Bases and Multilinear Maps 20.12. Bases for Tensor Products of Free Modules 20.13. Bases and Alternating Maps 20.14. Bases for Exterior Powers of Free Modules 20.15. Bases for Symmetric Powers of Free Modules 20.16. Tensor Product of Matrices 20.17. Determinants and Exterior Powers 20.18. From Modules to Algebras 20.19. Summary 20.20. Exercises Appendix: Basic Definitions Sets Functions Relations Partially Ordered Sets Further Reading Bibliography Index