Finite-Dimensional Linear Algebra / Edition 1

by Mark S. Gockenbach

Overview

Linear algebra forms the basis for much of modern mathematics—theoretical, applied, and computational. Finite-Dimensional Linear Algebra provides a solid foundation for the study of advanced mathematics and discusses applications of linear algebra to such diverse areas as combinatorics, differential equations, optimization, and approximation.

The author begins with an overview of the essential themes of the book: linear equations, best approximation, and diagonalization. He then takes students through an axiomatic development of vector spaces, linear operators, eigenvalues, norms, and inner products. In addition to discussing the special properties of symmetric matrices, he covers the Jordan canonical form, an important theoretical tool, and the singular value decomposition, a powerful tool for computation. The final chapters present introductions to numerical linear algebra and analysis in vector spaces, including a brief introduction to functional analysis (infinite-dimensional linear algebra).

Drawing on material from the author’s own course, this textbook gives students a strong theoretical understanding of linear algebra. It offers many illustrations of how linear algebra is used throughout mathematics.

Product Details

ISBN-13:	9781439815632
Publisher:	Taylor & Francis
Publication date:	05/06/2010
Series:	Discrete Mathematics and Its Applications , #59
Edition description:	New Edition
Pages:	674
Product dimensions:	6.40(w) x 9.30(h) x 1.40(d)

About the Author

Mark S. Gockenbach is a professor and chair of the Department of Mathematical Sciences at Michigan Technological University.

Table of Contents

Preface xv

About the author xxi

1 Some problems posed on vector spaces 1

1.1 Linear equations 1

1.1.1 Systems of linear algebraic equations 1

1.1.2 Linear ordinary differential equations 4

1.1.3 Some interpretation: The structure of the solution set to a linear equation 5

1.1.4 Finite fields and applications in discrete mathematics 7

1.2 Best approximation 8

1.2.1 Overdetermined linear systems 8

1.2.2 Best approximation by a polynomial 11

1.3 Diagonalization 13

1.4 Summary 17

2 Fields and vector spaces 19

2.1 Fields 19

2.1.1 Definition and examples 19

2.1.2 Basic properties of fields 21

2.2 Vector spaces 29

2.2.1 Examples of vector spaces 31

2.3 Subspaces 38

2.4 Linear combinations and spanning sets 43

2.5 Linear independence 50

2.6 Basis and dimension 57

2.7 Properties of bases 66

2.8 Polynomial interpolation and the Lagrange basis 73

2.8.1 Secret sharing 77

2.9 Continuous piecewise polynomial functions 82

2.9.1 Continuous piecewise linear functions 84

2.9.2 Continuous piecewise quadratic functions 87

2.9.3 Error in polynomial interpolation 90

3 Linear operators 93

3.1 Linear operators 93

3.1.1 Matrix operators 95

3.2 More properties of linear operators 101

3.2.1 Vector spaces of operators 101

3.2.2 The matrix of a linear operator on Euclidean spaces 101

3.2.3 Derivative and differential operators 103

3.2.4 Representing spanning sets and bases using matrices 103

3.2.5 The transpose of a matrix 104

3.3 Isomorphic vector spaces 107

3.3.1 Injective and surjective functions; inverses 108

3.3.2 The matrix of a linear operator on general vector spaces 111

3.4 Linear operator equations 116

3.4.1 Homogeneous linear equations 117

3.4.2 Inhomogeneous linear equations 118

3.4.3 General solutions 120

3.5 Existence and uniqueness of solutions 124

3.5.1 The kernel of a linear operator and injectivity 124

3.5.2 The rank of a linear operator and surjectivity 126

3.5.3 Existence and uniqueness 128

3.6 The fundamental theorem; inverse operators 131

3.6.1 The inverse of a linear operator 133

3.6.2 The inverse of a matrix 134

3.7 Gaussian elimination 142

3.7.1 Computing A^-1 148

3.7.2 Fields other than R 149

3.8 Newton's method 153

3.9 Linear ordinary differential equations 158

3.9.1 The dimension of ker(L) 158

