Basics of Algebra, Topology, and Differential Calculus by Jean Gallier - HTML preview

Introduction

9

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