Preface
Part I: Background on Algebraic Structures
Chapter 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
Chapter 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
Chapter 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
Chapter 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
Chapter 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
Chapter 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 Lineaer 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
Chapter 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
Chapter 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
Chapter 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
Chapter 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
Chapter 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: Caratheodory'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
Chapter 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
12.6: Proof that AC
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
Chapter 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
Chapter 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
Chapter 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
Chapter 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
Chapter 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-Holder Theorem for Modules
17.18: Modules of Finite Length
17.19: Summary
17.20: Exercises
Chapter 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
Chapter 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
Chapter 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
A.1: Sets
A.2: Functions
A.3: Relations
A.4: Partially Ordered Sets
Further Reading
Bibliography
Index
Biography
Nicholas A. Loehr received his Ph.D. in mathematics from the University of California at San Diego in 2003, studying algebraic combinatorics under the guidance of Professor Jeffrey Remmel. After spending two years at the University of Pennsylvania as an NSF postdoc, Dr. Loehr taught mathematics at the College of William and Mary, the United States Naval Academy, and Virginia Tech. Dr. Loehr has authored over sixty refereed journal articles and three textbooks on combinatorics, advanced linear algebra, and mathematical proofs. He teaches classes in these subjects and many others, including cryptography, vector calculus, modern algebra, real analysis, complex analysis, and number theory.
