Diagonalization & Matrix Powers

The matrix was never complicated — we were looking at it in the wrong basis. Consequences cascade: $A^k = PD^kP^{-1}$ (powers act on eigenvalues only), $\mathrm{tr}(A^k) = \sum\lambda_i^k$, and functions of matrices ($\sqrt A$, $e^{At}$) are defined by applying them to the diagonal. Computing $A^{100}$ costs a diagonalization, not a hundred multiplications. A concrete case: $A = \begin{pmatrix}4&1\\2&3\end{pmatrix}$ has eigenvectors $\mathbf v_1 = (1, 1)$ with $\lambda = 5$ and $\mathbf v_2 = (1, -2)$ with $\lambda = 2$. The vector $\mathbf x = (2, -1)$ is $\mathbf v_1 + \mathbf v_2$ — its eigen-coordinates are $(1, 1)$. So $A\mathbf x = 5\mathbf v_1 + 2\mathbf v_2 = (7, 1)$, computed without multiplying by $A$; check: $A(2, -1) = (8 - 1, 4 - 3) = (7, 1)$ ✓.

Diagonalizing $Q$ (eigenvalues $\varphi = \tfrac{1+\sqrt5}{2}$ and $\psi = \tfrac{1-\sqrt5}{2}$) yields Binet's formula $F_n = \tfrac{\varphi^n - \psi^n}{\sqrt5}$ — a closed form for a recursive sequence, and since $|\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.

The equation $AP = PD$ is just the eigenvector equations side by side: column $j$ of $AP$ is $A\mathbf v_j$, and column $j$ of $PD$ is $\lambda_j\mathbf v_j$. Multiplying on the right by $P^{-1}$, which exists because the columns are independent, gives $A = PDP^{-1}$. If a repeated eigenvalue has too few eigenvectors, there are not enough columns to fill an invertible $P$, and no change of basis can make $A$ diagonal.

So $P = \begin{pmatrix}2&1\\1&1\end{pmatrix}$ with $D = \begin{pmatrix}5&0\\0&4\end{pmatrix}$, in matching order. $\det P = 1$, so $P^{-1} = \begin{pmatrix}1&-1\\-1&2\end{pmatrix}$. Check:

Now any power is immediate, for instance $A^n = P\begin{pmatrix}5^n&0\\0&4^n\end{pmatrix}P^{-1}$.

For $\lambda = 2$: $A - 2I = \begin{pmatrix}0&0&0\\0&1&1\\0&1&1\end{pmatrix}$ has rank $1$, so its null space is two-dimensional — $v_2 + v_3 = 0$ with $v_1$ and $v_3$ free — spanned by $(1, 0, 0)$ and $(0, 1, -1)$. For $\lambda = 4$: $A - 4I = \begin{pmatrix}-2&0&0\\0&-1&1\\0&1&-1\end{pmatrix}$ gives $v_1 = 0$, $v_2 = v_3$: $(0, 1, 1)$. Three independent eigenvectors, so $A = PDP^{-1}$ with $P = \begin{pmatrix}1&0&0\\0&1&1\\0&-1&1\end{pmatrix}$ and $D = \mathrm{diag}(2, 2, 4)$. $A$ is symmetric, and its eigenvectors are even mutually perpendicular.

$A - 3I = \begin{pmatrix}2&-1\\4&-2\end{pmatrix}$ has rank $1$ (row 2 is twice row 1), so its null space is one-dimensional: only the multiples of $(1, 2)$. Two independent eigenvectors would be needed; there is one. So $A$ is not diagonalizable. Had it been, $D$ would be $3I$ and $A = P(3I)P^{-1} = 3I$ — but $A \ne 3I$. That one-line argument settles every $2\times2$ with a repeated eigenvalue: diagonalizable only if it is already a multiple of $I$.

Both formulas decouple the system: in eigen-coordinates each component evolves on its own, multiplied by $\lambda$ each step or growing like $e^{\lambda t}$. To check the continuous one, differentiate: each term's derivative is $\lambda_ic_ie^{\lambda_it}\mathbf v_i = A(c_ie^{\lambda_it}\mathbf v_i)$, so $\mathbf u' = A\mathbf u$, and at $t = 0$ the sum is $\mathbf x_0$'s expansion. The coefficients $c_i$ come from solving $P\mathbf c = \mathbf x_0$ once.

Expand the start: $(3, 0) = (2, 1) + (1, -1)$, so $c_1 = c_2 = 1$ and

The first few: $\mathbf x_1 = (1.5, 1.5)$, $\mathbf x_2 = (2.25, 0.75)$, $\mathbf x_3 = (1.875, 1.125)$; check $\mathbf x_1 = A\mathbf x_0 = (1.5, 1.5)$ ✓. The $\lambda = 1$ part never changes, and the $-\tfrac12$ part halves and flips sign each step, so the points hop from side to side of the eigenvector line and close in on $(2, 1)$.

So

Check the first equation, $u_1' = 4u_1 + u_2$: the left side is $5e^{5t} + 2e^{2t}$, the right side is $4e^{5t} + 4e^{2t} + e^{5t} - 2e^{2t} = 5e^{5t} + 2e^{2t}$ ✓; and $\mathbf u(0) = (2, -1)$ ✓. For large $t$ the $e^{5t}$ term dominates, so the solution heads off along the direction $(1, 1)$.

$\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.

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

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

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

Step 4 — $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 = 1$: $\tfrac13\begin{pmatrix}12&3\\6&9\end{pmatrix} = A$ ✓. Every entry is now a formula in $n$; the $5^n$ terms dominate, along the eigenvector $(1,1)$.

Step 1 — companion matrix: $\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 $\lambda^2 - 5\lambda + 6 = (\lambda-2)(\lambda-3)$ — exactly the recurrence with $\lambda$ in place of the shift.

Step 3 — so $a_n = c_1\cdot2^n + c_2\cdot3^n$; the data give $c_1 + c_2 = 1$ and $2c_1 + 3c_2 = 4$, hence $c_2 = 2$, $c_1 = -1$: $a_n = 2\cdot3^n - 2^n$.

Step 4 — verify $a_2$: recurrence gives $5\cdot4 - 6\cdot1 = 14$; formula gives $18 - 4 = 14$ ✓. Diagonalizing the companion matrix is the "characteristic equation" method — now you know why it works.