Case Study 2 — Cracking a Recurrence: Algorithm Analysis by Diagonalization

Field: computer science / algorithm analysis. This case study ties to the chapter anchor by decoupling a coupled recurrence into independent geometric modes, generalizing the Fibonacci computation of §25.5. Here the dominant eigenvalue exceeds $1$, so the sequence grows — and that growth rate is the algorithm's big-O.

A recurrence falls out of a recursive algorithm

You have written a recursive algorithm, and counting its operations leads to a recurrence relation — a formula that expresses the work at size $n$ in terms of the work at smaller sizes. Suppose the analysis yields $$T(n) = 5\,T(n-1) - 6\,T(n-2), \qquad T(0) = 0,\;\; T(1) = 1.$$ This is a linear recurrence with constant coefficients, the kind that governs the running time of countless divide-and-conquer and dynamic-programming algorithms. You want two things: a closed form for $T(n)$ (so you can predict the cost at any size without unrolling the recursion) and the asymptotic growth rate $\Theta(\cdot)$ (so you know how the algorithm scales). Diagonalization delivers both, and the path is the companion-matrix trick of §25.5.

The difficulty with a recurrence is that each term is coupled to the previous two — exactly the kind of coupling the eigenbasis exists to dissolve. The strategy: package the recurrence as a single matrix step, diagonalize the matrix to decouple the recurrence into independent geometric sequences, and read off the answer.

Package the recurrence as a matrix power

Stack two consecutive terms into a state vector $\mathbf{x}_n = \begin{bmatrix}T(n)\\T(n-1)\end{bmatrix}$. One step of the recurrence is one matrix multiplication: $$\begin{bmatrix}T(n)\\T(n-1)\end{bmatrix} = \begin{bmatrix}5 & -6 \\ 1 & 0\end{bmatrix}\begin{bmatrix}T(n-1)\\T(n-2)\end{bmatrix}, \qquad C = \begin{bmatrix}5 & -6 \\ 1 & 0\end{bmatrix}.$$ Check the top row: $5\,T(n-1) - 6\,T(n-2) = T(n)$ ✓; the bottom row $1\cdot T(n-1) + 0 = T(n-1)$ just slides the window forward. This $C$ is the companion matrix of the recurrence. Starting from $\mathbf{x}_1 = \begin{bmatrix}T(1)\\T(0)\end{bmatrix} = \begin{bmatrix}1\\0\end{bmatrix}$, the $n$-th state is $\mathbf{x}_n = C^{n-1}\mathbf{x}_1$. The sequence is a matrix power — and we know how to make powers trivial.

Diagonalize to decouple

Eigenvalues. The characteristic polynomial of the companion matrix is built right into the recurrence's coefficients: $$\det(C - \lambda I) = \lambda^2 - 5\lambda + 6 = (\lambda - 3)(\lambda - 2).$$ (For a recurrence $T(n) = a\,T(n-1) + b\,T(n-2)$, the characteristic polynomial is always $\lambda^2 - a\lambda - b$ — the recurrence is its own characteristic equation.) The eigenvalues are $\lambda_1 = 3$ and $\lambda_2 = 2$, distinct, so $C$ is diagonalizable (§25.3.1) and there is no defective surprise.

