Eigenvalues, Eigenvectors and Diagonalisation

Most vectors change direction when a matrix acts on them. Eigenvectors do not: they are only stretched.

These special directions reveal what a transformation really does, and they power Google's PageRank, principal component analysis, vibration analysis and the stability of dynamical systems.

4.1 Eigenvalues and eigenvectors

A non-zero vector v is an eigenvector of a square matrix A with eigenvalue λ if Av = \lambda v. Rewrite as (A - \lambda I) v = 0; a non-zero solution exists iff \det (A - \lambda I) = 0, the characteristic equation.

For an n \times n matrix it is a polynomial of degree n, so there are n eigenvalues counting multiplicity (possibly complex).

Procedure: (1) solve \det (A - \lambda I) = 0 for λ; (2) for each λ solve (A - \lambda I) v = 0; the non-zero solutions are the eigenvectors (the eigenspace).

Properties. Sum of eigenvalues = trace (sum of the diagonal): 5 + 2 = 7 = 4 + 3 ✓. Product of eigenvalues = determinant: 5 \cdot 2 = 10 = 12 - 2 ✓. A is invertible iff 0 is not an eigenvalue.

Eigenvalues of A^{k} are \lambda^{k}; of A^{-1} are \frac{1}{\lambda}; of A^{T} the same as A; of a triangular matrix the diagonal entries. Eigenvectors for distinct eigenvalues are linearly independent.

Cayley–Hamilton: a matrix satisfies its own characteristic equation: for the example, A^{2} − 7A + 10I = 0 (check: A^{2} = \begin{bmatrix} 18 & 7 \\ 14 & 11 \end{bmatrix}; 7A = \begin{bmatrix} 28 & 7 \\ 14 & 21 \end{bmatrix} ;\ A^{2} − 7A + 10I = \begin{bmatrix} 18 - 28 + 10 & 0 \\ 0 & 11 - 21 + 10 \end{bmatrix} = 0 ✓).

It gives A^{-1} = (7I − A ) / 10 quickly.

4.2 Diagonalisation

A is diagonalisable if there is an invertible P and a diagonal D with A = PDP⁻¹: the columns of P are n independent eigenvectors and D has the eigenvalues. It happens iff A has n independent eigenvectors (guaranteed when the n eigenvalues are distinct).

Not every matrix is diagonalisable: \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} has the single eigenvalue 1 (repeated) and only one independent eigenvector (1, 0); it is a defective matrix (a shear). The general fix is the Jordan form, outside this course.

Symmetric matrices (A = A^{T}) are special: all eigenvalues are real, eigenvectors of different eigenvalues are orthogonal, and they are always diagonalisable by an orthogonal P (spectral theorem): A = QDQᵀ.

Example \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix} has \lambda = 3 (eigenvector \frac{1 ,\ 1}{\sqrt{2}}) and \lambda = 1 (eigenvector \frac{1 ,\ - 1}{\sqrt{2}}).

A symmetric matrix is positive definite if all eigenvalues are > 0 (energy and covariance matrices).

4.3 Applications

Fibonacci in matrix form. \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}ⁿ = \begin{bmatrix} F_{n+1} & F_{n} \\ F_{n} & F_{n-1} \end{bmatrix}.

Its eigenvalues solve \lambda^{2} = \lambda + 1, i.e. \lambda = \frac{1 \pm \sqrt{5}}{2}, so diagonalisation gives Binet's formula (Discrete Structure, Unit 4), and F_{10} = 55 follows from the 10th power.

Markov chains. A stochastic matrix P (rows sum to 1) gives the probabilities of moving between states.

If the weather is "dry" or "wet" with P = \begin{bmatrix} 0.9 & 0.1 \\ 0.5 & 0.5 \end{bmatrix}, the long-run proportions π satisfy \pi P = \pi, i.e. π is a left eigenvector for \lambda = 1: 0.1 \pi_{1} = 0.5 \pi_{2} \Rightarrow \pi_{1} = 5 \pi_{2}, so with \pi_{1} + \pi_{2} = 1, \pi = \left( \frac{5}{6} ,\ \frac{1}{6} \right): in the long run, 83 % of days are dry.

The other eigenvalue is 0.4, so the chain converges geometrically at rate 0.4^{n}.

PageRank. The rank of web pages is the principal eigenvector of the (damped) link matrix: a page is important if important pages link to it. It is found by power iteration: multiply a vector by the matrix repeatedly, and it converges to the dominant eigenvector.

