Title: Eigenvalues and Eigenvectors — Module Summary
Thesis
This module established eigenvalues and eigenvectors as central tools for analyzing linear transformations, enabling structural understanding (diagonalization and spectral decompositions), efficient computation (via QR-type methods and Krylov subspace techniques), and broad applications (dimensionality reduction, dynamical systems, and networks). The key results, computational strategies, and applications were grounded in rigorous theory and supported by authoritative sources.
Core Concepts
- Definition and characteristic equation: For A ∈ C^{n×n}, λ ∈ C is an eigenvalue with eigenvector v ≠ 0 if Av = λv. Eigenvalues are the roots of the characteristic polynomial det(A − λI) = 0 (Horn and Johnson, 2013).
- Multiplicities: The algebraic multiplicity of λ is its multiplicity as a root of the characteristic polynomial; the geometric multiplicity is dim ker(A − λI). One always has 1 ≤ geometric multiplicity ≤ algebraic multiplicity (Horn and Johnson, 2013).
- Similarity invariance: Similar matrices share eigenvalues; triangular matrices have eigenvalues equal to their diagonal entries (Horn and Johnson, 2013).
- Field considerations: Over C, all matrices have a full set of eigenvalues (counting multiplicity). For real matrices, complex eigenvalues occur in conjugate pairs.
- Diagonalization: A is diagonalizable over C if and only if it has a basis of eigenvectors, equivalently, its minimal polynomial splits into distinct linear factors (Horn and Johnson, 2013).
- Spectral theorem: Normal matrices (AA* = A*A), including real symmetric and complex Hermitian matrices, are unitarily diagonalizable; their eigenvalues are real in the Hermitian/symmetric case, and eigenvectors can be taken orthonormal (Horn and Johnson, 2013).
- Positive (semi)definiteness: A real symmetric positive (semi)definite matrix has strictly positive (nonnegative) eigenvalues (Horn and Johnson, 2013).
- Perron–Frobenius theory: For a nonnegative irreducible matrix, the spectral radius is a simple eigenvalue with a strictly positive eigenvector; additional uniqueness and convergence properties hold under stronger conditions (Horn and Johnson, 2013).
Computational Methods and Stability
- Power method: Iterative estimation of the dominant eigenpair; converges when a unique eigenvalue has strictly maximal magnitude and the initial vector has a component in the dominant eigendirection (Trefethen and Bau, 1997).
- QR algorithm: The standard algorithm for all eigenvalues; shifted variants are efficient and, for symmetric/Hermitian matrices, exhibit excellent numerical stability (Golub and Van Loan, 2013).
- Krylov subspace methods: Lanczos (symmetric/Hermitian) and Arnoldi (general) scale well for large sparse matrices, approximating extremal eigenvalues and eigenvectors (Trefethen and Bau, 1997; Golub and Van Loan, 2013).
- Rayleigh quotient iteration: For symmetric/Hermitian problems, exhibits local cubic convergence to a simple eigenvalue (Trefethen and Bau, 1997).
- Localization and conditioning: Gershgorin discs provide eigenvalue inclusion sets. Sensitivity depends on the angle between left and right eigenvectors; normal matrices have well-conditioned eigen-structures, whereas highly non-normal matrices may exhibit extreme sensitivity and large pseudospectra (Trefethen and Embree, 2005; Trefethen and Bau, 1997).
Applications
- Principal component analysis (PCA): Principal components are eigenvectors of the covariance matrix; variances along components equal the corresponding eigenvalues. Symmetry and positive semidefiniteness ensure real, nonnegative spectra (Jolliffe, 2002).
- Graphs and networks: The graph Laplacian’s eigenvalues/eigenvectors encode connectivity; the Fiedler vector (second smallest eigenvector) supports partitioning and spectral clustering (Chung, 1997).
- Markov chains: The stationary distribution corresponds to eigenvalue 1 of a stochastic matrix; under irreducibility and aperiodicity, the stationary distribution is unique and globally attractive (Levin, Peres, and Wilmer, 2009; Horn and Johnson, 2013).
- Differential equations and dynamics: Spectral decompositions facilitate solutions of linear ODE systems and stability analysis via the real parts of eigenvalues (Strang, 2016; Trefethen and Bau, 1997).
Common Pitfalls and How to Address Them
- Confusing algebraic and geometric multiplicities: A multiple eigenvalue need not yield enough eigenvectors for diagonalization; check geometric multiplicity.
- Overlooking field issues: Diagonalization claims should specify the field (over C vs. over R); use the spectral theorem when symmetry/normality is available.
- Numerical misinterpretation: For non-normal matrices, small perturbations can cause large eigenvalue shifts; complement eigenvalue analysis with pseudospectral insight.
- Algorithmic mismatch: Use QR for dense problems; prefer Lanczos/Arnoldi for large sparse matrices; apply shifts and preconditioning where appropriate.
Quick Self-Check
- Can you state necessary and sufficient conditions for diagonalizability over C?
- When does the power method converge, and to what does it converge?
- Why are covariance matrices suitable for PCA, and what guarantees real principal components?
- How does the spectral theorem simplify solving symmetric linear systems and eigenproblems?
Key Takeaways
- Eigenvalues and eigenvectors reveal invariant directions and scaling factors of linear transformations, enabling reduction to simpler forms (diagonal or nearly diagonal).
- Structure informs computation: symmetry/normality yields real spectra, orthogonality, and robust algorithms.
- Robust practice integrates theory, numerics, and application context, with attention to conditioning and model structure.
Selected References
- Chung, F. R. K. (1997). Spectral Graph Theory. American Mathematical Society.
- Golub, G. H., & Van Loan, C. F. (2013). Matrix Computations (4th ed.). Johns Hopkins University Press.
- Horn, R. A., & Johnson, C. R. (2013). Matrix Analysis (2nd ed.). Cambridge University Press.
- Jolliffe, I. T. (2002). Principal Component Analysis (2nd ed.). Springer.
- Levin, D. A., Peres, Y., & Wilmer, E. L. (2009). Markov Chains and Mixing Times. American Mathematical Society.
- Strang, G. (2016). Introduction to Linear Algebra (5th ed.). Wellesley–Cambridge Press.
- Trefethen, L. N., & Bau, D. (1997). Numerical Linear Algebra. SIAM.
- Trefethen, L. N., & Embree, M. (2005). Spectra and Pseudospectra. Princeton University Press.
