Fundamentals of Linear Algebra and Optimization Jean Gallier and Jocelyn Quaintance Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104, USA e-mail: [email protected] c Jean Gallier (cid:13) February 23, 2017 2 Figure 1: Cover page from Bourbaki, Fascicule VI, Livre II, Alg`ebre, 1962 3 Figure 2: Page 156 from Bourbaki, Fascicule VI, Livre II, Alg`ebre, 1962 4 Contents 1 Vector Spaces, Bases, Linear Maps 11 1.1 Motivations: Linear Combinations, Linear Independence, Rank . . . . . . . 11 1.2 Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.3 Linear Independence, Subspaces . . . . . . . . . . . . . . . . . . . . . . . . 27 1.4 Bases of a Vector Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 1.5 Linear Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 1.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2 Matrices and Linear Maps 45 2.1 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.2 Haar Basis Vectors and a Glimpse at Wavelets . . . . . . . . . . . . . . . . 61 2.3 The Effect of a Change of Bases on Matrices . . . . . . . . . . . . . . . . . 78 2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 3 Direct Sums, Affine Maps, The Dual Space, Duality 83 3.1 Direct Products, Sums, and Direct Sums . . . . . . . . . . . . . . . . . . . . 83 3.2 Affine Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 3.3 The Dual Space E and Linear Forms . . . . . . . . . . . . . . . . . . . . . 100 (cid:3) 3.4 Hyperplanes and Linear Forms . . . . . . . . . . . . . . . . . . . . . . . . . 118 3.5 Transpose of a Linear Map and of a Matrix . . . . . . . . . . . . . . . . . . 119 3.6 The Four Fundamental Subspaces . . . . . . . . . . . . . . . . . . . . . . . 126 3.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 4 Gaussian Elimination, LU, Cholesky, Echelon Form 131 4.1 Motivating Example: Curve Interpolation . . . . . . . . . . . . . . . . . . . 131 4.2 Gaussian Elimination and LU-Factorization . . . . . . . . . . . . . . . . . . 135 4.3 Gaussian Elimination of Tridiagonal Matrices . . . . . . . . . . . . . . . . . 161 4.4 SPD Matrices and the Cholesky Decomposition . . . . . . . . . . . . . . . . 164 4.5 Reduced Row Echelon Form . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 4.6 Transvections and Dilatations . . . . . . . . . . . . . . . . . . . . . . . . . . 186 4.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 5 Determinants 193 5.1 Permutations, Signature of a Permutation . . . . . . . . . . . . . . . . . . . 193 5 6 CONTENTS 5.2 Alternating Multilinear Maps . . . . . . . . . . . . . . . . . . . . . . . . . . 197 5.3 Definition of a Determinant . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 5.4 Inverse Matrices and Determinants . . . . . . . . . . . . . . . . . . . . . . . 208 5.5 Systems of Linear Equations and Determinants . . . . . . . . . . . . . . . . 211 5.6 Determinant of a Linear Map . . . . . . . . . . . . . . . . . . . . . . . . . . 212 5.7 The Cayley–Hamilton Theorem . . . . . . . . . . . . . . . . . . . . . . . . . 213 5.8 Permanents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 5.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 5.10 Further Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 6 Vector Norms and Matrix Norms 223 6.1 Normed Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 6.2 Matrix Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 6.3 Condition Numbers of Matrices . . . . . . . . . . . . . . . . . . . . . . . . . 242 6.4 An Application of Norms: Inconsistent Linear Systems . . . . . . . . . . . . 251 6.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252 7 Eigenvectors and Eigenvalues 255 7.1 Eigenvectors and Eigenvalues of a Linear Map . . . . . . . . . . . . . . . . . 255 7.2 Reduction to Upper Triangular Form . . . . . . . . . . . . . . . . . . . . . . 262 7.3 Location of Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267 7.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269 8 Iterative Methods for Solving Linear Systems 271 8.1 Convergence of Sequences of Vectors and Matrices . . . . . . . . . . . . . . 271 8.2 Convergence of Iterative Methods . . . . . . . . . . . . . . . . . . . . . . . . 274 8.3 Methods of Jacobi, Gauss-Seidel, and Relaxation . . . . . . . . . . . . . . . 276 8.4 Convergence of the Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 281 8.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288 9 Euclidean Spaces 289 9.1 Inner Products, Euclidean Spaces . . . . . . . . . . . . . . . . . . . . . . . . 289 9.2 Orthogonality, Duality, Adjoint of a Linear Map . . . . . . . . . . . . . . . 297 9.3 Linear Isometries (Orthogonal Transformations) . . . . . . . . . . . . . . . . 309 9.4 The Orthogonal Group, Orthogonal Matrices . . . . . . . . . . . . . . . . . 312 9.5 QR-Decomposition for Invertible Matrices . . . . . . . . . . . . . . . . . . . 314 9.6 Some Applications of Euclidean Geometry . . . . . . . . . . . . . . . . . . . 318 9.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319 10 QR-Decomposition for Arbitrary Matrices 321 10.1 Orthogonal Reflections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321 10.2 QR-Decomposition Using Householder Matrices . . . . . . . . . . . . . . . . 324 10.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329 CONTENTS 7 11 Hermitian Spaces 331 11.1 Hermitian Spaces, Pre-Hilbert Spaces . . . . . . . . . . . . . . . . . . . . . 331 11.2 Orthogonality, Duality, Adjoint of a Linear Map . . . . . . . . . . . . . . . 340 11.3 Linear Isometries (Also Called Unitary Transformations) . . . . . . . . . . . 345 11.4 The Unitary Group, Unitary Matrices . . . . . . . . . . . . . . . . . . . . . 347 11.5 Orthogonal Projections and Involutions . . . . . . . . . . . . . . . . . . . . 350 11.6 Dual Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353 11.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356 12 Spectral Theorems 359 12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359 12.2 Normal Linear Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359 12.3 Self-Adjoint and Other Special Linear Maps . . . . . . . . . . . . . . . . . . 368 12.4 Normal and Other Special Matrices . . . . . . . . . . . . . . . . . . . . . . . 375 12.5 Conditioning of Eigenvalue Problems . . . . . . . . . . . . . . . . . . . . . . 378 12.6 Rayleigh Ratios and the Courant-Fischer Theorem . . . . . . . . . . . . . . 381 12.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389 13 Introduction to The Finite Elements Method 391 13.1 A One-Dimensional Problem: Bending of a Beam . . . . . . . . . . . . . . . 391 13.2 A Two-Dimensional Problem: An Elastic Membrane . . . . . . . . . . . . . 402 13.3 Time-Dependent Boundary Problems . . . . . . . . . . . . . . . . . . . . . . 405 14 Singular Value Decomposition and Polar Form 413 14.1 Singular Value Decomposition for Square Matrices . . . . . . . . . . . . . . 413 14.2 Singular Value Decomposition for Rectangular Matrices . . . . . . . . . . . 421 14.3 Ky Fan Norms and Schatten Norms . . . . . . . . . . . . . . . . . . . . . . 424 14.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425 15 Applications of SVD and Pseudo-Inverses 427 15.1 Least Squares Problems and the Pseudo-Inverse . . . . . . . . . . . . . . . . 427 15.2 Properties of the Pseudo-Inverse . . . . . . . . . . . . . . . . . . . . . . . . 432 15.3 Data Compression and SVD . . . . . . . . . . . . . . . . . . . . . . . . . . . 437 15.4 Principal Components Analysis (PCA) . . . . . . . . . . . . . . . . . . . . . 438 15.5 Best Affine Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . 445 15.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 448 16 Annihilating Polynomials; Primary Decomposition 451 16.1 Annihilating Polynomials and the Minimal Polynomial . . . . . . . . . . . . 451 16.2 Minimal Polynomials of Diagonalizable Linear Maps . . . . . . . . . . . . . 457 16.3 The Primary Decomposition Theorem . . . . . . . . . . . . . . . . . . . . . 463 16.4 Nilpotent Linear Maps and Jordan Form . . . . . . . . . . . . . . . . . . . . 469 8 CONTENTS 17 Topology 475 17.1 Metric Spaces and Normed Vector Spaces . . . . . . . . . . . . . . . . . . . 475 17.2 Topological Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481 17.3 Continuous Functions, Limits . . . . . . . . . . . . . . . . . . . . . . . . . . 490 17.4 Continuous Linear and Multilinear Maps . . . . . . . . . . . . . . . . . . . . 497 17.5 The Contraction Mapping Theorem . . . . . . . . . . . . . . . . . . . . . . 502 17.6 Futher Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503 17.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503 18 Differential Calculus 505 18.1 Directional Derivatives, Total Derivatives . . . . . . . . . . . . . . . . . . . 505 18.2 Jacobian Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 518 18.3 The Implicit and The Inverse Function Theorems . . . . . . . . . . . . . . . 526 18.4 Second-Order and Higher-Order Derivatives . . . . . . . . . . . . . . . . . . 530 18.5 Taylor’s Formula, Fa`a di Bruno’s Formula . . . . . . . . . . . . . . . . . . . 535 18.6 Futher Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539 18.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539 19 Quadratic Optimization Problems 541 19.1 Quadratic Optimization: The Positive Definite Case . . . . . . . . . . . . . 541 19.2 Quadratic Optimization: The General Case . . . . . . . . . . . . . . . . . . 549 19.3 Maximizing a Quadratic Function on the Unit Sphere . . . . . . . . . . . . 553 19.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 558 20 Schur Complements and Applications 561 20.1 Schur Complements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 561 20.2 SPD Matrices and Schur Complements . . . . . . . . . . . . . . . . . . . . . 563 20.3 SP Semidefinite Matrices and Schur Complements . . . . . . . . . . . . . . 565 21 Convex Sets, Cones, -Polyhedra 567 H 21.1 What is Linear Programming? . . . . . . . . . . . . . . . . . . . . . . . . . 567 21.2 Affine Subsets, Convex Sets, Hyperplanes, Half-Spaces . . . . . . . . . . . . 569 21.3 Cones, Polyhedral Cones, and -Polyhedra . . . . . . . . . . . . . . . . . . 572 H 22 Linear Programs 579 22.1 Linear Programs, Feasible Solutions, Optimal Solutions . . . . . . . . . . . 579 22.2 Basic Feasible Solutions and Vertices . . . . . . . . . . . . . . . . . . . . . . 585 23 The Simplex Algorithm 593 23.1 The Idea Behind the Simplex Algorithm . . . . . . . . . . . . . . . . . . . . 593 23.2 The Simplex Algorithm in General . . . . . . . . . . . . . . . . . . . . . . . 602 23.3 How Perform a Pivoting Step Efficiently . . . . . . . . . . . . . . . . . . . . 609 23.4 The Simplex Algorithm Using Tableaux . . . . . . . . . . . . . . . . . . . . 612 CONTENTS 9 23.5 Computational Efficiency of the Simplex Method . . . . . . . . . . . . . . . 622 24 Linear Programming and Duality 625 24.1 Variants of the Farkas Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . 625 24.2 The Duality Theorem in Linear Programming . . . . . . . . . . . . . . . . . 630 24.3 Complementary Slackness Conditions . . . . . . . . . . . . . . . . . . . . . 639 24.4 Duality for Linear Programs in Standard Form . . . . . . . . . . . . . . . . 640 24.5 The Dual Simplex Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 643 24.6 The Primal-Dual Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 649 25 Extrema of Real-Valued Functions 661 25.1 Local Extrema and Lagrange Multipliers . . . . . . . . . . . . . . . . . . . . 661 25.2 Using Second Derivatives to Find Extrema . . . . . . . . . . . . . . . . . . . 671 25.3 Using Convexity to Find Extrema . . . . . . . . . . . . . . . . . . . . . . . 674 25.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 684 26 Newton’s Method and Its Generalizations 685 26.1 Newton’s Method for Real Functions of a Real Argument . . . . . . . . . . 685 26.2 Generalizations of Newton’s Method . . . . . . . . . . . . . . . . . . . . . . 686 26.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 692 27 Basics of Hilbert Spaces 693 27.1 The Projection Lemma, Duality . . . . . . . . . . . . . . . . . . . . . . . . 693 27.2 Farkas–Minkowski Lemma in Hilbert Spaces . . . . . . . . . . . . . . . . . . 710 28 General Results of Optimization Theory 713 28.1 Existence of Solutions of an Optimization Problem . . . . . . . . . . . . . . 713 28.2 Gradient Descent Methods for Unconstrained Problems . . . . . . . . . . . 727 28.3 Conjugate Gradient Methods for Unconstrained Problems . . . . . . . . . . 743 28.4 Gradient Projection for Constrained Optimization . . . . . . . . . . . . . . 753 28.5 Penalty Methods for Constrained Optimization . . . . . . . . . . . . . . . . 756 28.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 758 29 Introduction to Nonlinear Optimization 759 29.1 The Cone of Feasible Directions . . . . . . . . . . . . . . . . . . . . . . . . . 759 29.2 The Karush–Kuhn–Tucker Conditions . . . . . . . . . . . . . . . . . . . . . 772 29.3 Hard Margin Support Vector Machine . . . . . . . . . . . . . . . . . . . . . 784 29.4 Lagrangian Duality and Saddle Points . . . . . . . . . . . . . . . . . . . . . 794 29.5 Uzawa’s Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 810 29.6 Handling Equality Constraints Explicitly . . . . . . . . . . . . . . . . . . . . 816 29.7 Conjugate Function and Legendre Dual Function . . . . . . . . . . . . . . . 823 29.8 Some Techniques to Obtain a More Useful Dual Program . . . . . . . . . . 833 29.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 842 10 CONTENTS 30 Soft Margin Support Vector Machines 845 30.1 Soft Margin Support Vector Machines; (SVM ) . . . . . . . . . . . . . . . . 846 s1 30.2 Soft Margin Support Vector Machines; (SVM ) . . . . . . . . . . . . . . . . 855 s2 30.3 Soft Margin Support Vector Machines; (SVM ) . . . . . . . . . . . . . . . 861 s2(cid:48) 30.4 Soft Margin SVM; (SVM ) . . . . . . . . . . . . . . . . . . . . . . . . . . . 875 s3 30.5 Soft Margin Support Vector Machines; (SVM ) . . . . . . . . . . . . . . . . 878 s4 30.6 Soft Margin SVM; (SVM ) . . . . . . . . . . . . . . . . . . . . . . . . . . . 885 s5 30.7 Summary and Comparison of the SVM Methods . . . . . . . . . . . . . . . 887 31 Total Orthogonal Families in Hilbert Spaces 899 31.1 Total Orthogonal Families, Fourier Coefficients . . . . . . . . . . . . . . . . 899 31.2 The Hilbert Space l2(K) and the Riesz-Fischer Theorem . . . . . . . . . . . 907 Bibliography 916