Algebra

Eigenvalues and diagonalization

Special scalars and vectors that reveal the simplest form of a linear transformation.

IntuitionWhat an eigenvector really is

Most vectors get pushed off in a completely new direction when a linear map $A$ acts on them, and often get rotated as well as stretched. But for a special few directions, the map only stretches or shrinks the vector along the same line it already lay on — it never rotates it. Those special directions are the eigenvectors of $A$ , and the stretching factor along each one is the corresponding eigenvalue: $A\mathbf{v} = \lambda \mathbf{v}$ . Picture a rubber sheet being stretched: most marked points slide sideways, but a couple of lines on the sheet only get longer or shorter, staying put on the same axis. Those axes are exactly the eigenvectors.

For a symmetric matrix (

a_{12}=a_{21}

), the two green dashed eigenvector axes are orthogonal: vectors along those axes only stretch by

\lambda_1, \lambda_2

without rotating.

SchoolFrom geometric picture to precise definition

Definition: Eigenvalue and eigenvector

Let $A$ be an $n \times n$ matrix. A nonzero vector $\mathbf{v}$ is called an eigenvector of $A$ if there is a scalar $\lambda$ such that $A\mathbf{v} = \lambda \mathbf{v}$ ; the scalar $\lambda$ is the eigenvalue attached to $\mathbf{v}$ . Geometrically, $A$ maps the whole line through $\mathbf{v}$ to itself, merely rescaling it by $\lambda$ .

A\mathbf{v} = \lambda \mathbf{v}

Rewriting the defining equation as $(A - \lambda I)\mathbf{v} = \mathbf{0}$ shows that $\mathbf{v} \neq \mathbf{0}$ can only exist when $A - \lambda I$ is singular, i.e. when its determinant vanishes: $\det(A - \lambda I) = 0$ . Expanding this determinant gives a degree- $n$ polynomial in $\lambda$ , the characteristic polynomial; its roots are exactly the eigenvalues of $A$ .

\det(A - \lambda I) = 0

Types of eigenvalues and what they mean geometrically
Case	Geometric meaning
$n$ distinct real eigenvalues	$n$ independent stretch axes; $A$ is always diagonalizable
Repeated eigenvalue, full eigenspace	Still diagonalizable: an entire plane (or higher) is stretched by the same factor
Repeated eigenvalue, defective eigenspace	Not diagonalizable: some directions get sheared, not just stretched
Complex conjugate pair	No real invariant line; the map rotates while it scales, like a spiral

UndergraduateDiagonalization and the spectral theorem

Theorem: Eigenvectors of distinct eigenvalues are independent

If $\lambda_1, \dots, \lambda_k$ are pairwise distinct eigenvalues of $A$ with eigenvectors $\mathbf{v}_1, \dots, \mathbf{v}_k$ , then $\{\mathbf{v}_1, \dots, \mathbf{v}_k\}$ is a linearly independent set.

Why is it true?

Each eigenvector marks out its own private invariant direction with its own private scaling factor; if one such direction could be built out of the others, applying $A$ would have to scale it by every one of those different factors at once, which is impossible unless the vector is zero.

Proof

We argue by induction on $k$ . For $k = 1$ the claim is trivial: a single nonzero vector is automatically linearly independent.

Assume the result holds for $k - 1$ distinct eigenvalues, and suppose toward contradiction that $\mathbf{v}_1, \dots, \mathbf{v}_k$ are linearly dependent. Then there is a relation $c_1 \mathbf{v}_1 + \cdots + c_k \mathbf{v}_k = \mathbf{0}$ with not all $c_i$ zero.

Apply $A$ to both sides: since $A\mathbf{v}_i = \lambda_i \mathbf{v}_i$ , this gives $c_1 \lambda_1 \mathbf{v}_1 + \cdots + c_k \lambda_k \mathbf{v}_k = \mathbf{0}$ . Now multiply the original relation by $\lambda_k$ and subtract it from this new equation; the terms with $\mathbf{v}_k$ cancel exactly, leaving $c_1(\lambda_1 - \lambda_k)\mathbf{v}_1 + \cdots + c_{k-1}(\lambda_{k-1} - \lambda_k)\mathbf{v}_{k-1} = \mathbf{0}$ .

By the induction hypothesis, $\mathbf{v}_1, \dots, \mathbf{v}_{k-1}$ are linearly independent, so every coefficient in this last relation must vanish: $c_i(\lambda_i - \lambda_k) = 0$ for $i < k$ . Since the eigenvalues are pairwise distinct, $\lambda_i - \lambda_k \neq 0$ , forcing $c_i = 0$ for all $i < k$ .