Example starting from (1, 0) and applying A = \begin{bmatrix} 4 & 1 \\ 2 & 3 \end{bmatrix}: (4, 2), (18, 14), (86, 70), … the ratio tends to (1, 1)-direction: \frac{86}{70} = 1.23, then slowly towards 1 (5^{n} dominates 2^{n}).

Principal component analysis (PCA). For data, form the covariance matrix (symmetric); its eigenvectors with the largest eigenvalues are the directions of greatest variance.

Keeping the top k reduces dimensions with minimal information loss (image compression, face recognition, visualising data).

Systems of differential equations and stability. x' = Ax has solutions made of e^{\lambda t} v; the system is stable (solutions decay) if all eigenvalues have negative real parts.

Vibrations of a structure are governed by eigenvalues (natural frequencies). Graph theory: the eigenvalues of a graph's adjacency matrix describe its connectivity.

4.4 What an eigenvector looks like

Most vectors are turned and stretched when a matrix acts on them. An eigenvector is special: the matrix only stretches it along its own line, by the factor λ.

Figure 4.1 shows A = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix} acting on the unit circle.

Every point of the circle goes to an ellipse; the ellipse's long axis lies along the eigenvector (1, 1), stretched by \lambda = 3, and its short axis along (1, −1), stretched by \lambda = 1.

A symmetric matrix always has such perpendicular axes, which is why principal-component analysis of data works.

4.5 Eight uses of eigenvalues

1. Ranking web pages. PageRank is the eigenvector for the eigenvalue 1 of the web's link matrix. The largest component belongs to the page that many important pages point to. A search engine finds it by repeated multiplication.
2. Markov chains and long-run forecasts. If tomorrow's weather depends only on today's, the chain has a steady state that is the eigenvector for \lambda = 1 (Section 4.3 and the answers below). It predicts the long-run share of sunny days, customers or users.
3. Principal component analysis (PCA). The eigenvectors of a data covariance matrix point along the directions of greatest spread. Keeping the top few reduces hundreds of columns to two or three. Face recognition and survey analysis use it.
4. Vibrations and earthquakes. The natural frequencies of a building or bridge are the square roots of eigenvalues of its stiffness matrix. If shaking from an earthquake matches one, resonance can be destructive. Engineers in Nepal check this for tall buildings.
5. Population growth. In a Leslie matrix, the dominant eigenvalue is the long-run growth factor per period, and its eigenvector is the stable age distribution. Planners use this to project school and health needs.
6. Stability of systems. For x' = Ax, all eigenvalues with negative real part mean the system settles. Control engineers choose a controller by moving eigenvalues. Cruise control and drone stabilisation rely on this.
7. Image and data compression. The singular-value decomposition, built from eigenvalues of A^{T} A, stores a picture with a few large values and drops the rest. Recommenders and photo apps compress this way.
8. Quantum and physical systems. Energy levels of atoms are eigenvalues of an operator; the allowed states are eigenvectors. The idea that measurement gives eigenvalues is the heart of quantum mechanics.

(a) Tacoma Narrows Bridge twisting, 1940

(b) Two normal modes of a 2-mass, 3-spring system

(a) Andrey Markov (Markov chains)

(b) PageRank of four pages by the power method

Formula and fact sheet

• Av = \lambda v ;\ \det (A - \lambda I) = 0; eigenspace = null space of A - \lambda I.
• \sum \lambda = trace; \prod \lambda = \det. Eigenvalues of A^{k}: \lambda^{k}; of A^{-1}: \frac{1}{\lambda}.
• Cayley–Hamilton: p (A) = 0. A = PDP⁻¹ ⇒ Aⁿ = PDⁿP⁻¹.
• Symmetric: real eigenvalues, orthogonal eigenvectors, A = QDQᵀ.
• Markov steady state: \pi P = \pi (eigenvalue 1). PageRank: power iteration.

Chapter summary

• Eigenvectors are the directions a matrix only stretches; eigenvalues are the stretch factors.
• The characteristic polynomial finds them; trace and determinant give quick checks.
• Diagonalisation turns matrix powers into powers of numbers; symmetric matrices diagonalise orthogonally.
• Markov chains, PageRank, PCA, stability and vibration analysis are all eigenvalue problems.

Practice

