Eigenvalues & Eigenvectors

Table of Contents

1. Learning Objectives
2. Prerequisites
3. Notation
4. Core Intuition
5. Definition and the Characteristic Polynomial
6. Properties of Eigenvalues and Eigenvectors
7. Diagonalization
8. The Spectral Theorem
9. Rayleigh Quotient and Variational Characterization
10. Application: Principal Component Analysis
11. Application: Gradient Descent Convergence
12. Spectral Properties of Matrices in ML
13. Appendix: Completing the Spectral Theorem Proof
14. Common Pitfalls and Misconceptions
15. Research Perspective
16. Summary of Takeaways
17. Exercises

Learning Objectives

After reading this chapter, you should be able to:

1. Define eigenvalues and eigenvectors and derive the characteristic equation $\det(\mathbf{A} - \lambda\mathbf{I}) = 0$.
2. Prove that eigenvectors for distinct eigenvalues are linearly independent.
3. State and apply the spectral theorem for real symmetric matrices.
4. Derive PCA as maximization of the Rayleigh quotient.
5. Analyze gradient descent convergence on quadratic objectives via eigenvalue decomposition.
6. Interpret covariance, Hessian, and graph Laplacian spectra in machine learning contexts.

Prerequisites

• Vectors, Spans & Linear Independence: inner products, orthogonality, basis.
• Matrix Operations & Linear Transformations: determinants, rank, null space, symmetric matrices.

Notation

• $\lambda$ — Eigenvalue
• $\mathbf{v}$ — Eigenvector with $\mathbf{A}\mathbf{v} = \lambda \mathbf{v}$
• $p(\lambda) = \det(\mathbf{A} - \lambda \mathbf{I})$ — Characteristic polynomial
• $\mathbf{Q}, \boldsymbol{\Lambda}$ — Eigenvector matrix and diagonal eigenvalue matrix
• $\text{tr}(\mathbf{A}), \det(\mathbf{A})$ — Trace and determinant

Core Intuition

Every linear transformation $\mathbf{A}$ mixes directions in general — rotating, shearing, and scaling simultaneously. Eigenvectors are the privileged directions that $\mathbf{A}$ acts on by pure scaling: $\mathbf{A}\mathbf{v} = \lambda\mathbf{v}$. The scalar $\lambda$ is the eigenvalue. When we express a vector in the eigenbasis, the action of $\mathbf{A}$ becomes diagonal — each coordinate is multiplied by its eigenvalue.

For symmetric matrices — covariance matrices, Hessians, kernel Gram matrices — eigenvectors are orthogonal and eigenvalues are real. This is the spectral theorem, the mathematical engine behind PCA, spectral clustering, and quadratic optimization theory. The ratio $\lambda_{\max}/\lambda_{\min}$, the condition number, governs how fast gradient descent converges on quadratic losses.

Series context. This is Part III of Chapter 1. The SVD generalizes eigendecomposition to rectangular matrices.

Definition and the Characteristic Polynomial

Definition 1 (Eigenvalue, Eigenvector). Let $\mathbf{A} \in \mathbb{R}^{n \times n}$. A nonzero vector $\mathbf{v} \in \mathbb{R}^n$ is an eigenvector with eigenvalue $\lambda \in \mathbb{C}$ if

Derivation of the characteristic equation. Rearranging (1):

For nonzero $\mathbf{v}$, the matrix $(\mathbf{A} - \lambda\mathbf{I})$ must be singular:

Definition 2 (Characteristic Polynomial).

is a polynomial of degree $n$. Its roots (in $\mathbb{C}$) are the eigenvalues.

Example 1. For $\mathbf{A} = \begin{bmatrix} 4 & 1 \\ 2 & 3 \end{bmatrix}$:

Eigenvalues: $\lambda_1 = 5$, $\lambda_2 = 2$.

For $\lambda_1 = 5$: $(\mathbf{A} - 5\mathbf{I})\mathbf{v} = \mathbf{0}$ gives $\mathbf{v}_1 \propto (1, 1)^T$.