Substituting back into the original relation leaves $c_k \mathbf{v}_k = \mathbf{0}$ ; since $\mathbf{v}_k \neq \mathbf{0}$ by definition of eigenvector, $c_k = 0$ as well. Every coefficient is zero, contradicting our assumption that not all $c_i$ vanish. Hence no such dependence relation exists, and the eigenvectors are linearly independent.

Theorem: Spectral theorem for real symmetric matrices

If $A$ is a real $n \times n$ symmetric matrix, $A^\top = A$ , then there is an orthogonal matrix $Q$ (meaning $Q^\top Q = I$ ) and a real diagonal matrix $\Lambda$ such that $A = Q \Lambda Q^\top$ . Equivalently, $A$ has $n$ real eigenvalues and an orthonormal basis of eigenvectors.

Why is it true?

Symmetric matrices show up constantly — covariance matrices, moments of inertia, Hessians of smooth functions — and this theorem guarantees you can always rotate to a coordinate frame where the matrix acts by pure independent scaling along perpendicular axes, with no shearing and no complex behaviour whatsoever.

Proof

We first record a lemma: every eigenvalue of a real symmetric matrix is real. If $A\mathbf{v} = \lambda \mathbf{v}$ with $\mathbf{v} \neq \mathbf{0}$ possibly complex, consider $\mathbf{v}^{*}A\mathbf{v}$ where $\mathbf{v}^{*}$ is the conjugate transpose. Since $A$ is real and symmetric, $\mathbf{v}^{*}A\mathbf{v} = (\mathbf{v}^{*}A\mathbf{v})^{*}$ , so this quantity is real; but it also equals $\lambda \, \mathbf{v}^{*}\mathbf{v}$ , and $\mathbf{v}^{*}\mathbf{v} > 0$ is a positive real number, forcing $\lambda$ itself to be real.

We now prove the theorem by induction on $n$ . The case $n = 1$ is trivial: any $1 \times 1$ matrix is already diagonal, with $Q = (1)$ .

For the inductive step, assume the theorem holds for all real symmetric matrices of size $n - 1$ . Since $A$ is $n \times n$ real symmetric, by the lemma its characteristic polynomial has a real root $\lambda_1$ ; choose a corresponding eigenvector and normalize it to a unit vector $\mathbf{v}_1$ .

Let $W$ be the orthogonal complement of the line spanned by $\mathbf{v}_1$ , an $(n-1)$ -dimensional subspace. We claim $W$ is invariant under $A$ : for any $\mathbf{w} \in W$ (so $\mathbf{w}^\top \mathbf{v}_1 = 0$ ), we compute $(A\mathbf{w})^\top \mathbf{v}_1 = \mathbf{w}^\top A^\top \mathbf{v}_1 = \mathbf{w}^\top A \mathbf{v}_1 = \lambda_1 \mathbf{w}^\top \mathbf{v}_1 = 0$ , using symmetry of $A$ in the middle step. So $A\mathbf{w}$ is again orthogonal to $\mathbf{v}_1$ , i.e. $A\mathbf{w} \in W$ .

Choose an orthonormal basis of $W$ ; in this basis, the restriction of $A$ to $W$ is represented by an $(n-1) \times (n-1)$ matrix $A'$ , and $A'$ is symmetric because $A$ is (restricting a symmetric bilinear form to a subspace, in an orthonormal basis, keeps it symmetric). By the induction hypothesis, $A'$ has an orthonormal basis of eigenvectors $\mathbf{v}_2, \dots, \mathbf{v}_n$ inside $W$ , with real eigenvalues $\lambda_2, \dots, \lambda_n$ ; since $W$ is $A$ -invariant, these are also genuine eigenvectors of $A$ itself.

Collecting $\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_n$ gives an orthonormal basis of $\mathbb{R}^n$ made entirely of eigenvectors of $A$ . Assembling them as the columns of a matrix $Q$ makes $Q$ orthogonal, and $AQ = Q\Lambda$ where $\Lambda = \mathrm{diag}(\lambda_1, \dots, \lambda_n)$ ; since $Q^{-1} = Q^\top$ for an orthogonal matrix, this rearranges exactly to $A = Q \Lambda Q^\top$ , completing the induction.

UndergraduateReal-World Applications and Worked Examples

Eigenvalues and eigenvectors are the hidden variables behind vibration frequencies of bridges and buildings, the ranking algorithm behind web search, and the principal directions used to compress data.

