List of results

Definition 0.9.1 Matrix
Example Matrices over different fields
Definition 0.9.2 Zero matrix
Definition 0.9.3 Identity matrix
Definition 0.9.4 Diagonal matrix
Definition 0.9.5 Upper triangular matrix
Example Zero and identity matrices
Example Diagonal and triangular
Definition 0.9.6 Matrix addition
Definition 0.9.7 Scalar multiplication
Definition 0.9.8 Additive inverse
Example Adding and scaling
Theorem 0.9.1 Properties of addition and scalar multiplication
Definition 0.9.9 Matrix multiplication
Example A product of square matrices
Example Products of rectangular matrices
Theorem 0.9.2 Three views of a product
Theorem 0.9.3 $\mathbf{A}\mathbf{x}$ is a combination of the columns of $\mathbf{A}$
Example One product, three ways
Theorem 0.9.4 Properties of matrix multiplication
Definition 0.9.10 Transpose
Definition 0.9.11 Symmetric and skew-symmetric matrices
Example Transposes, symmetric and skew-symmetric matrices
Theorem 0.9.5 Properties of the transpose
Definition 0.9.12 Trace
Example Computing traces
Theorem 0.9.6 Properties of the trace
Definition 0.9.13 Invertible matrix
Theorem 0.9.7 Properties of inverses
Example Some invertible matrices
Theorem 0.9.8 Inverse of a $2 \times 2$ matrix
Definition 0.9.14 Powers and polynomials of a matrix
Theorem 0.9.9 Polynomials in one matrix
Example Plugging a matrix into a polynomial
Example Similarity
Example Row equivalence
Exercise A1
Exercise B1: Products and sizes
Exercise B2: Traces of products
Exercise B3: Inverses of $2 \times 2$ matrices
Exercise B4: Transposes of products
Exercise C1: $\mathbf{A}\mathbf{B} - \mathbf{B}\mathbf{A} = \mathbf{I}$ is impossible, or is it?
Exercise C2: Triangular matrices with non-zero diagonal
Exercise C3: Matrices that commute

0.10 Groups and Permutations

Definition 0.10.1 Group
Example Groups
Theorem 0.10.1 Basic properties of groups
Definition 0.10.2 Subgroup
Theorem 0.10.2 Subgroup test
Definition 0.10.3 Group homomorphism
Theorem 0.10.3 Basic properties of homomorphisms
Example Computing with cycles
Theorem 0.10.4 Transpositions generate $S_n$
Exercise A1
Exercise B1: The table of $S_3$
Exercise B2: Invertible upper triangular matrices
Exercise B3: The exponential is an isomorphism
Exercise C1: Every element its own inverse
Exercise C2: The order of a product of disjoint cycles

Vector Spaces

1.1 Vector Spaces

Definition 1.1.1 Vector Space
Definition 1.1.2 Vectors and Scalars
Example The Standard Vector Spaces
Example $\mathbb{Q}(\sqrt{2})$ over $\mathbb{Q}$
Example The Same Set over Different Fields
Example Positive Reals with Exotic Operations
Theorem 1.1.1 Left Cancellation Law
Theorem 1.1.2 Right Cancellation Law
Theorem 1.1.3 Zero Vector Is Unique
Theorem 1.1.4 Additive Inverse Is Unique
Definition 1.1.3 Notation for the Additive Inverse
Theorem 1.1.5 Zero Scalar Gives the Zero Vector
Theorem 1.1.6 Scalar Multiple of the Zero Vector
Theorem 1.1.7 Negation as Scalar Multiplication
Theorem 1.1.8 Negative Scalars
Theorem 1.1.9 Zero Product Law
Exercise A1
Exercise B1: Which Are Vector Spaces?
Exercise B2: More Rules for Signs
Exercise B3: Finishing the Positive Reals
Exercise C1: Commutativity Comes for Free
Exercise C2: How Big Is a Vector Space?
Exercise C3: Shrinking the Field

1.2 Subspaces

Definition 1.2.1 Subspace
Example Trivial Subspaces
Theorem 1.2.1 Subspace Test
Example A Line through the Origin
Example A Line Missing the Origin
Example Solutions of a Homogeneous System
Example Polynomials of Bounded Degree
Example Polynomials of Exact Degree
Example Differentiable Functions
Example Symmetric Matrices
Example Trace-Free Matrices
Theorem 1.2.2 Intersection of Subspaces
Example The Union of the Two Axes
Proposition 1.2.3 Union of Two Subspaces
Exercise A1
Exercise B1: Which Are Subspaces?
Exercise B2: Matrices Commuting with a Given Matrix
Exercise B3: Intersection and Union of Two Planes
Exercise C1: Covering a Space by Subspaces
Exercise C2: The Sum of Two Subspaces
Exercise C3: A One-Line Test, and a Test over $\mathbb{F}_2$

1.3 Linear Combinations and Span

Definition 1.3.1 Linear Combination
Example Linear Combinations in Four Families
Definition 1.3.2 Span
Example Computing Spans
Theorem 1.3.1 Span Is the Smallest Subspace
Corollary 1.3.2 Span as an Intersection
Definition 1.3.3 Spanning List, Spanning Set
Example Spanning Lists
Definition 1.3.4 Finite-Dimensional
Theorem 1.3.3 $F\lbrack x\rbrack$ Is Infinite-Dimensional
Proposition 1.3.4 Basic Properties of Span
Theorem 1.3.5 Absorbing a Vector into a Span
Example Two Lists with the Same Span
Exercise A1
Exercise B1: Membership in a Span
Exercise B2: Two Lists with the Same Span
Exercise B3: Spans in $\mathbb{R}^3$ , Geometrically
Exercise C1: Spans of Intersections and Unions
Exercise C2: The Span Depends on the Field

1.4 Linear Independence

Definition 1.4.1 Linear Independence
Example Independent Lists in Four Families
Example Degenerate Lists
Example A Parameter and a List of Matrices
Theorem 1.4.1 Linear Dependence Lemma
Example The Lemma on a Concrete List
Theorem 1.4.2 Span Preservation
Theorem 1.4.3 Independence and Uniqueness of Coefficients
Theorem 1.4.4 Polynomials of Distinct Degrees Are Independent
Exercise A1
Exercise B1: Independent or Not?
Exercise B2: A Parameter
Exercise B3: Sub-Lists
Exercise C1: Sums of Pairs, and the Field $\mathbb{F}_2$
Exercise C2: Adding a Vector outside the Span
Exercise C3: $1, \sqrt 2, \sqrt 3$ over $\mathbb{Q}$

1.5 Bases and Coordinates

Definition 1.5.1 Basis
Example Standard Bases
Example Three More Bases
Theorem 1.5.1 Unique Representation
Definition 1.5.2 Coordinates
Example Coordinates of a Polynomial
Theorem 1.5.2 Coordinates Respect the Operations
Lemma 1.5.3 Appending a Vector to an Independent List
Theorem 1.5.4 Sifting Theorem
Example Sifting a List in $\mathbb{R}^3$
Example The Order Matters
Corollary 1.5.5 Existence of Bases
Exercise A1
Exercise B1: A Basis of $\mathbb{R}^3$ and Coordinates
Exercise B2: Sifting Polynomials
Exercise B3: Symmetric Matrices
Exercise C1: Polynomials Vanishing at 1
Exercise C2: The Same List over a Different Field
Exercise C3: Rescaling a Basis

1.6 The Exchange Theorem and Dimension

Theorem 1.6.1 Steinitz Exchange Theorem
Theorem 1.6.2 Basis Theorem
Definition 1.6.1 Dimension
Example Dimensions of the Running Examples
Theorem 1.6.3 Size Bounds
Theorem 1.6.4 Count Instead of Check
Example A Basis by Counting
Theorem 1.6.5 Basis Extension Theorem
Example Extending an Independent List
Theorem 1.6.6 Maximal Independent and Minimal Spanning Lists
Theorem 1.6.7 Dimension of a Subspace
Theorem 1.6.8 Equal Dimension Forces Equality
Exercise A1
Exercise B1: Dimension and a Basis of a Subspace
Exercise B2: Extending to a Basis of $\mathbb{R}^4$
Exercise B3: Count Instead of Check
Exercise C1: Symmetric and Skew-Symmetric Matrices
Exercise C2: A complex space viewed over the reals
Exercise C3: Counting Elements over a Finite Field

1.7 Sums and Direct Sums

Definition 1.7.1 Sum of Subspaces
Theorem 1.7.1 Sum of Subspaces Theorem
Proposition 1.7.2 Sum of Spans
Theorem 1.7.3 Dimension Formula for Sums
Example Two planes in $\mathbb{R}^3$
Example Two planes in $\mathbb{R}^4$ from spanning lists
Definition 1.7.2 Direct Sum
Theorem 1.7.4 Direct Sum Criteria for Two Subspaces
Example A plane and a line in $\mathbb{R}^3$
Example Even and odd functions
Example Symmetric and skew-symmetric matrices
Theorem 1.7.5 Direct Sum Criteria for Several Subspaces
Theorem 1.7.6 Existence of Complements
Exercise A1
Exercise B1: Two Planes in $\mathbb{R}^4$
Exercise B2: A Plane and a Line
Exercise B3: Direct or Not?
Exercise C1: Symmetric Plus Skew over $\mathbb{F}_2$
Exercise C2: Subspaces That Must Meet
Exercise C3: Three Subspaces

1.8 Infinite-Dimensional Spaces

Example A Basis of $F[x]$
Example The Vectors $\mathbf{e}_i$ Do Not Span $F^{\mathbb{N}}$
Definition 1.8.1 Partial Order, Chain, Upper Bound, Maximal Element
Example Inclusion as a Partial Order
Theorem 1.8.1 Zorn’s Lemma
Theorem 1.8.2 Basis Extension, General Form
Theorem 1.8.3 Every Vector Space Has a Basis
Definition 1.8.2 Countable Set
Lemma 1.8.4 Countable Sets
Lemma 1.8.5 $\mathbb{R}$ Is Uncountable
Theorem 1.8.6 $\mathbb{R}$ Is Infinite-Dimensional over $\mathbb{Q}$
Exercise A1
Exercise B1: Finitely Supported Sequences
Exercise B2: Exponentials Are Independent
Exercise B3: Continuous Functions
Exercise C1: Complements in Any Dimension
Exercise C2: Bases of $\mathbb{R}$ over $\mathbb{Q}$ Are Uncountable

1.9 Changing the Field

Example $\mathbb{C}^2$ as a Real Vector Space
Definition 1.9.1 Subfield, Restriction of Scalars, Degree
Example Degrees of Some Fields
Theorem 1.9.1 Tower Law
Theorem 1.9.2 Complex Spaces as Real Spaces
Definition 1.9.2 Complexification
Theorem 1.9.3 A Real Basis Is a Complex Basis of the Complexification
Example The Complexification of $\mathbb{R}^n$ Is $\mathbb{C}^n$
Exercise A1
Exercise B1: A Tower over $\mathbb{Q}$
Exercise B2: Complex Matrices over $\mathbb{R}$
Exercise B3: Working in a Complexification
Exercise C1: When Is a Real Subspace Complex?
Exercise C2: A Tower of Degree Four

Linear Maps

2.1 Linear Maps

Definition 2.1.1 Linear Map
Example Multiplication by a Matrix
Example Maps Given by Formulas in Coordinates
Example Projection onto an Axis
Example Rotation of the Plane
Example Differentiation
Example Integration
Example Multiplication by $x$
Example Trace and Transpose
Example The Shift Maps on Sequences
Example Composition with a Fixed Function
Example Identity Map
Example Inclusion Map
Example Zero Map
Theorem 2.1.1 Linear Maps Send Zero to Zero
Theorem 2.1.2 Linear Maps Preserve Negatives
Theorem 2.1.3 One-Line Test for Linearity
Theorem 2.1.4 Linear Maps Preserve Linear Combinations
Example A Constant Function
Example Translation
Example Squaring
Example Length
Example Complex Conjugation: the Field Matters
Theorem 2.1.5 Linear Maps Are Determined by a Basis
Theorem 2.1.6 Linear Maps on an Arbitrary Basis
Example Finding a Formula from Values on a Basis
Example Too Many Conditions
Example Recognizing Differentiation
Exercise A1
Exercise B1: Which Maps Are Linear?
Exercise B2: A Formula from Values on a Basis
Exercise B3: Evaluation and Integration
Exercise C1: Over $\mathbb{Q}$ , Additivity Is Enough
Exercise C2: Over $\mathbb{C}$ , Additivity Is Not Enough

2.2 Kernel and Image

Definition 2.2.1 Kernel
Definition 2.2.2 Image
Theorem 2.2.1 The Kernel Is a Subspace
Theorem 2.2.2 The Image Is a Subspace
Example The Zero Map and the Identity
Example Projection onto an Axis
Theorem 2.2.3 Kernel Test for Injectivity
Theorem 2.2.4 The Image Is Spanned by the Images of a Spanning List
Example Differentiation
Example Trace
Example Integration
Example The Shifts: Injective but Not Surjective, and Conversely
Theorem 2.2.5 Injective Maps Preserve Independence, Surjective Maps Preserve Spanning
Exercise A1
Exercise B1: Kernel and Image from the Definitions
Exercise B2: Kernels and Images Beyond $F^n$
Exercise C1: Kernels and Images of a Composite
Exercise C2: When Is a Composite Injective?
Exercise C3: Differentiation over $\mathbb{F}_2$

2.3 The Rank–Nullity Theorem

Definition 2.3.1 Nullity
Definition 2.3.2 Rank
Example Rank and Nullity in Examples
Theorem 2.3.1 Rank–Nullity Theorem
Corollary 2.3.2 Consequences of Rank–Nullity
Example Prescribing Values and Slopes
Example Dimension of a Kernel from a Surjective Map
Exercise A1
Exercise B1: Verifying Rank–Nullity
Exercise B2: Bijective by the Kernel Alone
Exercise B3: A Dimension via a Surjective Map
Exercise C1: A Lower Bound for the Rank of a Composite
Exercise C2: When the Kernel Equals the Image

2.4 The Algebra of Linear Maps

Definition 2.4.1 The space of linear maps
Theorem 2.4.1 $\mathcal{L}(V, W)$ Is a Vector Space
Example Sums of Matrix Maps and Other First Examples
Theorem 2.4.2 Composition of Linear Maps
Example Rotate, Then Project
Definition 2.4.2 Powers and Polynomials of an Operator
Theorem 2.4.3 Polynomials in One Operator
Example Differentiation Is Nilpotent
Example Operators That Satisfy a Polynomial
Exercise A1
Exercise B1: Computing compositions
Exercise B2: Operators that preserve a subspace
Exercise B3: A polynomial that kills $D$
Exercise C1: The Heisenberg relation
Exercise C2: Commuting nilpotent operators

2.5 Invertible Maps and Isomorphisms

Definition 2.5.1 Invertible Linear Map
Theorem 2.5.1 The Inverse of a Linear Bijection Is Linear
Definition 2.5.2 Isomorphism
Definition 2.5.3 Isomorphic Spaces
Example The Standard Isomorphisms
Example One Equation Is Not Enough
Theorem 2.5.2 Isomorphisms Carry Bases to Bases
Theorem 2.5.3 Isomorphism Is an Equivalence Relation
Theorem 2.5.4 Classification of Finite-Dimensional Spaces
Corollary 2.5.5 The Coordinate Isomorphism
Example Sorting Spaces by Dimension
Theorem 2.5.6 One-Sided Inverses of Linear Maps
Theorem 2.5.7 Invertible Operator Theorem
Example Invertibility Without Solving Equations
Exercise A1
Exercise B1: An explicit isomorphism
Exercise B2: Inverting $\operatorname{id} + D$
Exercise B3: Deciding isomorphism
Exercise C1: Invertible products
Exercise C2: A space isomorphic to a proper subspace

Linear Systems and Matrices

3.1 Three Views of a Linear System

Definition 3.1.1 Linear system
Example None, one, or a whole line
Example Exactly two solutions over $\mathbb{F}_2$
Definition 3.1.2 Homogeneous system
Theorem 3.1.1 Consistency and the span of the columns
Example Span membership as a system
Theorem 3.1.2 Homogeneous solutions form a subspace
Theorem 3.1.3 Structure of the solution set
Example Particular plus homogeneous
Corollary 3.1.4 Uniqueness of solutions
Exercise A1
Exercise B1: Three views
Exercise B2: In the span or not?
Exercise B3: Solve and describe
Exercise C1: How many solutions?
Exercise C2: The right-hand sides that work

3.2 Gaussian Elimination

Definition 3.2.1 Elementary row operations
Lemma 3.2.1 Row operations act column by column
Definition 3.2.2 Row equivalence
Theorem 3.2.2 Row operations preserve solutions
Definition 3.2.3 Row echelon form
Definition 3.2.4 Reduced row echelon form
Example Echelon or not?
Theorem 3.2.3 Existence of the reduced row echelon form
Example Gauss–Jordan on a $3 \times 4$ system
Theorem 3.2.4 Reading solutions from the RREF
Example Elimination over $\mathbb{F}_2$
Example A system with a parameter
Corollary 3.2.5 More unknowns than equations
Exercise A1
Exercise B1: Reduce and solve
Exercise B2: A parameter
Exercise B3: Over $\mathbb{F}_3$
Exercise C1: Why $i \neq j$ ?
Exercise C2: The cost of elimination
Exercise C3: Solvable for every right-hand side

3.3 Uniqueness of the Reduced Form

Lemma 3.3.1 Row equivalent matrices have the same homogeneous solutions
Lemma 3.3.2 Row operations preserve column relations
Lemma 3.3.3 Columns of a matrix in RREF
Theorem 3.3.4 Uniqueness of the reduced row echelon form
Example Two echelon forms, one reduced form
Corollary 3.3.5 Pivot columns are well defined
Exercise A1
Exercise B1: Column relations
Exercise B2: Row equivalence via the RREF
Exercise B3: Row equivalent or not?
Exercise C1: Counting reduced forms
Exercise C2: Deleting a column

3.4 Elementary Matrices and Inverses

Definition 3.4.1 Elementary matrix
Theorem 3.4.1 Row operations are left multiplications
Example Three operations, three products
Theorem 3.4.2 Elementary matrices are invertible
Lemma 3.4.3 Square reduced matrices
Theorem 3.4.4 Invertible Matrix Theorem
Theorem 3.4.5 One-sided inverses of square matrices
Theorem 3.4.6 Inverse by row reduction
Example A $3 \times 3$ inverse
Example When the algorithm stops
Example Factoring into elementary matrices
Definition 3.4.2 Permutation matrix
Lemma 3.4.7 Permutation matrices
Theorem 3.4.8 Row equivalence is left multiplication by an invertible matrix
Exercise A1
Exercise B1: Inverses by row reduction
Exercise B2: A product of elementary matrices
Exercise B3: Invertible products
Exercise C1: Triangular matrices
Exercise C2: All right inverses
Exercise C3: Nilpotent perturbations of the identity

3.5 Row Space, Column Space, Null Space and Rank

Definition 3.5.1 Column space
Definition 3.5.2 Row space
Definition 3.5.3 Null space
Definition 3.5.4 Rank of a matrix
Definition 3.5.5 Nullity of a matrix
Theorem 3.5.1 Row operations and the three spaces
Theorem 3.5.2 Pivot columns form a basis of the column space
Theorem 3.5.3 Basis of the row space
Theorem 3.5.4 Basis of the null space
Example Bases for the running example
Theorem 3.5.5 Row rank equals column rank
Corollary 3.5.6 Rank from any echelon form
Theorem 3.5.7 Rank–Nullity for Matrices
Theorem 3.5.8 Rouché–Capelli Theorem
Example Counting solutions over $\mathbb{F}_3$
Theorem 3.5.9 Rank of a product
Theorem 3.5.10 Independence and spanning by rank
Example Testing independence
Example Extending to a basis by elimination
Proposition 3.5.11 Sum and intersection by elimination
Example A basis of a sum
Example A basis of an intersection
Exercise A1
Exercise B1: The three subspaces of a $3 \times 5$ matrix
Exercise B2: Independence and extension in $\mathbb{R}^4$
Exercise B3: Sum and intersection in $\mathbb{R}^5$
Exercise C1: Rank of a sum
Exercise C2: Matrices of rank one
Exercise C3: The matrix $i + j$
Exercise C4: Counting right-hand sides over a finite field

3.6 LU and PLU Factorizations

Definition 3.6.1 LU factorization
Example An LU factorization from elimination
Example An invertible matrix with no LU factorization
Lemma 3.6.1 Unit lower triangular matrices are closed
Lemma 3.6.2 Invertibility of a triangular matrix
Lemma 3.6.3 Multiplier matrices
Theorem 3.6.4 LU from elimination
Example Two right-hand sides, one factorization
Theorem 3.6.5 Uniqueness of the LU factorization
Lemma 3.6.6 Pushing a Swap Past a Gauss Transform
Definition 3.6.2 PLU factorization
Theorem 3.6.7 Existence of a PLU factorization
Example A swap in the middle
Theorem 3.6.8 LDLᵀ factorization
Exercise A1
Exercise B1: An LU factorization
Exercise B2: Two systems, one factorization
Exercise B3: A PLU factorization
Exercise C1: Leading principal submatrices
Exercise C2: An LDLᵀ factorization
Exercise C3: Counting matrices without an LU factorization

3.7 Applications of Linear Systems

Lemma 3.7.1 Factor Theorem for a Linear Divisor
Lemma 3.7.2 Root bound
Theorem 3.7.3 Polynomial interpolation
Example A cubic through four points
Example Interpolation as a Count
Example Burning ammonia
Definition 3.7.1 Incidence matrix
Proposition 3.7.4 Rank of an incidence matrix
Corollary 3.7.5 Solvable flow problems
Example Traffic in a town center
Example Every pattern of the 3 × 3 puzzle is solvable
Example Switching off the center
Exercise A1
Exercise B1: Interpolating four points
Exercise B2: Balancing a redox reaction
Exercise B3: A ring road
Exercise C1: The 2 × 2 puzzle
Exercise C2: Interpolating values and slopes
Exercise C3: Networks in several pieces

Matrices of Maps

4.1 The Matrix of a Linear Map

Definition 4.1.1 Matrix of a Linear Map
Example Differentiation on Cubic Polynomials
Example Matrix Maps and the Identity
Example The Transpose Map
Example A Reflection in Two Bases
Theorem 4.1.1 Coordinates of an Image
Example Kernel and Image Through a Matrix
Theorem 4.1.2 Matrix of a Composition
Example Multiply by $x$ , Then Differentiate
Corollary 4.1.3 Matrices of Powers and Polynomials
Theorem 4.1.4 $\mathcal{L}(V, W) \cong M_{m \times n}(F)$
Theorem 4.1.5 Rank and Invertibility from the Matrix
Example A Matrix Map
Example Rank of $\mathbf{X} \mapsto \mathbf{X} + \mathbf{X}^{\top}$
Exercise A1
Exercise B1: Matrices in given bases
Exercise B2: Recovering a map from its matrix
Exercise B3: A composition computed two ways
Exercise C1: Upper triangular matrices and invariant subspaces
Exercise C2: Integrating with a matrix

4.2 Change of Basis and Similarity

Definition 4.2.1 Change-of-coordinates matrix
Theorem 4.2.1 Change of Coordinates
Proposition 4.2.2 Invertible matrices are changes of basis
Example Coordinates around the point $1$
Theorem 4.2.3 Change of Basis for Linear Maps
Example The reflection in a mirror-adapted basis
Example Differentiation with a rescaled basis
Definition 4.2.2 Similar matrices
Theorem 4.2.4 Similar Matrices Represent the Same Operator
Theorem 4.2.5 Trace Is a Similarity Invariant
Proposition 4.2.6 More similarity invariants
Example Making a matrix diagonal with a well-chosen basis
Exercise A1
Exercise B1: Change-of-coordinates matrices
Exercise B2: A matrix in a new basis, two ways
Exercise B3: Similar or not?
Exercise C1: Matrices similar only to themselves
Exercise C2: $\mathbf{A}\mathbf{B}$ and $\mathbf{B}\mathbf{A}$
Exercise C3: Every non-zero $2 \times 2$ matrix with square zero