For $\lambda_2 = 2$: $\mathbf{v}_2 \propto (1, -2)^T$.

Geometric interpretation. Along $\mathbf{v}_1$, $\mathbf{A}$ stretches by factor 5. Along $\mathbf{v}_2$, by factor 2. In general directions, the transformation combines rotation and scaling.

Visual description. Imagine a unit circle in $\mathbb{R}^2$. A linear map sends it to an ellipse. The eigenvectors point along the major and minor axes of that ellipse; eigenvalues give the axis lengths (up to sign).

Properties of Eigenvalues and Eigenvectors

Theorem 1 (Trace and Determinant). If $\mathbf{A} \in \mathbb{R}^{n \times n}$ has eigenvalues $\lambda_1, \ldots, \lambda_n$ (with algebraic multiplicity):

Proof. The characteristic polynomial factors as $p(\lambda) = (-1)^n \prod_{i=1}^n (\lambda - \lambda_i)$. Comparing coefficients: the $\lambda^{n-1}$ term gives $\text{tr}(\mathbf{A}) = \sum \lambda_i$; setting $\lambda = 0$ gives $\det(\mathbf{A}) = \prod \lambda_i$. $\blacksquare$

Corollary 1. $\mathbf{A}$ is singular iff $\lambda = 0$ is an eigenvalue.

Theorem 2 (Independence of Eigenvectors). Eigenvectors corresponding to distinct eigenvalues are linearly independent.

Proof (induction on number of distinct eigenvalues). For one eigenvector, independence is trivial. Suppose $\mathbf{v}_1, \ldots, \mathbf{v}_k$ are eigenvectors with distinct eigenvalues $\lambda_1, \ldots, \lambda_k$. Assume $\sum_{i=1}^k \alpha_i \mathbf{v}_i = \mathbf{0}$ with not all $\alpha_i = 0$. Apply $\mathbf{A}$:

Multiply the original equation by $\lambda_k$ and subtract:

By induction, $\alpha_i(\lambda_i - \lambda_k) = 0$ for $i < k$. Since $\lambda_i \neq \lambda_k$, $\alpha_i = 0$ for $i < k$. Then $\alpha_k \mathbf{v}_k = \mathbf{0}$ gives $\alpha_k = 0$. $\blacksquare$

Proposition 1 (Similarity invariance of spectrum). If $\mathbf{B} = \mathbf{P}^{-1}\mathbf{A}\mathbf{P}$, then $\mathbf{A}$ and $\mathbf{B}$ have the same eigenvalues.

Proof. $\det(\mathbf{B} - \lambda\mathbf{I}) = \det(\mathbf{P}^{-1}(\mathbf{A}-\lambda\mathbf{I})\mathbf{P}) = \det(\mathbf{A}-\lambda\mathbf{I})$. $\blacksquare$

Diagonalization

Definition 3 (Diagonalizable). $\mathbf{A}$ is diagonalizable if $\mathbf{A} = \mathbf{P}\boldsymbol{\Lambda}\mathbf{P}^{-1}$ where $\boldsymbol{\Lambda} = \text{diag}(\lambda_1, \ldots, \lambda_n)$ and columns of $\mathbf{P}$ are eigenvectors.

Theorem 3. $\mathbf{A} \in \mathbb{R}^{n \times n}$ is diagonalizable iff $\mathbb{R}^n$ has a basis of eigenvectors — equivalently, iff there are $n$ linearly independent eigenvectors.

Proof. If $\mathbf{A} = \mathbf{P}\boldsymbol{\Lambda}\mathbf{P}^{-1}$, then $\mathbf{A}\mathbf{P} = \mathbf{P}\boldsymbol{\Lambda}$, so column $j$ of $\mathbf{P}$ satisfies $\mathbf{A}\mathbf{p}_j = \lambda_j \mathbf{p}_j$. Conversely, if $\mathbf{p}_1, \ldots, \mathbf{p}_n$ are independent eigenvectors with eigenvalues $\lambda_i$, then $\mathbf{P} = [\mathbf{p}_1 | \cdots | \mathbf{p}_n]$ is invertible and $\mathbf{A}\mathbf{P} = \mathbf{P}\boldsymbol{\Lambda}$, giving $\mathbf{A} = \mathbf{P}\boldsymbol{\Lambda}\mathbf{P}^{-1}$. $\blacksquare$

