Eigenvalues and Eigenvectors

The eigenvalue equation

A non-zero vector $\mathbf v$ is an eigenvector of a square matrix $A$ with eigenvalue $\lambda$ if

$$A\mathbf v = \lambda\mathbf v.$$

$A$ merely stretches $\mathbf v$ (by $\lambda$; flipping it if $\lambda < 0$) without changing its line. Rewriting, $(A - \lambda I)\mathbf v = \mathbf 0$ needs a non-zero solution, so $A - \lambda I$ must be singular:

$$\det(A - \lambda I) = 0 \quad\text{(the characteristic equation)}.$$

Procedure

1. Solve $\det(A - \lambda I) = 0$ for the eigenvalues (a degree-$n$ polynomial).
2. For each $\lambda$, find the null space of $A - \lambda I$: the eigenspace $E_\lambda$.

$2\times 2$ shortcut: $\lambda^2 - (\operatorname{tr}A)\lambda + \det A = 0$.

Trace, determinant and multiplicities

$$\sum_i\lambda_i = \operatorname{tr}A, \qquad \prod_i\lambda_i = \det A.$$

• Algebraic multiplicity of $\lambda$: its multiplicity as a root of the characteristic polynomial.
• Geometric multiplicity: $\dim E_\lambda = n - \operatorname{rank}(A - \lambda I)$.
• Always $1 \le \text{geometric} \le \text{algebraic}$.

Eigenvalues of related matrices

If $A\mathbf v = \lambda\mathbf v$:

Diagonalisation

$A$ is diagonalisable if $A = PDP^{-1}$, where $D = \operatorname{diag}(\lambda_1, \dots, \lambda_n)$ and the columns of $P$ are $n$ independent eigenvectors. This holds iff geometric = algebraic multiplicity for every eigenvalue. Sufficient conditions: $n$ distinct eigenvalues, or $A$ symmetric.

Payoff: powers and functions become easy: $A^k = PD^kP^{-1}$, $e^A = Pe^DP^{-1}$.

The spectral theorem

Every real symmetric matrix has real eigenvalues and an orthonormal basis of eigenvectors:

$$A = Q\Lambda Q^\top = \sum_{i=1}^n \lambda_i\,\mathbf q_i\mathbf q_i^\top.$$

It is a weighted sum of projections onto its eigen-directions. This is the decomposition behind PCA (covariance matrices are symmetric PSD), quadratic forms and the SVD.

Cayley–Hamilton theorem

Every square matrix satisfies its own characteristic equation: if $p(\lambda) = \det(\lambda I - A)$, then $p(A) = 0$.

Uses: express $A^n$ and higher powers in terms of $I, A, \dots, A^{n-1}$, and find $A^{-1}$ without row reduction. For $2\times 2$: $A^2 - (\operatorname{tr}A)A + (\det A)I = 0$.

Why eigenvectors matter

• PCA: principal components are eigenvectors of the covariance matrix, and eigenvalues are the variances along them — see PCA.
• Markov chains: the stationary distribution is the eigenvector of the transition matrix for $\lambda = 1$.
• Power method: repeatedly computing $\mathbf x_{k+1} = A\mathbf x_k/\lVert A\mathbf x_k\rVert$ converges to the eigenvector of the largest-magnitude eigenvalue (rate $\lvert\lambda_2/\lambda_1\rvert$) — the idea behind PageRank.
• Stability: iterations $\mathbf x_{k+1} = A\mathbf x_k$ converge to 0 iff all $\lvert\lambda_i\rvert < 1$.
• Optimisation: eigenvalues of the Hessian classify critical points (see maxima and minima).

Quick revision