Diagonalization & Matrix Powers

Study Sheet

Diagonalization & Matrix Powers

A = PDP⁻¹ and everything it unlocks

Changing to the Eigenbasis

Tip
Diagonalization is a change of glasses

If a matrix AA has nn independent eigenvectors, pack them as the columns of PP and their eigenvalues into the diagonal of DD: then A=PDP−1A = PDP^{-1}. Reading right to left: P−1P^{-1} translates a vector into eigen-coordinates, DD stretches each coordinate by its eigenvalue (the easy part), and PP translates back.

The matrix was never complicated — we were looking at it in the wrong basis. Consequences cascade: Ak=PDkP−1A^k = PD^kP^{-1} (powers act on eigenvalues only), tr(Ak)=∑λik\mathrm{tr}(A^k) = \sum\lambda_i^k, and functions of matrices (A\sqrt A, eAte^{At}) are defined by applying them to the diagonal. Computing A100A^{100} costs a diagonalization, not a hundred multiplications.

Side note
When diagonalization fails

A repeated eigenvalue may come with too few eigenvectors: the shear (1101)\begin{pmatrix}1&1\\0&1\end{pmatrix} has the double eigenvalue 11 but only ONE eigenvector direction — it is DEFECTIVE, and no basis makes it diagonal. The fix (Jordan form) adds an off-diagonal 11 and, in differential equations, produces exactly the teλtte^{\lambda t} solutions you met with repeated characteristic roots. The two "repeated root" phenomena are one phenomenon.

Tip
Recurrences are matrix powers

Fibonacci's Fn+1=Fn+Fn−1F_{n+1} = F_n + F_{n-1} is the matrix iteration (Fn+1Fn)=(1110)(FnFn−1)\binom{F_{n+1}}{F_n} = \begin{pmatrix}1&1\\1&0\end{pmatrix}\binom{F_n}{F_{n-1}}, so FnF_n lives inside QnQ^n.

Diagonalizing QQ (eigenvalues φ=1+52\varphi = \tfrac{1+\sqrt5}{2} and ψ=1−52\psi = \tfrac{1-\sqrt5}{2}) yields BINET'S FORMULA Fn=φn−ψn5F_n = \tfrac{\varphi^n - \psi^n}{\sqrt5} — a closed form for a recursive sequence, and since ∣ψ∣<1|\psi| < 1, the growth rate of Fibonacci is exactly the golden ratio. Every linear recurrence yields to the same treatment: its characteristic equation is the characteristic polynomial of its companion matrix.

Try it
Try it: trace of a big power in ten seconds

Compute tr(A5)\mathrm{tr}(A^5) for A=(2112)A = \begin{pmatrix}2&1\\1&2\end{pmatrix}. Work: eigenvalues from trace 44, det 33: λ=1,3\lambda = 1, 3. Then tr(A5)=15+35=244\mathrm{tr}(A^5) = 1^5 + 3^5 = 244. No matrix was multiplied. (For contrast, try computing A5A^5 by hand — five multiplications, sixteen entries each — then take the trace and confirm.)

Proofs & Why It Matters

Tip
Proof: Aᵏ = PDᵏP⁻¹, and why traces are power sums

A2=(PDP−1)(PDP−1)=PD(P−1P)DP−1=PD2P−1A^2 = (PDP^{-1})(PDP^{-1}) = PD(P^{-1}P)DP^{-1} = PD^2P^{-1} — the inner pair cancels; induction extends to all kk. For the trace, use tr(XY)=tr(YX)\mathrm{tr}(XY) = \mathrm{tr}(YX): tr(Ak)=tr(PDkP−1)=tr(DkP−1P)=tr(Dk)=∑λik\mathrm{tr}(A^k) = \mathrm{tr}(PD^kP^{-1}) = \mathrm{tr}(D^kP^{-1}P) = \mathrm{tr}(D^k) = \sum\lambda_i^k.