4.3 Rank, Equivalence and Factorizations

Theorem 4.3.1 Column–Row Factorization
Proposition 4.3.2 Rank as the size of the thinnest factorization
Example A column–row factorization
Definition 4.3.1 Equivalent matrices
Theorem 4.3.3 Rank Normal Form
Example Bringing a $2 \times 3$ matrix to normal form
Theorem 4.3.4 Rank of a Composition
Theorem 4.3.5 Sylvester’s Rank Inequality
Exercise A1
Exercise B1: A column–row factorization
Exercise B2: Normal form of a rank-one matrix
Exercise B3: Rank-one pieces
Exercise C1: Frobenius’s rank inequality
Exercise C2: Counting over $\mathbb{F}_2$

4.4 Products and Quotient Spaces

Definition 4.4.1 Product of vector spaces
Theorem 4.4.1 Dimension of a Product
Theorem 4.4.2 Internal and External Direct Sums
Definition 4.4.2 Coset
Lemma 4.4.3 When two cosets are equal
Definition 4.4.3 Quotient space
Theorem 4.4.4 The Quotient Space Is a Vector Space
Theorem 4.4.5 Dimension of a Quotient
Example A basis of a quotient of $\mathbb{R}^3$
Proposition 4.4.6 A complement is a model of the quotient
Theorem 4.4.7 First Isomorphism Theorem
Example Identifying quotients
Theorem 4.4.8 Second Isomorphism Theorem
Theorem 4.4.9 Third Isomorphism Theorem
Theorem 4.4.10 Universal Property of the Quotient
Exercise A1
Exercise B1: A basis of a quotient of $\mathbb{R}^4$
Exercise B2: A map that factors through a quotient
Exercise B3: Matrices modulo scalars
Exercise C1: The dimension formula from isomorphisms
Exercise C2: The operator induced on a quotient
Exercise C3: Counting cosets over a finite field

4.5 Projections and the Trace of an Operator

Definition 4.5.1 Projection
Theorem 4.5.1 Projections and Direct Sums
Corollary 4.5.2 The matrix of a projection
Example Projecting onto a plane along a line
Definition 4.5.2 Trace of an operator
Theorem 4.5.3 Properties of the Trace of an Operator
Theorem 4.5.4 Trace of a Projection
Theorem 4.5.5 Involutions Split the Space
Exercise A1
Exercise B1: A projection in $\mathbb{R}^3$
Exercise B2: The complementary projection
Exercise B3: Traces of operators on matrices
Exercise C1: When is a sum of projections a projection?
Exercise C2: The trace is the only trace-like functional

Duality

5.1 Linear Functionals and the Dual Space

Definition 5.1.1 Linear Functional
Definition 5.1.2 Dual Space
Example Four Families of Functionals
Theorem 5.1.1 Functionals on $F^n$ Are Row Vectors
Proposition 5.1.2 A Non-Zero Functional Is Surjective
Theorem 5.1.3 The Dual Basis
Definition 5.1.3 Dual Basis
Corollary 5.1.4 Dimension of the Dual Space
Example The Dual Basis Is Read Off the Inverse Matrix
Example Dual Bases in $\mathbb{R}[x]_{\le 2}$
Theorem 5.1.5 Functionals Separate Vectors
Example A Matrix Killed by Every Trace
Proposition 5.1.6 The Coordinate Functionals Do Not Span $F[x]^{*}$
Exercise A1
Exercise B1: Finding dual bases
Exercise B2: Which maps are functionals?
Exercise B3: Coordinates of a functional
Exercise C1: Functionals with the same kernel
Exercise C2: Functionals vanishing where others vanish
Exercise C3: Evaluations as a dual basis
Exercise C4: How large is $F\lbrack x\rbrack^{*}$ ?

5.2 Annihilators

Definition 5.2.1 Annihilator
Proposition 5.2.1 The Annihilator Is a Subspace
Example First Annihilators
Theorem 5.2.2 Dimension of the Annihilator
Example An Annihilator as a Null Space
Example The Equations of a Root Condition
Theorem 5.2.3 Properties of Annihilators
Exercise A1
Exercise B1: Computing annihilators
Exercise B2: Equations of the symmetric matrices
Exercise B3: The equations of a hyperplane
Exercise C1: The intersection formula without counting
Exercise C2: Equations of a double root
Exercise C3: Dual of a direct sum decomposition

5.3 The Double Dual

Definition 5.3.1 Double Dual and Evaluation Map
Example Evaluation in Three Spaces
Theorem 5.3.1 The Evaluation Map Is Linear and Injective
Theorem 5.3.2 The Double Dual Isomorphism
Corollary 5.3.3 Every Basis of the Dual Is a Dual Basis
Example A Basis With Prescribed Dual Basis
Corollary 5.3.4 The Annihilator of the Annihilator
Corollary 5.3.5 Subspaces Are Determined by Their Annihilators
Example A Functional on $F\lbrack x\rbrack^{*}$ That Is Not an Evaluation
Exercise A1
Exercise B1: A basis with a given dual basis
Exercise B2: $U^{00} = U$ for a line
Exercise B3: Recognizing an evaluation
Exercise C1: Subspaces of $V$ and of $V^{*}$
Exercise C2: Spans cut out by equations
Exercise C3: Where finite dimension is needed

5.4 The Dual Map and the Transpose

Definition 5.4.1 Dual Map
Example Dual Maps in Four Settings
Theorem 5.4.1 Properties of the Dual Map
Theorem 5.4.2 The Matrix of the Dual Map Is the Transpose
Example A $2 \times 3$ Example
Theorem 5.4.3 Kernel and Image of the Dual Map
Example Kernel and Image of a Dual Map
Corollary 5.4.4 Rank of the Dual Map
Corollary 5.4.5 Injective and Surjective Swap Under Duality
Theorem 5.4.6 The Evaluation Map Is Natural
Exercise A1
Exercise B1: Differentiation in dual bases
Exercise B2: Kernel and image of a dual map
Exercise B3: The transpose of a product, again
Exercise C1: The Fredholm alternative
Exercise C2: Invariant subspaces and annihilators
Exercise C3: Duality without finite dimension

5.5 Duality for Subspaces and Quotients

Theorem 5.5.1 Dual of a Subspace
Theorem 5.5.2 Dual of a Quotient
Example Both isomorphisms for a line
Definition 5.5.1 Codimension
Definition 5.5.2 Hyperplane
Theorem 5.5.3 Hyperplanes Are Kernels of Functionals
Exercise A1
Exercise B1: The dual of a quotient of $\mathbb{R}^4$
Exercise B2: Functionals with the same kernel
Exercise B3: Dimension computations
Exercise C1: Subspaces of finite codimension are intersections of hyperplanes
Exercise C2: Complements and a choice of copy of $U^{*}$

5.6 Hyperplanes and Linear Systems Revisited

Lemma 5.6.1 A subspace is cut out by its annihilator
Theorem 5.6.2 Every Subspace Is a Solution Set
Example Equations for a plane in $\mathbb{R}^4$
Theorem 5.6.3 Correctness of the Conversion
Proposition 5.6.4 Cosets as intersections of affine hyperplanes
Theorem 5.6.5 The Row Space Is the Annihilator of the Null Space
Corollary 5.6.6 Same solutions, same row space
Example An intersection computed from equations
Theorem 5.6.7 Independent Functionals
Exercise A1
Exercise B1: Equations for a span
Exercise B2: A spanning list for a system
Exercise B3: Two planes in $\mathbb{R}^4$
Exercise C1: Avoiding finitely many subspaces
Exercise C2: The least number of equations for a system

Polynomials

6.1 Division with Remainder

Theorem 6.1.1 Polynomial Division with Remainder
Example Long Division with a Non-Monic Divisor
Definition 6.1.1 Divisibility, Associates
Proposition 6.1.2 Rules for Divisibility
Theorem 6.1.3 Remainder Theorem and Factor Theorem
Example Remainders Without Dividing
Corollary 6.1.4 Distinct Roots Give a Product of Linear Factors
Theorem 6.1.5 Values Determine a Polynomial
Exercise A1
Exercise B1: Dividing Over Two Fields
Exercise B2: A Factor of $x^n - c^n$
Exercise B3: A Remainder Without Long Division
Exercise C1: Division by a Monic Polynomial Over $\mathbb{Z}$
Exercise C2: Remainders on Division by a Quadratic
Exercise C3: Equal Functions Over $\mathbb{F}_p$

6.2 Ideals and Greatest Common Divisors

Definition 6.2.1 Ideal of $F\lbrack x\rbrack$
Proposition 6.2.1 The Ideal Generated by Finitely Many Polynomials
Example First Ideals
Theorem 6.2.2 Every Ideal of $F\lbrack x\rbrack$ Is Principal
Definition 6.2.2 Greatest Common Divisor
Example First Greatest Common Divisors
Theorem 6.2.3 Characterization of the gcd
Corollary 6.2.4 Bézout’s Identity for Polynomials
Lemma 6.2.5 Dividing Does Not Change the Ideal
Theorem 6.2.6 Euclidean Algorithm
Example The Euclidean Algorithm with Back-Substitution
Definition 6.2.3 Coprime Polynomials
Proposition 6.2.7 Coprime Means 1 Is a Combination
Theorem 6.2.8 A Coprime Factor Can Be Canceled
Definition 6.2.4 Least Common Multiple
Proposition 6.2.9 The gcd Is the Same Over a Larger Field
Exercise A1
Exercise B1: gcd and Bézout Coefficients of Two Cubics
Exercise B2: Ideal or Not?
Exercise B3: The gcd of $x^m - 1$ and $x^n - 1$
Exercise C1: Polynomials Vanishing on a Set
Exercise C2: A Non-Principal Ideal in Two Variables
Exercise C3: gcd Times lcm

6.3 Irreducible Polynomials and Unique Factorization

Definition 6.3.1 Irreducible Polynomial
Example First Irreducible and Reducible Polynomials
Theorem 6.3.1 Irreducibility in Degree 2 and 3
Lemma 6.3.2 The gcd with an Irreducible Polynomial
Theorem 6.3.3 Euclid’s Lemma for Polynomials
Corollary 6.3.4 Euclid’s Lemma for Several Factors
Theorem 6.3.5 Unique Factorization in $F\lbrack x\rbrack$
Example Factoring $x^4 - 1$ Over Six Fields
Theorem 6.3.6 Rational Root Theorem
Example A Cubic That Is Irreducible Over $\mathbb{Q}$
Theorem 6.3.7 Eisenstein’s Criterion
Example Irreducible Polynomials of Every Degree Over $\mathbb{Q}$
Exercise A1
Exercise B1: Irreducible or Not?
Exercise B2: Factoring $x^6 - 1$ Over $\mathbb{Q}$
Exercise B3: Small Irreducibles Over $\mathbb{F}_2$
Exercise C1: Infinitely Many Irreducibles
Exercise C2: Gauss’s Lemma and Eisenstein’s Criterion

6.4 Roots, Multiplicity and Derivatives