Corollary 2 (Powers of matrices).

For recurrent networks, if $|\lambda_i| > 1$ for some $i$, repeated application causes exploding activations; if $|\lambda_i| < 1$, vanishing activations.

Example 2 (Non-diagonalizable). $\mathbf{A} = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}$ has eigenvalue 1 with algebraic multiplicity 2 but geometric multiplicity 1 (only one independent eigenvector). Such defective matrices require Jordan form beyond this chapter.

The Spectral Theorem

Theorem 4 (Spectral Theorem for Real Symmetric Matrices). If $\mathbf{A} \in \mathbb{R}^{n \times n}$ satisfies $\mathbf{A} = \mathbf{A}^T$, then:

1. All eigenvalues are real.
2. Eigenvectors for distinct eigenvalues are orthogonal.
3. $\mathbf{A}$ is orthogonally diagonalizable:

Proof of (1): Real eigenvalues.

Let $\mathbf{A}\mathbf{v} = \lambda\mathbf{v}$ with $\mathbf{v} \neq \mathbf{0}$, $\lambda \in \mathbb{C}$. Take complex conjugate: $\mathbf{A}\bar{\mathbf{v}} = \bar{\lambda}\bar{\mathbf{v}}$ (since $\mathbf{A}$ is real). Then:

Since $\mathbf{v}^T\bar{\mathbf{v}} = \|\mathbf{v}\|^2 > 0$, we have $\lambda = \bar{\lambda} \in \mathbb{R}$. $\blacksquare$

Proof of (2): Orthogonality.

Let $\mathbf{A}\mathbf{v}_1 = \lambda_1 \mathbf{v}_1$, $\mathbf{A}\mathbf{v}_2 = \lambda_2 \mathbf{v}_2$, $\lambda_1 \neq \lambda_2$. Then:

So $(\lambda_1 - \lambda_2)\mathbf{v}_1^T\mathbf{v}_2 = 0$, hence $\mathbf{v}_1^T\mathbf{v}_2 = 0$. $\blacksquare$

Important equation. Equation (10) is the central decomposition for symmetric matrices. For covariance $\boldsymbol{\Sigma}$, columns of $\mathbf{Q}$ are principal directions and $\boldsymbol{\Lambda}$ contains variances along those directions.

Rayleigh Quotient and Variational Characterization

Definition 4 (Rayleigh Quotient). For symmetric $\mathbf{A}$ and nonzero $\mathbf{x}$:

Theorem 5 (Rayleigh's Principle). Let $\mathbf{A}$ be symmetric with eigenvalues $\lambda_1 \leq \cdots \leq \lambda_n$. Then:

The minimum is achieved at an eigenvector of $\lambda_{\min}$; the maximum at an eigenvector of $\lambda_{\max}$.

Proof sketch. Write $\mathbf{x} = \sum_{i=1}^n c_i \mathbf{q}_i$ in the orthonormal eigenbasis. Then $R(\mathbf{x}) = \sum_i \lambda_i c_i^2 / \sum_i c_i^2$, a weighted average of eigenvalues. Extremal values occur when all weight is on one eigenvalue. $\blacksquare$

Corollary 3 (Courant-Fischer). The $k$-th largest eigenvalue satisfies:

This variational characterization underpins PCA and spectral methods.

Application: Principal Component Analysis

Given centered data matrix $\mathbf{X} \in \mathbb{R}^{N \times d}$ (each row a sample), the sample covariance is:

$\mathbf{C}$ is symmetric positive semidefinite (Section on Positive Definite Matrices).

Goal. Find unit vector $\mathbf{u}$ maximizing projection variance:

Derivation via Lagrange multipliers. Define $\mathcal{L}(\mathbf{u}, \mu) = \mathbf{u}^T\mathbf{C}\mathbf{u} - \mu(\mathbf{u}^T\mathbf{u} - 1)$. Setting $\nabla_{\mathbf{u}} \mathcal{L} = \mathbf{0}$:

This is the eigenvalue equation. The maximum variance is $\mu = \lambda_{\max}$, achieved by the corresponding eigenvector — the first principal component.

Proportion of variance explained by the $k$-th component:

Connection to SVD. When $\mathbf{X} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^T$, columns of $\mathbf{V}$ are principal directions and $\sigma_i^2/(N-1) = \lambda_i$. See SVD.

Application: Gradient Descent Convergence

Consider minimizing the quadratic

where $\mathbf{A}$ is symmetric positive definite with eigenvalues $0 < \lambda_1 \leq \cdots \leq \lambda_n$.

The gradient is $\nabla f(\mathbf{x}) = \mathbf{A}\mathbf{x} - \mathbf{b}$. Gradient descent with step size $\eta$:

Analysis in the eigenbasis. Let $\mathbf{A} = \mathbf{Q}\boldsymbol{\Lambda}\mathbf{Q}^T$ and define $\mathbf{y}_t = \mathbf{Q}^T(\mathbf{x}_t - \mathbf{x}^*)$ where $\mathbf{A}\mathbf{x}^* = \mathbf{b}$. Then:

Each coordinate decouples: $y_{t+1,i} = (1 - \eta\lambda_i) y_{t,i}$.

Convergence condition. $|1 - \eta\lambda_i| < 1$ for all $i$, requiring:

Optimal step size (minimizing worst-case contraction factor):

Convergence rate:

where $\kappa = \lambda_n / \lambda_1$ is the condition number.

Important equation. Equation (25) shows that large $\kappa$ (elongated level sets) causes slow convergence — the motivation for preconditioning and adaptive optimizers in Gradient Descent.

Spectral Properties of Matrices in ML

• Covariance $\mathbf{C}$ — $\lambda_i \geq 0$, real — Variance along PC $i$
• Hessian $\mathbf{H}$ — Real (symmetric) — Curvature; negative $\lambda$ at saddles
• Graph Laplacian $\mathbf{L}$ — $\lambda_i \geq 0$, $\lambda_1 = 0$ — Smoothness on graphs
• Attention (pre-softmax) — Not symmetric in general — Affinity structure
• Normalized adjacency — $— \lambda — \leq 1$ — Random walk mixing

Power iteration. To find the dominant eigenvector, iterate $\mathbf{v}_{t+1} = \mathbf{A}\mathbf{v}_t / \|\mathbf{A}\mathbf{v}_t\|$. Convergence rate depends on $|\lambda_2|/|\lambda_1|$ — the foundation of PageRank and spectral methods.

Appendix: Completing the Spectral Theorem Proof

Proof of (3) in Theorem 4 (existence of orthonormal eigenbasis).

Proceed by induction on $n$. For $n = 1$, trivial. Assume true for $(n-1) \times (n-1)$ symmetric matrices.

Let $\lambda_1$ be an eigenvalue of $\mathbf{A}$ with unit eigenvector $\mathbf{q}_1$. Extend to orthonormal basis $\{\mathbf{q}_1, \mathbf{w}_2, \ldots, \mathbf{w}_n\}$ and form orthogonal $\mathbf{Q}_1 = [\mathbf{q}_1 | \mathbf{w}_2 | \cdots | \mathbf{w}_n]$.

Then:

where $\mathbf{B} \in \mathbb{R}^{(n-1)\times(n-1)}$ is symmetric (since $\mathbf{Q}_1^T\mathbf{A}\mathbf{Q}_1$ is symmetric). By induction, $\mathbf{B} = \mathbf{Q}_2\boldsymbol{\Lambda}_2\mathbf{Q}_2^T$. Assembling gives $\mathbf{A} = \mathbf{Q}\boldsymbol{\Lambda}\mathbf{Q}^T$ with $\mathbf{Q}$ orthogonal. $\blacksquare$

Common Pitfalls and Misconceptions

Pitfall 1: Assuming all matrices are diagonalizable. Defective matrices exist. Symmetric matrices are always diagonalizable; general matrices may require Jordan form.

Pitfall 2: Confusing algebraic and geometric multiplicity. A repeated eigenvalue may have fewer independent eigenvectors than its multiplicity.

Pitfall 3: Using eigenvalues of nonsymmetric weight matrices for stability. RNN weight matrices are generally nonsymmetric; spectral radius (max $|\lambda_i|$) determines stability, but eigenvectors need not be orthogonal.

Pitfall 4: PCA on uncentered data. Covariance (16) assumes centered data. Without centering, the first PC may capture the mean offset rather than variance structure.

Pitfall 5: Equating small eigenvalues with "unimportant" directions. Small covariance eigenvalues may correspond to noise — or to rare but semantically critical features. Truncation requires domain judgment.

Research Perspective

Eigendecomposition dates to Cauchy and Jacobi. The spectral theorem for symmetric operators was extended to infinite dimensions by Hilbert, enabling quantum mechanics and functional analysis.

In machine learning, PCA (Pearson, 1901; Hotelling, 1933) was among the first spectral learning methods. Spectral clustering (Ng, Jordan, Weiss, 2002) uses eigenvectors of graph Laplacians for nonlinear cluster structure. The Neural Tangent Kernel literature analyzes training dynamics via the spectrum of infinite-width kernel matrices.

Modern research on sharpness-aware minimization and Hessian spectrum analysis uses eigenvalues of the loss Hessian to characterize generalization. The condition number (25) remains the standard language for optimization difficulty in convex settings.

Summary of Takeaways

• Eigenvalue equation — $\mathbf{A}\mathbf{v} = \lambda\mathbf{v}$ — Characteristic modes
• Characteristic polynomial — $\det(\mathbf{A}-\lambda\mathbf{I})=0$ — Computing spectra
• Spectral theorem — $\mathbf{A} = \mathbf{Q}\boldsymbol{\Lambda}\mathbf{Q}^T$ for symmetric $\mathbf{A}$ — PCA, Hessian analysis
• Rayleigh quotient — Extrema = eigenvalues — Variational PCA
• Condition number — $\kappa = \lambda_{\max}/\lambda_{\min}$ — GD convergence rate
• Power iteration — Finds dominant eigenvector — PageRank, spectral methods

Next article: Singular Value Decomposition → — extending spectral analysis to arbitrary rectangular matrices.

Exercises

Exercise 1. Compute eigenvalues and eigenvectors of $\mathbf{A} = \begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix}$. Verify orthogonality of eigenvectors and diagonalize $\mathbf{A}$.