1. Find the eigenvalues and eigenvectors of \begin{bmatrix} 3 & 1 \\ 0 & 2 \end{bmatrix} and of \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}.
2. Find the eigenvalues of \begin{bmatrix} 1 & 2 & 3 \\ 0 & 4 & 5 \\ 0 & 0 & 6 \end{bmatrix} and the determinant.
3. If the eigenvalues of A are 2, 3 and 5, find \det A ,\ t r A, eigenvalues of A^{2} and of A^{-1}.
4. Verify the Cayley–Hamilton theorem for \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} and use it to find A^{-1}.
5. Diagonalise \begin{bmatrix} 4 & 1 \\ 2 & 3 \end{bmatrix} and find A^{3}.
6. Is \begin{bmatrix} 2 & 1 \\ 0 & 2 \end{bmatrix} diagonalisable? Explain.
7. A 2-state Markov chain has P = \begin{bmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{bmatrix}. Find the steady state.
8. Show that the eigenvalues of a symmetric 2 \times 2 matrix \begin{bmatrix} a & b \\ b & c \end{bmatrix} are always real.
9. Find the eigenvalues of the rotation matrix \begin{bmatrix} 0 & - 1 \\ 1 & 0 \end{bmatrix}. Interpret.
10. A population model: young Y and adults A, with Y_{n+1} = 2 A_{n} ,\ A_{n+1} = 0.5 Y_{n} + 0.6 A_{n}. Find the long-term growth rate.

Answers and worked solutions

1. \begin{bmatrix} 3 & 1 \\ 0 & 2 \end{bmatrix}: triangular, \lambda = 3 ( v = ( 1, 0)) and \lambda = 2 ( A − 2I = \begin{bmatrix} 1 & 1 \\ 0 & 0 \end{bmatrix} \Rightarrow v = (1 ,\ - 1)). \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}: \lambda = 3 (v = (1 ,\ 1)) ,\ \lambda = 1 (v = (1 ,\ - 1)).

2. Triangular: 1, 4, 6; \det = 1 \cdot 4 \cdot 6 = 24.

3. det = 2·3·5 = 30; trace = 10; A^{2} has 4 ,\ 9 ,\ 25 ;\ A^{-1} has \frac{1}{2} ,\ \frac{1}{3} ,\ \frac{1}{5}.

4. t r = 5 ,\ \det = - 2: \lambda^{2} - 5 \lambda - 2 = 0. A^{2} = \begin{bmatrix} 7 & 10 \\ 15 & 22 \end{bmatrix} ;\ A^{2} − 5A − 2I = \begin{bmatrix} 7 - 5 - 2 & 10 - 10 \\ 15 - 15 & 22 - 20 - 2 \end{bmatrix} = 0 ✓.

Then A^{2} − 5A = 2I ⇒ A ( A − 5I) = 2I ⇒ A^{-1} = \frac{A - 5 I}{2} = \begin{bmatrix} - 2 & 1 \\ 1.5 & - 0.5 \end{bmatrix}.

5. P D P^{-1} as in §4.2. A^{3} = P diag(125, 8) P^{-1} = \begin{bmatrix} 125 & 8 \\ 125 & - 16 \end{bmatrix} \cdot \begin{bmatrix} \frac{2}{3} & \frac{1}{3} \\ \frac{1}{3} & - \frac{1}{3} \end{bmatrix} = \begin{bmatrix} \frac{250 + 8}{3} & \frac{125 - 8}{3} \\ \frac{250 - 16}{3} & \frac{125 + 16}{3} \end{bmatrix} = \begin{bmatrix} 86 & 39 \\ 78 & 47 \end{bmatrix}. (Trace 133 = 125 + 8 ✓.)

6. No: \lambda = 2 is repeated but A − 2I = \begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix} has a one-dimensional null space, so there is only one independent eigenvector.

7. \pi P = \pi: 0.3 \pi_{1} = 0.4 \pi_{2} \Rightarrow \pi_{1} = \left( \frac{4}{3} \right) \pi_{2} ;\ \pi_{1} + \pi_{2} = 1 \Rightarrow \pi_{2} = \frac{3}{7}. \pi = \left( \frac{4}{7} ,\ \frac{3}{7} \right) \approx ( 0.571, 0.429).

8. \lambda^{2} - (a + c) \lambda + (a c - b^{2}) = 0 has discriminant (a + c)^{2} - 4 (a c - b^{2}) = (a - c)^{2} + 4 b^{2} \geq 0, so the roots are real.

9. \lambda^{2} + 1 = 0 \Rightarrow \lambda = \pm i (complex): a rotation has no real direction that stays fixed (it turns every vector by 90 ^{\circ}).