Definition 6.4.1 Multiplicity of a Root
Lemma 6.4.1 Multiplicity via the Cofactor
Theorem 6.4.2 Multiplicity of a Product
Example Finding a Multiplicity by Repeated Division
Definition 6.4.2 Splitting into Linear Factors
Theorem 6.4.3 Roots Counted with Multiplicity
Definition 6.4.3 Formal Derivative
Theorem 6.4.4 Rules for the Formal Derivative
Theorem 6.4.5 Repeated Root Test
Corollary 6.4.6 Repeated Factors and $\gcd(f, f')$
Example Detecting a Repeated Root with a gcd
Theorem 6.4.7 Taylor Expansion of a Polynomial
Example Re-centering a Cubic
Exercise A1
Exercise B1: Multiplicities over different fields
Exercise B2: A gcd test
Exercise B3: The multiplicity of $1$
Exercise C1: Real roots of the derivative
Exercise C2: $x^p - x$ over $\mathbb{F}_p$
Exercise C3: Removing repeated factors

6.5 The Fundamental Theorem of Algebra

Theorem 6.5.1 Fundamental Theorem of Algebra
Lemma 6.5.2 Growth of a Polynomial
Lemma 6.5.3 The Minimum of $\lvert p \rvert$ Is Attained
Lemma 6.5.4 d’Alembert’s Lemma
Example One Step Downhill
Corollary 6.5.5 Complex Polynomials Split
Example Factoring $x^4 + 1$ over $\mathbb{C}$ and over $\mathbb{R}$
Theorem 6.5.6 Conjugate Roots Have Equal Multiplicity
Corollary 6.5.7 Irreducible Real Polynomials
Corollary 6.5.8 Factorization over $\mathbb{R}$
Corollary 6.5.9 Odd Degree Forces a Real Root
Exercise A1
Exercise B1: $x^4 + 4$
Exercise B2: $x^6 + 1$
Exercise B3: Real cubics
Exercise B4: Running the proof on an example
Exercise C1: Fields where the theorem fails
Exercise C2: Sums of two squares

6.6 Interpolation and the Chinese Remainder Theorem

Definition 6.6.1 Lagrange Basis
Theorem 6.6.1 Lagrange Interpolation
Example The Chapter 3 Cubic by Lagrange’s Formula
Corollary 6.6.2 Evaluations Are Dual to the Lagrange Basis
Example Integrals and Slopes from Values
Definition 6.6.2 Congruence Modulo a Polynomial
Lemma 6.6.3 Coprime to Each, Coprime to the Product
Theorem 6.6.4 Chinese Remainder Theorem for Polynomials
Example A Linear and a Quadratic Modulus
Example Values and Slopes by CRT
Theorem 6.6.5 Dimension of $F[x]/\langle m \rangle$
Theorem 6.6.6 CRT as an Isomorphism
Exercise A1
Exercise B1: A Lagrange interpolant
Exercise B2: A CRT system
Exercise B3: The Lagrange basis sums to one
Exercise C1: Interpolation over a finite field
Exercise C2: Newton’s form of the interpolant

6.7 Polynomials of an Operator

Theorem 6.7.1 Evaluation at an Operator
Example Two Ways to Evaluate
Definition 6.7.1 Annihilating Polynomial
Theorem 6.7.2 Every Operator Satisfies a Polynomial
Example Finding an Annihilating Polynomial
Theorem 6.7.3 The Annihilating Polynomials Form an Ideal
Theorem 6.7.4 $T$ Preserves Kernels and Images of Polynomials in $T$
Theorem 6.7.5 Kernel Splitting Lemma
Example Recovering Projections and Direct Sums
Example Recovering the Involution Decomposition
Example A Splitting with a Repeated Factor
Exercise A1
Exercise B1: A polynomial of a $2 \times 2$ matrix
Exercise B2: An annihilating polynomial by elimination
Exercise B3: Operators with $T^3 = T$
Exercise C1: Inverses are polynomials
Exercise C2: Splitting with $k$ coprime factors
Exercise C3: The same rotation over $\mathbb{R}$ and over $\mathbb{C}$

Determinants

7.1 Signed Area and Volume

Example $ad - bc$ from the Rules
Exercise A1
Exercise B1: Signed Areas from the Rules
Exercise B2: Equal Sides Force the Swap Rule
Exercise C1: Area of a Triangle
Exercise C2: The $1 \times 1$ Case

7.2 Multilinear Alternating Forms

Definition 7.2.1 Multilinear Form
Definition 7.2.2 Alternating Form
Definition 7.2.3 Skew-Symmetric Form
Example Alternating Forms
Theorem 7.2.1 Properties of Alternating Forms
Theorem 7.2.2 Skew-Symmetric and Alternating Forms
Theorem 7.2.3 Alternating Forms Form a Vector Space
Exercise A1
Exercise B1: Multilinear or Alternating?
Exercise B2: Alternating Bilinear Forms on $F^2$
Exercise B3: The Triple Product
Exercise C1: Too Many Arguments
Exercise C2: Bilinear Forms over $\mathbb{F}_2$

7.3 Permutations and Sign

Definition 7.3.1 Inversion
Definition 7.3.2 Sign of a Permutation
Theorem 7.3.1 The Sign Is Multiplicative
Corollary 7.3.2 Sign of a Transposition
Corollary 7.3.3 Parity Is Well Defined
Proposition 7.3.4 Sign of a Cycle
Definition 7.3.3 Alternating Group
Example A Sign Computed Two Ways
Exercise A1
Exercise B1: Computing Signs
Exercise B2: Sign of the Inverse
Exercise B3: The Reversal Permutation
Exercise C1: Half the Permutations Are Even
Exercise C2: Sign from the Number of Cycles

7.4 Existence and Uniqueness of the Determinant

Lemma 7.4.1 Permuting the arguments of an alternating form
Theorem 7.4.2 Uniqueness of Alternating Forms
Theorem 7.4.3 Existence: the Leibniz Formula
Definition 7.4.1 Determinant
Corollary 7.4.4 Alternating $n$ -Forms on $F^n$ Form a Line
Theorem 7.4.5 Determinant of the Transpose
Theorem 7.4.6 Determinant of a Triangular Matrix
Exercise A1
Exercise B1: Six-term determinants
Exercise B2: The determinant of $\mathbf{P}_\sigma$
Exercise B3: A zero row
Exercise C1: Too many zeros
Exercise C2: Counting the cost
Exercise C3: The permanent, and a change of field

7.5 Row Operations and Multiplicativity

Theorem 7.5.1 Row Operations and the Determinant
Example A $4 \times 4$ Determinant by Elimination
Theorem 7.5.2 Invertible if and only if Non-Zero Determinant
Theorem 7.5.3 Invertible Matrix Theorem, with Determinants
Theorem 7.5.4 Multiplicativity of the Determinant
Theorem 7.5.5 Properties of Determinants
Corollary 7.5.6 Determinant of the Inverse
Corollary 7.5.7 Determinant Is a Similarity Invariant
Definition 7.5.1 Determinant of an operator
Theorem 7.5.8 Properties of the Determinant of an Operator
Theorem 7.5.9 The Determinant Is a Group Homomorphism
Exercise A1
Exercise B1: Determinants by elimination
Exercise B2: A parameter
Exercise B3: The shift operator
Exercise C1: Orthogonal-type matrices
Exercise C2: Left multiplication on matrices
Exercise C3: Non-square factors

7.6 Cofactor Expansion, the Adjugate and Cramer's Rule

Definition 7.6.1 Minor and cofactor
Theorem 7.6.1 Laplace Expansion
Example A $4 \times 4$ Expansion
Definition 7.6.2 Adjugate
Theorem 7.6.2 The Adjugate Identity
Corollary 7.6.3 Inverse via the Adjugate
Theorem 7.6.4 Cramer’s Rule
Corollary 7.6.5 Integer Matrices with Integer Inverses
Exercise A1
Exercise B1: Adjugate and inverse
Exercise B2: Cramer’s rule
Exercise B3: Choosing the best line
Exercise C1: The determinant of the adjugate
Exercise C2: The rank of the adjugate
Exercise C3: An adjugate over $F[x]$

7.7 Minors, Rank and Cauchy–Binet

Definition 7.7.1 Submatrix and Minor
Theorem 7.7.1 Rank via Minors
Example Rank of a Family of Matrices
Theorem 7.7.2 Cauchy–Binet Formula
Example Cauchy–Binet for a $2 \times 3$ times $3 \times 2$ Product
Corollary 7.7.3 Gram Determinants Are Non-negative
Exercise A1
Exercise B1: Rank with a parameter
Exercise B2: Checking Cauchy–Binet
Exercise B3: The Lagrange identity
Exercise C1: Counting spanning trees
Exercise C2: Rank does not depend on the field

7.8 Special Determinants

Theorem 7.8.1 Vandermonde Determinant
Example A $3 \times 3$ Vandermonde Determinant
Corollary 7.8.2 Distinct Nodes Give an Invertible Vandermonde Matrix
Theorem 7.8.3 Tridiagonal Recurrence
Example Fibonacci Numbers as Determinants
Theorem 7.8.4 Block Triangular Determinant
Theorem 7.8.5 Matrix Determinant Lemma
Example $a$ on the Diagonal, $1$ Elsewhere
Exercise A1
Exercise B1: A $4 \times 4$ Vandermonde determinant
Exercise B2: The second-difference matrix
Exercise B3: A rank-one update
Exercise C1: The Cauchy determinant
Exercise C2: A circulant determinant over $\mathbb{C}$
Exercise C3: Rank-one updates of an invertible matrix

7.9 Orientation and Volume

Definition 7.9.1 Volume of a Parallelepiped
Theorem 7.9.1 Volume Is Determined by Its Rules
Theorem 7.9.2 Linear Maps Scale Volume by $\lvert \det \rvert$
Example Area of an Image
Definition 7.9.2 Orientation
Theorem 7.9.3 There Are Exactly Two Orientations
Proposition 7.9.4 Determinant Sign and Orientation
Exercise A1
Exercise B1: Volume of a parallelepiped
Exercise B2: Comparing orientations
Exercise B3: Areas of images
Exercise C1: Area of a triangle in space
Exercise C2: Rotations and reflections

7.10 The Characteristic Polynomial

Definition 7.10.1 Characteristic Polynomial
Example A $3 \times 3$ Characteristic Polynomial
Lemma 7.10.1 Evaluating the Characteristic Polynomial
Theorem 7.10.2 Coefficients of the Characteristic Polynomial
Theorem 7.10.3 Similar Matrices Have the Same Characteristic Polynomial
Definition 7.10.2 Characteristic Polynomial of an Operator
Example Characteristic Polynomials of Two Operators
Theorem 7.10.4 Roots of the Characteristic Polynomial
Exercise A1
Exercise B1: Computing characteristic polynomials
Exercise B2: Transpose
Exercise B3: $\mathbf{A}\mathbf{B}$ and $\mathbf{B}\mathbf{A}$
Exercise C1: Companion matrices
Exercise C2: Nilpotent $2 \times 2$ matrices
Exercise C3: Odd size over the reals

Block Matrices

8.1 Partitions and Block Multiplication

Definition 8.1.1 Block Partition
Theorem 8.1.1 Block Multiplication
Proposition 8.1.2 Transpose of a Block Matrix
Corollary 8.1.3 Outer Product Expansion
Definition 8.1.2 Block Diagonal Matrix
Theorem 8.1.4 Arithmetic of Block Diagonal Matrices
Theorem 8.1.5 Block Triangular Products and Inverses
Theorem 8.1.6 Direct Sums Give Block Diagonal Matrices
Theorem 8.1.7 Subspaces Mapped into Themselves Give Block Triangular Matrices
Example A Plane Mapped into Itself
Exercise A1
Exercise B1: Multiplying block matrices
Exercise B2: Inverting a block triangular matrix
Exercise B3: A projection in an adapted basis
Exercise C1: Square-zero matrices of half rank
Exercise C2: Powers of block triangular matrices

8.2 Rank and Block Matrices

Theorem 8.2.1 Rank Inequalities for Block Matrices
Theorem 8.2.2 Block Elimination Preserves Rank
Theorem 8.2.3 Frobenius’s Rank Inequality
Example Rank of $\mathbf{I} - \mathbf{A} \mathbf{B}$ versus $\mathbf{I} - \mathbf{B} \mathbf{A}$
Exercise A1
Exercise B1: Ranks of block matrices
Exercise B2: Shifted products
Exercise B3: Idempotents by blocks
Exercise C1: The rank of $\mathbf{A} - \mathbf{A} \mathbf{B} \mathbf{A}$
Exercise C2: Involutions and the field

8.3 Schur Complements

Definition 8.3.1 Schur Complement
Theorem 8.3.1 Block LDU Factorization
Theorem 8.3.2 Schur Determinant Formula
Theorem 8.3.3 Schur Rank Formula
Theorem 8.3.4 Block Inverse Formula
Example A $4 \times 4$ Inverse through a $2 \times 2$ Schur Complement
Theorem 8.3.5 Sherman–Morrison–Woodbury Formula
Corollary 8.3.6 Sherman–Morrison Formula
Lemma 8.3.7 Evaluating a Matrix of Polynomials
Theorem 8.3.8 Determinant with Commuting Blocks
Exercise A1
Exercise B1: A Schur complement, a determinant and a rank
Exercise B2: A rank-one update
Exercise B3: Identity corners
Exercise C1: Sylvester’s determinant identity
Exercise C2: Pivots as Schur complements
Exercise C3: When $\mathbf{A}$ and $\mathbf{C}$ commute

8.4 The Kronecker Product

Definition 8.4.1 Kronecker product
Theorem 8.4.1 Properties of the Kronecker Product
Proposition 8.4.2 Swapping the Factors Is a Permutation Similarity
Theorem 8.4.3 Rank, Trace and Determinant of a Kronecker Product
Definition 8.4.2 Vectorization
Theorem 8.4.4 The vec Identity
Example A Sylvester Equation as a Linear System
Exercise A1
Exercise B1: Computing with Kronecker products
Exercise B2: One-sided equations
Exercise B3: Which identities hold?
Exercise C1: When is a Kronecker product invertible?
Exercise C2: Kronecker sums

8.5 Commutators and Trace-Zero Matrices

Definition 8.5.1 Commutator
Proposition 8.5.1 Rules for Commutators
Example The Identity as a Commutator in Characteristic $p$
Lemma 8.5.2 A Non-Scalar Matrix Has a Similar Matrix with Zero Corner
Lemma 8.5.3 Trace Zero Means Similar to Zero Diagonal
Theorem 8.5.4 Shoda’s Theorem
Example Writing a Trace-Zero $3 \times 3$ Matrix as a Commutator
Theorem 8.5.5 Commutators Span the Trace-Zero Matrices
Exercise A1
Exercise B1: A $2 \times 2$ commutator
Exercise B2: A commutator over $\mathbb{F}_2$
Exercise B3: Commuting with a diagonal matrix
Exercise C1: Trace-like functionals, again
Exercise C2: When $\mathbf{A}$ commutes with $[\mathbf{A}, \mathbf{B}]$

Eigenvalues and Diagonalization

9.1 Invariant Subspaces

Definition 9.1.1 Invariant Subspace
Lemma 9.1.1 Invariance Can Be Checked on a Spanning List
Proposition 9.1.2 Invariant Lines
Example A Rotation Has No Invariant Lines
Definition 9.1.2 Restriction and Induced Operator
Theorem 9.1.3 Invariant Subspaces and Block Triangular Matrices
Proposition 9.1.4 Sums and Intersections of Invariant Subspaces
Theorem 9.1.5 Invariant Direct Sums and Block Diagonal Matrices
Exercise A1
Exercise B1: All invariant subspaces of a diagonal matrix
Exercise B2: Kernels of $T - c\,\operatorname{id}$
Exercise B3: Invariance under differentiation
Exercise C1: A chain of invariant subspaces
Exercise C2: Invariance under the inverse

9.2 Eigenvalues and Eigenvectors

Definition 9.2.1 Eigenvalue and Eigenvector
Definition 9.2.2 Eigenspace
Theorem 9.2.1 Characterizations of Eigenvalues
Example Eigenvalues and Eigenspaces of a $2 \times 2$ Matrix
Definition 9.2.3 Spectrum
Theorem 9.2.2 Distinct Eigenvalues Give Independent Eigenvectors
Corollary 9.2.3 Eigenspaces Form a Direct Sum
Theorem 9.2.4 Complex Operators Have Eigenvalues
Theorem 9.2.5 Complex Eigenvalues of Real Matrices Come in Conjugate Pairs
Example A Real Matrix with Non-Real Eigenvalues
Theorem 9.2.6 Invertible Matrix Theorem, with Eigenvalues
Exercise A1
Exercise B1: Computing eigenvalues and eigenspaces
Exercise B2: The transpose map
Exercise B3: Eigenvalues of powers and inverses
Exercise C1: Every vector an eigenvector
Exercise C2: Nilpotent operators
Exercise C3: Real matrices of odd size

9.3 Algebraic and Geometric Multiplicity

Definition 9.3.1 Algebraic Multiplicity
Definition 9.3.2 Geometric Multiplicity
Theorem 9.3.1 Geometric Multiplicity Is at Most Algebraic Multiplicity
Proposition 9.3.2 Similar Matrices Have the Same Multiplicities
Theorem 9.3.3 Trace and Determinant from Eigenvalues
Exercise A1
Exercise B1: Computing multiplicities
Exercise B2: A parameter that merges eigenvalues
Exercise B3: Eigenvalues from trace and determinant
Exercise C1: Nilpotent matrices
Exercise C2: Multiplicities do not determine similarity

9.4 Diagonalization

Definition 9.4.1 Diagonalizable
Theorem 9.4.1 Diagonalization Theorem
Corollary 9.4.2 Distinct Eigenvalues Imply Diagonalizable
Example Diagonalizing a $3 \times 3$ Matrix with a Repeated Eigenvalue
Theorem 9.4.3 Powers and Polynomials of a Diagonalizable Matrix
Example A Closed Formula for the Fibonacci Numbers
Example Diagonalizability with a Parameter
Exercise A1
Exercise B1: Diagonalize or show impossible
Exercise B2: A tenth power
Exercise B3: A matrix with a parameter
Exercise C1: Matrices with $\mathbf{A}^k = \mathbf{I}$
Exercise C2: Polynomials of diagonalizable matrices
Exercise C3: The transpose map on $M_n(F)$

9.5 The Minimal Polynomial

Definition 9.5.1 Minimal Polynomial
Theorem 9.5.1 Annihilating Polynomials Are Multiples of the Minimal Polynomial
Lemma 9.5.2 Monic Divisors of a Factored Polynomial
Theorem 9.5.3 Roots of the Minimal Polynomial
Proposition 9.5.4 The First Dependence Among the Powers
Example The Minimal Polynomial from the First Dependence
Example The Minimal Polynomial from the Eigenvalues
Theorem 9.5.5 Similar Matrices Have the Same Minimal Polynomial
Proposition 9.5.6 Minimal Polynomial of a Block Diagonal Matrix
Exercise A1
Exercise B1: Computing minimal polynomials
Exercise B2: Operators with $T^2 = T$
Exercise B3: Companion matrices
Exercise C1: Cyclic vectors
Exercise C2: Minimal polynomials of the pieces

9.6 The Cayley–Hamilton Theorem

Theorem 9.6.1 Cayley–Hamilton Theorem
Corollary 9.6.2 The Minimal Polynomial Divides the Characteristic Polynomial
Corollary 9.6.3 The Inverse Is a Polynomial in the Matrix
Example Cayley–Hamilton for a $3 \times 3$ Matrix
Exercise A1
Exercise B1: Inverse and a hundredth power
Exercise B2: Trace zero in size two
Exercise B3: Minimal polynomial from one product
Exercise C1: Cayley–Hamilton over a commutative ring
Exercise C2: The adjugate is a polynomial in the matrix
Exercise C3: Nilpotent matrices of size $n$

9.7 Triangularization

Theorem 9.7.1 Triangular Matrices and Chains of Invariant Subspaces
Definition 9.7.1 Triangularizable
Theorem 9.7.2 Triangularization Theorem
Corollary 9.7.3 Complex Operators Are Triangularizable
Theorem 9.7.4 The Diagonal of a Triangular Form
Example Triangularizing a Matrix with a Single Eigenvector Line
Exercise A1
Exercise B1: Triangularizing matrices
Exercise B2: Nilpotent matrices are strictly triangular
Exercise B3: Eigenvalues of powers from a triangular form
Exercise C1: A second proof of Cayley–Hamilton
Exercise C2: Real operators have small invariant subspaces
Exercise C3: Traces of powers detect nilpotency

9.8 Primary Decomposition

Theorem 9.8.1 Primary Decomposition Theorem
Example A Primary Decomposition with an Irreducible Quadratic
Theorem 9.8.2 Diagonalizability via the Minimal Polynomial
Example Complex Matrices of Finite Order Are Diagonalizable
Corollary 9.8.3 Restrictions of Diagonalizable Operators
Corollary 9.8.4 Dimensions of the Primary Components
Exercise A1
Exercise B1: Diagonalizable or not?
Exercise B2: Decomposing $\mathbb{R}^3$
Exercise B3: Matrices with $\mathbf{A}^3 = \mathbf{A}$
Exercise C1: $\mathbf{A}^p = \mathbf{A}$ over $\mathbb{F}_p$
Exercise C2: Irreducible minimal polynomials

9.9 Commuting Operators

Theorem 9.9.1 Commuting Operators Preserve Eigenspaces
Lemma 9.9.2 Restrictions and Quotients Inherit Splitting
Theorem 9.9.3 Commuting Operators Have a Common Eigenvector
Theorem 9.9.4 Simultaneous Triangularization
Definition 9.9.1 Simultaneously Diagonalizable
Theorem 9.9.5 Simultaneous Diagonalization
Example Diagonalizing Two Commuting Matrices Together
Theorem 9.9.6 Simultaneous Diagonalization of a Commuting Family
Exercise A1
Exercise B1: Common eigenvectors
Exercise B2: Decide simultaneous diagonalizability
Exercise B3: Matrices commuting with a diagonal matrix
Exercise C1: The commutant of a matrix with distinct eigenvalues
Exercise C2: Commuting nilpotent matrices

9.10 Spectral Mapping, Products in Both Orders, Left Eigenvectors

Theorem 9.10.1 Spectral Mapping Theorem
Corollary 9.10.2 Trace and Determinant of a Polynomial in $T$
Example A Polynomial in a Non-Diagonalizable Matrix
Theorem 9.10.3 Nilpotent Matrices via Eigenvalues and Traces
Theorem 9.10.4 $\mathbf{A} \mathbf{B}$ and $\mathbf{B} \mathbf{A}$ Have the Same Non-zero Eigenvalues
Definition 9.10.1 Left Eigenvector
Proposition 9.10.5 Left Eigenvectors Are Eigenvectors of the Transpose
Theorem 9.10.6 Left and Right Eigenvectors Are Biorthogonal
Proposition 9.10.7 Expansion in Left and Right Eigenvectors
Exercise A1
Exercise B1: Eigenvalues of a polynomial in $\mathbf{A}$
Exercise B2: $\mathbf{A} \mathbf{B}$ and $\mathbf{B} \mathbf{A}$ for a $2 \times 3$ example
Exercise B3: Left eigenvectors of a $2 \times 2$ matrix
Exercise C1: Traces of powers of $\mathbf{A} \mathbf{B}$ and $\mathbf{B} \mathbf{A}$
Exercise C2: Adding a commuting nilpotent matrix
Exercise C3: How many traces, and which field?

9.11 Powers, Recurrences and Markov Chains

Theorem 9.11.1 Solving a Diagonalizable Recurrence
Theorem 9.11.2 Scalar Recurrences with Distinct Roots
Example A Third-Order Recurrence
Example A Repeated Root
Definition 9.11.1 Stochastic Matrix, Probability Vector
Proposition 9.11.3 Basic Properties of Stochastic Matrices
Definition 9.11.2 Markov Chain, Steady State
Example A Two-State Chain
Theorem 9.11.4 Long-Run Behavior of a Diagonalizable Markov Chain
Example Bicycles at Three Stations
Example Three Age Classes
Exercise A1
Exercise B1: Two recurrences
Exercise B2: A three-state chain
Exercise B3: The limit of a matrix power
Exercise C1: Eigenvalues of a stochastic matrix
Exercise C2: Two-state chains

Canonical Forms

10.1 Generalized Eigenspaces

Definition 10.1.1 Generalized Eigenvector
Definition 10.1.2 Generalized Eigenspace
Theorem 10.1.1 The Kernel Chain Stabilizes
Corollary 10.1.2 The Generalized Eigenspace Is One Kernel
Theorem 10.1.3 Generalized Eigenspace Decomposition
Example Generalized Eigenspaces of a $4 \times 4$ Matrix
Exercise A1
Exercise B1: Computing generalized eigenspaces
Exercise B2: The image chain stabilizes too
Exercise B3: Reading the dimensions off a triangular matrix
Exercise C1: The Fitting decomposition
Exercise C2: Commuting operators preserve generalized eigenspaces

10.2 Nilpotent Operators

Definition 10.2.1 Nilpotent Operator, Index of Nilpotency
Proposition 10.2.1 Basic Properties of Nilpotent Operators
Definition 10.2.2 Jordan Chain
Lemma 10.2.2 A Jordan Chain Is Independent
Theorem 10.2.3 Structure Theorem for Nilpotent Operators
Theorem 10.2.4 Block Sizes from Ranks of Powers
Corollary 10.2.5 Similarity of Nilpotent Matrices
Definition 10.2.3 Partition of an Integer, Young Diagram, Dual Partition
Example A Jordan Basis for a $4 \times 4$ Nilpotent Matrix
Exercise A1
Exercise B1: Block sizes from rank data
Exercise B2: The five classes in dimension four
Exercise B3: A Jordan basis by hand
Exercise C1: A nilpotent matrix is similar to its transpose
Exercise C2: One long chain

10.3 The Jordan Canonical Form

Definition 10.3.1 Jordan Block
Definition 10.3.2 Jordan Matrix, Jordan Basis, Jordan Form
Theorem 10.3.1 Jordan Canonical Form Theorem
Corollary 10.3.2 Invariants from the Jordan Form
Corollary 10.3.3 Similarity via the Jordan Form
Example The Jordan Form of a $5 \times 5$ Matrix
Exercise A1
Exercise B1: Jordan forms from polynomial data
Exercise B2: Jordan forms and Jordan bases
Exercise B3: Similar or not?
Exercise C1: A matrix is similar to its transpose
Exercise C2: How much do $p$ and $m$ decide?

10.4 The Real Jordan Form and the Weyr Form

Definition 10.4.1 Rotation-Scaling Block, Real Jordan Block
Lemma 10.4.1 Realifying a Conjugate Pair of Chains
Corollary 10.4.2 A Real Jordan Block Splits into Two Complex Ones
Lemma 10.4.3 Real and Complex Null Spaces of a Real Matrix
Theorem 10.4.4 Real Jordan Form
Example The Real Jordan Form of a $4 \times 4$ Matrix
Definition 10.4.2 Basic Weyr Matrix, Weyr Structure, Weyr Form
Theorem 10.4.5 Weyr Form
Proposition 10.4.6 The Commutant of a Basic Weyr Matrix Is Block Triangular
Exercise A1
Exercise B1: Real forms of two by two matrices
Exercise B2: Weyr forms of Jordan matrices
Exercise B3: Real forms of three by three matrices from the characteristic polynomial
Exercise C1: The real form of a companion matrix
Exercise C2: Commuting with a Weyr matrix, and with a Jordan matrix

10.5 Cyclic Subspaces and Companion Matrices

Definition 10.5.1 Cyclic Subspace
Proposition 10.5.1 The Cyclic Subspace Is the Smallest Invariant Subspace Containing the Vector
Definition 10.5.2 The $T$ -Annihilator of a Vector
Theorem 10.5.2 Basis and Matrix of a Cyclic Subspace
Definition 10.5.3 Companion Matrix
Theorem 10.5.3 The Companion Matrix Realizes Its Polynomial Twice
Definition 10.5.4 Cyclic Vector, Cyclic Operator
Lemma 10.5.4 Annihilator of a Sum with Coprime Annihilators
Proposition 10.5.5 Some Vector Has the Minimal Polynomial as Its Annihilator
Theorem 10.5.6 Cyclic Operators
Example A Cyclic Subspace and a Cyclic Vector
Exercise A1
Exercise B1: Annihilators of vectors
Exercise B2: Cyclic or not?
Exercise B3: Cyclic subspaces for differentiation
Exercise C1: What commutes with a cyclic operator
Exercise C2: How many cyclic vectors?

10.6 The Rational Canonical Form

Theorem 10.6.1 Cyclic Decomposition for a Single Prime Power
Theorem 10.6.2 Cyclic Decomposition Theorem
Proposition 10.6.3 Counting the Exponents
Corollary 10.6.4 Uniqueness of the Chain and of the Prime Powers
Definition 10.6.1 Invariant Factors, Elementary Divisors
Theorem 10.6.5 Rational Canonical Form
Corollary 10.6.6 Similarity via the Invariant Factors
Theorem 10.6.7 Elementary Divisor Form
Corollary 10.6.8 Companion Blocks of Linear Powers Are Jordan Blocks
Lemma 10.6.9 Rank Does Not Change with the Field
Corollary 10.6.10 Similarity Is Independent of the Field
Example Invariant Factors from Polynomial Data
Example The Rational Canonical Form of a Matrix over the Rationals
Exercise A1
Exercise B1: Invariant factors from given data
Exercise B2: Rational forms of matrices
Exercise B3: Counting similarity classes over a finite field
Exercise C1: Which matrices are companion matrices
Exercise C2: All similarity classes of two by two matrices over the smallest field
Exercise C3: A matrix over the rationals is similar to its transpose

10.7 Polynomial Matrices and the Smith Normal Form

Definition 10.7.1 Elementary Operations over $F\lbrack x\rbrack$
Proposition 10.7.1 Invertible Polynomial Matrices
Definition 10.7.2 Equivalence over $F\lbrack x\rbrack$
Proposition 10.7.2 Operations and Equivalence
Theorem 10.7.3 Smith Normal Form
Example A Smith Normal Form Computed by Hand
Lemma 10.7.4 Division of a Polynomial Matrix by $x\mathbf{I} - \mathbf{A}$
Theorem 10.7.5 Similarity as Equivalence of $x\mathbf{I} - \mathbf{A}$ and $x\mathbf{I} - \mathbf{B}$
Corollary 10.7.6 The Smith Form of $x\mathbf{I} - \mathbf{A}$ Carries the Invariant Factors
Corollary 10.7.7 A Matrix Is Similar to Its Transpose
Exercise A1
Exercise B1: Smith normal forms
Exercise B2: Invariant factors from determinantal divisors
Exercise B3: Deciding similarity
Exercise C1: The same algorithm over the integers
Exercise C2: Uniqueness by hand in the smallest case

10.8 Semisimple Operators and the Jordan–Chevalley Decomposition

Definition 10.8.1 Semisimple Operator
Lemma 10.8.1 The Minimal Polynomial Does Not Notice a Larger Field
Proposition 10.8.2 Semisimple Means Diagonalizable After Enlarging the Field
Theorem 10.8.3 Jordan–Chevalley Decomposition
Example The Semisimple and Nilpotent Parts of a $3 \times 3$ Matrix
Exercise A1
Exercise B1: Semisimple and nilpotent parts
Exercise B2: When is the nilpotent part zero?
Exercise B3: Block diagonal matrices
Exercise C1: The multiplicative version
Exercise C2: The parts inherit every symmetry

10.9 Functions of Matrices, the Exponential and Linear Differential Equations

Lemma 10.9.1 A Polynomial of a Jordan Block
Definition 10.9.1 Function of a Matrix
Theorem 10.9.2 Functions of a Matrix Are Polynomials in It
Example Square Roots of Two Matrices
Definition 10.9.2 Matrix Exponential
Theorem 10.9.3 The Exponential Series Converges to the Jordan Definition
Theorem 10.9.4 Properties of the Matrix Exponential
Corollary 10.9.5 Exponential of a Jordan Block, with a Parameter
Theorem 10.9.6 Solution of a Linear System
Example Two Two-Dimensional Systems
Example A Second-Order Equation with a Repeated Root
Exercise A1
Exercise B1: Computing exponentials
Exercise B2: Solving systems
Exercise B3: A square root and a logarithm
Exercise C1: How badly the exponential law fails
Exercise C2: When does every solution die out?

10.10 Convergent and Power-Bounded Matrices

Definition 10.10.1 Entrywise Convergence and Boundedness
Lemma 10.10.1 Convergence and Boundedness Survive a Similarity
Theorem 10.10.4 Convergent Matrices
Theorem 10.10.2 Powers Tending to Zero
Theorem 10.10.3 Power-Bounded Matrices
Example Deciding and Computing Limits of Powers
Corollary 10.10.5 Convergence of a Markov Chain
Example A Two-State Chain
Theorem 10.10.6 Neumann Series
Example Inverting by Summing a Series
Exercise A1
Exercise B1: Decide the behavior
Exercise B2: Computing limits
Exercise B3: A Neumann series
Exercise C1: Bounded but not convergent
Exercise C2: Chapter 9’s Markov theorem without diagonalizability

Inner Product Spaces

11.1 Inner Products and Norms

Definition 11.1.1 Inner Product
Theorem 11.1.1 First Properties of an Inner Product
Definition 11.1.2 Conjugate Transpose
Definition 11.1.3 Induced Norm
Theorem 11.1.2 Properties of the Induced Norm
Definition 11.1.4 Orthogonal Vectors
Theorem 11.1.3 Pythagorean Theorem
Theorem 11.1.4 Orthogonal Non-zero Vectors Are Independent
Theorem 11.1.5 Cauchy–Schwarz Inequality
Corollary 11.1.6 Triangle Inequality
Definition 11.1.5 Angle Between Vectors
Example Three Angles
Exercise A1
Exercise B1: Determine which are inner products
Exercise B2: Norms and angles
Exercise B3: Cauchy–Schwarz, concretely
Exercise B4: A lower bound for a difference of norms
Exercise C1: The parallelogram law characterizes inner-product norms
Exercise C2: Recovering the inner product from the norm
Exercise C3: The equality cases

11.2 Orthonormal Bases and Gram–Schmidt

Definition 11.2.1 Orthonormal List
Definition 11.2.2 Orthonormal Basis
Theorem 11.2.1 Coordinates, Inner Products and Norms in an Orthonormal Basis
Example Reading Off Coordinates
Theorem 11.2.2 Gram–Schmidt Process
Corollary 11.2.3 Extending an Orthonormal List
Example Gram–Schmidt in $\mathbb{R}^3$
Example Gram–Schmidt on $1, x, x^2$
Corollary 11.2.4 Classification of Finite-Dimensional Inner Product Spaces
Definition 11.2.3 Gram Matrix
Theorem 11.2.5 Properties of the Gram Matrix
Example Deciding Independence with a Gram Matrix
Exercise A1
Exercise B1: Gram–Schmidt with numbers
Exercise B2: Gram–Schmidt on polynomials
Exercise B3: Coordinates without solving a system
Exercise B4: Gram matrices
Exercise C1: The Gram matrix determines the list
Exercise C2: Gram–Schmidt on a dependent list

11.3 Orthogonal Complements and Projections

Definition 11.3.1 Orthogonal complement
Proposition 11.3.1 Perp is always a subspace
Theorem 11.3.2 Orthogonal Decomposition Theorem
Definition 11.3.2 Orthogonal projection
Theorem 11.3.3 Projection formula
Corollary 11.3.4 Projecting with an orthogonal basis
Theorem 11.3.5 Best Approximation Theorem
Definition 11.3.3 Distance to a subspace
Example Distance from a point to a plane
Example The best quadratic approximation to a cubic
Exercise A1
Exercise B1: A complement and a projection in $\mathbb{R}^4$
Exercise B2: Distance from a point to a plane
Exercise B3: The best quadratic approximation to a quartic
Exercise C1: Perp turns sums into intersections
Exercise C2: A subspace with no orthogonal complement
Exercise C3: Which projections are orthogonal

11.4 Least Squares and Minimum-Norm Solutions

Lemma 11.4.1 Moving a matrix across the inner product
Theorem 11.4.2 Least Squares Theorem
Lemma 11.4.3 The null space of $\mathbf{A}^{*}\mathbf{A}$
Corollary 11.4.4 Uniqueness of the least-squares solution
Example The least-squares line through four points
Example The least-squares parabola
Theorem 11.4.5 Minimum-Norm Solution
Example A minimum-norm solution
Exercise A1
Exercise B1: A least-squares line
Exercise B2: A least-squares parabola
Exercise B3: A minimum-norm solution
Exercise C1: Weighted least squares
Exercise C2: The residual, two ways
Exercise C3: A rank-deficient least-squares problem

11.5 The Riesz Representation Theorem

Theorem 11.5.1 Riesz Representation Theorem
Example Two Riesz vectors
Corollary 11.5.2 The Riesz map
Theorem 11.5.3 Perp corresponds to the annihilator
Example A functional with no Riesz vector
Exercise A1
Exercise B1: Riesz vectors for evaluation
Exercise B2: Riesz vectors on matrices
Exercise B3: The correspondence in $\mathbb{R}^4$
Exercise C1: Riesz without an orthonormal basis
Exercise C2: Evaluation at $0$ is not represented

11.6 The Adjoint

Theorem 11.6.1 Existence and Uniqueness of the Adjoint
Definition 11.6.1 Adjoint
Example Four Adjoints
Example Differentiation on a Polynomial Space
Example A Map With No Adjoint
Theorem 11.6.2 Properties of the Adjoint
Theorem 11.6.3 The Matrix of the Adjoint Is the Conjugate Transpose
Example The Transpose Rule Breaks
Theorem 11.6.4 The Adjoint Is the Dual Map Read Through Riesz
Theorem 11.6.5 The Four Fundamental Subspaces
Example All Four Subspaces of a 3 × 3 Matrix
Corollary 11.6.6 Rank of the Adjoint
Definition 11.6.2 Self-adjoint Operator
Definition 11.6.3 Normal Operator
Proposition 11.6.7 First Properties of Self-adjoint Operators
Exercise A1
Exercise B1: Adjoints of matrix maps
Exercise B2: Adjoints on a polynomial space
Exercise B3: Locating the kernel of the adjoint
Exercise C1: The adjoint of integration
Exercise C2: Skew-adjoint operators
Exercise C3: The adjoint in an arbitrary basis

11.7 Isometries and Unitary Maps

Definition 11.7.1 Isometry
Proposition 11.7.1 Eigenvalues of an Isometry Have Modulus 1
Example Isometries and Near-Isometries
Lemma 11.7.2 Polarization Identities
Theorem 11.7.3 Characterizations of Isometries
Definition 11.7.2 Unitary and Orthogonal
Definition 11.7.3 The Unitary and Orthogonal Groups
Proposition 11.7.4 The Groups and Their Determinants
Lemma 11.7.5 Unitary Invariance of the Frobenius Norm
Theorem 11.7.6 Classification of the Plane Isometries
Example Naming Two Plane Isometries
Theorem 11.7.7 Every Element of SO(3) Is a Rotation
Example Axis and Angle of a Rotation
Theorem 11.7.8 Distance-Preserving Maps Are Affine
Exercise A1
Exercise B1: Determine which are unitary
Exercise B2: Name the plane isometry
Exercise B3: Permutations are orthogonal
Exercise C1: Determinant as a homomorphism
Exercise C2: Linearity is a hypothesis, not a consequence
Exercise C3: Two reflections make a rotation

11.8 QR, Householder and Hessenberg

Theorem 11.8.1 QR Factorization
Example A $3 \times 2$ QR, and a least-squares problem
Definition 11.8.1 Householder Reflection
Proposition 11.8.2 Properties of a Householder Reflection
Theorem 11.8.3 A Reflection Flattening a Vector
Theorem 11.8.4 QR by Householder Reflections
Example A $3 \times 3$ QR by reflections
Definition 11.8.2 Givens Rotation
Theorem 11.8.5 Reduction to Hessenberg Form
Example Hessenberg form of a $3 \times 3$ matrix
Exercise A1
Exercise B1: QR by Gram–Schmidt
Exercise B2: The same matrix by reflections
Exercise B3: A least-squares fit through QR
Exercise B4: Determine which are QR factorizations
Exercise C1: All the QR factorizations of a matrix
Exercise C2: Reflections do not mind dependence
Exercise C3: Triangularizing with rotations

11.9 Bessel, Parseval and Fourier Series

Definition 11.9.1 Fourier Coefficients With Respect to an Orthonormal List
Theorem 11.9.1 Bessel’s Inequality
Theorem 11.9.2 Parseval’s Identity
Example The Trigonometric System Is Orthonormal
Theorem 11.9.3 Fourier Partial Sums Are Best Approximations
Example The Fourier Coefficients of $f(x) = x$
Exercise A1
Exercise B1: Fourier coefficients
Exercise B2: Verifying Bessel for a truncation
Exercise B3: The best approximation by $\operatorname{span}(1, \cos x)$
Exercise C1: Parseval for the full trigonometric system
Exercise C2: Chebyshev orthogonality by substitution

11.10 Orthogonal Polynomials

Proposition 11.10.1 Multiplication by x is symmetric
Definition 11.10.1 Orthogonal Polynomial Sequence
Proposition 11.10.2 Existence and uniqueness of the monic sequence
Theorem 11.10.3 Three-Term Recurrence
Example The monic Legendre polynomials, continued
Lemma 11.10.4 Even multiplicities mean no sign change
Theorem 11.10.5 Roots of an Orthogonal Polynomial
Theorem 11.10.6 Gaussian Quadrature
Example Two-point Gauss–Legendre
Exercise A1
Exercise B1: A weighted interval
Exercise B2: Two rows of the table
Exercise B3: One more Legendre polynomial
Exercise B4: A two-point rule on the unit interval
Exercise C1: Interlacing roots
Exercise C2: The ceiling is 2k − 1

Spectral Theory

12.1 Schur Triangularization

Example An Eigenline Whose Complement Is Not Invariant
Lemma 12.1.1 Eigenvectors of the Adjoint Cut Out Invariant Subspaces
Theorem 12.1.2 Schur’s Unitary Triangularization
Corollary 12.1.3 Schur Factorization
Example A Two-by-Two Schur Factorization
Example A Three-by-Three Schur Factorization
Corollary 12.1.4 Trace Is the Sum of the Eigenvalues
Corollary 12.1.5 Determinant Is the Product of the Eigenvalues
Corollary 12.1.6 Diagonalizable Matrices Are Everywhere
Theorem 12.1.7 Real Schur Form
Exercise A1
Exercise B1: A Schur form with complex entries
Exercise B2: A three-by-three Schur form
Exercise B3: The field matters
Exercise C1: Cayley–Hamilton from the triangular factors
Exercise C2: The Frobenius norm is unitarily invariant
Exercise C3: Distinct eigenvalues are dense, but not over the reals

12.2 Self-Adjoint Operators

Example Four Tests
Theorem 12.2.1 Self-adjoint Operators Have Real Eigenvalues
Theorem 12.2.2 Real Self-adjoint Operators Have an Eigenvalue
Theorem 12.2.3 Distinct Eigenvalues Give Orthogonal Eigenvectors
Example A Hermitian Two-by-Two
Theorem 12.2.4 Self-adjointness Passes to Orthogonal Complements
Theorem 12.2.5 The Zero Test for Self-adjoint Operators
Theorem 12.2.6 The Zero Test over the Complex Numbers
Exercise A1
Exercise B1: Determine which are self-adjoint
Exercise B2: Eigenvalues and orthogonality
Exercise B3: A self-adjoint square root of zero
Exercise C1: The operator $S^{*}S$
Exercise C2: Sums and products
Exercise C3: What the real quadratic form does determine

12.3 Normal Operators

Example Which of these are normal?
Theorem 12.3.1 Characterizations of Normality
Corollary 12.3.2 Kernel, Image and an Orthogonal Splitting
Theorem 12.3.3 An Eigenvector of a Normal Operator Is an Eigenvector of Its Adjoint
Corollary 12.3.4 Eigenvectors for Distinct Eigenvalues Are Orthogonal
Theorem 12.3.5 A Normal Operator Has No Hidden Kernel
Proposition 12.3.6 An Invariant Subspace of a Normal Operator Is Reducing
Exercise A1
Exercise B1: Determine which are normal
Exercise B2: The splitting of a singular normal operator
Exercise B3: Triangular and normal, by hand
Exercise C1: A normal operator with no proper invariant subspace
Exercise C2: Arithmetic of normal operators
Exercise C3: Normality depends on the inner product

12.4 The Complex Spectral Theorem

Lemma 12.4.1 A Normal Triangular Matrix Is Diagonal
Theorem 12.4.2 Complex Spectral Theorem
Corollary 12.4.3 Unitary Diagonalization
Example Unitarily diagonalizing a Hermitian matrix
Corollary 12.4.4 The Spectrum Decides
Corollary 12.4.5 The Adjoint of a Normal Operator Is a Polynomial in It
Example Diagonalizable, and no orthonormal eigenbasis
Exercise A1
Exercise B1: Unitarily diagonalize
Exercise B2: A circulant, diagonalized
Exercise B3: Decide unitary diagonalizability
Exercise C1: Operators of finite order
Exercise C2: Same spectrum, same multiplicities
Exercise C3: Normality cannot be dropped

12.5 The Real Spectral Theorem

Theorem 12.5.1 Real Spectral Theorem
Corollary 12.5.2 Orthogonal Diagonalization
Example A normal real operator with no eigenvector
Theorem 12.5.3 Real Normal Form of a Normal Operator
Corollary 12.5.4 Spectral Decomposition of a Symmetric Matrix
Example Orthogonally diagonalizing a 3 by 3 matrix
Theorem 12.5.5 Principal Axis Theorem
Example Finding the axes of a conic
Exercise A1
Exercise B1: Orthogonally diagonalize
Exercise B2: Identify the conic
Exercise B3: A sum of rank-one projections
Exercise C1: One eigenvalue only
Exercise C2: Diagonalizing two matrices at once
Exercise C3: A rotation-scaling in normal form

12.6 The Shape of an Orthogonal Matrix

Theorem 12.6.1 Canonical Form of an Orthogonal Matrix
Corollary 12.6.2 Orthogonal Matrices in Dimension Three
Definition 12.6.1 Cross-product Matrix
Lemma 12.6.3 Properties of the Cross-product Matrix
Theorem 12.6.4 Rodrigues’ Rotation Formula
Theorem 12.6.5 Axis and Angle from the Matrix
Example Axis and Angle of a Space Rotation
Lemma 12.6.6 A Mirror Between Two Vectors of Equal Length
Theorem 12.6.7 Reflections Generate the Orthogonal Group
Example Two Quarter Turns in Two Orders
Exercise A1
Exercise B1: Axis and angle
Exercise B2: Mirrors
Exercise B3: Rodrigues in an example
Exercise C1: The plane, re-derived
Exercise C2: Products of rotations
Exercise C3: Moving one point of the sphere to another

12.7 Commuting Families

Theorem 12.7.1 One Orthonormal Eigenbasis for a Commuting Family
Corollary 12.7.2 Commuting Normal Matrices
Corollary 12.7.3 Commuting Symmetric Matrices
Example Two Commuting Symmetric Matrices, Diagonalized Together
Theorem 12.7.4 Sums and Products of Commuting Normal Operators
Theorem 12.7.5 Simultaneous Unitary Triangularization
Exercise A1
Exercise B1: Diagonalize two at once
Exercise B2: Check the two warnings
Exercise B3: Triangularize two at once
Exercise C1: A special case of a theorem of Fuglede
Exercise C2: A commuting family of orthogonal projections

12.8 Spectral Resolutions and Functions of a Normal Operator

Definition 12.8.1 Spectral Resolution
Theorem 12.8.1 The Spectral Resolution and Its Projections
Example A Symmetric $3 \times 3$ Matrix
Example Two Projections That Are Not Orthogonal
Theorem 12.8.2 Uniqueness of the Spectral Resolution
Definition 12.8.2 Function of an Operator
Theorem 12.8.3 Properties of the Functional Calculus
Theorem 12.8.4 The Square Root of a Non-negative Normal Operator
Example A Square Root, and Three Impostors
Theorem 12.8.5 Unitary Matrices Are Exponentials of Hermitian Matrices
Example Exponentiating a Hermitian Matrix, and Undoing It
Exercise A1
Exercise B1: Write these as $\sum\lambda_i\mathbf{P}_i$
Exercise B2: Computing through the resolution
Exercise B3: Is it a spectral resolution?
Exercise C1: The projections are polynomials in the operator
Exercise C2: When the projections have rank one
Exercise C3: What the functional calculus forgets

12.9 Circulants and the Discrete Fourier Transform

Definition 12.9.1 Circulant matrix
Theorem 12.9.1 Circulants Are Exactly the Polynomials in the Shift
Theorem 12.9.2 Eigenvectors of the Cyclic Shift
Theorem 12.9.3 The Fourier Matrix Is Unitary
Example The Fourier matrix of size four
Theorem 12.9.4 Circulant Diagonalization
Example The running example, diagonalized
Corollary 12.9.5 Circulants Form a Commutative Algebra
Theorem 12.9.6 Convolution Theorem
Example Convolution in size four
Example A circulant system
Exercise A1
Exercise B1: Eigenvalues of small circulants
Exercise B2: Solve a circulant system by transforming
Exercise B3: The convolution theorem in an example
Exercise C1: What commutes with the shift
Exercise C2: Determinant and invertibility
Exercise C3: The real orthogonal form of a real circulant

12.10 The Sylvester Equation

Definition 12.10.1 Sylvester operator
Lemma 12.10.1 The Eigenvalues of a Kronecker Sum
Theorem 12.10.2 Sylvester’s Theorem
Example Solving a Sylvester Equation
Corollary 12.10.3 Block Diagonalization by a Sylvester Solution
Example Clearing a Corner
Corollary 12.10.4 Disjoint Spectra Split the Commutant
Definition 12.10.2 Lyapunov equation
Exercise A1
Exercise B1: A Sylvester equation by vectorization
Exercise B2: Block-diagonalizing a 3 × 3 matrix
Exercise B3: Which equations are uniquely solvable?
Exercise C1: Eigenvectors of the Sylvester operator
Exercise C2: The kernel when the spectra meet
Exercise C3: Only the scalars commute with everything

12.11 How Far from Normal

Theorem 12.11.1 Schur’s Inequality
Example Both sides of Schur’s inequality
Definition 12.11.1 Departure from Normality
Example The defect of a Jordan block
Example A perturbation that moves the eigenvalues a thousand times as far
Theorem 12.11.2 Normality as a Trace Identity
Theorem 12.11.3 Normality: The Complete List
Exercise A1
Exercise B1: Computing the defect
Exercise B2: Verifying Schur’s inequality
Exercise B3: The nearest symmetric matrix
Exercise C1: Unitary similarity preserves the defect, ordinary similarity does not
Exercise C2: Equality plus a single eigenvalue forces a scalar
Exercise C3: The commutator is at least as big as the defect squared

Positive Matrices and the Singular Value Decomposition

13.1 Positive Semidefinite and Positive Definite Matrices

Definition 13.1.1 Positive Semidefinite and Positive Definite
Proposition 13.1.1 Over $\mathbb{C}$ , positivity implies Hermitian
Example Five Positive Matrices
Proposition 13.1.2 Congruence preserves positivity
Lemma 13.1.3 Shifting by $t\mathbf{I}$ , minor by minor
Theorem 13.1.4 Characterizations of Positive Semidefiniteness
Theorem 13.1.5 Characterizations of Positive Definiteness, with Sylvester’s Criterion
Example The $2 \times 2$ Test
Example A Covariance-style Matrix
Theorem 13.1.6 Invertible Matrix Theorem, with Positive Definiteness
Exercise A1
Exercise B1: Determine the definiteness
Exercise B2: A parameter
Exercise B3: The inverse of a positive definite matrix
Exercise C1: Zero trace forces zero
Exercise C2: The cone of positive matrices
Exercise C3: The largest entry sits on the diagonal

13.2 Square Roots and the Cholesky Factorization

Theorem 13.2.1 The Positive Square Root
Example Two Square Roots
Definition 13.2.1 Absolute Value of a Matrix
Proposition 13.2.2 What the absolute value preserves
Example Two Absolute Values
Theorem 13.2.3 Cholesky Factorization
Example A Cholesky Factorization, and One That Fails
Exercise A1
Exercise B1: Square roots
Exercise B2: Cholesky, and a planted failure
Exercise B3: An absolute value
Exercise C1: The trace of a product of positive matrices
Exercise C2: Commuting positive matrices
Exercise C3: Why definiteness is needed

13.3 Gram Matrices

Theorem 13.3.1 Gram Matrices Are Exactly the Positive Semidefinite Matrices
Definition 13.3.1 Volume of a list
Lemma 13.3.2 Bordering a Gram matrix
Theorem 13.3.3 The Gram Determinant Is the Squared Volume
Theorem 13.3.4 Distance by Gram Determinants
Example The same distance twice
Exercise A1
Exercise B1: Which are Gram matrices?
Exercise B2: A volume two ways
Exercise B3: A distance in $\mathbb{R}^4$
Exercise C1: Rank of a Gram matrix
Exercise C2: Why the conjugate is not optional
Exercise C3: Height and volume

13.4 Two Forms at Once

Theorem 13.4.1 Diagonalizing Two Forms by Congruence
Definition 13.4.1 Generalized eigenvalue
Theorem 13.4.2 The Definite Generalized Eigenvalue Problem
Example A pencil that does not commute
Exercise A1
Exercise B1: A generalized eigenvalue problem
Exercise B2: Whitening by hand
Exercise B3: A pair that resists
Exercise C1: The $\mathbf{A}$ -inner product
Exercise C2: Signs of the generalized eigenvalues
Exercise C3: Dropping definiteness of $\mathbf{A}$

13.5 The Loewner Order

Definition 13.5.1 The Loewner order
Proposition 13.5.1 The Loewner order is a partial order
Lemma 13.5.2 The extreme eigenvalues as extreme values
Theorem 13.5.3 Basic Properties of the Loewner Order
Example Squaring does not preserve the Loewner order
Proposition 13.5.4 The square root is order preserving
Exercise A1
Exercise B1: Decide the relation
Exercise B2: The order reverses
Exercise B3: Another failure of squaring
Exercise C1: When squaring does work
Exercise C2: Kernels and ranks
Exercise C3: Largest eigenvalue of a sum

13.6 Positive Matrices in Blocks

Theorem 13.6.1 Positive Definiteness Block by Block
Example A $4 \times 4$ Tested in $2 \times 2$ Blocks
Lemma 13.6.2 Adding a positive matrix does not decrease the determinant
Corollary 13.6.3 Fischer’s Inequality
Theorem 13.6.4 Hadamard’s Inequality
Example Two Determinant Bounds
Exercise A1
Exercise B1: Definiteness by blocks
Exercise B2: A bordered matrix
Exercise B3: Hadamard bounds
Exercise C1: A zero corner kills its border
Exercise C2: A Cauchy–Schwarz inequality for blocks
Exercise C3: How large can a determinant be?

13.7 Products Entry by Entry

Definition 13.7.1 Hadamard Product
Lemma 13.7.1 Entrywise product of two rank-one positive matrices
Theorem 13.7.2 Schur Product Theorem
Example A $3 \times 3$ Entrywise Product
Theorem 13.7.3 Oppenheim’s Inequality
Exercise A1
Exercise B1: Compute and decide
Exercise B2: Entrywise squares
Exercise C1: Polynomials applied entrywise
Exercise C2: The product of the determinants
Exercise C3: The rank of an entrywise product

13.8 The Singular Value Decomposition

Definition 13.8.1 Singular Values
Theorem 13.8.1 Singular Value Decomposition
Theorem 13.8.2 The Singular Values Are Determined
Theorem 13.8.3 Compact Singular Value Decomposition
Corollary 13.8.4 The Four Fundamental Subspaces from the Compact Form
Example A singular value decomposition of a 2 by 3 matrix
Exercise A1
Exercise B1: A 2 by 2 decomposition
Exercise B2: When the left singular vectors must be padded
Exercise B3: Compact form and the four subspaces
Exercise B4: Determine whether
Exercise C1: The Frobenius norm and the largest singular value
Exercise C2: The adjoint and the determinant
Exercise C3: Singular values equal to eigenvalue moduli

13.9 Polar Decomposition and Takagi's Factorization

Theorem 13.9.1 Polar Decomposition
Example A polar decomposition
Corollary 13.9.2 The Polar Factor Is the Nearest Unitary Matrix
Theorem 13.9.3 Takagi’s Factorization
Example Takagi for a real symmetric matrix
Exercise A1
Exercise B1: A polar decomposition by hand
Exercise B2: The nearest unitary matrix
Exercise B3: A Takagi factorization
Exercise C1: The positive factor is forced
Exercise C2: Normality through the polar factors
Exercise C3: Complex symmetric matrices are transposed squares

13.10 Low-Rank Approximation

Definition 13.10.1 Truncated singular value decomposition
Example Truncating a diagonal matrix
Lemma 13.10.1 The Frobenius norm counts singular values
Lemma 13.10.2 An orthonormal list captures at most the leading singular values
Theorem 13.10.3 Eckart–Young Theorem, Frobenius case
Example The best rank-one approximation of a 3 × 2 matrix
Corollary 13.10.4 The best-fitting subspace
Exercise A1
Exercise B1: Errors from the singular values alone
Exercise B2: A best rank-one approximation
Exercise B3: Pythagoras for the truncation
Exercise C1: How far is a matrix from being singular?
Exercise C2: The best line through a cloud of points
Exercise C3: Truncation respects unitaries but not sums

13.11 The Moore–Penrose Pseudoinverse

Definition 13.11.1 Moore–Penrose pseudoinverse
Proposition 13.11.1 The pseudoinverse does not depend on the decomposition
Example Five pseudoinverses
Theorem 13.11.2 The Penrose Conditions
Theorem 13.11.3 Properties of the pseudoinverse
Theorem 13.11.4 The pseudoinverse solves both problems at once
Example Chapter 11’s minimum-norm solution, recomputed
Example Inconsistent and underdetermined at once
Proposition 13.11.5 The Semidefinite Block Criterion
Exercise A1
Exercise B1: Four pseudoinverses
Exercise B2: A system that is both inconsistent and underdetermined
Exercise B3: Checking a candidate
Exercise C1: Pseudoinverses of $\mathbf{A}^{*}\mathbf{A}$
Exercise C2: When the reversal rule does hold
Exercise C3: When the pseudoinverse is the adjoint

13.12 Projections Revisited

Theorem 13.12.1 Orthogonal Projections Among the Idempotents
Corollary 13.12.2 One Orthogonal Projection per Subspace
Theorem 13.12.3 Canonical Form of an Idempotent in an Orthonormal Basis
Example Two Oblique Projections, Measured
Exercise A1
Exercise B1: Which are orthogonal projections?
Exercise B2: Putting a projection in canonical form
Exercise B3: The complementary projection
Exercise C1: Products of orthogonal projections
Exercise C2: The Frobenius norm detects obliqueness
Exercise C3: How far an oblique projection can stretch

Bilinear and Quadratic Forms

14.1 Bilinear Forms and Their Matrices

Definition 14.1.1 Bilinear Form
Example Six two-slot functions
Definition 14.1.2 Matrix of a Bilinear Form
Theorem 14.1.1 Forms and Matrices Correspond
Example Four Gram matrices
Definition 14.1.3 Radical of a Form
Definition 14.1.4 Non-degenerate Form
Proposition 14.1.2 Non-degeneracy is invertibility of the Gram matrix
Example Three radicals
Exercise A1
Exercise B1: Which are forms?
Exercise B2: A Gram matrix from sample values
Exercise B3: Two radicals
Exercise C1: Over $\mathbb{F}_2$
Exercise C2: Orthogonal complements for a form
Exercise C3: The evaluation pairing

14.2 Congruence

Theorem 14.2.1 Change of Basis for a Form
Example Killing the cross term
Definition 14.2.1 Congruent Matrices
Example Congruences and a non-congruence
Proposition 14.2.2 Congruence is an equivalence relation
Theorem 14.2.3 Congruence preserves rank
Proposition 14.2.4 Congruence preserves the symmetry type
Theorem 14.2.5 Congruence changes the determinant by a square
Definition 14.2.2 Discriminant
Example Congruent, with no eigenvalue in common
Proposition 14.2.6 An orthogonal change of basis is both
Exercise A1
Exercise B1: A congruence in $\mathbb{Q}$
Exercise B2: A non-congruence over $\mathbb{Q}$
Exercise B3: Completing the square, again
Exercise C1: Congruence versus equivalence
Exercise C2: Orthogonal congruence
Exercise C3: How much the discriminant sees

14.3 Three Kinds of Form

Definition 14.3.1 Symmetric Bilinear Form
Proposition 14.3.1 Symmetry Is Visible in the Matrix
Proposition 14.3.2 Alternation and Skewness in the Matrix
Theorem 14.3.3 Alternating Versus Skew-Symmetric
Example The dot product over the field with two elements
Theorem 14.3.4 Symmetric Plus Alternating
Definition 14.3.2 Quadratic Form
Example From a polynomial to its matrix and back
Theorem 14.3.5 Polarization
Definition 14.3.3 Hermitian Form
Proposition 14.3.6 Hermitian Forms and Hermitian Matrices
Exercise A1
Exercise B1: Determine which of the following
Exercise B2: Polarizing a quadratic form
Exercise B3: Splitting a form
Exercise C1: Is this still true over $\mathbb{F}_2$ ?
Exercise C2: How much of a form does $q$ see?
Exercise C3: A Hermitian form is a real symmetric form in disguise

14.4 Completing the Square

Definition 14.4.1 Orthogonal Basis for a Form
Lemma 14.4.1 A Non-Zero Form Is Non-Zero Somewhere on the Diagonal
Theorem 14.4.2 Diagonalization of a Symmetric Form
Example Diagonalizing a symmetric matrix with zero diagonal
Proposition 14.4.3 Diagonal Entries Are Defined Only up to Squares
Corollary 14.4.4 Classification of Complex Symmetric Matrices by Rank
Exercise A1
Exercise B1: Symmetric elimination
Exercise B2: No pivot on the diagonal
Exercise B3: Reading off the rank
Exercise C1: Square classes over a finite field
Exercise C2: Is this still true over $\mathbb{F}_2$ ?
Exercise C3: Diagonalizing the restriction

14.5 Sylvester's Law of Inertia

Theorem 14.5.1 Sylvester’s Law of Inertia
Definition 14.5.1 Inertia and Signature
Corollary 14.5.2 Classification of Real Symmetric Matrices by Signature
Theorem 14.5.3 Inertia Is the Sign Pattern of the Spectrum
Example A signature by symmetric elimination
Exercise A1
Exercise B1: Signatures by elimination
Exercise B2: Which of these are congruent?
Exercise B3: Inertia from a characteristic polynomial
Exercise C1: An intrinsic description of $n_+$
Exercise C2: Congruence cannot be read off the eigenvalues, and inertia can
Exercise C3: Inertia of a block matrix

14.6 Definiteness and Second Derivatives

Definition 14.6.1 Definiteness of a Real Symmetric Form
Theorem 14.6.1 Definiteness Is the Signature
Proposition 14.6.2 Chapter 13’s Tests, in the Language of Forms
Definition 14.6.2 Hessian
Lemma 14.6.3 A Positive Definite Form Is Bounded Below by a Multiple of the Norm Squared
Theorem 14.6.4 The Second-Derivative Test
Example Two critical points of a cubic surface
Example One Hessian, three answers
Exercise A1
Exercise B1: Classify by the signature
Exercise B2: Critical points of a quartic
Exercise C1: The signature measures positive subspaces
Exercise C2: A saddle the determinant hides

14.7 Where the Form Vanishes

Definition 14.7.1 Isotropic and Anisotropic
Definition 14.7.2 Totally Isotropic Subspace
Lemma 14.7.1 Dimension of an Orthogonal Complement
Proposition 14.7.2 Half the Dimension, at Most
Proposition 14.7.3 A Non-degenerate Subspace Splits Off
Definition 14.7.3 Hyperbolic Pair, Hyperbolic Plane
Lemma 14.7.4 Every Isotropic Vector Lies in a Hyperbolic Plane
Theorem 14.7.5 Witt Decomposition
Definition 14.7.4 Witt Index
Proposition 14.7.6 The Number of Hyperbolic Planes Is the Witt Index
Proposition 14.7.7 The Witt Index over the Reals and the Complexes
Exercise A1
Exercise B1: Find the isotropic vectors
Exercise B2: Build a hyperbolic basis
Exercise B3: A totally isotropic subspace of the largest size
Exercise C1: Isotropy makes the form surjective
Exercise C2: A maximal totally isotropic subspace and its complement
Exercise C3: Where characteristic 2 breaks

14.8 Witt's Extension and Cancellation Theorems

Definition 14.8.1 Isometry of Bilinear Spaces
Definition 14.8.2 Reflection in an Anisotropic Vector
Proposition 14.8.1 Reflections Are Involutive Isometries
Lemma 14.8.2 Moving One Anisotropic Vector to Another
Theorem 14.8.3 Witt’s Extension Theorem
Corollary 14.8.4 Witt’s Cancellation Theorem
Corollary 14.8.5 The Anisotropic Part Is Determined
Exercise A1
Exercise B1: Extend an isometry by hand
Exercise B2: Cancel a hyperbolic plane
Exercise B3: Reflections in an indefinite space
Exercise C1: Inertia from cancellation
Exercise C2: The isometry group acts transitively
Exercise C3: What extension does not say

14.9 Alternating Forms and Darboux Bases

Example Alternating Forms on a Plane
Definition 14.9.1 Hyperbolic Pair
Lemma 14.9.1 Peeling Off a Hyperbolic Plane
Theorem 14.9.2 Standard Form of an Alternating Form
Definition 14.9.2 Symplectic Basis
Example A Symplectic Basis for a 4 × 4 Form
Corollary 14.9.3 Alternating Matrices Are Classified by Rank
Corollary 14.9.4 The Determinant of an Alternating Matrix Is a Square
Example The Pfaffian in Sizes 2 and 4
Exercise A1
Exercise B1: A symplectic basis
Exercise B2: Pfaffians and determinants
Exercise B3: Determine which of the following
Exercise C1: Lagrangian subspaces
Exercise C2: The inverse of an alternating matrix
Exercise C3: Counting over a finite field

14.10 Groups Defined by Forms

Definition 14.10.1 Isometry Group of a Form
Theorem 14.10.1 Isometry Groups Are Groups
Proposition 14.10.2 Congruence Conjugates the Isometry Group
Definition 14.10.2 The Indefinite Orthogonal and Symplectic Groups
Example Members of Each Family
Theorem 14.10.3 Determinants in the Classical Groups
Exercise A1
Exercise B1: Determine which of the following
Exercise B2: A symplectic matrix of size four
Exercise B3: Counting parameters
Exercise C1: Isometries of a degenerate form
Exercise C2: The symplectic group of a two-dimensional form, revisited
Exercise C3: Bounded and unbounded

14.11 Minkowski Space

Definition 14.11.1 Minkowski Space
Definition 14.11.2 Timelike, Spacelike, Null
Example Reading off the three types
Definition 14.11.3 Boost
Theorem 14.11.1 Classification of the Plane Lorentz Transformations
Lemma 14.11.2 Reversed Cauchy–Schwarz Inequality
Theorem 14.11.3 Reversed Triangle Inequality
Exercise A1
Exercise B1
Exercise B2
Exercise B3
Exercise C1
Exercise C2
Exercise C3

14.12 A First Look at Clifford Algebras

Definition 14.12.1 Algebra over a Field
Definition 14.12.2 Clifford Algebra
Proposition 14.12.1 Uniqueness of the Clifford Algebra
Lemma 14.12.2 The Anticommutation Relation
Example The zero space
Example The complex numbers
Definition 14.12.3 The Quaternions
Example The quaternions
Proposition 14.12.3 The Clifford Algebra Is Spanned by Sorted Products
Theorem 14.12.4 Dimension of a Clifford Algebra
Proposition 14.12.5 Reflections Are Conjugations
Exercise A1
Exercise B1: The split case
Exercise B2
Exercise B3
Exercise C1: A Clifford algebra of matrices
Exercise C2: Why characteristic 2 is excluded

Tensors and Exterior Algebra

15.1 Multilinear Maps

Definition 15.1.1 Multilinear Map
Example Seven functions of several vectors
Theorem 15.1.1 Multilinear Maps from Values on Basis Tuples
Definition 15.1.2 The Space of Multilinear Maps
Theorem 15.1.2 Dimension of the Space of Multilinear Maps
Example Counting bilinear maps
Exercise A1
Exercise B1: Determine which are multilinear
Exercise B2: Dimension counts
Exercise B3: Expanding in the basis
Exercise C1: Bilinear forms on coordinate spaces are matrices
Exercise C2: Linear and bilinear at once
Exercise C3: Counting over a finite field

15.2 The Tensor Product

Definition 15.2.1 Tensor Product
Theorem 15.2.1 Uniqueness of the Tensor Product
Definition 15.2.2 Notation for Tensors
Definition 15.2.3 Free Vector Space on a Set
Lemma 15.2.2 Universal Property of the Free Vector Space
Theorem 15.2.3 Existence of the Tensor Product
Proposition 15.2.4 Simple Tensors Span
Theorem 15.2.5 Basis of a Tensor Product
Corollary 15.2.6 Bilinear Maps Are Linear Maps on the Tensor Product
Theorem 15.2.7 $F^m \otimes F^n \cong M_{m \times n}(F)$
Example Computing in $F^2 \otimes F^3$
Example A tensor that is not simple
Proposition 15.2.8 When a Simple Tensor Is Zero
Proposition 15.2.9 When Two Simple Tensors Agree
Exercise A1
Exercise B1: Simple or not
Exercise B2: Inducing maps from bilinear maps
Exercise B3: Dimensions and bases
Exercise C1: The tensor product is commutative, up to a unique isomorphism
Exercise C2: Recovering the factors from a simple tensor

15.3 Tensor Products of Maps

Theorem 15.3.1 Tensor Product of Two Linear Maps
Definition 15.3.1 Tensor product of linear maps
Lemma 15.3.2 Simple Tensors Determine a Map
Proposition 15.3.3 Algebra of Tensor Products of Maps
Lemma 15.3.4 Universal Property for $k$ Factors
Proposition 15.3.5 Associativity of the Tensor Product
Definition 15.3.2 The product basis, ordered
Theorem 15.3.6 The Kronecker Product Is the Matrix of a Tensor Product of Maps
Example Computing with a tensor product of maps
Corollary 15.3.7 The Mixed Product Rule Is Functoriality
Corollary 15.3.8 Rank, Determinant and Trace of a Tensor Product of Maps
Theorem 15.3.9 Tensors Are Maps
Example The vec identity, read as a tensor product of maps
Exercise A1
Exercise B1: A tensor product of maps, two ways
Exercise B2: Invariants without multiplying matrices
Exercise B3: Which statements hold?
Exercise C1: When a tensor product of maps vanishes
Exercise C2: Rank-one maps and simple tensors
Exercise C3: Reproving the swap

15.4 Contraction and the Trace

Definition 15.4.1 Contraction
Theorem 15.4.1 The Trace Is a Contraction
Corollary 15.4.2 Trace of a Rank-One Map
Proposition 15.4.3 The Dual of a Tensor Product
Corollary 15.4.4 Why the Trace Multiplies
Definition 15.4.2 Tensor of type $(p, q)$
Definition 15.4.3 Contraction on a pair of slots
Exercise A1
Exercise B1: Contracting a mixed tensor
Exercise B2: Two contractions of one tensor
Exercise B3: Which statements hold?
Exercise C1: Composition, in tensor language
Exercise C2: The contraction of the identity, over any field

15.5 Index Notation and the Transformation Law

Definition 15.5.1 Components of a tensor
Lemma 15.5.1 Dual Bases Move by the Inverse Matrix
Theorem 15.5.2 Transformation Law for Components
Definition 15.5.2 Classical tensor
Theorem 15.5.3 The Two Definitions Agree
Exercise A1
Exercise B1: Transforming components
Exercise B2: Tensor or not?
Exercise C1: Contraction in indices
Exercise C2: Raising an index needs a form

15.6 The Tensor Algebra

Definition 15.6.1 $k$ -th Tensor Power
Theorem 15.6.1 Uniqueness of the Tensor Power
Theorem 15.6.2 Existence of the Tensor Power
Theorem 15.6.3 Basis of a Tensor Power
Example A tensor cube, in coordinates
Proposition 15.6.4 Concatenation of Tensors
Definition 15.6.2 Tensor Algebra
Theorem 15.6.5 The Tensor Algebra Is an Algebra
Example The tensor algebra of a line
Theorem 15.6.6 Universal Property of the Tensor Algebra
Exercise A1
Exercise B1: Expanding a simple tensor
Exercise B2: A product in the tensor algebra
Exercise B3: A homomorphism built from the universal property
Exercise C1: The grading is a direct sum of subspaces
Exercise C2: Extending an operator to the algebra
Exercise C3: Why the empty degree is $F$

15.7 Symmetric Powers

Definition 15.7.1 Symmetric Multilinear Map
Definition 15.7.2 $k$ -th Symmetric Power
Theorem 15.7.1 Uniqueness of the Symmetric Power
Theorem 15.7.2 Existence of the Symmetric Power
Theorem 15.7.3 Basis of a Symmetric Power
Example A symmetric square, in coordinates
Proposition 15.7.4 The Symmetric Product of Two Symmetric Tensors
Definition 15.7.3 Symmetric Algebra
Proposition 15.7.5 $\operatorname{Sym}(V)$ Is a Commutative Algebra
Definition 15.7.4 The Polynomial Algebra $F[x_1, \dots, x_n]$
Theorem 15.7.6 The Symmetric Algebra Is a Polynomial Algebra
Lemma 15.7.7 Permuting the Slots of a Tensor
Definition 15.7.5 Symmetric Tensor
Theorem 15.7.8 Symmetric Tensors and the Symmetric Power
Exercise A1
Exercise B1: Expanding symmetric products
Exercise B2: Counting
Exercise B3: A form factored through the symmetric square
Exercise C1: The characteristic-two witness in full
Exercise C2: $\operatorname{Sym}(V)$ is the free commutative algebra
Exercise C3: One variable

15.8 Exterior Powers

Definition 15.8.1 Alternating Multilinear Map
Lemma 15.8.1 Properties of Alternating Maps
Proposition 15.8.2 The Repetition Relations Are the Stronger Ones
Definition 15.8.2 $k$ -th Exterior Power
Theorem 15.8.3 Uniqueness of the Exterior Power
Theorem 15.8.4 Existence of the Exterior Power
Theorem 15.8.5 Basis of an Exterior Power
Corollary 15.8.6 The Top Exterior Power Is a Line
Example A wedge in $\Lambda^2(F^3)$
Theorem 15.8.7 Wedges Detect Independence
Exercise A1
Exercise B1: Computing wedges
Exercise B2: Independence by wedging
Exercise B3: A functional built from the universal property
Exercise C1: The characteristic-two witness
Exercise C2: Alternating forms, recounted
Exercise C3: A wedge sees only the subspace

15.9 The Determinant as a Top Exterior Power

Lemma 15.9.1 Wedging with a Fixed Vector
Definition 15.9.1 Exterior Power of a Linear Map
Theorem 15.9.2 Exterior Powers Respect Composition
Example The second exterior power of a 3 × 3 matrix
Theorem 15.9.3 The Determinant Is the Top Exterior Power
Corollary 15.9.4 Multiplicativity and Invertibility, from Functoriality
Theorem 15.9.5 The Coordinates of a Wedge Are the Minors
Example A wedge of two vectors in four-dimensional space
Corollary 15.9.6 Independence via Minors
Corollary 15.9.7 Cofactor Expansion, from a Wedge
Exercise A1
Exercise B1: A second exterior power
Exercise B2: Independence by minors
Exercise B3: Determinant of an inverse
Exercise C1: The trace of an exterior power
Exercise C2: Cauchy–Binet from a wedge
Exercise C3: Exterior powers of an injection

15.10 The Exterior Algebra, and Clifford at Last

Proposition 15.10.1 The Wedge of Two Exterior Powers
Definition 15.10.1 Exterior Algebra
Theorem 15.10.2 Structure of the Exterior Algebra
Theorem 15.10.3 Graded Commutativity
Example The exterior algebra of a three-dimensional space
Definition 15.10.2 Decomposable Element
Theorem 15.10.4 Not Every 2-Vector Is Decomposable
Definition 15.10.3 Two-Sided Ideal, and the Ideal Generated by a Set
Lemma 15.10.5 Quotient of an Algebra by an Ideal
Theorem 15.10.6 Existence of the Clifford Algebra
Lemma 15.10.7 Creation and Deletion Operators
Theorem 15.10.8 Dimension of a Clifford Algebra
Proposition 15.10.9 Comparing the Two Algebras
Corollary 15.10.10 Recognizing a Clifford Algebra
Example The Clifford algebra of the Euclidean plane
Exercise A1
Exercise B1: Multiplying in the exterior algebra
Exercise B2: Decomposable or not
Exercise B3: A Clifford algebra of a line
Exercise C1: The Plücker relation
Exercise C2: Characteristic two
Exercise C3: The even part of a Clifford algebra

15.11 Tensors in Quantum Mechanics

Proposition 15.11.1 The Inner Product on a Tensor Product
Definition 15.11.1 Product State, Entangled State
Example The Bell state
Theorem 15.11.2 Schmidt Decomposition
Definition 15.11.2 Schmidt Coefficients, Schmidt Rank
Corollary 15.11.3 Entanglement Is Schmidt Rank at Least Two
Example A Schmidt decomposition in two by three
Exercise A1
Exercise B1: Determine which are entangled
Exercise B2: A Schmidt decomposition
Exercise B3: How large can the Schmidt rank be?
Exercise C1: Acting on one part at a time
Exercise C2: Best approximation by a state of small Schmidt rank
Exercise C3: Does the field matter?

Norms and Matrix Analysis

16.1 Norms

Definition 16.1.1 Norm
Example The $1$ -, $2$ - and $\infty$ -norms on $F^n$
Example Inner products, weights, and a function space
Example Three near misses
Lemma 16.1.1 Reverse Triangle Inequality
Definition 16.1.2 Closed Unit Ball
Proposition 16.1.2 Comparing the Three Norms
Theorem 16.1.3 The Parallelogram Law Characterizes Inner-Product Norms
Exercise A1
Exercise B1: Three measurements
Exercise B2: Determine which are norms
Exercise B3: Which of these come from an inner product?
Exercise C1: Sharpness of the comparison constants
Exercise C2: A real norm that is not a complex norm
Exercise C3: The ball determines the norm

16.2 All Norms Agree

Definition 16.2.1 Equivalent Norms
Example The three $p$ -norms, with best constants
Proposition 16.2.1 Equivalence of Norms Is an Equivalence Relation
Theorem 16.2.2 Equivalence of Norms in Finite Dimension
Example Agreeing on a basis is not enough
Corollary 16.2.3 Convergence and Boundedness Do Not Depend on the Norm
Corollary 16.2.4 Entrywise Convergence Is Convergence in Every Norm
Example Watching one sequence converge
Corollary 16.2.5 Closed and Bounded Is Compact, in Every Norm
Example Two inequivalent norms on a space of polynomials
Exercise A1
Exercise B1: Best constants for a weighted norm
Exercise B2: Reading a convergence off the entries
Exercise B3: An equivalence with the constants written down
Exercise C1: Every linear map out of a finite-dimensional space is continuous
Exercise C2: No dimension-free constants
Exercise C3: A finite-dimensional subspace is closed

16.3 Measuring a Matrix

Definition 16.3.1 Matrix Norm
Example The Frobenius norm is submultiplicative
Example The entrywise maximum is not submultiplicative
Lemma 16.3.1 The Largest Stretch Is Attained
Definition 16.3.2 Operator Norm
Theorem 16.3.2 Properties of the Operator Norm
Theorem 16.3.3 Computing the 1-, 2- and Infinity-Norms
Example One matrix, four numbers
Example The oblique projection, finally measured
Proposition 16.3.4 Frobenius Against Spectral
Exercise A1
Exercise B1: Four numbers for one matrix
Exercise B2: A rank-one matrix
Exercise B3: The star trick
Exercise C1: The spectral norm between the other two
Exercise C2: Repairing the entrywise maximum
Exercise C3: When is a bound an equality?

16.4 The Spectral Radius

Definition 16.4.1 Spectral Radius
Theorem 16.4.1 The Spectral Radius Is a Lower Bound for Every Norm
Corollary 16.4.2 Cheap Bounds on the Spectrum
Example Bounding a spectrum without finding it
Theorem 16.4.3 Norms Close to the Spectral Radius
Theorem 16.4.4 Gelfand’s Formula
Example Watching the limit converge
Corollary 16.4.5 Powers Tending to Zero, with a Rate
Exercise A1
Exercise B1: Four numbers again
Exercise B2: Gelfand exactly
Exercise B3: Deciding convergence without eigenvalues
Exercise C1: A norm that sees the decay
Exercise C2: Spectral radius zero
Exercise C3: When the infimum is attained

16.5 Inverting a Perturbation of the Identity

Theorem 16.5.1 Neumann Series with a Bound
Example The bound and the truth
Corollary 16.5.2 Invertibility Is an Open Condition, and Inversion Is Continuous
Example How far an invertible matrix can be pushed
Theorem 16.5.3 Relative Error in a Perturbed Solve
Example A perturbation of the matrix
Exercise A1
Exercise B1: Check, sum, compare
Exercise B2: A perturbed right-hand side
Exercise B3: Staying invertible
Exercise C1: The inverse to first order
Exercise C2: Distance to the singular matrices
Exercise C3: Without $\left\| \mathbf{I} \right\| = 1$

16.6 Bounds for the Exponential, and Two Derivatives

Theorem 16.6.1 Bounds for the Exponential
Example Where the bound is exact, and where it is useless
Lemma 16.6.2 The Spectrum of the Exponential
Theorem 16.6.3 Exponential Decay of a Stable System
Example Decay after a detour
Definition 16.6.1 Derivative of a Matrix-Valued Function
Lemma 16.6.4 Product Rule for Matrices
Theorem 16.6.5 Derivative of the Inverse
Theorem 16.6.6 Jacobi’s Formula
Corollary 16.6.7 The Determinant’s Derivative at the Identity Is the Trace
Example Both derivatives on one family
Exercise A1
Exercise B1: Bound against truth
Exercise B2: A rate for a stable matrix
Exercise B3: Two derivatives
Exercise C1: The determinant of the exponential, again
Exercise C2: Comparing two exponentials
Exercise C3: A quantity that measures the decay

16.7 Eigenvalues Move Continuously

Lemma 16.7.1 Polynomial Maps of the Entries Are Continuous
Proposition 16.7.2 There Is No Continuous Choice of a Single Eigenvalue
Theorem 16.7.3 Continuous Dependence of the Roots on the Coefficients
Corollary 16.7.4 Eigenvalues Depend Continuously on the Matrix
Corollary 16.7.5 Diagonalizable Matrices Are Dense
Corollary 16.7.6 Proving an Identity by Density
Example Cayley–Hamilton, by a limit
Example A Jordan block’s eigenvalues move like $\varepsilon^{1/k}$
Exercise A1
Exercise B1: Two perturbations of the same size
Exercise B2: A diagonalizable neighbor, explicitly
Exercise B3: The determinant and the trace, by density
Exercise C1: How close to singular a nearby eigenvalue forces you to be
Exercise C2: Density of the invertible matrices, and $\mathbf{A}\mathbf{B}$ versus $\mathbf{B}\mathbf{A}$
Exercise C3: Distinct eigenvalues is an open condition

16.8 How Wrong Can the Answer Be

Definition 16.8.1 Condition Number
Lemma 16.8.1 The Inverse Measures the Smallest Stretch
Example Three condition numbers of one matrix
Proposition 16.8.2 Properties of the Condition Number
Theorem 16.8.3 Relative Error Under Perturbation of the Data
Example A system where the bound is attained
Theorem 16.8.4 The Normal Equations Square the Condition Number
Example Squaring, on a $3 \times 2$ example
Exercise A1
Exercise B1: Three condition numbers
Exercise B2: A perturbation, measured against the bound
Exercise B3: Squaring, again
Exercise C1: Changing the norm changes $\kappa$ , but not much
Exercise C2: The condition number is the reciprocal distance to singularity
Exercise C3: A well-conditioned problem and a bad method

Variational Principles and Interlacing

17.1 The Rayleigh Quotient

Definition 17.1.1 Rayleigh Quotient
Example A diagonal matrix, and the whole chapter in miniature
Example A symmetric matrix on the unit circle
Example Two matrices whose quotient is forced
Example Change one word: drop Hermitian
Proposition 17.1.1 The Range of the Rayleigh Quotient
Proposition 17.1.2 Critical Points of the Rayleigh Quotient
Proposition 17.1.3 Eigenvalues by Deflation
Exercise A1
Exercise B1: Locating four values
Exercise B2: A prescribed value
Exercise B3: The quotient of a projection
Exercise C1: Why the quotient estimates eigenvalues so well
Exercise C2: The equality case at the top
Exercise C3: What the quotient cannot see

17.2 The Min–Max Theorem

Lemma 17.2.1 Large Subspaces Intersect
Lemma 17.2.2 The Rayleigh Quotient on a Subspace
Theorem 17.2.3 Courant–Fischer Min–Max Theorem
Example Both forms on one matrix
Corollary 17.2.4 The Loewner Order Compares Every Eigenvalue
Example Checking the corollary on a pair
Corollary 17.2.5 Courant–Fischer for a Self-Adjoint Operator
Exercise A1
Exercise B1: Both forms on a diagonal matrix
Exercise B2: Shifting by a multiple of the identity
Exercise B3: Comparing two matrices
Exercise C1: The definite generalized eigenvalue problem
Exercise C2: How much weaker the eigenvalue comparison is
Exercise C3: Does enlarging the field change the answer?

17.3 How Far Eigenvalues Move

Lemma 17.3.1 The Quotient on a Span of Eigenvectors
Lemma 17.3.2 Negation Reverses the List
Theorem 17.3.3 Weyl’s Inequalities
Example Both families on one pair
Corollary 17.3.4 Perturbation, Two-Sided
Lemma 17.3.5 The Spectral Norm of a Hermitian Matrix
Corollary 17.3.6 Hermitian Eigenvalues Are 1-Lipschitz
Corollary 17.3.7 The Hermitian Eigenvalue Problem Is Perfectly Conditioned in Absolute Terms
Example Locating eigenvalues without recomputing them
Corollary 17.3.8 A Rank- $r$ Perturbation Shifts the Index by $r$
Exercise A1
Exercise B1: A small table
Exercise B2: An interval for each eigenvalue
Exercise B3: What a low-rank update can do
Exercise C1: The Loewner order through Weyl
Exercise C2: The largest eigenvalue is a convex function
Exercise C3: Sharpness of the whole family

17.4 Deleting a Row and a Column

Lemma 17.4.1 Deleting a Row and a Column Is Restricting to a Hyperplane
Theorem 17.4.2 Cauchy’s Interlacing Theorem
Corollary 17.4.3 Deleting $m$ Rows and the Same $m$ Columns
Example The diagonal lies inside the spectrum
Theorem 17.4.4 Bordering a Hermitian Matrix
Lemma 17.4.5 Eigenvectors of an Unreduced Tridiagonal Matrix
Corollary 17.4.6 Zeros of Orthogonal Polynomials Interlace
Example One matrix and all three of its corners
Corollary 17.4.7 A Principal Submatrix Keeps Most of the Inertia
Example A corner outside the spectrum
Exercise A1
Exercise B1: Interlacing in integers
Exercise B2: Bounds without a characteristic polynomial
Exercise B3: Deciding strictness
Exercise C1: Rank under compression
Exercise C2: The converse, in the smallest case
Exercise C3: How far apart can the extremes be

17.5 Adding a Rank-One Matrix

Theorem 17.5.1 Interlacing for a Rank-One Update
Example A bump on a diagonal matrix
Definition 17.5.1 Secular function
Theorem 17.5.2 Eigenvalues from the Secular Equation
Example A three-by-three update, found from its secular equation
Corollary 17.5.3 Total Eigenvalue Shift
Exercise A1
Exercise B1: A secular equation, end to end
Exercise B2: Reading the chain backwards
Exercise B3: The missing eigenvalue
Exercise C1: What a zero coordinate does
Exercise C2: Only one eigenvalue can escape
Exercise C3: Bumping along an eigenvector

17.6 Subspaces and Sums of Eigenvalues

Definition 17.6.1 Compression to a subspace
Theorem 17.6.1 Poincaré Separation Theorem
Example A compression of a diagonal matrix
Theorem 17.6.2 Ky Fan Maximum Principle
Example Which pairs of directions capture the most
Corollary 17.6.3 Partial Sums of the Diagonal
Corollary 17.6.4 The Capture Bound as a Case of Ky Fan
Corollary 17.6.5 Subadditivity of the Top Partial Sums
Corollary 17.6.6 The Bottom Partial Sums as a Minimum
Exercise A1
Exercise B1: A compression, and two bounds
Exercise B2: Reading the sums off the spectrum
Exercise B3: Subadditivity, and how loose it can be
Exercise C1: The Loewner order and the partial sums
Exercise C2: Partial sums that behave like a norm
Exercise C3: How much of a matrix a subspace holds

17.7 Arbitrary Index Sets

Definition 17.7.1 Flags of a given type, and adapted lists
Theorem 17.7.1 Wielandt’s Minimax Principle
Example The selection at work, and why it is needed
Theorem 17.7.2 Lidskii’s Inequality
Example All seven index sets
Corollary 17.7.3 Weyl and Ky Fan as Cases of Lidskii
Exercise A1
Exercise B1: Running the selection
Exercise B2: A complex pair
Exercise B3: The lower bound
Exercise C1: A second proof of Lidskii’s inequality
Exercise C2: The total absolute shift

17.8 The Diagonal and the Spectrum

Definition 17.8.1 Majorization
Example A chain, the two extremes, and size one
Example Neither majorizes the other
Proposition 17.8.1 Basic Properties of Majorization
Theorem 17.8.2 Schur’s Majorization Theorem
Example Coordinate vectors against eigenvectors
Lemma 17.8.3 The Two-by-Two Rotation
Theorem 17.8.4 Horn’s Theorem
Theorem 17.8.5 Schur–Horn Theorem
Example Building a matrix from its diagonal and spectrum
Lemma 17.8.6 The Arithmetic–Geometric Mean Inequality
Corollary 17.8.7 Hadamard’s Inequality, Second Proof
Exercise A1
Exercise B1: Determine which pairs are comparable
Exercise B2: Schur’s theorem for one matrix
Exercise B3: Which diagonals are ruled out?
Exercise C1: Majorization squeezes the range
Exercise C2: A weaker determinant bound
Exercise C3: The possible diagonals form a convex set

17.9 The Same Theory for Singular Values

Lemma 17.9.1 Stretching in the Right Singular Basis
Theorem 17.9.2 Min–Max for Singular Values
Proposition 17.9.3 The Hermitian Dilation
Theorem 17.9.4 Weyl’s Inequalities for Singular Values
Corollary 17.9.5 Singular Values Are Perfectly Conditioned
Example The Jordan block again, measured by its singular values
Theorem 17.9.6 Eckart–Young Theorem, Spectral Case
Example One matrix, two norms
Corollary 17.9.7 The Distance to Singularity
Example The nearest singular matrix, exactly and approximately
Theorem 17.9.8 Interlacing Under Deletion of a Row or a Column
Example Interlacing on a 3 × 2 matrix
Exercise A1
Exercise B1: Two norms, one list of singular values
Exercise B2: The nearest singular matrix
Exercise B3: Interlacing by hand
Exercise C1: Rank cannot drop suddenly
Exercise C2: The dilation, and a second proof of the perturbation bound

17.10 Inertia, Again and Additively

Definition 17.10.1 The Inertia Triple
Theorem 17.10.1 Sylvester’s Law of Inertia, Second Proof
Corollary 17.10.2 What Each Count Is a Maximum Of
Theorem 17.10.3 Inertia Moves by at Most the Rank
Example A rank-one perturbation, three ways
Theorem 17.10.4 Haynsworth’s Inertia Additivity Formula
Example The Chapter 14 example, through a Schur complement
Example A 4 × 4 inertia in two lines
Corollary 17.10.5 Block Definiteness, a Second Proof
Exercise A1
Exercise B1: Two inertias by Schur complement
Exercise B2: How much can a rank-two perturbation do?
Exercise B3: A bordered matrix
Exercise C1: How large can a subspace be on which the form vanishes?
Exercise C2: The inertia of a Hermitian dilation
Exercise C3: Inertia from the leading principal minors

17.11 Which Functions Respect the Order

Definition 17.11.1 Operator Monotone and Operator Convex Functions
Proposition 17.11.1 Operator Monotone Functions Are Increasing
Proposition 17.11.2 Increasing Affine Functions
Proposition 17.11.3 The Negative Reciprocal Is Operator Monotone
Proposition 17.11.4 Combining Operator Monotone Functions
Corollary 17.11.5 Shifted Reciprocals
Lemma 17.11.6 The Eigenvalue List of an Increasing Function
Proposition 17.11.7 Every Increasing Function Is Monotone on Eigenvalues
Example The Squares Are Not Ordered, but Their Eigenvalues Are
Proposition 17.11.8 The Square Is Operator Convex
Theorem 17.11.9 Loewner’s Theorem, Statement
Exercise A1
Exercise B1: Which are operator monotone?
Exercise B2: One pair, three functions
Exercise B3: The convexity identity in numbers
Exercise C1: Iterated square roots
Exercise C2: The reciprocal is operator convex
Exercise C3: The cube needs its own witness

Convexity

18.1 Convex Sets and Hulls

Definition 18.1.1 Convex Set
Example The first convex sets
Definition 18.1.2 Standard Simplex
Example The vectors majorized by a fixed vector
Proposition 18.1.1 Operations Preserving Convexity
Definition 18.1.3 Convex Combination
Lemma 18.1.2 Convex Sets Contain Their Convex Combinations
Definition 18.1.4 Convex Hull
Theorem 18.1.3 The Hull Is the Set of Convex Combinations
Example Deciding membership in a triangle
Definition 18.1.5 Affine Combination, Affine Hull
Proposition 18.1.4 The Affine Hull Is a Coset
Definition 18.1.6 Closed Set, Open Set
Lemma 18.1.5 Linear Maps Are Lipschitz
Proposition 18.1.6 Closed and Open Sets: First Facts
Exercise A1
Exercise B1: Determine which are convex
Exercise B2: Membership in a hull
Exercise C1: Midpoint convexity
Exercise C3: Sets that contain lines

18.2 Carathéodory's Theorem

Definition 18.2.1 Affine Independence
Lemma 18.2.1 Affine Dependence by Differences
Theorem 18.2.2 Carathéodory’s Theorem
Example Dropping a point in the plane
Example The bound is attained
Example Two points suffice for a circle
Corollary 18.2.3 The Hull of a Compact Set Is Compact
Theorem 18.2.4 Radon’s Theorem
Theorem 18.2.5 Helly’s Theorem
Example Helly’s proof run on four half-planes
Exercise A1
Exercise B1: Shortening a combination
Exercise B2: Radon partitions in the plane
Exercise B3: Linear functionals on a polygon
Exercise C1: Carathéodory in the affine hull
Exercise C2: Helly’s theorem for a sequence of compact sets
Exercise C3: The counts are sharp

18.3 Separating Hyperplanes

Theorem 18.3.1 Nearest Point Theorem
Example Three projections
Definition 18.3.1 Separation by a Hyperplane
Theorem 18.3.2 Separating a Point from a Closed Convex Set
Corollary 18.3.3 A Closed Convex Set Is an Intersection of Half-Spaces
Definition 18.3.2 Interior Point, Closure, Boundary Point
Lemma 18.3.4 A Convex Set Is Solid or Flat
Lemma 18.3.5 Closure and Interior of a Convex Set
Theorem 18.3.6 Supporting Hyperplane Theorem
Theorem 18.3.7 Separating Hyperplane Theorem
Example A hyperbola and its asymptote
Definition 18.3.3 Sublinear Functional
Theorem 18.3.8 Hahn–Banach Theorem, Finite-Dimensional
Corollary 18.3.9 Norm-Preserving Extension
Example Many extensions
Exercise A1
Exercise B1: Projection onto a half-plane
Exercise B2: Cutting off a point from a diamond
Exercise B3: A unique extension
Exercise C1: The projection does not stretch
Exercise C2: Strict separation and distance

18.4 Gauges, Support Functions and Dual Norms

Definition 18.4.1 Gauge
Proposition 18.4.1 Properties of the Gauge
Theorem 18.4.2 Convex Bodies and Norms
Definition 18.4.2 Support Function
Proposition 18.4.3 Properties of the Support Function
Theorem 18.4.4 The Support Function Determines a Closed Convex Set
Definition 18.4.3 Polar Set
Theorem 18.4.5 Bipolar Theorem
Definition 18.4.4 Dual Norm
Proposition 18.4.6 Properties of the Dual Norm
Proposition 18.4.7 Duals of the 1-, 2- and Infinity-Norms
Theorem 18.4.8 The Dual of the Dual Norm
Corollary 18.4.9 A Norm Is a Maximum of Linear Functions
Proposition 18.4.10 Operator Norms through Dual Norms
Exercise A1
Exercise B1: A weighted norm and its dual
Exercise B2: A hexagonal norm
Exercise B3: The polar of a triangle
Exercise C1: The norm from 1 to infinity
Exercise C2: Equivalence constants dualize
Exercise C3: The gauge is the support function of the polar

18.5 Cones and Farkas's Lemma

Definition 18.5.1 Convex Cone
Definition 18.5.2 Finitely Generated Cone
Definition 18.5.3 Dual Cone
Proposition 18.5.1 Basic Properties of the Dual Cone
Theorem 18.5.2 Carathéodory’s Theorem for Cones
Lemma 18.5.3 Injective Images of the Orthant Are Closed
Theorem 18.5.4 Finitely Generated Cones Are Closed
Lemma 18.5.5 Separating a Point from a Closed Cone
Theorem 18.5.6 Farkas’s Lemma
Example Deciding a system both ways
Corollary 18.5.7 Farkas’s Lemma for Inequalities
Theorem 18.5.8 The Bidual of a Closed Cone
Example A closed cone with a non-closed shadow
Exercise A1
Exercise B1: Recognizing cones
Exercise B2: A certificate either way
Exercise B3: A dual cone and its dual
Exercise C1: Gordan’s alternative
Exercise C2: The ice-cream cone is its own dual
Exercise C3: The bidual sees only the closure

18.6 Linear Programming Duality

Definition 18.6.1 Linear Program
Example The workshop problem, drawn
Definition 18.6.2 Dual Program
Theorem 18.6.1 Weak Duality
Corollary 18.6.2 Certificates from Weak Duality
Theorem 18.6.3 Strong Duality for Linear Programs
Corollary 18.6.4 Bounded Linear Programs Attain Their Optimum
Theorem 18.6.5 Complementary Slackness
Example Capacities on every street
Exercise A1
Exercise B1: Solve and certify
Exercise B2: Which case?
Exercise B3: A network with one flow
Exercise C1: The dual of the dual
Exercise C2: Free variables

18.7 Matrix Games and the Minimax Theorem

Lemma 18.7.1 Max–Min Never Exceeds Min–Max
Definition 18.7.1 Mixed Strategy
Lemma 18.7.2 A Pure Best Response Exists
Theorem 18.7.3 Von Neumann’s Minimax Theorem
Definition 18.7.2 Value and Optimal Strategies
Example A game with an unused column
Exercise A1
Exercise B1: A two-by-two game
Exercise B2: A saddle point
Exercise B3: Many optimal strategies
Exercise C1: Symmetric games
Exercise C2: The value depends continuously on the payoffs

18.8 Extreme Points

Definition 18.8.1 Extreme Point
Lemma 18.8.1 The Midpoint Test
Proposition 18.8.2 Extreme Points of a Hull Come From the Generators
Definition 18.8.2 Face
Lemma 18.8.3 Extreme Points of a Face
Proposition 18.8.4 Supporting Slices Are Faces
Theorem 18.8.5 Minkowski’s Theorem
Corollary 18.8.6 Linear Functions Peak at Extreme Points
Example The diamond, the cube and the sphere
Definition 18.8.3 Density Matrix
Lemma 18.8.7 A Zero of the Form Is a Null Vector
Theorem 18.8.8 Extreme Points of the Density Matrices
Example The largest eigenvalue as a linear maximum
Definition 18.8.4 Doubly Stochastic Matrix
Proposition 18.8.9 Permutation Matrices Are Extreme
Example A double cone over a circle
Exercise A1
Exercise B1: Finding extreme points
Exercise B2: A density matrix split into pure pieces
Exercise B3: A doubly stochastic matrix from permutations
Exercise C1: Deleting an extreme point
Exercise C2: Every contraction is an average of orthogonal matrices
Exercise C3: The corners of the Loewner interval

18.9 Polytopes

Definition 18.9.1 Polytope
Definition 18.9.2 Polyhedron
Proposition 18.9.1 Polyhedra Are Closed and Convex
Definition 18.9.3 Active Set, Basic Feasible Point
Theorem 18.9.2 Vertices Are Basic Feasible Points
Corollary 18.9.3 A Polyhedron Has Finitely Many Vertices
Example The vertices of a quadrilateral
Lemma 18.9.4 Fourier–Motzkin Elimination
Example A triangle, both ways
Definition 18.9.4 Polyhedral Cone
Theorem 18.9.5 Minkowski–Weyl Theorem
Example The cube and the cross-polytope
Exercise A1
Exercise B1: Vertices of a pentagon
Exercise B2: Inequalities for a quadrilateral
Exercise B3: Which of these are vertices?
Exercise C1: Unbounded polyhedra
Exercise C2: Linear images of polyhedra
Exercise C3: Vertices in standard form

18.10 Convex Functions

Definition 18.10.1 Convex Function
Example First convex functions
Proposition 18.10.1 Convex Function, Convex Epigraph
Theorem 18.10.2 Jensen’s Inequality
Proposition 18.10.3 A Supremum of Affine Functions Is Convex
Corollary 18.10.4 The Top Eigenvalue Sums Are Convex
Lemma 18.10.5 Increasing Derivative Gives Convexity
Theorem 18.10.6 Convexity from the Hessian
Theorem 18.10.7 Convex Functions Are Continuous
Exercise A1
Exercise B1: Which are convex?
Exercise C1: Subadditive and homogeneous
Exercise C2: Tangent lines
Exercise C3: Where a convex function is largest

18.11 Three Classical Inequalities

Lemma 18.11.1 Exponential and Logarithm
Theorem 18.11.2 Weighted Arithmetic–Geometric Mean Inequality
Lemma 18.11.3 Young’s Inequality
Theorem 18.11.4 Hölder’s Inequality
Corollary 18.11.5 Minkowski’s Inequality
Theorem 18.11.6 The Dual of the p-Norm
Example A dual norm by hand
Exercise A1
Exercise B1: A dual norm by hand
Exercise B2: Harmonic and arithmetic means
Exercise C1: The exponential above its tangent
Exercise C2: When Hölder is an equality

Non-negative Matrices

19.1 Positive Matrices and Perron's Theorem

Definition 19.1.1 Entrywise Order; Non-negative and Positive Matrices
Lemma 19.1.1 Rules of the Entrywise Order
Lemma 19.1.2 Absolute Value of a Product
Lemma 19.1.3 Equality in the Triangle Inequality
Proposition 19.1.4 Monotonicity of the Spectral Radius
Example Enlarging one entry
Theorem 19.1.5 Perron’s Theorem
Example Perron’s theorem for Chapter 9’s first example
Example A positive $3 \times 3$ matrix
Definition 19.1.2 Perron Root, Perron Vector
Exercise A1
Exercise B1: A Perron vector by hand
Exercise B2: Which order?
Exercise B3: Bounds from the smallest and largest entry
Exercise C1: Symmetry passes to the Perron vector
Exercise C2: Every conclusion fails for some non-negative matrix
Exercise C3: The Perron root is strictly monotone

19.2 Irreducibility and Graphs

Definition 19.2.1 Directed Graph of a Matrix; Walks and Paths
Lemma 19.2.1 Powers Count Walks
Lemma 19.2.2 Shortening a Walk to a Path
Definition 19.2.2 Strongly Connected
Definition 19.2.3 Irreducible Matrix
Lemma 19.2.3 Relabeling the Coordinates
Lemma 19.2.4 Reducible Means a Set of Vertices With No Exit
Example A reducible matrix that does not look it
Theorem 19.2.5 Irreducible If and Only If Strongly Connected
Theorem 19.2.6 Irreducibility Through a Power of $\mathbf{I} + \mathbf{A}$
Example The cycle, by one power
Theorem 19.2.7 Reducible Normal Form
Example A normal form with three blocks
Exercise A1
Exercise B1: Deciding irreducibility
Exercise B2: One power decides
Exercise B3: Eigenvalues from the normal form
Exercise C1: A necessary condition that is not sufficient
Exercise C2: The exponent $n - 1$ is sharp
Exercise C3: Irreducibility as growth of supports

19.3 The Perron–Frobenius Theorem

Example Three non-negative matrices that break Perron’s theorem
Theorem 19.3.1 The Spectral Radius of a Non-negative Matrix Is an Eigenvalue
Theorem 19.3.2 Perron–Frobenius Theorem
Example The theorem on a matrix with zeros
Corollary 19.3.3 The Left Perron Vector
Definition 19.3.1 Perron Root, Perron Vectors
Example An irreducible stochastic matrix
Exercise A1
Exercise B1: Does the theorem apply?
Exercise B2: Both Perron vectors
Exercise B3: A reducible matrix, clause by clause
Exercise C1: A positive eigenvector always belongs to the spectral radius
Exercise C2: What the limit loses
Exercise C3: Uniqueness through the left Perron vector

19.4 The Collatz–Wielandt Formula

Proposition 19.4.1 Subinvariance
Proposition 19.4.2 Superinvariance
Definition 19.4.1 Collatz–Wielandt Functions
Theorem 19.4.3 Collatz–Wielandt Formula
Corollary 19.4.4 Row and Column Sums Bound the Spectral Radius
Example Four bounds, and which one to keep
Example Trapping the spectral radius
Exercise A1
Exercise B1: A certified bracket
Exercise B2: When a sum bound is exact
Exercise B3: A weighted test vector
Exercise C1: Lower bounds from single entries
Exercise C2: Strict monotonicity
Exercise C3: The minimum need not be attained

19.5 Primitive Matrices

Definition 19.5.1 Primitive Matrix
Proposition 19.5.1 First Properties of Primitive Matrices
Theorem 19.5.2 Limit Theorem for Primitive Matrices
Example A Limit Computed Two Ways
Theorem 19.5.3 Primitivity from the Spectrum
Definition 19.5.2 Period
Theorem 19.5.4 The Peripheral Spectrum
Corollary 19.5.5 Primitivity from Walks
Example The Cyclic Permutation
Theorem 19.5.6 Wielandt’s Bound
Exercise A1
Exercise B1: Which are primitive?
Exercise B2: A limit without diagonalizing
Exercise B3: Period and peripheral eigenvalues
Exercise C1: Shifting by the identity
Exercise C2: Traces detect the period
Exercise C3: A finite test for primitivity

19.6 Markov Chains

Proposition 19.6.1 The Perron Root of a Stochastic Matrix
Theorem 19.6.2 Long-Run Behavior of a Markov Chain
Example A Chain that Cannot Be Diagonalized
Theorem 19.6.3 Averages of an Irreducible Chain
Example A Walk that Oscillates
Example Two Traps
Definition 19.6.1 Absorbing Chain
Lemma 19.6.4 Transient Mass Dies Out
Theorem 19.6.5 Absorbing Chains
Example Gambler’s Ruin
Exercise A1
Exercise B1: When does the long-run theorem apply?
Exercise B2: A three-state chain
Exercise B3: An unfair game
Exercise C1: The lazy chain
Exercise C2: The converse of the long-run theorem
Exercise C3: First-step analysis

19.7 Birkhoff's Theorem

Lemma 19.7.1 The Row and Column Sum Conditions
Theorem 19.7.2 Birkhoff’s Theorem
Corollary 19.7.3 Birkhoff’s Theorem with a Count
Corollary 19.7.4 A Positive Diagonal
Example Peeling a 4 × 4 matrix
Lemma 19.7.5 The Diagonal Is a Doubly Stochastic Image of the Spectrum
Proposition 19.7.6 Doubly Stochastic Maps Even Out
Example The averaging made visible
Exercise A1
Exercise B1: Which are corners?
Exercise B2: Peeling a 3 × 3 matrix
Exercise B3: Schur’s theorem by averaging
Exercise C1: Five permutation matrices can be needed
Exercise C2: Integer matrices with equal line sums
Exercise C3: The dimension, and a matrix that is not unistochastic

19.8 PageRank

Definition 19.8.1 Link Matrix
Example Three ways a web can fail to rank
Definition 19.8.2 Google Matrix, PageRank Vector
Theorem 19.8.1 The PageRank Vector
Theorem 19.8.2 The Eigenvalues of the Google Matrix
Proposition 19.8.3 Convergence at the Damping Rate
Example Four pages, one dangling
Exercise A1
Exercise B1: A three-page web
Exercise B2: A cycle of three pages
Exercise B3: Personalized jumps
Exercise C1: PageRank as a sum over paths
Exercise C2: When the bound is attained

19.9 M-Matrices

Definition 19.9.1 Z-Matrix
Lemma 19.9.1 Z-Matrices Are Shifts of Non-negative Matrices
Definition 19.9.2 M-Matrix
Lemma 19.9.2 The Smallest Real Eigenvalue of a Z-Matrix
Lemma 19.9.3 Test Vectors Survive Deletion
Theorem 19.9.4 Characterizations of Non-singular M-Matrices
Corollary 19.9.5 Symmetric M-Matrices Are Positive Definite
Proposition 19.9.6 The Second-Difference Matrix
Example The Case n = 4
Corollary 19.9.7 Productive Economies
Example Three Sectors
Exercise A1
Exercise B1: Which are non-singular M-matrices?
Exercise B2: A string with a free end
Exercise B3: A two-sector economy
Exercise C1: Raising the diagonal
Exercise C2: The singular case
Exercise C3: Non-negative dynamics

Perturbation Theory

20.1 Gershgorin Discs

Definition 20.1.1 Gershgorin Discs
Theorem 20.1.1 Gershgorin’s Theorem
Example Discs, eigenvectors, and where each eigenvalue sits
Corollary 20.1.2 Strict Diagonal Dominance Implies Invertibility
Proposition 20.1.3 Rescaling the Gershgorin Discs
Example Separating a disc by scaling
Theorem 20.1.4 Taussky’s Theorem
Corollary 20.1.5 Irreducible Diagonal Dominance Implies Invertibility
Example The second-difference matrix
Exercise A1
Exercise B1: Deciding invertibility
Exercise B2: An interval for a symmetric matrix
Exercise B3: Choosing the scaling
Exercise C1: Dominance and definiteness
Exercise C2: Irreducibility cannot be dropped

20.2 Other Inclusion Regions

Theorem 20.2.1 Brauer’s Ovals of Cassini
Example Ovals where discs fail
Definition 20.2.1 Numerical Range
Example The numerical range of a Jordan block
Proposition 20.2.2 Basic Properties of the Numerical Range
Lemma 20.2.3 Real and Imaginary Parts of a Matrix
Theorem 20.2.4 Toeplitz–Hausdorff Theorem
Proposition 20.2.5 The Numerical Range of a Normal Matrix
Theorem 20.2.6 Bendixson’s Theorem
Example A rectangle beats the discs
Exercise A1
Exercise B1: Invertibility from ovals
Exercise B2: A Bendixson rectangle
Exercise B3: Computing numerical ranges
Exercise C1: Direct sums
Exercise C2: When the numerical range is real, or a point
Exercise C3: The numerical radius

20.3 Continuity of Roots

Lemma 20.3.1 Cauchy’s Bound for the Roots
Theorem 20.3.2 Continuous Dependence of the Roots on the Coefficients
Theorem 20.3.3 Elsner’s Spectral Variation Bound
Example The Jordan block meets Elsner’s bound
Lemma 20.3.4 Eigenvalue Counts Are Constant Along a Path
Theorem 20.3.5 Gershgorin’s Counting Theorem
Corollary 20.3.6 An Isolated Disc Holds One Eigenvalue
Example Isolating a real eigenvalue by scaling
Theorem 20.3.7 Elsner’s Matching Bound
Exercise A1
Exercise B1: Cauchy’s bound
Exercise B2: Counting with discs
Exercise C1: Stability is an open condition
Exercise C2: Why one-sided bounds do not give a matching
Exercise C3: Sharpening Cauchy’s bound by rescaling

20.4 The Bauer–Fike Theorem

Lemma 20.4.1 A Perturbed Eigenvalue Forces a Large Resolvent
Theorem 20.4.2 Bauer–Fike Theorem
Corollary 20.4.3 Bauer–Fike for Normal Matrices
Theorem 20.4.4 Residual Bound
Example An error bar from one product
Example A large corner, separated eigenvalues
Theorem 20.4.5 Bauer–Fike for a Jordan Form
Exercise A1
Exercise B1: A Bauer–Fike region
Exercise B2: A residual certificate
Exercise B3: A defective bound
Exercise C1: One eigenvalue in each disc
Exercise C2: The best shift for a residual

20.5 The Hoffman–Wielandt Theorem

Lemma 20.5.1 A Fractional Pairing Is Never Cheaper
Theorem 20.5.2 Hoffman–Wielandt Theorem
Example A Hermitian and a diagonal matrix
Example Every pairing fails
Lemma 20.5.3 The Sorted Pairing Is Cheapest
Example Three numbers, six pairings
Corollary 20.5.4 Hoffman–Wielandt for Hermitian Matrices
Exercise A1
Exercise B1: A pair of normal matrices
Exercise B2: Hermitian, compared with Weyl
Exercise B3: Sorting
Exercise C1: The most expensive pairing
Exercise C2: Each eigenvalue keeps its own disc
Exercise C3: A Jordan block of any size

20.6 Hermitian Perturbations

Theorem 20.6.1 Residual Bound for Hermitian Matrices
Theorem 20.6.2 Kato–Temple Theorem
Example Bracketing the top eigenvalue
Theorem 20.6.3 Ostrowski’s Theorem
Example A tiny eigenvalue under a change of variables
Exercise A1
Exercise B1: Three bounds for one estimate
Exercise B2: Ostrowski’s factors
Exercise B3: The Rayleigh quotient minimizes the residual
Exercise C1: A residual that guarantees an eigenvalue
Exercise C2: Relative bounds need structured perturbations
Exercise C3: Kato–Temple is sharp

20.7 The Sylvester Equation Revisited

Definition 20.7.1 Separation
Proposition 20.7.1 Properties of the Separation
Theorem 20.7.2 Separation of Normal Matrices
Example A Normal Pair
Example Separation Far Below the Gap
Theorem 20.7.3 One-Sided Sylvester Bound
Corollary 20.7.4 Sylvester Bound for Positive Matrices
Example The Bound Can Be Attained
Exercise A1
Exercise B1: A positive Sylvester equation
Exercise B2: Separations of four pairs
Exercise B3: A symmetric Sylvester equation
Exercise C1: The separation is stable, and it measures a distance
Exercise C2: Interlaced spectra break the spectral-norm bound

20.8 Principal Angles

Lemma 20.8.1 Orthonormal Basis Matrices
Definition 20.8.1 Principal Angles
Proposition 20.8.2 Principal Angles Are Well Defined
Proposition 20.8.3 Principal Vectors
Theorem 20.8.4 Sines of Principal Angles
Theorem 20.8.5 The Distance Between Projections
Example Two Planes in Four Dimensions
Exercise A1
Exercise B1: Two planes in three dimensions
Exercise B2: Which projections are at distance one?
Exercise B3: Two lines
Exercise C1: Counting zero and right angles
Exercise C2: The smallest angle as a maximum

20.9 The Davis–Kahan Theorem

Example A tiny perturbation that turns the eigenvectors through 45°
Lemma 20.9.1 Moving Factors in and out of the Two Norms
Lemma 20.9.2 The Subspace Perturbation Equation
Theorem 20.9.3 The Davis–Kahan $\sin\Theta$ Theorem
Theorem 20.9.4 The $\sin\Theta$ Theorem, One-Sided Case
Corollary 20.9.5 Perturbation of a Single Eigenvector
Example The theorem and the corollary, side by side
Example A stable plane with unstable lines inside it
Exercise A1
Exercise B1: How far does the top eigenvector move?
Exercise B2: Which theorem applies?
Exercise B3: The same bounds for the projections
Exercise C1: A bound that needs only the perturbed matrix
Exercise C2: The constant in the eigenvector bound is sharp

20.10 Singular Values and Polar Factors

Theorem 20.10.1 Mirsky’s Theorem
Example Two matrices that differ in one entry
Theorem 20.10.2 Perturbation of the Square Root
Theorem 20.10.3 Perturbation of the Positive Polar Factor
Theorem 20.10.4 Perturbation of the Unitary Polar Factor
Example The polar factors of two nearby matrices
Exercise A1
Exercise B1: Mirsky by hand
Exercise B2: A square root that does not commute
Exercise B3: A nearly sharp instance
Exercise C1: The square root is continuous everywhere
Exercise C2: Both Eckart–Young lower bounds from perturbation theory
Exercise C3: The nearest unitary to an almost-unitary matrix

20.11 Condition Numbers of Eigenvalues

Lemma 20.11.1 Left and Right Eigenvectors of a Simple Eigenvalue
Theorem 20.11.2 Derivative of a Simple Eigenvalue
Definition 20.11.1 Condition Number of a Simple Eigenvalue
Proposition 20.11.3 Properties of the Eigenvalue Condition Number
Example The condition numbers of a triangular $2 \times 2$ matrix
Exercise A1
Exercise B1: Three condition numbers
Exercise B2: A derivative checked against the exact answer
Exercise B3: Invariance of the condition number
Exercise C1: Perfect conditioning characterizes normality
Exercise C2: The derivatives add up to the trace
Exercise C3: The adjugate at a simple eigenvalue

Matrix Inequalities

21.1 Doubly Stochastic Maps

Definition 21.1.1 T-transform
Proposition 21.1.1 T-transforms Are Doubly Stochastic
Example Three T-transforms, and two impostors
Lemma 21.1.2 One Averaging Step
Theorem 21.1.3 Hardy–Littlewood–Pólya Theorem
Example Four coordinates, two transforms
Corollary 21.1.4 Majorization Is Membership in a Permutation Polytope
Exercise A1
Exercise B1: Run the construction
Exercise B2: Determine which are majorizations
Exercise B3: Into the polytope
Exercise C1: Row-stochastic is not enough, twice over
Exercise C2: Transitivity, a second time
Exercise C3: The count $n - 1$ cannot be improved

21.2 Convex Functions of a Majorization

Theorem 21.2.1 Karamata’s Inequality
Example One majorization, four inequalities
Proposition 21.2.2 Convex Functions Detect Majorization
Proposition 21.2.3 Karamata for Weak Majorization
Definition 21.2.1 Schur-Convex Function
Definition 21.2.2 Schur-Concave Function
Example Four functions on $\mathbb{R}^n$
Theorem 21.2.4 A Symmetric Convex Function Is Schur-Convex
Corollary 21.2.5 The Product Is Schur-Concave
Lemma 21.2.6 Reading a Trace on an Orthonormal Basis
Lemma 21.2.7 Peierls’ Inequality
Theorem 21.2.8 The Trace of a Convex Function Is Convex
Example The logarithm of the determinant
Exercise A1
Exercise B1: Four consequences of one majorization
Exercise B2: Which are Schur-convex?
Exercise B3: Trace convexity on two-by-two matrices
Exercise C1: Entropy
Exercise C2: Three norms under majorization
Exercise C3: One convex function is not enough

21.3 Symmetric Gauge Functions

Definition 21.3.1 Symmetric Gauge Function
Example The p-norms, the Ky Fan gauges, and size one
Definition 21.3.2 Ky Fan Gauge
Proposition 21.3.1 Symmetric Gauges Are Monotone
Corollary 21.3.2 A Symmetric Gauge Is Trapped Between Two Norms
Lemma 21.3.3 Weak Majorization Is Domination plus Majorization
Example Filling from the bottom
Theorem 21.3.4 Symmetric Gauges Respect Majorization
Definition 21.3.3 Dual Gauge
Theorem 21.3.5 The Dual of a Symmetric Gauge
Exercise A1
Exercise B1: Which of these are symmetric gauges
Exercise B2: Filling from the bottom
Exercise B3: Monotonicity used twice
Exercise C1: Symmetric gauges detect weak majorization
Exercise C2: The dual of a Ky Fan gauge
Exercise C3: Where each hypothesis is used

21.4 Unitarily Invariant Norms

Definition 21.4.1 Unitarily Invariant Norm
Example The two familiar norms
Definition 21.4.2 Ky Fan k-Norms
Lemma 21.4.1 The Gauge of a Unitarily Invariant Norm
Lemma 21.4.2 Weak Subadditivity of the Singular Values
Theorem 21.4.3 Unitarily Invariant Norms Are Symmetric Gauges
Example The Schatten norms
Proposition 21.4.4 Basic Properties
Exercise A1
Exercise B1: Which of these are unitarily invariant norms
Exercise B2: Measuring one matrix in every way
Exercise B3: Moving a factor across
Exercise C1: A gauge built from two Ky Fan gauges
Exercise C2: How much scaling submultiplicativity can stand
Exercise C3: The correspondence in the smallest case

21.5 The Trace Inequality

Definition 21.5.1 Doubly Substochastic Matrix
Lemma 21.5.1 Substochastic Pairing
Theorem 21.5.2 Von Neumann’s Trace Inequality
Example A strict case and an equality case
Corollary 21.5.3 Duality of Unitarily Invariant Norms
Exercise A1
Exercise B1: Both sides of the inequality
Exercise B2: The trace against the trace norm
Exercise B3: A weight matrix
Exercise C1: The triangle inequality for the trace norm
Exercise C2: The nearest unitary, again

21.6 Ky Fan Dominance

Theorem 21.6.1 Ky Fan Dominance Theorem
Corollary 21.6.2 Eckart–Young Theorem in Every Unitarily Invariant Norm
Example One matrix, four norms
Lemma 21.6.3 Top Sums of a Symmetric List
Corollary 21.6.4 The Polar Factor Is Nearest in Every Unitarily Invariant Norm
Corollary 21.6.5 Compressions Are Contractions
Example Weak majorization is the most that holds
Exercise A1
Exercise B1: Dominance by hand
Exercise B2: Best approximations of a 2 by 2 matrix
Exercise B3: A compression
Exercise C1: Dominance for sums
Exercise C2: Distance to the singular matrices, in every norm
Exercise C3: Unitary matrices are far apart

21.7 Lidskii's Theorem in Majorization Form

Example A pair to keep in mind
Theorem 21.7.1 Lidskii’s Theorem, Convex Form
Theorem 21.7.2 Lidskii’s Theorem, Norm Form
Corollary 21.7.3 Hoffman–Wielandt for Hermitian Matrices, Again
Theorem 21.7.4 Mirsky’s Theorem in Every Unitarily Invariant Norm
Exercise A1
Exercise B1: Running the three consequences
Exercise B2: Singular values of a one-entry change
Exercise B3: A bound with no norm in sight
Exercise C1: The Schatten norms
Exercise C2: What the dilation costs

21.8 Operator Convex Functions

Lemma 21.8.1 Three Ways to Move the Functional Calculus
Proposition 21.8.2 Combining Operator Convex Functions
Theorem 21.8.3 Four Operator Convex Functions
Example The Cube Is Convex and Not Operator Convex
Definition 21.8.1 Contraction
Lemma 21.8.4 Unitary Dilation of a Contraction
Theorem 21.8.5 Hansen–Pedersen–Jensen Inequality
Corollary 21.8.6 Compression
Exercise A1
Exercise B1: Which are operator convex?
Exercise B2: A dilation by hand
Exercise B3: Compression of a square
Exercise C1: The square, without the dilation
Exercise C2: Shrinking the matrix
Exercise C3: What the trace does not see

21.9 Loewner Matrices

Definition 21.9.1 Divided Difference
Lemma 21.9.1 Divided Differences Are Continuous
Definition 21.9.2 Loewner Matrix
Example The Loewner Matrix of the Square
Example A Cauchy Matrix
Definition 21.9.3 Monotone of Order n
Lemma 21.9.2 The Two-Resolution Identity
Lemma 21.9.3 Continuity of the Functional Calculus
Theorem 21.9.4 The Derivative of a Matrix Function
Theorem 21.9.5 Loewner’s Matrix Criterion
Corollary 21.9.6 The Criterion at Order Two
Exercise A1
Exercise B1: Loewner matrices by hand
Exercise B2: A derivative, two ways
Exercise B3: Refuting order two
Exercise C1: Powers, directly
Exercise C2: The logarithm at order two
Exercise C3: Orders are nested

21.10 Loewner's Theorem

Proposition 21.10.1 Riemann Sums of a Continuous Matrix Function Converge
Definition 21.10.1 Integral of a Continuous Matrix-Valued Function
Lemma 21.10.2 The Integral of a Positive Semidefinite Integrand
Theorem 21.10.3 (A7) The Theorem of Pick and Nevanlinna
Theorem 21.10.4 Loewner’s Theorem
Lemma 21.10.5 The Integral That Represents a Power
Lemma 21.10.6 Composites of Operator Monotone Functions
Lemma 21.10.7 Pointwise Limits Stay Operator Monotone
Corollary 21.10.8 The Operator Monotone Powers
Corollary 21.10.9 The Logarithm Is Operator Monotone
Corollary 21.10.10 Two Operator Convex Functions from the Logarithm
Example The exponential is not operator monotone
Exercise A1
Exercise B1: One matrix integral
Exercise B2: The constant for the square root
Exercise B3: Which are operator monotone?
Exercise C1: When the integral loses information
Exercise C2: The cube, by a Loewner matrix
Exercise C3: Half of the representation, by hand

21.11 Means and Matrix Cauchy–Schwarz

Lemma 21.11.1 The Off-Diagonal Block of a Positive Semidefinite Matrix
Theorem 21.11.2 Arithmetic–Geometric Mean Inequality for Matrices
Theorem 21.11.3 Cauchy–Schwarz for Unitarily Invariant Norms
Definition 21.11.1 Geometric Mean of Positive Definite Matrices
Theorem 21.11.4 Properties of the Geometric Mean
Corollary 21.11.5 Harmonic, Geometric and Arithmetic
Exercise A1
Exercise B1: A geometric mean, exactly
Exercise B2: The two inequalities on one pair
Exercise B3: Means of commuting matrices
Exercise C1: The determinant of a geometric mean
Exercise C2: The geometric mean solves an equation
Exercise C3: Cauchy–Schwarz for the Ky Fan norms, directly

21.12 Golden–Thompson

Lemma 21.12.1 Lie’s Product Formula
Lemma 21.12.2 Powers of a Product of Two Positive Matrices
Lemma 21.12.3 The Trace Power Inequality
Theorem 21.12.4 The Golden–Thompson Inequality
Example The inequality on a two-by-two family
Example The three-matrix version fails
Lemma 21.12.5 A Convex Function Lies Above Its Tangent
Theorem 21.12.6 Klein’s Inequality
Lemma 21.12.7 The Derivative of the Logarithm
Corollary 21.12.8 Non-negativity of the Relative Entropy
Exercise A1
Exercise B1: Both sides, exactly
Exercise B2: The trace power inequality on integers
Exercise B3: Klein with the exponential
Exercise C1: Two out of three is enough
Exercise C2: The symmetric Lie formula
Exercise C3: When is the relative entropy zero?

Affine and Projective Geometry

22.1 Affine Spaces and Affine Maps

Definition 22.1.1 Affine Space
Lemma 22.1.1 First consequences of Chasles
Proposition 22.1.2 The two forms of the definition agree
Example Four affine spaces
Proposition 22.1.3 Choice of Origin
Definition 22.1.2 Affine Combination
Proposition 22.1.4 Affine combinations are exactly the origin-free ones
Definition 22.1.3 Affine Map
Theorem 22.1.5 An Affine Map Is Linear Plus a Translation
Example Two points are not enough in the plane
Theorem 22.1.6 Composition, Inverses, and the Affine Group
Proposition 22.1.7 The Block Matrix of an Affine Map
Example Composing a shear and a quarter turn
Exercise A1
Exercise B1: Determine which are affine
Exercise B2: Block matrices
Exercise B3: The four-point plane
Exercise C1: Fixed points
Exercise C2: Affine maps on two points, over two fields
Exercise C3: Conjugating a translation

22.2 Flats, Independence and Coordinates

Definition 22.2.1 Flat
Proposition 22.2.1 Flats Are the Cosets
Proposition 22.2.2 Intersections of Flats
Definition 22.2.2 Join of Flats
Definition 22.2.3 Parallel Flats
Proposition 22.2.3 Parallelism
Theorem 22.2.4 Intersection and Join of Two Flats
Example Two lines in space, twice
Lemma 22.2.5 Affine Independence by Differences
Definition 22.2.4 Affine Frame
Theorem 22.2.6 Barycentric Coordinates
Example Reading a triangle
Proposition 22.2.7 The Medians Meet at the Centroid
Theorem 22.2.8 An Affine Map Is Determined by a Frame
Proposition 22.2.9 Points inside a proper flat do not determine an affine map
Theorem 22.2.10 Flats Are Exactly the Solution Sets
Example Equations for a plane in four-space
Exercise A1
Exercise B1: Two flats in four-space
Exercise B2: Barycentric arithmetic
Exercise B3: From parameters to equations and back
Exercise C1: Affine maps and flats
Exercise C2: The midpoint quadrilateral
Exercise C3: Medians over the field with three elements

22.3 Convex Polyhedra, Geometrically

Definition 22.3.1 Face of a Polyhedron
Proposition 22.3.1 Faces Are Polyhedra, and There Are Finitely Many
Definition 22.3.2 Edge, Facet
Proposition 22.3.2 Three Descriptions of a Corner
Theorem 22.3.3 A Bounded Polyhedron Is the Hull of Its Vertices
Proposition 22.3.4 An Edge Joins Two Vertices
Example The faces of a cube
Example The faces of a simplex
Proposition 22.3.5 The Optimal Set Is a Face
Example A linear program and its picture
Proposition 22.3.6 Dual Variables Are the Weights of the Active Normals
Example A slab, and a quadrant
Exercise A1
Exercise B1: Vertices and faces of a region
Exercise B2: Reading the dual off the normals
Exercise B3: Faces of the cross-polytope
Exercise C1: A face of a face
Exercise C2: The two notions of face agree for a polyhedron
Exercise C3: The optimal face has no better vertex outside it

22.4 Euclidean Motions

Definition 22.4.1 Euclidean Motion
Theorem 22.4.1 Every Motion Is Affine
Corollary 22.4.2 Motions Are Bijections
Definition 22.4.2 Direct and Opposite Motions
Proposition 22.4.3 The Euclidean Group
Definition 22.4.3 Translation, Rotation, Reflection, Glide Reflection
Theorem 22.4.4 Classification of the Motions of the Plane
Example Naming a plane motion
Example Two mirrors
Definition 22.4.4 Screw Motion, Rotatory Reflection
Theorem 22.4.5 Classification of the Motions of Space
Example Naming a space motion
Exercise A1
Exercise B1: Classify three plane motions
Exercise B2: A space motion
Exercise B3: A motion is determined by few points
Exercise C1: Reflections generate the motions
Exercise C2: Matching two congruent frames
Exercise C3: Motions of a finite set

22.5 Affine and Euclidean Quadrics

Definition 22.5.1 Quadric
Proposition 22.5.1 Affine Substitution Is Congruence of the Big Matrix
Definition 22.5.2 Affine Equivalence of Quadric Polynomials
Definition 22.5.3 Center of a Quadric
Proposition 22.5.2 When a Center Exists
Example The parabola is centerless
Theorem 22.5.3 Affine Classification of Real Quadrics
Theorem 22.5.4 Euclidean Classification of Real Quadrics
Example One conic, two classifications
Exercise A1
Exercise B1: Centers
Exercise B2: Affine type
Exercise B3: Principal axes
Exercise C1: Which quadrics are determined by their points
Exercise C2: Over another field
Exercise C3: The center as a projection

22.6 Projective Space

Definition 22.6.1 Projective Space
Proposition 22.6.1 Points Are Lines Through the Origin
Definition 22.6.2 Homogeneous Coordinates
Theorem 22.6.2 The Standard Affine Chart
Proposition 22.6.3 Completing an Affine Line
Definition 22.6.3 Projective Subspace
Lemma 22.6.4 A Projective Subspace Remembers Its Subspace
Proposition 22.6.5 Meet and Join
Theorem 22.6.6 Projective Dimension Formula
Corollary 22.6.7 Two Lines in a Projective Plane Meet
Proposition 22.6.8 Two Points Determine a Line
Proposition 22.6.9 The Number of Points of a Finite Projective Space
Example The Fano plane
Exercise A1
Exercise B1: Meeting at infinity
Exercise B2: Joins and meets
Exercise B3: A projective plane over three elements
Exercise C1: Other charts
Exercise C2: Counting subspaces
Exercise C3: Where the affine formula goes wrong

22.7 Projective Transformations

Definition 22.7.1 Projective Transformation
Proposition 22.7.1 Projectivities Compose and Invert
Proposition 22.7.2 Projectivities Preserve Subspaces, Joins and Meets
Theorem 22.7.3 Projectivities and Scalars
Definition 22.7.2 General Position
Lemma 22.7.4 Normalizing a Frame
Theorem 22.7.5 Fundamental Theorem of Projective Geometry
Example Moving the standard frame
Proposition 22.7.6 What Fixes the Coordinate Points
Proposition 22.7.7 Over the Two-Element Field, $n+1$ Points Suffice
Definition 22.7.3 Cross-Ratio
Proposition 22.7.8 Computing the Cross-Ratio
Theorem 22.7.9 Invariance and Completeness of the Cross-Ratio
Example A cross-ratio, before and after
Proposition 22.7.10 Projection From a Point Is a Projectivity
Theorem 22.7.11 Affine Maps Are the Projectivities Fixing Infinity
Exercise A1
Exercise B1: A projectivity of the line
Exercise B2: General position
Exercise B3: Cross-ratio
Exercise C1: Sharp triple transitivity, and a count
Exercise C2: Rearranging the four points
Exercise C3: Cross-ratio characterizes projectivities of a line

22.8 Duality

Lemma 22.8.1 Passing Between $U$ and $\mathbb{P}(U)$
Definition 22.8.1 Dual Projective Space
Proposition 22.8.2 Points of the Dual Are Hyperplanes
Example A line and its point
Theorem 22.8.3 The Duality Correspondence
Theorem 22.8.4 Dualizing Twice Returns the Original
Proposition 22.8.5 Duality and Projectivities
Theorem 22.8.6 The Duality Principle
Corollary 22.8.7 Two Points, Two Lines
Exercise A1
Exercise B1: Lines and dual points
Exercise B2: Dimension bookkeeping
Exercise B3: Dualize a statement
Exercise C1: Counting in a finite projective plane
Exercise C2: A form makes a self-duality
Exercise C3: What the correspondence does to a chain

22.9 Desargues and Pappus

Definition 22.9.1 Triangles, and the Two Perspectives
Lemma 22.9.1 Scaling Three Collinear Points
Lemma 22.9.2 Perspective from a Point Gives an Axis
Theorem 22.9.3 Desargues’s Theorem
Example Desargues with exact coordinates
Theorem 22.9.4 Pappus’s Theorem
Example Pappus with exact coordinates
Exercise A1
Exercise B1: A Desargues configuration
Exercise B2: A Pappus configuration
Exercise B3: Concurrency from collinearity
Exercise C1: Desargues in space
Exercise C2: Pappus over the two smallest fields
Exercise C3: Why the side hypothesis is there

22.10 Conics and Lines in Space

Definition 22.10.1 Projective Quadric, Conic, Smooth Quadric
Theorem 22.10.1 Classification of Projective Quadrics
Corollary 22.10.2 The Conics of a Projective Plane
Example Classifying a conic by hand
Lemma 22.10.3 A Conic Containing a Line Is Degenerate
Theorem 22.10.4 Five Points Determine a Conic
Example A conic through five points
Theorem 22.10.5 Projection from a Point of a Conic
Example Pythagorean triples from one point
Definition 22.10.2 Polar Line, Tangent Line
Proposition 22.10.6 Reciprocity and Tangency
Corollary 22.10.7 The Dual Conic
Definition 22.10.3 Plücker Coordinates of a Line
Proposition 22.10.8 The Plücker Point Determines the Line
Theorem 22.10.9 The Plücker Relation and the Klein Quadric
Example A line, its Plücker point, and back
Exercise A1
Exercise B1: Classify these conics
Exercise B2: A conic through five points
Exercise B3: Plücker coordinates
Exercise C1: All rational points of a circle
Exercise C2: The Klein quadric

Algebras and Representations

23.1 Associative Algebras

Definition 23.1.1 Subalgebra
Example Six subalgebras
Definition 23.1.2 Algebra Homomorphism, Kernel and Image
Definition 23.1.3 Isomorphic Algebras
Definition 23.1.4 The Subalgebra Generated by a Set
Proposition 23.1.1 What the Generated Subalgebra Contains
Proposition 23.1.2 The Algebra Generated by One Operator
Example Two polynomial algebras
Definition 23.1.5 Group Algebra
Example Three group algebras
Theorem 23.1.3 Left Multiplication Embeds an Algebra in Its Own Operators
Example Left multiplication for the upper triangular algebra
Definition 23.1.6 Commutant and Center
Proposition 23.1.4 Properties of the Commutant
Example Commutants of three matrices
Proposition 23.1.5 The Center of the Matrix Algebra Is the Scalars
Exercise A1
Exercise B1: Determine which are subalgebras
Exercise B2: A commutant
Exercise B3: Cayley for the quaternions
Exercise C1: The center of a group algebra
Exercise C2: Generated by two matrix units
Exercise C3: Is the group algebra ever a field?

23.2 Ideals and Quotients

Definition 23.2.1 Left and Right Ideals
Example Ideals in five algebras
Lemma 23.2.1 The Matrix Unit Product Rule
Theorem 23.2.2 The Matrix Algebra Has No Proper Two-Sided Ideals
Corollary 23.2.3 Homomorphisms out of a Matrix Algebra Are Injective
Proposition 23.2.4 The Left Ideals of $M_n(F)$
Definition 23.2.2 Quotient Algebra
Theorem 23.2.5 First Isomorphism Theorem for Algebras
Example The group algebra of a cyclic group
Example Upper triangular matrices modulo their strictly upper part
Exercise A1
Exercise B1: Determine which are ideals
Exercise B2: A quotient computed
Exercise B3: An ideal generated
Exercise C1: All the ideals of the upper triangular algebra
Exercise C2: Simplicity over a small field, and a failure
Exercise C3: Left ideals and null spaces

23.3 Simple and Semisimple Algebras

Definition 23.3.1 Simple Algebra
Proposition 23.3.1 Maps Out of a Simple Algebra
Definition 23.3.2 Representation of an Algebra, and Invariant Subspaces
Definition 23.3.3 Irreducible, or Simple, $A$ -space
Definition 23.3.4 Semisimple Action, Semisimple Algebra
Lemma 23.3.2 Splitting Is Inherited by Invariant Subspaces
Theorem 23.3.3 Complete Reducibility
Example Upper Triangular Matrices Are Not Semisimple
Example Matrix Algebras Are Semisimple
Proposition 23.3.4 A Semisimple Algebra Has No Other Kind of Representation
Definition 23.3.5 Radical of an Algebra
Lemma 23.3.5 A Nilpotent Ideal Is Invisible
Proposition 23.3.6 A Semisimple Algebra Has Zero Radical
Theorem 23.3.7 The Two Meanings of Semisimple Agree
Exercise A1
Exercise B1: Which actions split?
Exercise B2: A two-dimensional algebra
Exercise B3: Semisimple operators
Exercise C1: The diagonal algebra
Exercise C2: The radical is never everything

23.4 Schur's Lemma

Definition 23.4.1 $A$ -Map, and Isomorphism of $A$ -spaces
Theorem 23.4.1 Schur’s Lemma
Example A Real Irreducible Representation with Commutant $\mathbb{C}$
Lemma 23.4.2 A Family and the Algebra It Generates
Corollary 23.4.3 An Operator Commuting with an Irreducible Family Is a Scalar
Corollary 23.4.4 Over an Algebraically Closed Field, Commutative Means One-Dimensional
Corollary 23.4.5 Commuting Operators Have a Common Eigenvector
Proposition 23.4.6 Closed Under Adjoints Implies Semisimple
Exercise A1
Exercise B1: An irreducibility test
Exercise B2: The quarter turn, over two fields
Exercise B3: A common eigenvector
Exercise C1: A commutant that is a field
Exercise C2: Scalar commutant without irreducibility

23.5 Burnside and the Double Commutant

Lemma 23.5.1 An Irreducible Algebra Moves One Vector Everywhere
Theorem 23.5.2 Burnside’s Theorem
Corollary 23.5.3 An Irreducible Multiplicative Set Spans the Whole Algebra
Lemma 23.5.4 Matching on One Vector
Theorem 23.5.5 Double Commutant Theorem
Corollary 23.5.6 The Commutant of a Single Operator
Example The Two Extremes
Exercise A1
Exercise B1: Determine which are irreducible
Exercise B2: A commutant and a double commutant
Exercise B3: One theorem, once
Exercise C1: The rank-one step needs its hypothesis
Exercise C2: Commutants under a change of basis
Exercise C3: Is this look-alike a theorem?

23.6 The Structure Theorem

Definition 23.6.1 Product of algebras
Example Three products, seen from two sides
Theorem 23.6.1 Wedderburn’s Structure Theorem, Algebraically Closed Case
Corollary 23.6.2 Counting Dimensions in the Wedderburn Form
Example The group algebra of a cyclic group of order four
Example An algebra already in Wedderburn form
Exercise A1
Exercise B1: Determine which are semisimple
Exercise B2: A dimension count
Exercise B3: The group algebra of a group of order three
Exercise C1: Simple plus semisimple
Exercise C2: How often each irreducible appears
Exercise C3: Change the field

23.7 Group Representations

Definition 23.7.1 Representation of a group
Definition 23.7.2 Subrepresentation
Definition 23.7.3 Equivalence of representations
Definition 23.7.4 Irreducible representation
Theorem 23.7.1 Representations of $G$ are representations of $F[G]$
Lemma 23.7.2 When the group order is invertible
Theorem 23.7.3 Maschke’s Theorem
Example Maschke fails when the characteristic divides the order
Corollary 23.7.4 Complete Reducibility of Group Representations
Example The irreducible complex representations of a cyclic group
Example The irreducible complex representations of the symmetric group on three letters
Exercise A1
Exercise B1: Which of these are representations?
Exercise B2: Averaging an inner product
Exercise B3: Decomposing a permutation representation
Exercise C1: One-dimensional representations and the commutator
Exercise C2: Maschke over a field of the right characteristic
Exercise C3: The contragredient representation

23.8 Characters and Orthogonality

Definition 23.8.1 Conjugate elements, conjugacy class
Example The conjugacy classes of the symmetric group on three letters
Definition 23.8.2 Character
Lemma 23.8.1 Order of an Element
Proposition 23.8.2 Basic properties of characters
Definition 23.8.3 Class function
Proposition 23.8.3 The class functions have dimension the number of classes
Definition 23.8.4 The inner product of class functions
Lemma 23.8.4 The average of a representation is the projection onto the fixed space
Lemma 23.8.5 The trace of a two-sided multiplication
Proposition 23.8.6 The representation on the space of linear maps
Theorem 23.8.7 Orthogonality of Irreducible Characters
Corollary 23.8.8 Irreducibility criterion
Example Checking the standard representation by its character
Theorem 23.8.9 The Irreducible Characters Are a Basis of the Class Functions
Corollary 23.8.10 The sum of the squares of the degrees
Corollary 23.8.11 Orthogonality of the columns
Example The character table of the symmetric group on three letters
Example The character table of a cyclic group of order four
Exercise A1
Exercise B1: A character computed and decomposed
Exercise B2: Which of these are characters?
Exercise B3: Degree-one characters of a cyclic group
Exercise C1: Counting fixed points
Exercise C2: Degree-one characters form a group
Exercise C3: The second orthogonality relation

23.9 Finite Abelian Groups and the Fourier Transform

Definition 23.9.1 Cyclic group
Definition 23.9.2 Direct product of groups
Theorem 23.9.1 Characters of an Abelian Group Are Homomorphisms
Example The characters of a cyclic group
Example The Klein four-group
Definition 23.9.3 Dual group
Proposition 23.9.2 The Dual Group Is a Group
Proposition 23.9.3 The Dual Group Has the Same Size
Theorem 23.9.4 The Dual of a Product of Cyclic Groups
Definition 23.9.4 Character matrix
Definition 23.9.5 Fourier transform on a finite abelian group
Theorem 23.9.5 Fourier Inversion on a Finite Abelian Group
Theorem 23.9.6 The Character Matrix Is the Fourier Matrix
Theorem 23.9.7 The Group Algebra of an Abelian Group Splits
Theorem 23.9.8 Circulants Are the Group Algebra of the Cyclic Group
Example The case $n = 4$ , checked against Chapter 12
Exercise A1
Exercise B1: The character table of the group of order three
Exercise B2: A product of two cyclic groups
Exercise B3: A transform and its inversion
Exercise C1: The idempotents that do the splitting
Exercise C2: The double dual needs no choices
Exercise C3: The same theory over a finite field

23.10 What the Chapter Buys

Exercise A1
Exercise B1: Two group algebras of order six
Exercise B2: What the sum of squares allows at order eight
Exercise C1: The circulants as a semisimple algebra

Computation and Applications

24.1 Floating Point and Backward Error

Definition 24.1.1 The floating-point model
Example The model we compute in
Lemma 24.1.1 Accumulated rounding
Theorem 24.1.2 Backward Error of an Inner Product
Definition 24.1.2 Forward and backward error
Definition 24.1.3 Backward stability
Definition 24.1.4 Mixed forward-backward stability
Theorem 24.1.3 Forward Error from Backward Error
Example Two ways to solve a quadratic
Exercise A1
Exercise B1: The $\gamma$ calculus
Exercise B2: Summation
Exercise B3: The model by hand
Exercise C1: When backward stability says nothing
Exercise C2: An unstable way to compute a variance

24.2 Elimination, Pivoting and Cost

Theorem 24.2.1 Elimination Produces Schur Complements
Example Two steps, two Schur complements
Corollary 24.2.2 Pivots Are Ratios of Leading Minors
Proposition 24.2.3 The Cost of Elimination
Lemma 24.2.4 One Row of Substitution
Theorem 24.2.5 Backward Error of a Triangular Solve
Theorem 24.2.6 Backward Error of a Factorization
Definition 24.2.1 Growth factor
Proposition 24.2.7 Partial Pivoting Bounds the Multipliers
Theorem 24.2.8 Growth Under Partial Pivoting
Example A matrix that really grows
Example The tiny pivot, in the model
Theorem 24.2.9 Cholesky Does Not Grow
Exercise A1
Exercise B1: A Schur complement by two routes
Exercise B2: Growth, with and without a swap
Exercise B3: The Cholesky entry bound
Exercise C1: Column diagonal dominance needs no pivoting
Exercise C2: The growth bound is attained for every $n$

24.3 Least Squares in Practice

Theorem 24.3.1 Conditioning of the Least-Squares Problem
Theorem 24.3.2 The Normal Equations Lose Twice the Digits
Example A matrix where one route survives and the other does not
Theorem 24.3.3 Backward Stability of One Reflection
Example Three columns and three answers
Example The same vector, the two signs
Exercise A1
Exercise B1: Reading the bound
Exercise B2: Where the product goes singular
Exercise B3: One reflection, by hand
Exercise C1: The squared term is attained
Exercise C2: Why the residual has to appear
Exercise C3: A reflection applied to a matrix

24.4 The Power Method

Definition 24.4.1 Power Iteration
Theorem 24.4.1 The Power Method
Example Every iterate exactly
Corollary 24.4.2 Hermitian Matrices: the Rayleigh Quotient Converges Twice as Fast
Example The method that never converges
Definition 24.4.2 Inverse Iteration
Theorem 24.4.3 Inverse Iteration Converges to the Nearest Eigenvector
Example Aiming at the smaller eigenvalue
Definition 24.4.3 Rayleigh Quotient Iteration
Theorem 24.4.4 Rayleigh Quotient Iteration Converges Cubically
Example Three steps, exactly
Exercise A1
Exercise B1: A rate, read off the spectrum
Exercise B2: Choosing a shift
Exercise B3: Deflating a symmetric matrix
Exercise C1: What the squaring really needs
Exercise C2: Two eigenvalues of equal modulus, over the reals
Exercise C3: A small residual certifies an eigenpair

24.5 The QR Algorithm

Definition 24.5.1 The QR Iteration
Proposition 24.5.1 Every Step Is a Unitary Similarity
Example Two matrices the iteration cannot move
Theorem 24.5.2 QR Iterates Factor the Powers
Theorem 24.5.3 Convergence of the First Column
Example The unshifted algorithm on a rotation
Proposition 24.5.4 A QR Step Preserves Hessenberg Form
Proposition 24.5.5 An Exact Shift Deflates in One Step
Example The shift repairs the rotation, and deflates a symmetric example
Example The subdiagonal shrinking at the predicted rate
Exercise A1
Exercise B1: One step by hand
Exercise B2: Fixed points
Exercise B3: A shift that deflates
Exercise C1: Hessenberg form is not enough by itself
Exercise C2: Hermitian iterates and the Rayleigh quotient
Exercise C3: Why the powers are the right object

24.6 Krylov Subspaces

Definition 24.6.1 Krylov Subspace
Proposition 24.6.1 Krylov Spaces: Nesting, Dimension, Invariance
Theorem 24.6.2 The Arnoldi Process
Theorem 24.6.3 The Lanczos Recurrence
Example A breakdown at step two
Definition 24.6.2 Ritz Values and Ritz Vectors
Theorem 24.6.4 Ritz Values Interlace, and Their Residual Is One Number
Example Ritz values closing in on the extremes
Theorem 24.6.5 A Rate for the Largest Ritz Value
Exercise A1
Exercise B1: Dimensions
Exercise B2: Two Arnoldi steps
Exercise B3: Lanczos on a tridiagonal matrix
Exercise C1: Ritz values from the other end
Exercise C2: Shift invariance, and what it costs
Exercise C3: When the Krylov space is everything

24.7 Steepest Descent and Conjugate Gradients

Definition 24.7.1 The Energy Inner Product and the Energy Norm
Proposition 24.7.1 The Solution Minimizes the Energy Functional
Definition 24.7.2 Steepest Descent
Lemma 24.7.2 Kantorovich’s Inequality
Theorem 24.7.3 Convergence of Steepest Descent
Example The bound is attained
Definition 24.7.3 The Conjugate Gradient Iteration
Theorem 24.7.4 Conjugate Gradients: Orthogonality and Optimality
Corollary 24.7.5 Finite Termination
Example Two distinct eigenvalues, two steps
Definition 24.7.4 Chebyshev Polynomials
Lemma 24.7.6 Chebyshev Polynomials: Size Inside and Growth Outside
Theorem 24.7.7 Convergence of Conjugate Gradients
Exercise A1
Exercise B1: Steepest descent by hand
Exercise B2: Conjugate gradients by hand
Exercise B3: Chebyshev by recurrence
Exercise C1: Sharpness of Kantorovich
Exercise C2: Finite termination, from polynomials
Exercise C3: What preconditioning does to the spectrum

24.8 Lax Pairs and the Toda Flow

Definition 24.8.1 Lax Pair
Example A curve of matrices with a frozen spectrum
Theorem 24.8.1 Lax Pairs Are Isospectral
Corollary 24.8.2 Constant $\mathbf{B}$ : the flow is conjugation by the exponential
Definition 24.8.2 The Toda Flow
Proposition 24.8.3 The Toda Flow in Coordinates
Example The $2 \times 2$ flow, twice
Lemma 24.8.4 Skew plus upper triangular, uniquely
Theorem 24.8.5 One QR Step Is One Unit of Toda Time
Exercise A1
Exercise B1: A Lax pair verified
Exercise B2: The bracket by hand
Exercise B3: One QR step on an exponential
Exercise C1: The power sums are constants of the motion
Exercise C2: How far $\mathbf{B}$ is from being determined
Exercise C3: Symmetry constrains $\mathbf{B}$

24.9 Vibrations

Definition 24.9.1 The mass–spring model
Definition 24.9.2 Mass–spring system
Example Three systems
Lemma 24.9.1 The scalar oscillator
Theorem 24.9.2 Normal Modes
Example Three equal masses, four equal springs
Definition 24.9.3 Generalized Rayleigh quotient
Corollary 24.9.3 Frequencies from the Rayleigh Quotient
Example Guessing the lowest mode of the chain
Proposition 24.9.4 Stiffening Raises, Loading Lowers
Proposition 24.9.5 Pinning Interlaces the Frequencies
Example Pinning the middle mass
Exercise A1
Exercise B1: Two masses, two springs
Exercise B2: Bounding the slowest mode
Exercise B3: Stiffening a chain
Exercise C1: The free chain drifts
Exercise C2: Adding a mass cannot raise a frequency, and can lower it a lot

24.10 Principal Components

Definition 24.10.1 Data matrix, mean and centered data matrix
Example Centering three data sets
Lemma 24.10.1 Distance to a flat, and where its translate wants to be
Theorem 24.10.2 The Best-Fitting Affine Subspace
Definition 24.10.2 Sample covariance matrix
Example Three covariance matrices
Proposition 24.10.3 The Covariance Matrix and the Singular Value Decomposition
Definition 24.10.3 Principal directions and components
Theorem 24.10.4 Variance Captured by the Principal Directions
Example Four points, done exactly
Exercise A1
Exercise B1: A four-point cloud
Exercise B2: Variance direction by direction
Exercise B3: Changing the units
Exercise C1: The mean is forced, and the projection is not a shortcut
Exercise C2: Total variance is a trace, and what that buys

24.11 Graph Laplacians

Definition 24.11.1 Graph Laplacian
Proposition 24.11.1 First Properties of the Laplacian
Example A Laplacian computed twice
Theorem 24.11.2 The Kernel of the Laplacian
Definition 24.11.2 Fiedler value
Proposition 24.11.3 Positive Fiedler Value Means Connected
Proposition 24.11.4 The Fiedler Value as a Minimum
Example Two triangles and a bridge
Proposition 24.11.5 Adding an Edge Raises No Eigenvalue
Lemma 24.11.6 Unimodularity of Incidence Minors
Proposition 24.11.7 A Spanning Tree Has $m - 1$ Edges
Theorem 24.11.8 Matrix-Tree Theorem
Example The four-vertex graph, counted both ways
Exercise A1
Exercise B1: The four-cycle
Exercise B2: Counting trees in a bowtie
Exercise B3: Which minors are $\pm 1$ ?
Exercise C1: Cayley’s formula
Exercise C2: Weighted graphs

24.12 The Fast Fourier Transform

Definition 24.12.1 The transform matrix
Definition 24.12.2 The even-odd permutation, the twiddle matrix and the butterfly
Theorem 24.12.1 The Radix-Two Factorization
Example The factorization for $n = 4$
Theorem 24.12.2 The Cost of the Fast Fourier Transform
Example A transform of length eight
Corollary 24.12.3 Convolution in $O(n\log n)$
Corollary 24.12.4 Solving a Circulant System in $O(n\log n)$
Exercise A1
Exercise B1: A transform of length four
Exercise B2: A transform of length eight
Exercise B3: A product of polynomials by convolution
Exercise C1: Splitting into three
Exercise C2: The fourth power of the transform

24.13 Fast Matrix Multiplication

Definition 24.13.1 Arithmetic cost of a matrix product
Definition 24.13.2 The exponent of matrix multiplication
Proposition 24.13.1 The exponent is at least two
Theorem 24.13.2 Strassen’s identity
Example Seven products on integer data
Theorem 24.13.3 The cost of the recursion
Proposition 24.13.4 The classical product has a small entrywise error
Proposition 24.13.5 Strassen’s two-by-two product satisfies a norm bound
Theorem 24.13.6 Strassen’s algorithm has no useful entrywise error bound
Example A small entry lost entirely
Exercise A1
Exercise B1: Seven products by hand
Exercise B2: One block, one level
Exercise B3: Counting the recursion
Exercise C1: Would twenty-three products for three-by-three beat Strassen?
Exercise C2: Where the entrywise bound really fails
Exercise C3: Only the products recurse