■\blacksquare SIGNIFICANCE: this identity is how one counts closed walks in graphs (adjacency-matrix powers), computes partition functions in physics, and analyzes mixing of Markov chains — three fields, one cancellation.

Side note
Significance: exponentials of matrices

Define eAt=PeDtP−1e^{At} = Pe^{Dt}P^{-1}, i.e. exponentiate each eigenvalue. Then u(t)=eAtu0\mathbf u(t) = e^{At}\mathbf u_0 solves u′=Au\mathbf u' = A\mathbf u — the systems topic of Differential Equations is literally this formula. Diagonalization is the load-bearing wall between the two courses.

Going Deeper: Worked Problems

Example
Worked: a full diagonalization, then a closed-form power

Diagonalize A=(4123)A = \begin{pmatrix}4&1\\2&3\end{pmatrix} and use it to find a formula for AnA^n.

Step 1 — eigenvalues: trace 77, det 1010: λ2−7λ+10=(λ−2)(λ−5)=0\lambda^2 - 7\lambda + 10 = (\lambda-2)(\lambda-5) = 0.

Step 2 — eigenvectors: for λ=5\lambda = 5, (A−5I)v=(−112−2)v=0(A - 5I)\mathbf v = \begin{pmatrix}-1&1\\2&-2\end{pmatrix}\mathbf v = \mathbf 0 gives (1,1)(1,1); for λ=2\lambda = 2, (2121)v=0\begin{pmatrix}2&1\\2&1\end{pmatrix}\mathbf v = \mathbf 0 gives (1,−2)(1,-2).

Step 3 — P=(111−2)P = \begin{pmatrix}1&1\\1&-2\end{pmatrix}, D=diag(5,2)D = \mathrm{diag}(5, 2), and P−1=1−3(−2−1−11)P^{-1} = \tfrac{1}{-3}\begin{pmatrix}-2&-1\\-1&1\end{pmatrix}.

Step 4 — An=PDnP−1=13(2⋅5n+2n5n−2n2⋅5n−2⋅2n5n+2⋅2n)A^n = PD^nP^{-1} = \tfrac13\begin{pmatrix}2\cdot5^n + 2^n & 5^n - 2^n\\ 2\cdot5^n - 2\cdot2^n & 5^n + 2\cdot2^n\end{pmatrix}.

Step 5 — check n=1n = 1: 13(12369)=A\tfrac13\begin{pmatrix}12&3\\6&9\end{pmatrix} = A ✓. Every entry is now a formula in nn; the 5n5^n terms dominate, along the eigenvector (1,1)(1,1).

Example
Worked: solving a recurrence by diagonalization

A sequence satisfies an+1=5an−6an−1a_{n+1} = 5a_n - 6a_{n-1} with a0=1a_0 = 1, a1=4a_1 = 4. Find a closed form.

Step 1 — companion matrix: (an+1an)=(5−610)(anan−1)\binom{a_{n+1}}{a_n} = \begin{pmatrix}5&-6\\1&0\end{pmatrix}\binom{a_n}{a_{n-1}}.

Step 2 — its characteristic polynomial is λ2−5λ+6=(λ−2)(λ−3)\lambda^2 - 5\lambda + 6 = (\lambda-2)(\lambda-3) — exactly the recurrence with λ\lambda in place of the shift.

Step 3 — so an=c1⋅2n+c2⋅3na_n = c_1\cdot2^n + c_2\cdot3^n; the data give c1+c2=1c_1 + c_2 = 1 and 2c1+3c2=42c_1 + 3c_2 = 4, hence c2=2c_2 = 2, c1=−1c_1 = -1: an=2⋅3n−2na_n = 2\cdot3^n - 2^n.

Step 4 — verify a2a_2: recurrence gives 5⋅4−6⋅1=145\cdot4 - 6\cdot1 = 14; formula gives 18−4=1418 - 4 = 14 ✓. Diagonalizing the companion matrix IS the "characteristic equation" method — now you know why it works.