10. Matrix \begin{bmatrix} 0 & 2 \\ 0.5 & 0.6 \end{bmatrix} acting on (Y, A): \lambda^{2} - 0.6 \lambda - 1 = 0 \Rightarrow \lambda = \frac{0.6 + \sqrt{0.36 + 4}}{2} = \frac{0.6 + 2.088}{2} = 1.344, so the population grows about 34 % per period (the other eigenvalue −0.744 dies out).

Model answers: medium (5 marks) and long (10 marks) questions

Q1 (5 marks). Find the eigenvalues and eigenvectors of A = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}, diagonalise it and find A^{5}.

Introduction. λ is an eigenvalue of A if \det (A - \lambda I) = 0, and a non-zero vector v with Av = \lambda v is the eigenvector.

Characteristic equation. \det \begin{bmatrix} 2 - \lambda & 1 \\ 1 & 2 - \lambda \end{bmatrix} = (2 - \lambda)^{2} - 1 = \lambda^{2} - 4 \lambda + 3 = (\lambda - 1) (\lambda - 3) = 0, so \lambda = 3 and \lambda = 1.

Check trace 4 = 3 + 1 and \det 3 = 3 \times 1.

Eigenvectors. For \lambda = 3: (A − 3I)v = 0 gives - x + y = 0, so v_{1} = (1 ,\ 1). For \lambda = 1: x + y = 0, so v_{2} = (1 ,\ - 1).

Diagonalisation. P = \begin{bmatrix} 1 & 1 \\ 1 & - 1 \end{bmatrix} and D = \begin{bmatrix} 3 & 0 \\ 0 & 1 \end{bmatrix}, with A = PDP⁻¹.

Power. A^{5} = P D^{5} P^{-1} with D^{5} = \begin{bmatrix} 243 & 0 \\ 0 & 1 \end{bmatrix}. Multiplying gives A^{5} = \begin{bmatrix} 122 & 121 \\ 121 & 122 \end{bmatrix}.

Conclusion Eigenvalues 3 and 1; diagonalisation turns a matrix power into the power of two numbers.

Q2 (10 marks). Explain eigenvalues, eigenvectors and diagonalisation, state the conditions and properties, and show how a Markov chain uses them.

Introduction. Eigenvalues and eigenvectors expose the directions in which a matrix acts as a simple stretch. They turn hard problems (powers of a matrix, long-run behaviour) into easy ones.

Definitions and method.

1. Eigen-equation. Av = \lambda v with v \neq 0.
2. Characteristic equation. \det (A - \lambda I) = 0 is a polynomial of degree n in λ; its roots are the eigenvalues.
3. Eigenvectors. For each λ, solve (A - \lambda I) v = 0; the solutions form the eigenspace.
4. Properties. The sum of eigenvalues equals the trace and the product equals the determinant; for B = \begin{bmatrix} 4 & 1 \\ 2 & 3 \end{bmatrix} these are 5 + 2 = 7 and 5 \times 2 = 10. A matrix is invertible exactly when 0 is not an eigenvalue.

Diagonalisation.

5. Condition. An n \times n matrix is diagonalisable if it has n independent eigenvectors (distinct eigenvalues are enough; symmetric matrices always qualify).
6. Result. A = PDP⁻¹ with eigenvectors as columns of P and eigenvalues on the diagonal of D. For B: eigenvectors (1, 1) for 5 and (1, −2) for 2, so B^{n} = P \mathrm{diag} (5^{n} ,\ 2^{n}) P^{-1}.

Markov chain. Let sunny days follow sunny days with probability 0.9 and rainy days follow sunny days with probability 0.5 (the other columns 0.1 and 0.5), so the transition matrix is M = \begin{bmatrix} 0.9 & 0.5 \\ 0.1 & 0.5 \end{bmatrix}.

7. Eigenvalues. One is 1 (the chain conserves probability) and the other is 0.4.
8. Steady state. The eigenvector for \lambda = 1 solves 0.9x + 0.5y = x, giving y = x \div 5, normalised to \left( \frac{5}{6} ,\ \frac{1}{6} \right). In the long run about 83 percent of days are sunny, whatever today's weather is, because the 0.4^{n} part dies out.

Idea	Rule
Eigenvalues	roots of \det (A - \lambda I) = 0
Trace and determinant	sum and product of eigenvalues
Diagonalisation	A = PDP⁻¹, powers: A^{n} = P D^{n} P^{-1}
Steady state	eigenvector for \lambda = 1 of a stochastic matrix

Conclusion. Eigenvalues give the stretching factors, eigenvectors the directions, and together they make powers, long-run forecasts and principal axes easy to compute.