O'Reilly logo

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Handbook of Linear Algebra, 2nd Edition

Book Description

With a substantial amount of new material, the Handbook of Linear Algebra, Second Edition provides comprehensive coverage of linear algebra concepts, applications, and computational software packages in an easy-to-use format. It guides you from the very elementary aspects of the subject to the frontiers of current research. Along with revisions and updates throughout, the second edition of this bestseller includes 20 new chapters.

New to the Second Edition

  • Separate chapters on Schur complements, additional types of canonical forms, tensors, matrix polynomials, matrix equations, special types of matrices, generalized inverses, matrices over finite fields, invariant subspaces, representations of quivers, and spectral sets
  • New chapters on combinatorial matrix theory topics, such as tournaments, the minimum rank problem, and spectral graph theory, as well as numerical linear algebra topics, including algorithms for structured matrix computations, stability of structured matrix computations, and nonlinear eigenvalue problems
  • More chapters on applications of linear algebra, including epidemiology and quantum error correction
  • New chapter on using the free and open source software system Sage for linear algebra
  • Additional sections in the chapters on sign pattern matrices and applications to geometry
  • Conjectures and open problems in most chapters on advanced topics

Highly praised as a valuable resource for anyone who uses linear algebra, the first edition covered virtually all aspects of linear algebra and its applications. This edition continues to encompass the fundamentals of linear algebra, combinatorial and numerical linear algebra, and applications of linear algebra to various disciplines while also covering up-to-date software packages for linear algebra computations.