Eigenvectors. For $\lambda = 3$, solve $(C - 3I)\mathbf{v} = \mathbf{0}$: $\begin{bmatrix}2 & -6 \\ 1 & -3\end{bmatrix}$ gives $v_1 = 3v_2$, so $\mathbf{v}_1 = (3, 1)$. For $\lambda = 2$: $\begin{bmatrix}3 & -6 \\ 1 & -2\end{bmatrix}$ gives $v_1 = 2v_2$, so $\mathbf{v}_2 = (2, 1)$. (No accident: a companion matrix's eigenvector for $\lambda$ is always $(\lambda, 1)$, just as in Fibonacci.) Assemble: $$P = \begin{bmatrix}3 & 2 \\ 1 & 1\end{bmatrix}, \qquad D = \begin{bmatrix}3 & 0 \\ 0 & 2\end{bmatrix}, \qquad P^{-1} = \begin{bmatrix}1 & -2 \\ -1 & 3\end{bmatrix},$$ using $\det P = 3 - 2 = 1$, so $P^{-1} = \begin{bmatrix}1 & -2 \\ -1 & 3\end{bmatrix}$ by the $2\times 2$ inverse rule of Chapter 9.

Read off the closed form

In the eigenbasis the recurrence is two independent geometric sequences, one scaling by $3^n$ and one by $2^n$. The general solution is therefore $T(n) = c_1\,3^n + c_2\,2^n$ for constants set by the initial conditions. Imposing $T(0) = 0$ and $T(1) = 1$: $$T(0) = c_1 + c_2 = 0, \qquad T(1) = 3c_1 + 2c_2 = 1 \;\;\Longrightarrow\;\; c_1 = 1,\; c_2 = -1.$$ So the closed form is strikingly clean: $$\boxed{\,T(n) = 3^n - 2^n\,.}$$ The coupled recurrence has dissolved into the difference of two pure exponentials, one per eigenvalue. Verify it against both the recurrence and the matrix power with numpy:

# Recurrence T(n)=5T(n-1)-6T(n-2): companion matrix, diagonalization, closed form.
import numpy as np
C = np.array([[5., -6.], [1., 0.]])
w, V = np.linalg.eig(C)
print("eigenvalues:", np.sort(w)[::-1])          # [3. 2.]

# Closed form vs. the recurrence, for n = 0..6:
def recur(n):
    a, b = 0, 1                                   # T(0), T(1)
    if n == 0: return 0
    for _ in range(n - 1):
        a, b = b, 5*b - 6*a
    return b
for n in range(7):
    print(f"n={n}:  recurrence={recur(n):>4}   closed 3^n-2^n={3**n - 2**n:>4}")

The output is eigenvalues: [3. 2.], then a perfect match between the two columns: $T(0..6) = 0, 1, 5, 19, 65, 211, 665$, equal to $3^n - 2^n$ at every $n$. The diagonalization did not merely reproduce the sequence — it explained it as the superposition of a fast mode ($3^n$) and a slower mode ($2^n$).

The dominant eigenvalue is the algorithm's big-O

Now the asymptotics, which is what a computer scientist ultimately wants. By the long-run principle of §25.6.1, the term with the larger eigenvalue dominates: as $n$ grows, $3^n$ swamps $2^n$, so $$T(n) = 3^n - 2^n \sim 3^n, \qquad T(n) = \Theta(3^n).$$ The algorithm runs in exponential time with base $3$ — the dominant eigenvalue of its companion matrix. The subordinate eigenvalue $2$ is a lower-order correction that vanishes in the ratio: $T(n+1)/T(n) \to 3$, which you can watch approach $3$ numerically ($T(20)/T(19) \approx 3.0005$). This is a completely general principle worth stating plainly:

The asymptotic growth rate of a constant-coefficient linear recurrence is the largest-magnitude eigenvalue of its companion matrix. Solving a recurrence and diagonalizing its companion matrix are the same act: the eigenvalues are the bases of the exponential terms in the closed form, the eigenvectors encode how the initial conditions distribute across those terms, and the dominant eigenvalue is the $\Theta(\cdot)$. Algorithm analysis is eigenvalue analysis in disguise.

This reframes a familiar table of recurrence solutions as a table of eigenvalues. Fibonacci's $T(n) = T(n-1) + T(n-2)$ has companion eigenvalue $\varphi \approx 1.618$, so it grows as $\Theta(\varphi^n)$ — which is why naive recursive Fibonacci is exponentially slow (§25.5). A recurrence with a repeated root, like $T(n) = 4T(n-1) - 4T(n-2)$ (companion eigenvalue $2$ doubled), has a defective companion matrix — and that defect is precisely why its closed form needs the extra term $n\cdot 2^n$ rather than two clean exponentials, the Jordan-form correction of Chapter 36 showing up in algorithm analysis. The growth is still $\Theta(2^n)$ up to the polynomial factor, but the defective eigenvalue leaves a visible fingerprint.

Why this matters beyond one recurrence

The companion-matrix-and-diagonalize recipe is the engine behind the characteristic-equation method taught in every discrete mathematics and algorithms course — students learn the mechanical rule "write $\lambda^2 = a\lambda + b$, find the roots, form $c_1\lambda_1^n + c_2\lambda_2^n$" without always being told why it works. This case study is the why: the recurrence is a linear dynamical system, its companion matrix is the one-step map, and diagonalization decouples the system into independent modes whose growth rates are the eigenvalues. The same idea scales up — a depth-$d$ recurrence becomes a $d \times d$ companion matrix with $d$ eigenvalues, and a system of mutually recursive sequences becomes a single matrix whose eigenstructure untangles them all at once.

It is the discrete twin of the continuous story coming in Chapter 37, where a system of differential equations $\mathbf{x}' = A\mathbf{x}$ is decoupled by the same diagonalization into independent exponentials $e^{\lambda_i t}$, and the eigenvalues become continuous growth/decay rates. Discrete time gives powers $\lambda^n$; continuous time gives exponentials $e^{\lambda t}$; both are the eigenbasis dissolving coupling into independent one-dimensional motion. Whether you are bounding an algorithm's running time or predicting a circuit's response, the move is identical: find the eigenvalues, and the largest one tells you the fate.