2
Vector Spaces, Bases, Linear Maps
11
2.1
Groups, Rings, and Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.2
Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
2.3
Linear Independence, Subspaces . . . . . . . . . . . . . . . . . . . . . . . . .
25
2.4
Bases of a Vector Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
2.5
Linear Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
2.6 Quotient Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
2.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
3
Matrices and Linear Maps
45
3.1 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
3.2 Haar Basis Vectors and a Glimpse at Wavelets . . . . . . . . . . . . . . . . .
61
3.3 The Effect of a Change of Bases on Matrices . . . . . . . . . . . . . . . . . .
77
3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
80
4
Direct Sums, The Dual Space, Duality
81
4.1 Sums, Direct Sums, Direct Products
. . . . . . . . . . . . . . . . . . . . . .
81
4.2 The Dual Space E∗ and Linear Forms . . . . . . . . . . . . . . . . . . . . . .
94
4.3 Hyperplanes and Linear Forms . . . . . . . . . . . . . . . . . . . . . . . . . . 107
4.4 Transpose of a Linear Map and of a Matrix . . . . . . . . . . . . . . . . . . . 108
4.5 The Four Fundamental Subspaces . . . . . . . . . . . . . . . . . . . . . . . . 117
4.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
5
Determinants
123
5.1 Permutations, Signature of a Permutation . . . . . . . . . . . . . . . . . . . 123
5.2 Alternating Multilinear Maps . . . . . . . . . . . . . . . . . . . . . . . . . . 126
5.3 Definition of a Determinant . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
5.4 Inverse Matrices and Determinants . . . . . . . . . . . . . . . . . . . . . . . 136
5.5 Systems of Linear Equations and Determinants . . . . . . . . . . . . . . . . 140
5.6 Determinant of a Linear Map . . . . . . . . . . . . . . . . . . . . . . . . . . 141
5.7 The Cayley–Hamilton Theorem . . . . . . . . . . . . . . . . . . . . . . . . . 141
3
4
CONTENTS
5.8
Further Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
6
Gaussian Elimination, LU, Cholesky, Echelon Form
149
6.1
Motivating Example: Curve Interpolation
. . . . . . . . . . . . . . . . . . . 149
6.2
Gaussian Elimination and LU -Factorization . . . . . . . . . . . . . . . . . . 153
6.3
Gaussian Elimination of Tridiagonal Matrices . . . . . . . . . . . . . . . . . 175
6.4
SPD Matrices and the Cholesky Decomposition . . . . . . . . . . . . . . . . 178
6.5
Reduced Row Echelon Form . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
6.6
Transvections and Dilatations . . . . . . . . . . . . . . . . . . . . . . . . . . 197
6.7
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
7
Vector Norms and Matrix Norms
205
7.1
Normed Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
7.2
Matrix Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
7.3
Condition Numbers of Matrices . . . . . . . . . . . . . . . . . . . . . . . . . 223
7.4
An Application of Norms: Inconsistent Linear Systems . . . . . . . . . . . . 231
7.5
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
8
Iterative Methods for Solving Linear Systems
235
8.1 Convergence of Sequences of Vectors and Matrices . . . . . . . . . . . . . . . 235
8.2 Convergence of Iterative Methods . . . . . . . . . . . . . . . . . . . . . . . . 238
8.3 Methods of Jacobi, Gauss-Seidel, and Relaxation
. . . . . . . . . . . . . . . 240
8.4 Convergence of the Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
8.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
9
Euclidean Spaces
253
9.1 Inner Products, Euclidean Spaces . . . . . . . . . . . . . . . . . . . . . . . . 253
9.2 Orthogonality, Duality, Adjoint of a Linear Map . . . . . . . . . . . . . . . . 261
9.3 Linear Isometries (Orthogonal Transformations) . . . . . . . . . . . . . . . . 271
9.4 The Orthogonal Group, Orthogonal Matrices . . . . . . . . . . . . . . . . . . 274
9.5 QR-Decomposition for Invertible Matrices . . . . . . . . . . . . . . . . . . . 276
9.6 Some Applications of Euclidean Geometry . . . . . . . . . . . . . . . . . . . 278
9.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
10 QR-Decomposition for Arbitrary Matrices
281
10.1 Orthogonal Reflections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
10.2 QR-Decomposition Using Householder Matrices . . . . . . . . . . . . . . . . 284
10.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
11 Hermitian Spaces
291
11.1 Hermitian Spaces, Pre-Hilbert Spaces . . . . . . . . . . . . . . . . . . . . . . 291
11.2 Orthogonality, Duality, Adjoint of a Linear Map . . . . . . . . . . . . . . . . 300
11.3 Linear Isometries (Also Called Unitary Transformations) . . . . . . . . . . . 304
CONTENTS
5
11.4 The Unitary Group, Unitary Matrices . . . . . . . . . . . . . . . . . . . . . . 306
11.5 Orthogonal Projections and Involutions . . . . . . . . . . . . . . . . . . . . . 308
11.6 Dual Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
11.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
12 Eigenvectors and Eigenvalues
317
12.1 Eigenvectors and Eigenvalues of a Linear Map . . . . . . . . . . . . . . . . . 317
12.2 Reduction to Upper Triangular Form . . . . . . . . . . . . . . . . . . . . . . 324
12.3 Location of Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326
12.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328
13 Spectral Theorems
331
13.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
13.2 Normal Linear Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
13.3 Self-Adjoint and Other Special Linear Maps . . . . . . . . . . . . . . . . . . 340
13.4 Normal and Other Special Matrices . . . . . . . . . . . . . . . . . . . . . . . 346
13.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
14 Bilinear Forms and Their Geometries
351
14.1 Bilinear Forms
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351
14.2 Sesquilinear Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
14.3 Orthogonality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362
14.4 Adjoint of a Linear Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366
14.5 Isometries Associated with Sesquilinear Forms . . . . . . . . . . . . . . . . . 369
14.6 Totally Isotropic Subspaces. Witt Decomposition . . . . . . . . . . . . . . . 372
14.7 Witt’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385
14.8 Symplectic Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389
14.9 Orthogonal Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393
15 Introduction to The Finite Elements Method
401
15.1 A One-Dimensional Problem: Bending of a Beam . . . . . . . . . . . . . . . 401
15.2 A Two-Dimensional Problem: An Elastic Membrane . . . . . . . . . . . . . . 412
15.3 Time-Dependent Boundary Problems . . . . . . . . . . . . . . . . . . . . . . 415
16 Singular Value Decomposition and Polar Form
423
16.1 Singular Value Decomposition for Square Matrices . . . . . . . . . . . . . . . 423
16.2 Singular Value Decomposition for Rectangular Matrices . . . . . . . . . . . . 431
16.3 Ky Fan Norms and Schatten Norms . . . . . . . . . . . . . . . . . . . . . . . 434
16.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435
17 Applications of SVD and Pseudo-inverses
437
17.1 Least Squares Problems and the Pseudo-inverse . . . . . . . . . . . . . . . . 437
17.2 Data Compression and SVD . . . . . . . . . . . . . . . . . . . . . . . . . . . 445
6
CONTENTS
17.3 Principal Components Analysis (PCA) . . . . . . . . . . . . . . . . . . . . . 446
17.4 Best Affine Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454
18 Quadratic Optimization Problems
459
18.1 Quadratic Optimization: The Positive Definite Case . . . . . . . . . . . . . . 459
18.2 Quadratic Optimization: The General Case
. . . . . . . . . . . . . . . . . . 467
18.3 Maximizing a Quadratic Function on the Unit Sphere . . . . . . . . . . . . . 471
18.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476
19 Basics of Affine Geometry
477
19.1 Affine Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477
19.2 Examples of Affine Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484
19.3 Chasles’s Identity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486
19.4 Affine Combinations, Barycenters . . . . . . . . . . . . . . . . . . . . . . . . 487
19.5 Affine Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 490
19.6 Affine Independence and Affine Frames . . . . . . . . . . . . . . . . . . . . . 495
19.7 Affine Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 500
19.8 Affine Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507
19.9 Affine Geometry: A Glimpse . . . . . . . . . . . . . . . . . . . . . . . . . . . 509
19.10Affine Hyperplanes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 512
19.11Intersection of Affine Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . 514
19.12Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517
20 Polynomials, Ideals and PID’s
531
20.1 Multisets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531
20.2 Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 532
20.3 Euclidean Division of Polynomials . . . . . . . . . . . . . . . . . . . . . . . . 538
20.4 Ideals, PID’s, and Greatest Common Divisors . . . . . . . . . . . . . . . . . 540
20.5 Factorization and Irreducible Factors in K[X] . . . . . . . . . . . . . . . . . 548
20.6 Roots of Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 552
20.7 Polynomial Interpolation (Lagrange, Newton,
Hermite) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 559
21 UFD’s, Noetherian Rings, Hilbert’s Basis Theorem
565
21.1 Unique Factorization Domains (Factorial Rings) . . . . . . . . . . . . . . . . 565
21.2 The Chinese Remainder Theorem . . . . . . . . . . . . . . . . . . . . . . . . 579
21.3 Noetherian Rings and Hilbert’s Basis Theorem . . . . . . . . . . . . . . . . . 584
21.4 Futher Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 588
22 Annihilating Polynomials; Primary Decomposition
589
22.1 Annihilating Polynomials and the Minimal Polynomial . . . . . . . . . . . . 589
22.2 Minimal Polynomials of Diagonalizable Linear Maps . . . . . . . . . . . . . . 591
22.3 The Primary Decomposition Theorem . . . . . . . . . . . . . . . . . . . . . . 595
CONTENTS
7
22.4 Nilpotent Linear Maps and Jordan Form . . . . . . . . . . . . . . . . . . . . 600
23 Tensor Algebras
605
23.1 Tensors Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 605
23.2 Bases of Tensor Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 613
23.3 Some Useful Isomorphisms for Tensor Products . . . . . . . . . . . . . . . . 615
23.4 Duality for Tensor Products . . . . . . . . . . . . . . . . . . . . . . . . . . . 616
23.5 Tensor Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 618
23.6 Symmetric Tensor Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 624
23.7 Bases of Symmetric Powers
. . . . . . . . . . . . . . . . . . . . . . . . . . . 627
23.8 Some Useful Isomorphisms for Symmetric Powers . . . . . . . . . . . . . . . 630
23.9 Duality for Symmetric Powers . . . . . . . . . . . . . . . . . . . . . . . . . . 630
23.10Symmetric Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 632
23.11Exterior Tensor Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 634
23.12Bases of Exterior Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 638
23.13Some Useful Isomorphisms for Exterior Powers . . . . . . . . . . . . . . . . . 640
23.14Duality for Exterior Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . 641
23.15Exterior Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 643
23.16The Hodge ∗-Operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 646
23.17Testing Decomposability; Left and Right Hooks . . . . . . . . . . . . . . . . 648
23.18Vector-Valued Alternating Forms . . . . . . . . . . . . . . . . . . . . . . . . 655
23.19The Pfaffian Polynomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 658
24 Introduction to Modules; Modules over a PID
663
24.1 Modules over a Commutative Ring . . . . . . . . . . . . . . . . . . . . . . . 663
24.2 Finite Presentations of Modules . . . . . . . . . . . . . . . . . . . . . . . . . 671
24.3 Tensor Products of Modules over a Commutative Ring . . . . . . . . . . . . 676
24.4 Extension of the Ring of Scalars . . . . . . . . . . . . . . . . . . . . . . . . . 679
24.5 The Torsion Module Associated With An Endomorphism . . . . . . . . . . . 682
24.6 Torsion Modules over a PID; Primary Decomposition . . . . . . . . . . . . . 690
24.7 Finitely Generated Modules over a PID . . . . . . . . . . . . . . . . . . . . . 695
25 Normal Forms; The Rational Canonical Form
711
25.1 The Rational Canonical Form . . . . . . . . . . . . . . . . . . . . . . . . . . 711
25.2 The Rational Canonical Form, Second Version . . . . . . . . . . . . . . . . . 716
25.3 The Jordan Form Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . 717
25.4 The Smith Normal Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 719
26 Topology
733
26.1 Metric Spaces and Normed Vector Spaces . . . . . . . . . . . . . . . . . . . . 733
26.2 Topological Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 737
26.3 Continuous Functions, Limits . . . . . . . . . . . . . . . . . . . . . . . . . . 742
26.4 Connected Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 747
8
CONTENTS
26.5 Compact Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 753
26.6 Continuous Linear and Multilinear Maps . . . . . . . . . . . . . . . . . . . . 767
26.7 Normed Affine Spaces
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 772
26.8 Futher Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 772
27 A Detour On Fractals
773
27.1 Iterated Function Systems and Fractals . . . . . . . . . . . . . . . . . . . . . 773
28 Differential Calculus
781
28.1 Directional Derivatives, Total Derivatives . . . . . . . . . . . . . . . . . . . . 781
28.2 Jacobian Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 789
28.3 The Implicit and The Inverse Function Theorems . . . . . . . . . . . . . . . 794
28.4 Tangent Spaces and Differentials . . . . . . . . . . . . . . . . . . . . . . . . . 798
28.5 Second-Order and Higher-Order Derivatives . . . . . . . . . . . . . . . . . . 799
28.6 Taylor’s formula, Faà di Bruno’s formula . . . . . . . . . . . . . . . . . . . . 805
28.7 Vector Fields, Covariant Derivatives, Lie Brackets . . . . . . . . . . . . . . . 809
28.8 Futher Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 811
29 Extrema of Real-Valued Functions
813
29.1 Local Extrema and Lagrange Multipliers . . . . . . . . . . . . . . . . . . . . 813
29.2 Using Second Derivatives to Find Extrema . . . . . . . . . . . . . . . . . . . 822
29.3 Using Convexity to Find Extrema . . . . . . . . . . . . . . . . . . . . . . . . 825
29.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 833
30 Newton’s Method and its Generalizations
835
30.1 Newton’s Method for Real Functions of a Real Argument . . . . . . . . . . . 835
30.2 Generalizations of Newton’s Method . . . . . . . . . . . . . . . . . . . . . . 836
30.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 842
31 Appendix: Zorn’s Lemma; Some Applications
843
31.1 Statement of Zorn’s Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . 843
31.2 Proof of the Existence of a Basis in a Vector Space . . . . . . . . . . . . . . 844
31.3 Existence of Maximal Proper Ideals . . . . . . . . . . . . . . . . . . . . . . . 845
Bibliography
845
Chapter 1