Exercise 2. Prove that if $\mathbf{A}$ is symmetric and idempotent ($\mathbf{A}^2 = \mathbf{A}$), then eigenvalues are 0 or 1. Interpret projection matrices in regression.

Exercise 3. Derive equation (25) explicitly by substituting $\eta^* = 2/(\lambda_1 + \lambda_n)$ into $|1 - \eta\lambda_i|$ and maximizing over $i$.

Exercise 4 (PCA). For data with covariance $\mathbf{C} = \text{diag}(3, 1, 0.5)$, compute PVE for each principal component. How many components capture 90% of variance?

Exercise 5 (Rayleigh quotient). Prove Theorem 5 for the maximum eigenvalue using the eigenbasis expansion of $\mathbf{x}$.

Exercise 6 (Conceptual). Explain why the graph Laplacian $\mathbf{L} = \mathbf{D} - \mathbf{A}$ (degree minus adjacency) is positive semidefinite by showing $\mathbf{x}^T\mathbf{L}\mathbf{x} = \sum_{(i,j) \in E} (x_i - x_j)^2 / 2$ for an undirected graph.

Exercise 7 (Power iteration). For $\mathbf{A}$ with eigenvalues $|\lambda_1| > |\lambda_2| \geq \cdots$, show that power iteration converges to $\mathbf{v}_1$ with error decreasing as $O(|\lambda_2/\lambda_1|^t)$.