3.9.2 Finding a basis for ker(L) 161

3.9.2.1 The easy case: Distinct real roots 162

3.9.2.2 The case of repeated real roots 162

3.9.2.3 The case of complex roots 163

3.9.3 The Wronskian test for linear independence 163

3.9.4 The Vandermonde matrix 166

3.10 Graph theory 168

3.10.1 The incidence matrix of a graph 168

3.10.2 Walks and matrix multiplication 169

3.10.3 Graph isomorphisms 171

3.11 Coding theory 175

3.11.1 Generator matrices; encoding and decoding 177

3.11.2 Error correction 179

3.11.3 The probability of errors 181

3.12 Linear programming 183

3.12.1 Specification of linear programming problems 184

3.12.2 Basic theory 186

3.12.3 The simplex method 191

3.12.3.1 Finding an initial BFS 196

3.12.3.2 Unbounded LPs 199

3.12.3.3 Degeneracy and cycling 200

3.12.4 Variations on the standard LPs 202

4 Determinants and eigenvalues 205

4.1 The determinant function 206

4.1.1 Permutations 210

4.1.2 The complete expansion of the determinant 212

4.2 Further properties of the determinant function 217

4.3 Practical computation of det (A) 221

4.3.1 A recursive formula for det (A) 224

4.3.2 Cramer's rule 226

4.4 A note about polynomials 230

4.5 Eigenvalues and the characteristic polynomial 232

4.5.1 Eigenvalues of real matrix 235

4.6 Diagonalization 241

4.7 Eigenvalues of linear operators 251

4.8 Systems of linear ODEs 257

4.8.1 Complex eigenvalues 259

4.8.2 Solving the initial value problem 260

4.8.3 Linear systems in matrix form 261

4.9 Integer programming 265

4.9.1 Totally unimodular matrices 265

4.9.2 Transportation problems 268

5 The Jordan canonical form 273

5.1 Invariant subspaces 273

5.1.1 Direct sums 276

5.1.2 Eigenspaces and generalized eigenspaces 277

5.2 Generalized eigenspaces 283

5.2.1 Appendix: Beyond generalized eigenspaces 290

5.2.2 The Cayley-Hamilton theorem 294

5.3 Nilpotent operators 300

5.4 The Jordan canonical form of a matrix 309

5.5 The matrix exponential 318

5.5.1 Definition of the matrix exponential 319

5.5.2 Computing the matrix exponential 319

5.6 Graphs and eigenvalues 325

5.6.1 Cospectral graphs 325

5.6.2 Bipartite graphs and eigenvalues 326

5.6.3 Regular graphs 328

5.6.4 Distinct eigenvalues of a graph 330

6 Orthogonality and best approximation 333

6.1 Norms and inner products 333

6.1.1 Examples of norms and inner products 337

6.2 The adjoint of a linear operator 342

6.2.1 The adjoint of a linear operator 343

6.3 Orthogonal vectors and bases 350

6.3.1 Orthogonal bases 351

6.4 The projection theorem 357

6.4.1 Overdetermined linear systems 361

6.5 The Gram-Schmidt process 368

6.5.1 Least-squares polynomial approximation 371

6.6 Orthogonal complements 377

6.6.1 The fundamental theorem of linear algebra revisited 381

6.7 Complex inner product spaces 386

6.7.1 Examples of complex inner product spaces 388

6.7.2 Orthogonality in complex inner product spaces 389

6.7.3 The adjoint of a linear operator 390

6.8 More on polynomial approximation 394

6.8.1 A weighted L² inner product 397

6.9 The energy inner product and Galerkin's method 401

6.9.1 Piecewise polynomials 404

6.9.2 Continuous piecewise quadratic functions 407

6.9.3 Higher degree finite element spaces 409

6.10 Gaussian quadrature 411

6.10.1 The trapezoidal rule and Simpson's rule 412

6.10.2 Gaussian quadrature 413

6.10.3 Orthogonal polynomials 415

6.10.4 Weighted Gaussian quadrature 419

