22. Diagonalization and Powers of A

Overview

For a matrix A with n independent eigenvectors, placing those vectors in S gives the diagonalization A = SΛS⁻¹, where Λ contains the eigenvalues. This factorization turns powers and discrete-time systems into scalar eigenvalue calculations, and the Fibonacci recurrence demonstrates how the dominant eigenvalue determines long-term growth.

Key takeaways

When A has n independent eigenvectors, A = SΛS⁻¹ and Aᵏ = SΛᵏS⁻¹, reducing matrix powers to powers of the diagonal entries of Λ.
For a diagonalizable matrix, all eigenvalues having magnitude less than 1 ensures Aᵏ tends to zero as k increases.
Distinct eigenvalues guarantee independent eigenvectors, but repeated eigenvalues require checking eigenspace dimensions; the matrix [[2, 1], [0, 2]] has only one independent eigenvector.
A discrete-time system uₖ₊₁ = Auₖ has solution uₖ = Aᵏu₀; expressing u₀ in an eigenvector basis separates the evolution into independent modes.
The Fibonacci state matrix [[1, 1], [1, 0]] has dominant eigenvalue (1 + √5)/2, so Fibonacci growth is governed asymptotically by approximately 1.618 raised to the step number.

Chapters

0:00 Build the Eigenvector Matrix and Derive AS = SΛ

Place n linearly independent eigenvectors x₁ through xₙ in the columns of the eigenvector matrix S.
Multiplying A by S applies A to each column, so the resulting columns are λ₁x₁ through λₙxₙ.
Collect the eigenvalues in the diagonal matrix Λ to obtain AS = SΛ.

7:00 Diagonalize A When the Eigenvectors Are Independent

The n independent columns of S make S invertible, allowing multiplication of AS = SΛ by S⁻¹.
The resulting forms are S⁻¹AS = Λ and A = SΛS⁻¹.
Diagonalization is presented as a matrix factorization alongside LU and QR, with S and S⁻¹ surrounding a diagonal eigenvalue matrix.

10:00 Compute Matrix Powers by Raising Eigenvalues

If Ax = λx, then A²x = λ²x, so x remains an eigenvector of A² while its eigenvalue becomes λ².
From A = SΛS⁻¹, adjacent S⁻¹S factors cancel, yielding Aᵏ = SΛᵏS⁻¹.
The diagonal entries of Λᵏ are λ₁ᵏ through λₙᵏ, making high powers such as A¹⁰⁰ much easier to analyze.

14:00 Use Eigenvalue Magnitudes to Test Stability

For a diagonalizable matrix, the fixed factors S and S⁻¹ do not change as k grows; the powers of the eigenvalues control Aᵏ.
If every eigenvalue satisfies |λᵢ| < 1, then each diagonal entry of Λᵏ tends to zero and Aᵏ tends to zero.
Absolute values are necessary because eigenvalues may be negative or complex.

17:00 Distinguish Repeated Eigenvalues from Independent Eigenvectors

Distinct eigenvalues guarantee independent eigenvectors, so a matrix with n distinct eigenvalues is diagonalizable.
Repeated eigenvalues do not automatically prevent diagonalization: the 10-by-10 identity has eigenvalue 1 repeated ten times, yet every vector is an eigenvector.
For A = [[2, 1], [0, 2]], λ = 2 has algebraic multiplicity 2 but its eigenspace is only one-dimensional, so A lacks two independent eigenvectors and is not diagonalizable.

26:00 Represent a Discrete-Time System with Matrix Powers

For the first-order system uₖ₊₁ = Auₖ, repeated substitution gives uₖ = Aᵏu₀.
The formula provides the state after k steps, but evaluating a large power directly is difficult without diagonalization.
The next step is to express the initial state using eigenvectors so each component evolves independently.

29:16 Evolve Each Eigenvector Component Independently

Expand the initial vector as u₀ = c₁x₁ + ⋯ + cₙxₙ, or equivalently u₀ = Sc.
After k steps, each eigenvector component is multiplied by its eigenvalue raised to k: uₖ = SΛᵏc.
The eigenvalues indicate whether individual modes grow, decay, or persist, while the coefficients in c determine their contribution from the initial state.

34:18 Convert the Fibonacci Recurrence into a First-Order System

The Fibonacci rule Fₖ₊₂ = Fₖ₊₁ + Fₖ is a scalar second-order recurrence.
Define uₖ = (Fₖ₊₁, Fₖ)ᵀ to rewrite it as uₖ₊₁ = Auₖ with A = [[1, 1], [1, 0]].
With F₀ = 0 and F₁ = 1, the initial vector is u₀ = (1, 0)ᵀ.

39:16 Find Fibonacci Eigenvalues and Identify the Growth Rate

The characteristic polynomial of [[1, 1], [1, 0]] is λ² − λ − 1, matching the Fibonacci recurrence's coefficients.
Its eigenvalues are (1 + √5)/2, approximately 1.618, and (1 − √5)/2, approximately −0.618.
The eigenvalue with magnitude greater than 1 dominates repeated matrix multiplication, so Fibonacci numbers grow approximately like a constant times ((1 + √5)/2)ᵏ.

47:45 Complete the Fibonacci Eigenvector Solution

For either Fibonacci eigenvalue λ, an eigenvector of A is (λ, 1)ᵀ.
To obtain an exact formula from the eigenbasis, write u₀ = (1, 0)ᵀ as a linear combination of the two eigenvectors and apply the corresponding eigenvalue powers.
The example reinforces the general workflow: find eigenvalues and eigenvectors, decompose the initial state, then track each mode separately.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, MIT OpenCourseWare.