Table of Contents

  1. Discrete Mathematics and Its Applications
  2. Dedication
  3. Acknowledgments
  4. The Editor
  5. The Associate Editors (1st Edition)
  6. The Associate Editors (2nd Edition)
  7. Contributors
  8. Preface
    1. Preface to the Second Edition
    2. Updates and Feedback
    3. Preface to the First Edition
      1. Content
      2. Format
  9. Preliminaries
    1. Algebra
    2. Big-oh, Big-theta, Big-omega (asymptotic comparison)
    3. Boundary
    4. Complement
    5. Complex Numbers
    6. Conjugate Partition
    7. Convexity
    8. Elementary Symmetric Function
    9. Equivalence Relation
    10. Field
    11. Gradient
    12. Greatest Integer Function
    13. Group
    14. Interlaces
    15. Little-oh (asymptotic comparison)
    16. Majorization
    17. Metric
    18. Module
    19. Multiset
    20. NP, NP-hard
    21. O, o, Θ, Ω (asymptotic comparison)
    22. Path-connected
    23. Permutations
    24. Ring
    25. Sign
    26. References
  10. Part I Linear Algebra
    1. Linear Algebra
      1. Chapter 1 Vectors, Matrices, and Systems of Linear Equations
        1. 1.1 Vector Spaces
        2. 1.2 Matrices
        3. 1.3 Gaussian and Gauss--Jordan Elimination
        4. 1.4 Systems of Linear Equations
        5. 1.5 Matrix Inverses and Elementary Matrices
        6. 1.6 Factorization
        7. References
      2. Chapter 2 Linear Independence, Span, and Bases
        1. 2.1 Span and Linear Independence
        2. 2.2 Basis and Dimension of a Vector Space
        3. 2.3 Direct Sum Decompositions
        4. 2.4 Matrix Range, Null Space, Rank, and the Dimension Theorem
        5. 2.5 Nonsingularity Characterizations
        6. 2.6 Coordinates and Change of Basis
        7. 2.7 Idempotence and Nilpotence
        8. References
      3. Chapter 3 Linear Transformations
        1. 3.1 Basic Concepts
        2. 3.2 The Spaces L(V, W) and L(V, V)
        3. 3.3 Matrix of a Linear Transformation
        4. 3.4 Change of Basis and Similarity
        5. 3.5 Kernel and Range
        6. 3.6 Invariant Subspaces and Projections
        7. 3.7 Isomorphism and Nonsingularity Characterization
        8. 3.8 Linear Functionals and Annihilator
        9. References
      4. Chapter 4 Determinants and Eigenvalues
        1. 4.1 Determinants
        2. 4.2 Determinants: Advanced Results
        3. 4.3 The Pfaffian
        4. 4.4 Eigenvalues and Eigenvectors
        5. References
          1. Figure 4.1
      5. Chapter 5 Inner Product Spaces, Orthogonal Projection, Least Squares, and Singular Value Decomposition
        1. 5.1 Inner Product Spaces
        2. 5.2 Orthogonality
        3. 5.3 Adjoints of Linear Operators on Inner Product Spaces
        4. 5.4 Orthogonal Projection
        5. 5.5 Gram–Schmidt Orthogonalization and QR Factorization
        6. 5.6 Singular Value Decomposition
        7. 5.7 Pseudo-Inverse
        8. 5.8 Least Squares Problems
        9. References
      6. Chapter 6 Canonical Forms for Similarity
        1. 6.1 Generalized Eigenvectors
        2. 6.2 Jordan Canonical Form
        3. 6.3 Real-Jordan Canonical Form
        4. 6.4 Weyr Canonical Form
        5. 6.5 Rational Canonical For Elementary Divisors
        6. 6.6 Smith Normal Form on F[x]n×n
        7. 6.7 Rational Canonical For Invariant Factors
        8. Acknowledgment
        9. References
          1. Table 6.1
          2. Table 6.2
      7. Chapter 7 Other Canonical Forms
        1. 7.1 Equivalence and Unitary Equivalence
        2. 7.2 *Congruence (Conjunctivity) and Unitary Similarity
        3. 7.3 Congruence and Unitary Congruence
        4. 7.4 Consimilarity
        5. 7.5 Polar Decompositions
        6. References
      8. Chapter 8 Unitary Similarity, Normal Matrices, and Spectral Theory
        1. 8.1 Unitary Similarity
        2. 8.2 Normal Matrices and Spectral Theory
        3. References
      9. Chapter 9 Hermitian and Positive Definite Matrices
        1. 9.1 Hermitian Matrices
        2. 9.2 Order Properties of Eigenvalues of Hermitian Matrices
        3. 9.3 Congruence and Inertia
        4. 9.4 Positive Definite Matrices
        5. 9.5 Further Topics in Positive Definite Matrices
        6. References
      10. Chapter 10 Nonnegative Matrices and Stochastic Matrices
        1. 10.1 Notation, Terminology, and Preliminaries
        2. 10.2 Irreducible Matrices
        3. 10.3 Reducible Matrices
        4. 10.4 Stochastic and Substochastic Matrices
        5. 10.5 M-matrices
        6. 10.6 Scaling of Nonnegative Matrices
        7. 10.7 Miscellaneous Topics
        8. References
          1. Figure 10.1
      11. Chapter 11 Partitioned Matrices
        1. 11.1 Submatrices and Block Matrices
        2. 11.2 Block Diagonal and Block Triangular Matrices
        3. 11.3 Schur Complements
        4. 11.4 Kronecker Products
        5. References
    2. Topics in Linear Algebra
      1. Chapter 12 Schur Complements
        1. 12.1 Introduction and Notation
        2. 12.2 The Schur Complement
        3. 12.3 Closure Properties
        4. 12.4 The Quotient Formula and Schur Complements of Products
        5. 12.5 Haynsworth’s Inertia Addition Theorem
        6. 12.6 The Generalized Schur Complement
        7. 12.7 Interlacing Eigenvalues
        8. 12.8 Positive Semidefinite Matrices
        9. References
      2. Chapter 13 Quadratic, Bilinear, and Sesquilinear Forms
        1. 13.1 Bilinear Forms
        2. 13.2 Symmetric Bilinear Forms
        3. 13.3 Alternating Bilinear Forms
        4. 13.4 φ-Sesquilinear Forms
        5. 13.5 Hermitian Forms
        6. References
      3. Chapter 14 Multilinear Algebra
        1. 14.1 Multilinear Maps
        2. 14.2 Tensor Products
        3. 14.3 Rank of a Tensor: Decomposable Tensors
        4. 14.4 Tensor Product of Linear Maps
        5. 14.5 Symmetric and Antisymmetric Maps
        6. 14.6 Symmetric and Grassmann Tensors
        7. 14.7 The Tensor Multiplication, the Alt Multiplication, and the Sym Multiplication
        8. 14.8 Associated Maps
        9. 14.9 Tensor Algebras
        10. 14.10 Tensor Product of Inner Product Spaces
        11. 14.11 Orientation and Hodge Star Operator
        12. References
      4. Chapter 15 Tensors and Hypermatrices
        1. 15.1 Hypermatrices
        2. 15.2 Tensors and Multilinear Functionals
        3. 15.3 Tensor Rank
        4. 15.4 Border Rank
        5. 15.5 Generic and Maximal Rank
        6. 15.6 Rank-Retaining Decomposition
        7. 15.7 Multilinear Rank
        8. 15.8 Norms
        9. 15.9 Hyperdeterminants
        10. 15.10 Odds and Ends
        11. Acknowledgment
        12. References
      5. Chapter 16 Matrix Equalities and Inequalities
        1. 16.1 Eigenvalue Equalities and Inequalities
        2. 16.2 Spectrum Localization
        3. 16.3 Inequalities for the Singular Values and the Eigenvalues
        4. 16.4 Basic Determinantal Relations
        5. 16.5 Rank and Nullity Equalities and Inequalities
        6. 16.6 Useful Identities for the Inverse
        7. References
          1. Figure 16.1
          2. Figure 16.2
          3. Figure 16.3
          4. Figure 16.4
      6. Chapter 17 Functions of Matrices
        1. 17.1 General Theory
        2. 17.2 Matrix Exponential
        3. 17.3 Matrix Logarithm
        4. 17.4 Matrix Sine and Cosine
        5. 17.5 Matrix Square Root
        6. 17.6 Arbitrary Matrix Power
        7. 17.7 Matrix Sign Function
        8. 17.8 Computational Methods for General Functions
        9. 17.9 Computational Methods for Specific Functions
        10. References
      7. Chapter 18 Matrix Polynomials
        1. 18.1 Basic Definitions and Facts
        2. 18.2 Equivalence and the Smith Form
        3. 18.3 Spectral Theory of Matrix Polynomials
        4. 18.4 Linearization of Matrix Polynomials
        5. 18.5 Hermitian Matrix Polynomials
        6. Acknowledgment
        7. References
      8. Chapter 19 Matrix Equations
        1. 19.1 Introduction
        2. 19.2 Linear Matrix Equations
        3. 19.3 Polynomial Matrix Equations
        4. 19.4 Algebraic Riccati Equations
        5. References
      9. Chapter 20 Invariant Subspaces
        1. 20.1 Algebraic Properties
        2. 20.2 Analytic Properties
        3. 20.3 Residual and Perturbation Bounds
        4. References
      10. Chapter 21 Matrix Perturbation Theory
        1. 21.1 Eigenvalue Problems
        2. 21.2 Singular Value Problems
        3. 21.3 Polar Decomposition
        4. 21.4 Generalized Eigenvalue Problems
        5. 21.5 Generalized Singular Value Problems
        6. 21.6 Relative Perturbation Theory for Eigenvalue Problems
        7. 21.7 Relative Perturbation Theory for Singular Value Problems
        8. References
      11. Chapter 22 Special Types of Matrices
        1. 22.1 Circulant Matrices
        2. 22.2 Toeplitz Matrices
        3. 22.3 Hankel Matrices
        4. 22.4 Vandermonde Matrices
        5. 22.5 Cauchy Matrices
        6. 22.6 Loewner Matrices
        7. 22.7 Jacobi Matrices
        8. 22.8 There is More
        9. Acknowledgment
        10. References
      12. Chapter 23 Pseudospectra
        1. 23.1 Fundamentals of Pseudospectra
        2. 23.2 Toeplitz Matrices
        3. 23.3 Behavior of Functions of Matrices
        4. 23.4 Computation of Pseudospectra
        5. 23.5 Extensions
        6. References
          1. Figure 23.1
          2. Figure 23.2
          3. Figure 23.3
          4. Figure 23.4
          5. Figure 23.5
          6. Figure 23.6
          7. Figure 23.7
          8. Figure 23.8
          9. Figure 23.9
      13. Chapter 24 Singular Values and Singular Value Inequalities
        1. 24.1 Definitions and Characterizations
        2. 24.2 Singular Values of Special Matrices
        3. 24.3 Unitarily Invariant Norms
        4. 24.4 Inequalities
        5. 24.5 Matrix Approximation
        6. 24.6 Characterization of the Eigenvalues of Sums of Hermitian Matrices and Singular Values of Sums and Products of General Matrices
        7. 24.7 Miscellaneous Results and Generalizations
        8. References
      14. Chapter 25 Numerical Range
        1. 25.1 Basic Properties and Examples
        2. 25.2 The Spectrum and Special Boundary Points
        3. 25.3 Location of the Numerical Range
        4. 25.4 Numerical Radius
        5. 25.5 Products of Matrices
        6. 25.6 Dilations and Norm Estimation
        7. 25.7 Mappings on Matrices
        8. References
          1. Figure 25.1
          2. Figure 25.2
          3. Figure 25.3
      15. Chapter 26 Matrix Stability and Inertia
        1. 26.1 Inertia
        2. 26.2 Stability
        3. 26.3 Multiplicative D-Stability
        4. 26.4 Additive D-stability
        5. 26.5 Lyapunov Diagonal Stability
        6. References
      16. Chapter 27 Generalized Inverses of Matrices
        1. 27.1 Notation and Terminology
        2. 27.2 Moore-Penrose Inverse
        3. 27.3 Drazin Inverse
        4. 27.4 Outer Inverse
        5. 27.5 Conjectures and Open Questions
        6. Acknowledgments
        7. References
      17. Chapter 28 Inverse Eigenvalue Problems
        1. 28.1 IEPs with Prescribed Entries
        2. 28.2 PEIEPs of 2 × 2 Block Type
        3. 28.3 Nonnegative IEP (NIEP)
        4. 28.4 Spectra of Nonnegative Matrices
        5. 28.5 Nonzero Spectra of Nonnegative Matrices
        6. 28.6 Some Merging Results for Spectra of Nonnegative Matrices
        7. 28.7 Sufficient Conditions for Spectra of Nonnegative Matrices
        8. 28.8 Affine Parameterized IEPs (PIEPs)
        9. 28.9 Relevant PIEPs Which Are Solvable Everywhere
        10. 28.10 Numerical Methods for PIEPs
        11. References
      18. Chapter 29 Totally Positive and Totally Nonnegative Matrices
        1. 29.1 Basic Properties
        2. 29.2 Factorizations
        3. 29.3 Recognition and Testing
        4. 29.4 Spectral Properties
        5. 29.5 Deeper Properties
        6. References
      19. Chapter 30 Linear Preserver Problems
        1. 30.1 Basic Concepts
        2. 30.2 Standard Forms
        3. 30.3 Standard Linear Preserver Problems
        4. 30.4 Additive, Multiplicative, and Nonlinear Preservers
        5. References
      20. Chapter 31 Matrices over Finite Fields
        1. 31.1 Counting Matrices with a Given Property
        2. 31.2 Factorization of Matrices
        3. 31.3 Matrix Fields
        4. 31.4 Congruence
        5. 31.5 Generalized Inverses
        6. References
      21. Chapter 32 Matrices over Integral Domains
        1. 32.1 Certain Integral Domains
        2. 32.2 Equivalence of Matrices
        3. 32.3 Linear Equations over Bezout Domains
        4. 32.4 Strict Equivalence of Pencils
        5. References
      22. Chapter 33 Similarity of Families of Matrices
        1. 33.1 Similarity of Matrices
        2. 33.2 Simultaneous Similarity of Matrices
        3. 33.3 Property L
        4. 33.4 Simultaneous Similarity Classification I
        5. 33.5 Simultaneous Similarity Classification II
        6. References
      23. Chapter 34 Representations of Quivers and Mixed Graphs
        1. 34.1 Systems of Linear Mappings as Representations of Quivers
        2. 34.2 Tame and Wild Quivers
        3. 34.3 Quivers of Finite Dimensional Algebras
        4. 34.4 Systems of Linear Mappings and Forms as Representations of Mixed Graphs
        5. 34.5 Generalization of the Law of Inertia to Representations of Mixed Graphs
        6. References
      24. Chapter 35 Max-Plus Algebra
        1. 35.1 Preliminaries
        2. 35.2 The Maximal Cycle Mean
        3. 35.3 The Max-Plus Eigenproblem
        4. 35.4 Asymptotics of Matrix Powers
        5. 35.5 The Max-Plus Permanent
        6. 35.6 Linear Inequalities and Projections
        7. 35.7 Max-Plus Linear Independence and Rank
        8. References
          1. Figure 35.1
      25. Chapter 36 Matrices Leaving a Cone Invariant
        1. 36.1 Perron– –Frobenius Theorem for Cones
        2. 36.2 Collatz-Wielandt Sets and Distinguished Eigenvalues
        3. 36.3 The Peripheral Spectrum, the Core, and the Perron–Schaefer Condition
        4. 36.4 Spectral Theory of K-Reducible Matrices
        5. 36.5 Linear Equations over Cones
        6. 36.6 Elementary Analytic Results
        7. 36.7 Splitting Theorems and Stability
        8. References
      26. Chapter 37 Spectral Sets
        1. 37.1 Matrices and Operators
        2. 37.2 Basic Properties of Spectral Sets
        3. 37.3 Around the von Neumann Inequality
        4. 37.4 The Multidimensional von Neumann Inequality
        5. 37.5 Dilations, Complete Bounds, and Similarity Problems
        6. 37.6 Intersections of Spectral and K-Spectral Sets
        7. 37.7 The Numerical Range as a K-Spectral Set
        8. 37.8 Applications to the Approximate Computation of Matrix Functions
        9. References
          1. Figure 37.1
  11. Part II Combinatorial Matrix Theory and Graphs
    1. Combinatorial Matrix Theory
      1. Chapter 38 Combinatorial Matrix Theory
        1. 38.1 Combinatorial Structure and Invariants
        2. 38.2 Square Matrices and Strong Combinatorial Invariants
        3. 38.3 Square Matrices and Weak Combinatorial Invariants
        4. 38.4 The Class A(R, S) of (0, 1)-Matrices
        5. 38.5 The Class T(R) of Tournament Matrices
        6. 38.6 Convex Polytopes of Doubly Stochastic Matrices
        7. References
      2. Chapter 39 Matrices and Graphs
        1. 39.1 Graphs: Basic Notions
        2. 39.2 Special Graphs
        3. 39.3 The Adjacency Matrix and Its Eigenvalues
        4. 39.4 Other Matrix Representations
        5. 39.5 Graph Parameters
        6. 39.6 Association Schemes
        7. References
          1. Figure 39.1
          2. Figure 39.2
          3. Figure 39.3
          4. Figure 39.4
          5. Figure 39.5
          6. Figure 39.6
      3. Chapter 40 Digraphs and Matrices
        1. 40.1 Digraphs
        2. 40.2 The Adjacency Matrix of a Directed Graph and the Digraph of a Matrix
        3. 40.3 Walk Products and Cycle Products
        4. 40.4 Generalized Cycle Products
        5. 40.5 Strongly Connected Digraphs and Irreducible Matrices
        6. 40.6 Primitive Digraphs and Primitive Matrices
        7. 40.7 Irreducible, Imprimitive Matrices and Cyclic Normal Form
        8. 40.8 Minimally Connected Digraphs and Nearly Reducible Matrices
        9. References
          1. Figure 40.1
          2. Figure 40.2
          3. Figure 40.3
          4. Figure 40.4
      4. Chapter 41 Bipartite Graphs and Matrices
        1. 41.1 Basics of Bipartite Graphs
        2. 41.2 Bipartite Graphs Associated with Matrices
        3. 41.3 Factorizations and Bipartite Graphs
        4. References
          1. Figure 41.1
          2. Figure 41.2
          3. Figure 41.3
          4. Figure 41.4
          5. Figure 41.5
      5. Chapter 42 Sign Pattern Matrices
        1. 42.1 Basic Concepts
        2. 42.2 Sign Nonsingularity
        3. 42.3 Sign-Solvability, L-Matrices, and S*-Matrices
        4. 42.4 Stability
        5. 42.5 Other Eigenvalue Characterizations and Allowing Properties
        6. 42.6 Minimum Rank, Inertia
        7. 42.7 Spectrally Arbitrary, and Inertially Arbitrary Sign Patterns
        8. 42.8 Patterns That Allow Certain Types of Inverses
        9. 42.9 Orthogonality
        10. 42.10 Sign-Central Patterns
        11. 42.11 Power Positivity
        12. 42.12 Complex Sign Patterns and Ray Patterns
        13. 42.13 Powers of Sign Patterns and Ray Patterns
        14. References
    2. Topics in Combinatorial Matrix Theory
      1. Chapter 43 Permanents
        1. 43.1 Basic Concepts
        2. 43.2 Doubly Stochastic Matrices
        3. 43.3 Binary Matrices
        4. 43.4 Nonnegative Matrices
        5. 43.5 (±1)-Matrices
        6. 43.6 Matrices over ℂ
        7. 43.7 Subpermanents
        8. 43.8 Rook Polynomials
        9. 43.9 Evaluating Permanents
        10. 43.10 Connections between Determinants and Permanents
        11. References
          1. Figure 43.1
          2. Figure 43.2
          3. Figure 43.3
          4. Figure 43.4
          5. Figure 43.5
          6. Figure 43.6
      2. Chapter 44 D-Optimal Matrices
        1. 44.1 Introduction
        2. 44.2 The (±1) and (0,1) Square Case
        3. 44.3 The (±1) Nonsquare Case
        4. 44.4 The (0, 1) Nonsquare Case: Regular D-Optimal Matrices
        5. 44.5 The (0, 1) Nonsquare Case: Nonregular D-Optimal Matrices
        6. 44.6 The (0, 1) Nonsquare Case: Large m
        7. 44.7 The (0, 1) Nonsquare Case: n = −1 (mod 4) = −1 (mod 4)
        8. 44.8 Balanced (0, 1) -Matrices and (±1)-Matrices
        9. References
          1. Figure 44.1
      3. Chapter 45 Tournaments
        1. 45.1 Tournaments and Tournament Matrices
        2. 45.2 Score Sequences and the Class τ(s)
        3. 45.3 Regular and Doubly Regular Tournaments
        4. 45.4 Singularity, Rank, and Eigenvalues
        5. References
          1. Figure 45.1
      4. Chapter 46 Minimum Rank, Maximum Nullity, and Zero Forcing Number of Graphs
        1. 46.1 Standard Minimum Rank of Graphs
        2. 46.2 Minimum Rank over Other Fields
        3. 46.3 Minimum Positive Semidefinite Rank
        4. 46.4 Zero Forcing Parameters
        5. 46.5 Colin de Verdiére Parameters
        6. 46.6 Advanced Topics
        7. 46.7 Conjectures and Open Problems
        8. 46.8 Minimum Rank without Symmetry
        9. References
          1. Figure 46.1
          2. Figure 46.2
          3. Figure 46.3
          4. Figure 46.4
          5. Figure 46.5
          6. Figure 46.6
          7. Figure 46.7
          8. Figure 46.8
          9. Figure 46.9
          10. Figure 46.10
          11. Figure 46.11
          12. Figure 46.12
          13. Figure 46.13
          14. Figure 46.14
          15. Figure 46.15
      5. Chapter 47 Spectral Graph Theory
        1. 47.1 The Normalized Laplacian Matrix
        2. 47.2 Random Walks
        3. 47.3 Graphs with Shared Eigenvalues
        4. 47.4 Interlacing Eigenvalues
        5. 47.5 Isoperimetric Problems
        6. 47.6 Quasirandom Graphs
        7. References
          1. Figure 47.1
          2. Figure 47.2
          3. Figure 47.3
          4. Figure 47.4
          5. Figure 47.5
          6. Figure 47.6
      6. Chapter 48 Algebraic Connectivity
        1. 48.1 Algebraic Connectivity for Simple Graphs: Basic Theory
        2. 48.2 Algebraic Connectivity for Simple Graphs: Further Results
        3. 48.3 Algebraic Connectivity for Trees
        4. 48.4 Fiedler Vectors and Algebraic Connectivity for Weighted Graphs
        5. 48.5 Absolute Algebraic Connectivity for Simple Graphs
        6. 48.6 Generalized Laplacians and Multiplicity
        7. References
          1. Figure 48.1
          2. Figure 48.2
          3. Figure 48.3
          4. Figure 48.4
          5. Figure 48.5
          6. Figure 48.6
          7. Figure 48.7
          8. Figure 48.8.
          9. Figure 48.9
      7. Chapter 49 Matrix Completion Problems
        1. 49.1 Introduction
        2. 49.2 Positive Definite and Positive Semidefinite Matrices
        3. 49.3 Euclidean Distance Matrices
        4. 49.4 Completely Positive and Doubly Nonnegative Matrices
        5. 49.5 Doubly Negative Matrices
        6. 49.6 Copositive and Strictly Copositive Matrices
        7. 49.7 M- and M0-Matrices
        8. 49.8 Inverse M-Matrices
        9. 49.9 P-, P0,1-, and P0-Matrices
        10. 49.10 Positive P- and Nonnegative P- (P0,1-, P0-) Matrices
        11. 49.11 Entry Sign Symmetric P- (P0,1-, P0-) and Entry Weakly Sign Symmetric P- (P0,1-, P0-) Matrices
        12. 49.12 Q-Matrices
        13. 49.13 Totally Positive, Totally Nonnegative, and Totally Nonpositive Matrices
        14. References
          1. Figure 49.1
          2. Figure 49.2
          3. Figure 49.3
          4. Figure 49.4
          5. Figure 49.5
          6. Figure 49.6
  12. Part III Numerical Methods
    1. Numerical Methods for Linear Systems
      1. Chapter 50 Vector and Matrix Norms, Error Analysis, Efficiency, and Stability
        1. 50.1 Vector Norms
        2. 50.2 Vector Seminorms
        3. 50.3 Matrix Norms
        4. 50.4 Conditioning and Condition Numbers
        5. 50.5 Conditioning of Linear Systems
        6. 50.6 Floating Point Numbers
        7. 50.7 Algorithms and Efficiency
        8. 50.8 Numerical Stability and Instability
        9. References
          1. Figure 50.1
          2. Figure 50.2
      2. Chapter 51 Matrix Factorizations and Direct Solution of Linear Systems
        1. 51.1 Perturbations of Linear Systems
        2. 51.2 Triangular Linear Systems
        3. 51.3 Gauss Elimination and LU Decomposition
        4. 51.4 Symmetric Factorizations
        5. 51.5 Orthogonalization and the QR Factorization
        6. References
      3. Chapter 52 Least Squares Solution of Linear Systems
        1. 52.1 Basic Concepts
        2. 52.2 Least Squares Data Fitting
        3. 52.3 Geometric and Algebraic Aspects
        4. 52.4 Orthogonal Factorizations
        5. 52.5 Least Squares Algorithms
        6. 52.6 Sensitivity
        7. 52.7 Up- and Downdating of QR Factorization
        8. 52.8 Damped Least Squares
        9. 52.9 Rank Revealing Decompositions
        10. References
          1. Figure 52.1
      4. Chapter 53 Sparse Matrix Methods
        1. 53.1 Introduction
        2. 53.2 Sparse Matrices
        3. 53.3 Sparse Matrix Factorizations
        4. 53.4 Modeling and Analyzing Fill
        5. 53.5 Effect of Reorderings
        6. Author Note
        7. References
          1. Figure 53.1
          2. Figure 53.2
          3. Figure 53.3
          4. Figure 53.4
          5. Figure 53.5
          6. Figure 53.6
          7. Figure 53.7
          8. Figure 53.8
      5. Chapter 54 Iterative Solution Methods for Linear Systems
        1. 54.1 Krylov Subspaces and Preconditioners
        2. 54.2 Optimal Krylov Space Methods for Hermitian Problems
        3. 54.3 Optimal and Nonoptimal Krylov Space Methods for Non-Hermitian Problems
        4. 54.4 Preconditioners
        5. 54.5 Preconditioned Algorithms
        6. 54.6 Convergence Rates of CG and MINRES
        7. 54.7 Convergence Rate of GMRES
        8. 54.8 Inexact Preconditioners and Finite Precision Arithmetic, Error Estimation and Stopping Criteria, Text and Reference Books
        9. References
          1. Figure 54.1
          2. Figure 54.2
          3. Figure 54.3
          4. Figure 54.4
    2. Numerical Methods for Eigenvalues
      1. Chapter 55 Symmetric Matrix Eigenvalue Techniques
        1. 55.1 Basic Methods
        2. 55.2 Tridiagonalization
        3. 55.3 Implicitly Shifted QR Method
        4. 55.4 Divide and Conquer Method
        5. 55.5 Bisection and Inverse Iteration
        6. 55.6 Multiple Relatively Robust Representations
        7. 55.7 Jacobi Method
        8. 55.8 Lanczos Method
        9. 55.9 Comparison of Methods
        10. References
          1. Figure 55.1
          1. Table 55.1
      2. Chapter 56 Unsymmetric Matrix Eigenvalue Techniques
        1. 56.1 The Generalized Eigenvalue Problem
        2. 56.2 Dense Matrix Techniques
        3. 56.3 Sparse Matrix Techniques
        4. References
      3. Chapter 57 The Implicitly Restarted Arnoldi Method
        1. 57.1 Krylov Subspace Projection
        2. 57.2 The Arnoldi Factorization
        3. 57.3 Restarting the Arnoldi Process
        4. 57.4 Polynomial Restarting
        5. 57.5 Implicit Restarting
        6. 57.6 Convergence of IRAM
        7. 57.7 Convergence in Gap: Distance to a Subspace
        8. 57.8 The Generalized Eigenproblem
        9. 57.9 Krylov Methods with Spectral Transformations
        10. References
          1. Figure 57.1
          2. Figure 57.2
          3. Figure 57.3
          4. Figure 57.4
      4. Chapter 58 Computation of the Singular Value Decomposition
        1. 58.1 Singular Value Decomposition
        2. 58.2 Algorithms for the Singular Value Decomposition
        3. References
          1. Figure 58.1
          2. Figure 58.2
          3. Figure 58.3
          4. Figure 58.4
          5. Figure 58.5
          6. Figure 58.6
      5. Chapter 59 Computing Eigenvalues and Singular Values to High Relative Accuracy
        1. 59.1 Accurate SVD and One-Sided Jacobi SVD Algorithm
        2. 59.2 Preconditioned Jacobi SVD Algorithm
        3. 59.3 Accurate SVD from a Rank Revealing Decomposition: Structured Matrices
        4. 59.4 Positive Definite Matrices
        5. 59.5 Accurate Eigenvalues of Symmetric Indefinite Matrices
        6. References
          1. Table 59.1
      6. Chapter 60 Nonlinefr Eigenvalue Problems
        1. 60.1 Basic Properties
        2. 60.2 Analytic Matrix Functions
        3. 60.3 Variational Characterization of Eigenvalues
        4. 60.4 General Rayleigh Functionals
        5. 60.5 Methods for Dense Eigenvalue Problems
        6. 60.6 Iterative Projection Methods
          1. Jacobi–Davidson Method
          2. Two-Sided Jacobi Davidson Method
          3. Nonlinear Arnoldi Method
        7. 60.7 Methods Using Invariant Pairs
        8. 60.8 The Infinite Arnoldi Method
        9. References
    3. Topics in Numerical Linear Algebra
      1. Chapter 61 Fast Matrix Multiplication
        1. 61.1 Basic Concepts
        2. 61.2 Fast Algorithms
        3. 61.3 Other Algorithms
        4. 61.4 Approximation Algorithms
        5. 61.5 The Tensor of Matrix Multiplication
        6. 61.6 Advanced Techniques
        7. 61.7 Applications
        8. References
          1. Table 61.1
      2. Chapter 62 Fast Algorithms for Structured Matrix Computations
        1. 62.1 Classes of Structured Matrices
        2. 62.2 Transformations of Structured Matrices
        3. 62.3 Generalized Schur Algorithms
        4. 62.4 Schur Algorithms for Positive Definite Matrices
        5. 62.5 Fast Algorithms for Cauchy-like Systems
        6. 62.6 Fast Algorithms for Toeplitz-like Systems
        7. 62.7 Fast Algorithms for Vandermonde Systems
        8. 62.8 Superfast Algorithms
        9. References
      3. Chapter 63 Structured Eigenvalue Problems — Structure-Preserving Algorithms, Structured Error Analysis
        1. 63.1 Types of Matrices
        2. 63.2 (Structured) Backward Error and (Structured) Backward Stability
        3. 63.3 (Structured) Eigenvalue Methods
        4. 63.4 (Structured) Condition Numbers
        5. References
          1. Figure 63.1
      4. Chapter 64 Large-Scale Matrix Computations
        1. 64.1 Basic Concepts
        2. 64.2 Sparse Matrix Factorizations
        3. 64.3 Krylov Subspaces
        4. 64.4 The Symmetric Lanczos Process
        5. 64.5 The Nonsymmetric Lanczos Process
        6. 64.6 The Arnoldi Process
        7. 64.7 Eigenvalue Computations
        8. 64.8 Linear Systems of Equations
        9. 64.9 Dimension Reduction of Linear Dynamical Systems
        10. 64.10 A Band Arnoldi Process for Multiple Starting Vectors
        11. References
  13. Part IV Linear Algebra in Other Disciplines
    1. Applications to Physical and Biological Sciences
      1. Chapter 65 Linear Algebra and Mathematical Physics
        1. 65.1 Introduction
        2. 65.2 Normal Modes of Oscillation
        3. 65.3 Lagrangian Mechanics
        4. 65.4 Schrödinger's Equation
        5. 65.5 Angular Momentum and Representations of the Rotation Group
        6. 65.6 Green's Functions
        7. References
          1. Figure 65.1
          2. Figure 65.2
      2. Chapter 66 Linear Algebra in Biomolecular Modeling
        1. 66.1 Introduction
        2. 66.2 Mapping from Distances to Coordinates: NMR Protein Structure Determination
        3. 66.3 The Procrustes Problem for Protein Structure Comparison
        4. 66.4 The Karle–Hauptman Matrix in X-Ray Crystallographic Computing
        5. 66.5 Calculation of Fast and Slow Modes of Protein Motions
        6. 66.6 Flux Balancing Equation in Metabolic Network Simulation
        7. 66.7 Conclusion
        8. Acknowledgments
        9. References
          1. Figure 66.1
          2. Figure 66.2
          3. Figure 66.3
          4. Figure 66.4
          5. Figure 66.5
          6. Figure 66.6
      3. Chapter 67 Linear Algebra in Mathematical Population Biology and Epidemiology
        1. 67.1 Models for the Populations of Interacting Species
        2. 67.2 Compartmental Disease Transmission Models
        3. 67.3 The Next Generation Matrix
        4. 67.4 Discrete Age-Structured Population Models
        5. References
    2. Applications to Optimization
      1. Chapter 68 Linear Programming
        1. 68.1 What Is Linear Programming?
        2. 68.2 Setting Up (Formulating) Linear Programs
        3. 68.3 Standard and Canonical Forms for Linear Programs
        4. 68.4 Standard Row Tableaux
        5. 68.5 Pivoting
        6. 68.6 Simplex Method
        7. 68.7 Geometric Interpretation of Phase 2
        8. 68.8 Duality
        9. 68.9 Sensitivity Analysis and Parametric Programming
        10. 68.10 Matrix Games
        11. 68.11 Linear Approximation
        12. 68.12 Interior Point Methods
        13. References
      2. Chapter 69 Semidefinite Programming
        1. 69.1 Introduction
        2. 69.2 Specific Notation and Preliminary Results
        3. 69.3 Geometry
        4. 69.4 Duality and Optimality Conditions
        5. 69.5 Strong Duality without a Constraint Qualification
        6. 69.6 A Primal-Dual Interior-Point Algorithm
        7. 69.7 Applications of SDP
        8. References
    3. Applications to Probability and Statistics
      1. Chapter 70 Random Vectors and Linear Statistical Models
        1. 70.1 Introduction and Mise-En-Scéne
        2. 70.2 Introduction to Statistics and Random Variables
        3. 70.3 Random Vectors: Basic Definitions and Facts
        4. 70.4 Linear Statistical Models: Basic Definitions and Facts
        5. Acknowledgments
        6. References
      2. Chapter 71 Multivariate Statistical Analysis
        1. 71.1 Data Matrix
        2. 71.2 Multivariate Normal Distribution
        3. 71.3 Inference for the Multivariate Normal
        4. 71.4 Principal Component Analysis
        5. 71.5 Discriminant Coordinates
        6. 71.6 Canonical Correlations and Variates
        7. 71.7 Estimation of Canonical Correlations and Variates
        8. 71.8 Matrix Quadratic Forms
        9. 71.9 Multivariate Linear Model: Least Squares Estimation
        10. 71.10 Multivariate Linear Model: Statistical Inference
        11. 71.11 Metric Multidimensional Scaling
        12. Acknowledgments
        13. References
      3. Chapter 72 Markov Chains
        1. 72.1 Basic Concepts
        2. 72.2 Irreducible Classes
        3. 72.3 Classification of the States
        4. 72.4 Finite Markov Chains
        5. 72.5 Censoring
        6. 72.6 Numerical Methods
        7. References
          1. Figure 72.1
          2. Figure 72.2
    4. Applications to Computer Science
      1. Chapter 73 Coding Theory
        1. 73.1 Basic Concepts
        2. 73.2 Linear Block Codes
        3. 73.3 Main Linear Coding Problem and Distance Bounds
        4. 73.4 Important Classes of Linear Codes 1
        5. 73.5 Important Classes of Linear Codes 2
        6. 73.6 Convolutional Codes
        7. 73.7 Random Linear Network Codes
        8. References
        9. Web Resources
      2. Chapter 74 Quantum Computation
        1. 74.1 Basic Concepts
        2. 74.2 Universal Quantum Gates
        3. 74.3 Deutsch's Problem
        4. 74.4 Deutsch–Jozsa Problem
        5. 74.5 Bernstein–Vazirani Problem
        6. 74.6 Simon's Problem
        7. 74.7 Grover's Search Algorithm
        8. 74.8 Shor's Factorization Algorithm
        9. References
      3. Chapter 75 Operator Quantum Error Correction
        1. 75.1 Basic Concepts
        2. 75.2 Quantum Error Correction with Syndrome Measurement
        3. 75.3 Operator Quantum Error Correction
        4. 75.4 Knill-Laflamme Theorem and Higher Rank Numerical Ranges
        5. 75.5 Decoherence Free Subspace, Noiseless Subsystem, and Correctable Subsystem
        6. 75.6 Quantum Error Correction without Syndrome Measurement
        7. References
      4. Chapter 76 Information Retrieval and Web Search
        1. 76.1 The Traditional Vector Space Method
        2. 76.2 Latent Semantic Indexing
        3. 76.3 Nonnegative Matrix Factorizations
        4. 76.4 Web Search
        5. 76.5 Google's PageRank
        6. Acknowledgments
        7. References
          1. Figure 76.1
      5. Chapter 77 Signal Processing
        1. 77.1 Basic Concepts
        2. 77.2 Random Signals
        3. 77.3 Linear Prediction
        4. 77.4 Wiener Filtering
        5. 77.5 Adaptive Filtering
        6. 77.6 Spectral Estimation
        7. 77.7 Direction of Arrival Estimation
        8. References
    5. Applications to Analysis
      1. Chapter 78 Differential Equations and Stability
        1. 78.1 Linear Differential Equations with Constant Coefficients: Basic Concepts
        2. 78.2 Linear Ordinary Differential Equations
        3. 78.3 Linear Differential-Algebraic Equations
        4. 78.4 Stability of Linear Ordinary Differential Equations
        5. 78.5 Stability of Linear Differential-Algebraic Equations
        6. References
          1. Figure 78.1
          2. Figure 78.2
          3. Figure 78.3
          4. Figure 78.4
          5. Figure 78.5
          6. Figure 78.6
      2. Chapter 79 Dynamical Systems and Linear Algebra
        1. 79.1 Linear Differential Equations
        2. 79.2 Linear Dynamical Systems in ℝd
        3. 79.3 Chain Recurrence and Morse Decompositions of Dynamical Systems
        4. 79.4 Linear Systems on Grassmannian and Flag Manifolds
        5. 79.5 Linear Skew Product Flows
        6. 79.6 Periodic Linear Differential Equations: Floquet Theory
        7. 79.7 Random Linear Dynamical Systems
        8. 79.8 Robust Linear Systems
        9. 79.9 Linearization
        10. References
          1. Figure 79.1
          2. Figure 79.2
      3. Chapter 80 Control Theory
        1. 80.1 Basic Concepts
        2. 80.2 Frequency-Domain Analysis
        3. 80.3 Analysis of LTI Systems
        4. 80.4 Matrix Equations
        5. 80.5 State Estimation
        6. 80.6 Control Design for LTI Systems
        7. References
          1. Figure 80.1
          2. Figure 80.2
          3. Figure 80.3
      4. Chapter 81 Fourier Analysis
        1. 81.1 Introduction
        2. 81.2 The Function/Functional Theory
        3. 81.3 The Discrete Theory
        4. 81.4 Relating the Functional and Discrete Theories
        5. 81.5 The Fast Fourier Transform
        6. References
    6. Applications to Geometry
      1. Chapter 82 Geometry
        1. 82.1 Affine Spaces
        2. 82.2 Euclidean Spaces
        3. 82.3 Projective Spaces
        4. 82.4 Hyperbolic Spaces
        5. References
      2. Chapter 83 Some Applications of Matrices and Graphs in Euclidean Geometry
        1. 83.1 Euclidean Point Space
        2. 83.2 Gram Matrices
        3. 83.3 General Theory of Euclidean Simplexes
        4. 83.4 Special Simplexes
        5. 83.5 An Application to Resistive Electrical Networks
        6. References
          1. Figure 83.1
          2. Figure 83.2
          3. Figure 83.3
          4. Figure 83.4
    7. Applications to Algebra
      1. Chapter 84 Matrix Groups
        1. 84.1 Introduction
        2. 84.2 The General and Special Linear Groups
        3. 84.3 The BN Structure of the General Linear Group
        4. 84.4 Classical Groups
        5. Acknowledgment
        6. References
      2. Chapter 85 Group Representations
        1. 85.1 Basic Concepts
        2. 85.2 Matrix Representations
        3. 85.3 Characters
        4. 85.4 Orthogonality Relations and Character Table
        5. 85.5 Restriction and Induction of Characters
        6. 85.6 Representations of the Symmetric Group
        7. References
      3. Chapter 86 Nonassociative Algebras
        1. 86.1 Introduction
        2. 86.2 General Properties
        3. 86.3 Composition Algebras
        4. 86.4 Alternative Algebras
        5. 86.5 Jordan Algebras
        6. 86.6 Power Associative Algebras, Noncommutative Jordan Algebras, and Right Alternative Algebras
        7. 86.7 Malcev Algebras
        8. 86.8 Akivis and Sabinin Algebras
        9. 86.9 Computational Methods
        10. Acknowledgment
        11. References
          1. Table 86.1
          2. Table 86.2
          3. Table 86.3
          4. Table 86.4
          5. Table 86.5
          6. Table 86.6
          7. Table 86.7
          8. Table 86.8
          9. Table 86.9
          10. Table 86.10
          11. Table 86.11
          12. Table 86.12
      4. Chapter 87 Lie Algebras
        1. 87.1 Basic Concepts
        2. 87.2 Semisimple and Simple Algebras
        3. 87.3 Modules
        4. 87.4 Graded Algebras and Modules
        5. References
  14. Part V Computational Software
    1. Interactive Software for Linear Algebra
      1. Chapter 88 MATLAB®
        1. 88.1 Matrices, Submatrices, and Multidimensional Arrays?
        2. 88.2 Matrix Arithmetic
        3. 88.3 Built-in MATLAB® Functions?
        4. 88.4 Special Matrices
        5. 88.5 Linear Systems and Least Squares
        6. 88.6 Eigenvalues and Eigenvectors
        7. 88.7 Sparse Matrices
        8. 88.8 Programming?
        9. 88.9 Function Handles and Anonymous Functions
        10. 88.10 Graphics
        11. 88.11 Symbolic Mathematics in MATLAB®
        12. 88.12 Graphical User Interfaces
        13. References
          1. Figure 88.1
          2. Figure 88.2
          3. Figure 88.3
          4. Figure 88.4
          5. Figure 88.5
          6. Figure 88.6
          7. Figure 88.7
          8. Figure 88.8
      2. Chapter 89 Linear Algebra in Maple®
        1. 89.1 Introduction
        2. 89.2 Vectors
        3. 89.3 Matrices
        4. 89.4 Arrays
        5. 89.5 Efficient Working with Vectors and Matrices
        6. 89.6 Equation Solving and Matrix Factoring
        7. 89.7 Eigenvalues and Eigenvectors
        8. 89.8 Linear Algebra with Modular Arithmetic
        9. 89.9 Numerical Linear Algebra in Maple
        10. 89.10 Canonical Forms
        11. 89.11 Structured Matrices
        12. 89.12 Functions of Matrices
        13. 89.13 Matrix Stability
        14. Acknowledgments
        15. References
      3. Chapter 90 Mathematica
        1. 90.1 Introduction
          1. About Mathematica
          2. About this Chapter
        2. 90.2 Vectors
        3. 90.3 Basics of Matrices
        4. 90.4 Matrix Algebra
        5. 90.5 Manipulation of Matrices
        6. 90.6 Eigenvalues
        7. 90.7 Singular Values
        8. 90.8 Decompositions
        9. 90.9 Linear Systems
        10. 90.10 Linear Programming
        11. Appendix
          1. Introduction to Mathematica
          2. Getting Help
        12. References
      4. Chapter 91 Sage
        1. 91.1 Introduction
        2. 91.2 Working with Sage
        3. 91.3 Vectors
        4. 91.4 Matrices
        5. 91.5 Eigenvalues and Eigenvectors
        6. 91.6 Vector Spaces
        7. 91.7 Linear Transformations
        8. 91.8 Graphics
        9. 91.9 Conversion to Other Forms
        10. 91.10 General Rings
        11. 91.11 Numerical Linear Algebra
        12. 91.12 Applications of Linear Algebra
        13. 91.13 For More Information
          1. Figure 91.1
          2. Figure 91.2
    2. Packages of Subroutines for Linear Algebra
      1. Chapter 92 BLAS
        1. 92.1 Introduction
        2. References
          1. Figure 92.1
      2. Chapter 93 LAPACK Zhaojun Bai, James Demmel, Jack Dongarra, Julien Langou, and Jenny Wang
        1. 93.1 Introduction
        2. 93.2 Linear System of Equations
          1. Background:
          2. Driver Routines:
        3. 93.3 Linear Least Squares Problems
          1. Background:
          2. Driver Routines:
        4. 93.4 The Linear Equality-Constrained Least Squares Problem
          1. Background:
          2. Driver Routines:
        5. 93.5 A General Linear Model Problem
          1. Background:
          2. Driver Routines:
        6. 93.6 Symmetric Eigenproblems
          1. Background:
          2. Driver Routines:
        7. 93.7 Nonsymmetric Eigenproblems
          1. Background:
          2. Driver Routines:
        8. 93.8 Singular Value Decomposition
          1. Background:
          2. Driver Routines:
        9. 93.9 Generalized Symmetric Definite Eigenproblems
          1. Background:
          2. Driver Routines:
        10. 93.10 Generalized Nonsymmetric Eigenproblems
          1. Background:
          2. Driver Routines:
        11. 93.11 Generalized Singular Value Decomposition
          1. Background:
          2. Driver Routines:
        12. References
      3. Chapter 94 Use of ARPACK and EIGS
        1. 94.1 The ARPACK Software
        2. 94.2 Reverse Communication
        3. 94.3 Directory Structure and Contents
          1. Subdirectories:
        4. 94.4 Naming Conventions, Precisions, and Types
        5. 94.5 Getting Started
        6. 94.6 Setting Up the Problem
          1. Storage Declarations:
          2. Stopping Criterion:
          3. Initial Parameter Settings:
          4. Setting the Starting Vector:
          5. Trace Debugging Capability:
        7. 94.7 General Use of ARPACK
          1. The Shift and Invert Spectral Transformation Mode:
          2. M Is Hermitian Positive Definite:
          3. M Is NOT Hermitian Positive Semidefinite:
        8. 94.8 Using the Computational Modes
          1. When to Use a Spectral Transformation:
          2. Computational Modes for Real Nonsymmetric Problems:
        9. 94.9 MATLAB'S® EIGS
        10. References
          1. Figure 94.1
          2. Figure 94.2
      4. Chapter 95 Summary of Software for Linear Algebra Freely Available on the Web
        1. Table 95.1
        2. Table 95.2
        3. Table 95.3
        4. Table 95.4
        5. Table 95.5
  15. Glossary