6.11 The Helmholtz decomposition 420

6.11.1 The divergence theorem 421

6.11.2 Stokes's theorem 422

6.11.3 The Helmholtz decomposition 423

7 The spectral theory of symmetric matrices 425

7.1 The spectral theorem for symmetric matrices 425

7.1.1 Symmetric positive definite matrices 428

7.1.2 Hermitian matrices 430

7.2 The spectral theorem for normal matrices 434

7.2.1 Outer products and the spectral decomposition 437

7.3 Optimization and the Hessian matrix 440

7.3.1 Background 440

7.3.2 Optimization of quadratic functions 441

7.3.3 Taylor's theorem 443

7.3.4 First-and second-order optimality conditions 444

7.3.5 Local quadratic approximations 446

7.4 Lagrange multipliers 448

7.5 Spectral methods for differential equations 453

7.5.1 Eigenpairs of the differential operator 454

7.5.2 Solving the BVP using eigenfunctions 456

8 The singular value decomposition 463

8.1 Introduction to the SVD 463

8.1.1 The SVD for singular matrices 467

8.2 The SVD for general matrices 470

8.3 Solving least-squares problems using the SVD 476

8.4 The SVD and linear inverse problems 483

8.4.1 Resolving inverse problems through regularization 489

8.4.2 The truncated SVD method 489

8.4.3 Tikhonov regularization 490

8.5 The Smith normal form of a matrix 494

8.5.1 An algorithm to compute the Smith normal form 495

8.5.2 Applications of the Smith normal form 501

9 Matrix factorizations and numerical linear algebra 507

9.1 The LU factorization 507

9.1.1 Operation counts 512

9.1.2 Solving Ax=b using the LU factorization 514

9.2 Partial pivoting 516

9.2.1 Finite-precision arithmetic 517

9.2.2 Examples of errors in Gaussian elimination 518

9.2.3 Partial pivoting 519

9.2.4 The PLU factorization 522

9.3 The Cholesky factorization 524

9.4 Matrix norms 530

9.4.1 Examples of induced matrix norms 534

9.5 The sensitivity of linear systems to errors 537

9.6 Numerical stability 542

9.6.1 Backward error analysis 543

9.6.2 Analysis of Gaussian elimination with partial pivoting 545

9.7 The sensitivity of the least-squares problem 548

9.8 The QR factorization 554

9.8.1 Solving the least-squares problem 556

9.8.2 Computing the QR factorization 556

9.8.3 Backward stability of the Householder QR algorithm 561

9.8.4 Solving a linear system 562

9.9 Eigenvalues and simultaneous iteration 564

9.9.1 Reduction to triangular form 564

9.9.2 The power method 566

9.9.3 Simultaneous iteration 567

9.10 The QR algorithm 572

9.10.1 A practical QR algorithm 573

9.10.1.1 Reduction to upper Hessenberg form 574

9.10.1.2 The explicitly shifted QR algorithm 576

9.10.1.3 The implicitly shifted QR algorithm 579

10 Analysis in vector spaces 581

10.1 Analysis in Rⁿ 581

10.1.1 Convergence and continuity in Rⁿ 582

10.1.2 Compactness 584

10.1.3 Completeness of Rⁿ 586

10.1.4 Equivalence of norms on Rⁿ 586

10.2 Infinite-dimensional vector spaces 590

10.2.1 Banach and Hilbert spaces 592

10.3 Functional analysis 596

10.3.1 The dual of a Hilbert space 600

10.4 Weak convergence 605

10.4.1 Convexity 611

A The Euclidean algorithm 617

A.0.1 Computing multiplicative inverses in Z_p 618

A.0.2 Related results 619

B Permutations 621

C Polynomials 625

C.1 Rings of Polynomials 625

C.2 Polynomial functions 630

C.2.1 Factorization of polynomials 632

D Summary of analysis in R 633

D.0.1 Convergence 633

D.0.2 Completeness of R 634

D.0.3 Open and closed sets 635

D.0.4 Continuous functions 636

Bibliography 637

Index 641