{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Lesson 17 - The Whole Spectrum at Once\n", "\n", "**Learning goals.** By the end of this lecture, students should be able to:\n", "\n", "- explain what it means to compute the full spectrum of a matrix,\n", "- relate the characteristic polynomial to eigenvalues for small matrices,\n", "- use numerical routines to compute all eigenvalues and eigenvectors of a matrix,\n", "- interpret eigenvectors as modes associated with a linear operator,\n", "- compare single-eigenpair iteration with full-spectrum computation in terms of cost, information, and use case.\n", "\n", "**Key terms.** spectrum, characteristic polynomial, eigenbasis, modal matrix, diagonalization.\n", "\n", "Lesson 16 focused on one eigenpair selected by iteration. This chapter asks what is gained and what becomes more expensive when we ask for all eigenvalues and eigenvectors at once.\n", "\n", "## From one eigenpair to the full spectrum\n", "\n", "In Lesson 16, iteration singled out one dominant eigenpair. That is often enough for applications, but sometimes we want the entire set of eigenvalues at once. The central object is the *characteristic polynomial*.\n", "\n", "**Definition.**\n", "\n", "For an $n\\times n$ matrix $\\mathbf{A}$, the characteristic polynomial is\n", "\n", "$$\n", " p(\\lambda)=\\det(\\mathbf{A}-\\lambda\\mathbf{I}).\n", "$$\n", "\n", "The eigenvalues of $\\mathbf{A}$ are exactly the roots of $p(\\lambda)=0$.\n", "\n", "Why does this work? A nonzero vector $\\mathbf{v}$ satisfies\n", "\n", "$$\n", " \\mathbf{A}\\mathbf{v}=\\lambda\\mathbf{v}\n", "$$\n", "\n", "if and only if\n", "\n", "$$\n", " (\\mathbf{A}-\\lambda\\mathbf{I})\\mathbf{v}=\\mathbf{0}.\n", "$$\n", "\n", "A homogeneous linear system has a nontrivial solution precisely when its matrix is singular, so\n", "\n", "$$\n", " \\det(\\mathbf{A}-\\lambda\\mathbf{I})=0.\n", "$$\n", "\n", "The determinant appears here because it detects singularity. (If $\\mathbf{B}=[b_{ij}]$, the determinant can be expanded along any row or column using cofactors $C_{ij}=(-1)^{i+j}M_{ij}$, where $M_{ij}$ is the minor obtained by deleting row $i$ and column $j$. We mention cofactors only as a side note because they are exactly what appears when forming $\\det(\\mathbf{A}-\\lambda\\mathbf{I})$.) Once the determinant is written out, we obtain a polynomial of degree $n$ in $\\lambda$.\n", "\n", "## Low dimensions: what can be done analytically\n", "\n", "### One dimension\n", "\n", "For a $1\\times 1$ matrix,\n", "\n", "$$\n", " \\mathbf{A}=\\begin{bmatrix}a\\end{bmatrix},\n", "$$\n", "\n", "the characteristic equation is\n", "\n", "$$\n", " a-\\lambda=0,\n", "$$\n", "\n", "so the only eigenvalue is\n", "\n", "$$\n", " \\lambda=a.\n", "$$\n", "\n", "### Two dimensions\n", "\n", "For\n", "\n", "$$\n", " \\mathbf{A}=\\begin{bmatrix}a & b \\\\ c & d\\end{bmatrix},\n", "$$\n", "\n", "we compute\n", "\n", "$$\n", " \\det(\\mathbf{A}-\\lambda\\mathbf{I})=\\det\\begin{bmatrix}a-\\lambda & b \\\\ c & d-\\lambda\\end{bmatrix}=0.\n", "$$\n", "\n", "This gives\n", "\n", "$$\n", " \\lambda^2-(a+d)\\lambda+(ad-bc)=0.\n", "$$\n", "\n", "Thus the eigenvalues are\n", "\n", "$$\n", " \\lambda=\\frac{\\operatorname{tr}(\\mathbf{A})\\pm\\sqrt{\\operatorname{tr}(\\mathbf{A})^2-4\\det(\\mathbf{A})}}{2}.\n", "$$\n", "\n", "In two dimensions, the trace and determinant already summarize a great deal of spectral information.\n", "\n", "### Three and four dimensions\n", "\n", "For a $3\\times 3$ matrix, the characteristic polynomial is cubic. A closed-form cubic formula exists. For a $4\\times 4$ matrix, a quartic formula also exists. In principle these are analytical solutions; in practice they become cumbersome very quickly and are rarely the best way to compute eigenvalues by hand or on a computer.\n", "\n", "### Five dimensions and beyond\n", "\n", "For an $n\\times n$ matrix, the characteristic polynomial has degree $n$. When $n\\geq 5$, there is no general formula in radicals for an arbitrary polynomial of degree $n$. This does *not* mean that special matrices can never be solved analytically. It means that there is no universal closed-form recipe analogous to the quadratic formula for all higher-degree characteristic polynomials. That is why numerical methods become the natural default for general matrices.\n", "\n", "**Takeaway.**\n", "\n", "Up through $2\\times 2$, the formulas are friendly. By $3\\times 3$, they are already awkward. By $4\\times 4$, they are usually too ugly to be worth printing in full. Beyond that, a general algebraic formula is not available, so numerical eigensolvers are the right tool in the general case.\n", "\n", "## The full spectral picture\n", "\n", "If $\\mathbf{A}$ has $n$ linearly independent eigenvectors, collect them as the columns of\n", "\n", "$$\n", " \\mathbf{V}=\\begin{bmatrix}\\mathbf{v}_1 & \\mathbf{v}_2 & \\cdots & \\mathbf{v}_n\\end{bmatrix},\n", "$$\n", "\n", "and place the eigenvalues on the diagonal of\n", "\n", "$$\n", " \\mathbf{\\Lambda}=\\begin{bmatrix}\n", " \\lambda_1 & 0 & \\cdots & 0 \\\\\n", " 0 & \\lambda_2 & \\cdots & 0 \\\\\n", " \\vdots & \\vdots & \\ddots & \\vdots \\\\\n", " 0 & 0 & \\cdots & \\lambda_n\n", " \\end{bmatrix}.\n", "$$\n", "\n", "Then\n", "\n", "$$\n", " \\mathbf{A}\\mathbf{V}=\\mathbf{V}\\mathbf{\\Lambda},\n", "$$\n", "\n", "and, because $\\mathbf{V}$ is invertible,\n", "\n", "$$\n", " \\mathbf{A}=\\mathbf{V}\\mathbf{\\Lambda}\\mathbf{V}^{-1}.\n", "$$\n", "\n", "This is diagonalization. A matrix that admits this factorization is called *diagonalizable*. The condition matters: the eigenvectors must give a full basis for the state space, not just a few useful directions.\n", "\n", "Diagonalization is powerful because matrix powers become simple:\n", "\n", "$$\n", " \\mathbf{A}^k=\\mathbf{V}\\mathbf{\\Lambda}^k\\mathbf{V}^{-1}.\n", "$$\n", "\n", "So the full spectrum gives a complete modal description of repeated application of the matrix. It is also the same decoupling move used later for systems of differential equations: write the state as a combination of eigenvectors, evolve each modal coefficient separately, and then transform back.\n", "\n", "## Zero eigenvalues and invertibility\n", "\n", "One eigenvalue is especially important: zero.\n", "\n", "**Proposition.**\n", "\n", "For a square matrix $\\mathbf{A}$, the following are equivalent:\n", "\n", "1. $0$ is an eigenvalue of $\\mathbf{A}$,\n", "1. $\\mathbf{A}$ is singular,\n", "1. $\\det(\\mathbf{A})=0$,\n", "1. the homogeneous system $\\mathbf{A}\\mathbf{x}=\\mathbf{0}$ has a nontrivial solution.\n", "\n", "**Proof.**\n", "\n", "If $0$ is an eigenvalue, then there exists a nonzero vector $\\mathbf{v}$ with\n", "\n", "$$\n", " \\mathbf{A}\\mathbf{v}=0\\mathbf{v}=\\mathbf{0},\n", "$$\n", "\n", "so the nullspace is nontrivial and $\\mathbf{A}$ cannot be invertible. Conversely, if $\\mathbf{A}$ is singular, then the homogeneous system has a nonzero solution, which is exactly an eigenvector associated with $\\lambda=0$.\n", "\n", "In Gaussian elimination, singularity appears as an unavoidable zero pivot once the matrix has been reduced as far as row operations allow. Pivoting can move the location of the zero, but it cannot remove the underlying dependence. A zero eigenvalue is therefore the spectral signature of dependence among rows or columns.\n", "\n", "**Example.**\n", "\n", "Consider\n", "\n", "$$\n", " \\mathbf{A}=\\begin{bmatrix}1 & 2 \\\\ 2 & 4\\end{bmatrix}.\n", "$$\n", "\n", "The second row is twice the first, so the rows are linearly dependent and\n", "\n", "$$\n", " \\det(\\mathbf{A})=1\\cdot 4-2\\cdot 2=0.\n", "$$\n", "\n", "The characteristic polynomial is\n", "\n", "$$\n", " \\det(\\mathbf{A}-\\lambda\\mathbf{I})=\\lambda^2-5\\lambda,\n", "$$\n", "\n", "so the eigenvalues are\n", "\n", "$$\n", " \\lambda_1=5, \\qquad \\lambda_2=0.\n", "$$\n", "\n", "The zero eigenvalue is exactly what tells us that $\\mathbf{A}$ is not invertible.\n", "\n", "## Computing eigenpairs in practice\n", "\n", "For a small dense matrix, it is often reasonable to compute the full spectrum directly with a library routine. In Python/NumPy, a standard choice for a general square matrix is `numpy.linalg.eig`. For a real symmetric matrix or a complex Hermitian matrix, `numpy.linalg.eigh` is usually the better match because it is specialized to that structure.\n", "\n", "For large sparse matrices, forming the full dense spectrum is usually wasteful. In that setting, sparse iterative solvers are preferred when only a few eigenpairs are needed. Common choices are `scipy.sparse.linalg.eigs` for a general sparse matrix and `scipy.sparse.linalg.eigsh` for a real symmetric or complex Hermitian sparse matrix. These routines are especially useful when combined with the same shift-invert logic discussed in Lesson 16.\n", "\n", "**Listing.** Typical dense and sparse eigensolver calls in Python.\n", "\n", "```python\n", "import numpy as np\n", "from scipy.sparse.linalg import eigs, eigsh\n", "\n", "# Dense, general matrix\n", "w, V = np.linalg.eig(A)\n", "\n", "# Dense, symmetric/Hermitian matrix\n", "w_sym, V_sym = np.linalg.eigh(A)\n", "\n", "# Sparse, a few eigenpairs of largest magnitude\n", "w_sparse, V_sparse = eigs(A_sparse, k=3, which='LM')\n", "\n", "# Sparse, symmetric/Hermitian case\n", "w_sparse_sym, V_sparse_sym = eigsh(A_sparse, k=3, which='LM')\n", "```\n", "\n", "No matter which routine is used, it is good practice to verify the result with a residual check. For a computed pair $(\\lambda,\\mathbf{v})$, examine\n", "\n", "$$\n", " \\left\\lVert \\mathbf{A}\\mathbf{v}-\\lambda\\mathbf{v} \\right\\rVert.\n", "$$\n", "\n", "A small residual means the pair is numerically consistent with the eigenvalue equation.\n", "\n", "## What about the eigenvectors?\n", "\n", "Once an eigenvalue $\\lambda$ is known, the corresponding eigenvectors are found from the homogeneous system\n", "\n", "$$\n", " (\\mathbf{A}-\\lambda\\mathbf{I})\\mathbf{v}=\\mathbf{0}.\n", "$$\n", "\n", "Because any nonzero scalar multiple of an eigenvector is again an eigenvector, eigenvectors are never unique in magnitude. We therefore choose a normalization convention such as\n", "\n", "$$\n", " \\left\\lVert \\mathbf{v} \\right\\rVert=1.\n", "$$\n", "\n", "A repeated eigenvalue does not automatically imply repeated eigenvectors. Some matrices have enough independent eigenvectors to diagonalize cleanly; others do not. For symmetric matrices, life is especially pleasant: eigenvectors associated with distinct eigenvalues are orthogonal, so they can be arranged into an orthonormal basis.\n", "\n", "This is the right place to preview Gram--Schmidt. Gram--Schmidt can be used to orthogonalize a set of already computed vectors, or to complete a partial set to a full orthonormal basis of the vector space. However, the vectors added during that completion are not generally eigenvectors. Gram--Schmidt is therefore a basis-building and orthogonalization tool, not a stand-alone eigenvector finder.\n", "\n", "## Exercises\n", "\n", "1. Find the characteristic polynomial of\n", "$$\n", " \\mathbf{A}=\n", " \\begin{bmatrix}\n", " 2 & 1\\\\\n", " 1 & 2\n", " \\end{bmatrix}.\n", "$$\n", "\n", "What are the eigenvalues?\n", "\n", "1. Explain why a zero eigenvalue means that a matrix is singular.\n", "1. If $\\mathbf{A}=\\mathbf{V}\\mathbf{\\Lambda}\\mathbf{V}^{-1}$, write a formula for $\\mathbf{A}^k$. What happens to the eigenvalues?\n", "1. Why is a symmetric eigensolver such as `eigh` preferred for real symmetric matrices?\n", "\n", "**Answers.**\n", "\n", "1. The characteristic polynomial is\n", "$$\n", " \\det(\\mathbf{A}-\\lambda\\mathbf{I})\n", " =(2-\\lambda)^2-1\n", " =\\lambda^2-4\\lambda+3.\n", "$$\n", "\n", "The eigenvalues are $1$ and $3$.\n", "\n", "1. If $\\lambda=0$, then there is a nonzero vector $\\mathbf{v}$ with $\\mathbf{A}\\mathbf{v}=\\mathbf{0}$. The null space is nontrivial, so $\\mathbf{A}$ cannot be invertible.\n", "1. The power is\n", "$$\n", " \\mathbf{A}^k=\\mathbf{V}\\mathbf{\\Lambda}^k\\mathbf{V}^{-1}.\n", "$$\n", "\n", "Each eigenvalue is raised to the $k$th power.\n", "\n", "1. The symmetric solver uses the symmetry of the matrix, returns real eigenvalues with orthogonal eigenvectors, and is usually more stable and efficient than a general eigensolver for this case.\n", "\n", "## End-of-lecture summary\n", "\n", "**Takeaway.**\n", "\n", "- The full set of eigenvalues is obtained from the characteristic polynomial $\\det(\\mathbf{A}-\\lambda\\mathbf{I})=0$.\n", "- Low-dimensional cases admit analytical formulas, but those formulas quickly become impractical.\n", "- A zero eigenvalue means the matrix is singular and cannot be inverted.\n", "- Numerical methods are the standard approach for general matrices, especially in moderate-to-large dimensions.\n", "- Once eigenvalues are known, eigenvectors come from solving homogeneous systems and then normalizing.\n", "- Lesson 18 uses these modal ingredients to interpret growth, decay, stability, and reactor-physics examples.\n" ], "id": "l17-thewholespectrumatonce" } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3" } }, "nbformat": 4, "nbformat_minor": 5 }