Example: Natural frequencies of a two-mass spring system

Two equal masses $m$ slide on a frictionless line; each is tied to a wall by a spring of stiffness $k$ , and the two masses are also tied to each other by a third spring of stiffness $k$ . Find the natural frequencies of oscillation and describe the corresponding modes of vibration.

Solution

Newton's second law for displacements $x_1, x_2$ gives $m\ddot{x}_1 = -2kx_1 + kx_2$ and $m\ddot{x}_2 = kx_1 - 2kx_2$ , i.e. $m\ddot{\mathbf{x}} = -K\mathbf{x}$ with matrix $K = \begin{pmatrix} 2k & -k \\ -k & 2k \end{pmatrix}$ .

Seeking oscillatory solutions $\mathbf{x}(t) = \mathbf{v}\cos(\omega t)$ turns the system into the eigenvalue problem $K\mathbf{v} = m\omega^2 \mathbf{v}$ , so $m\omega^2$ must be an eigenvalue of $K$ . The characteristic equation $\det(K - \mu I) = (2k-\mu)^2 - k^2 = 0$ gives $\mu = 3k$ or $\mu = k$ .

For $\mu = 3k$ : $(K - 3kI)\mathbf{v} = 0$ gives $-k v_1 - k v_2 = 0$ , i.e. $\mathbf{v} = (1,-1)$ — the masses swing in opposite directions, and $\omega_1 = \sqrt{3k/m}$ . For $\mu = k$ : $(K - kI)\mathbf{v}=0$ gives $k v_1 - k v_2 = 0$ , i.e. $\mathbf{v} = (1,1)$ — the masses swing together in phase, with $\omega_2 = \sqrt{k/m}$ .

So the two eigenvectors of $K$ are exactly the two normal modes of vibration, and their eigenvalues fix the two natural frequencies — precisely why this problem is, at heart, an eigenvalue problem.

Example: PageRank as a dominant eigenvector

A tiny web of three pages $A, B, C$ links as follows: $A$ links equally to $B$ and $C$ ; $B$ links only to $C$ ; $C$ links only to $A$ . Model a random surfer with a column-stochastic transition matrix and find the long-run fraction of time spent on each page.

Solution

The column-stochastic transition matrix (columns give outgoing link probabilities from each page) is $P = \begin{pmatrix} 0 & 0 & 1 \\ 0.5 & 0 & 0 \\ 0.5 & 1 & 0 \end{pmatrix}$ (rows/columns ordered $A,B,C$ ). The steady-state ranking $\boldsymbol{\pi}$ is the eigenvector of $P$ for eigenvalue $1$ , satisfying $P\boldsymbol{\pi} = \boldsymbol{\pi}$ and $\pi_A + \pi_B + \pi_C = 1$ .

Writing out $P\boldsymbol{\pi} = \boldsymbol{\pi}$ : $\pi_C = \pi_A$ , $0.5\pi_A = \pi_B$ , and $0.5\pi_A + \pi_B = \pi_C$ . The first two equations already give $\pi_C = \pi_A$ and $\pi_B = 0.5\pi_A$ ; substituting into the third confirms $0.5\pi_A + 0.5\pi_A = \pi_A = \pi_C$ , consistent.

Setting $\pi_A = x$ gives $\pi_B = 0.5x$ , $\pi_C = x$ , so the normalization $x + 0.5x + x = 2.5x = 1$ gives $x = 0.4$ . The steady-state ranking is $(\pi_A, \pi_B, \pi_C) = (0.4, 0.2, 0.4)$ : pages $A$ and $C$ are equally and most "important", exactly as one expects since they link directly to each other in a tight cycle, while $B$ only receives traffic from $A$ .

This is precisely the idea behind PageRank: importance is not counted by counting links, but by finding the dominant eigenvector (eigenvalue $1$ ) of the link-transition matrix, found in practice by repeatedly multiplying by $P$ (the power method), which always converges to the same principal eigenvector regardless of the starting guess.

What are the eigenvalues of $A = \begin{pmatrix} 4 & 1 \\ 2 & 3 \end{pmatrix}$ ?

What is the key geometric property that distinguishes an eigenvector from an ordinary vector under a linear map $A$ ?

In the PageRank model, why does the steady-state importance ranking of web pages correspond to an eigenvector?

Why is the matrix $\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$ not diagonalizable, even though it has a repeated eigenvalue $\lambda = 1$ ?

References

Gilbert Strang (2016). Introduction to Linear Algebra
Sheldon Axler (2015). Linear Algebra Done Right