Week 10: Diagonalization and Markov Matrices

Diagonalization#

Week 9 produced eigenvalues $\lambda$ and eigenvectors $v$ from $Av = \lambda v$. This week assembles those pieces into a factorization of $A$ itself.

Suppose $A$ is $n \times n$ and has $n$ linearly independent eigenvectors $v_1, \ldots, v_n$ with eigenvalues $\lambda_1, \ldots, \lambda_n$. Form the matrix $S$ whose columns are those eigenvectors, and the diagonal matrix $\Lambda$ of the matching eigenvalues:

The eigen-equations $A v_j = \lambda_j v_j$ stack column by column into a single matrix identity:

Because the columns of $S$ are independent, $S$ is invertible. Multiply on the right by $S^{-1}$:

This is the diagonalization (or eigen-decomposition) of $A$. In the eigenbasis, $A$ acts as pure scaling: $\Lambda$ stretches each coordinate axis by its own $\lambda_j$, and $S$ / $S^{-1}$ change coordinates into and out of that basis.

Worked example. Continue with

from Week 9. Eigenvalues were $\lambda_1 = 5$, $\lambda_2 = 2$ with eigenvectors $v_1 = (1,1)^\top$ and $v_2 = (1,-2)^\top$. So

Then $\det(S) = -2 - 1 = -3 \neq 0$, so $S$ is invertible. You can check $AS = S\Lambda$ by multiplying both sides, or reconstruct $A = S\Lambda S^{-1}$ with

When diagonalization fails. Not every matrix has $n$ independent eigenvectors. Week 9's defective example

has a repeated eigenvalue $\lambda = 1$ of algebraic multiplicity $2$, but only a one-dimensional eigenspace. You cannot form an invertible $S$ of eigenvectors, so $J$ is not diagonalizable. The precise criterion:

Distinct eigenvalues always give independent eigenvectors (Strang §6.2), so a matrix with $n$ different eigenvalues is always diagonalizable. A repeated eigenvalue is the dangerous case: you must check whether the eigenspace is large enough.

Complex eigenvalues. A real matrix can have complex conjugate eigenvalues (and complex eigenvectors). The same algebra $A = S\Lambda S^{-1}$ still holds over $\mathbb{C}$. Real normal forms (block-diagonal with $2 \times 2$ rotation-scaling blocks) exist but are not needed for the Markov applications below.

Powers of a Matrix#

Once $A = S\Lambda S^{-1}$, powers of $A$ collapse to powers of a diagonal matrix. Compute

By induction,

for every positive integer $k$. And $\Lambda^k$ is trivial:

You raise $n$ numbers to the $k$-th power — no matrix multiplications of growing size.

Cost contrast. Computing $A^k$ by repeated multiplication ($A$, then $A^2 = A\cdot A$, then $A^3 = A^2\cdot A$, …) costs $O(k)$ multiplications of $n \times n$ matrices, each $O(n^3)$ in naive arithmetic — total $O(k n^3)$. Diagonalization pays a one-time eigen-decomposition cost, after which each power is $O(n)$ for the diagonal entries plus $O(n^3)$ for the two multiplications by $S$ and $S^{-1}$. When many powers are needed, or $k$ is huge, the eigen route wins.

Negative powers. If $A$ is invertible (equivalently, no $\lambda_j = 0$), then $A^{-1} = S\Lambda^{-1}S^{-1}$ with $\Lambda^{-1} = \operatorname{diag}(1/\lambda_1,\ldots,1/\lambda_n)$, and $A^{-k} = S\Lambda^{-k}S^{-1}$.

Determinant of a power. Because $\det(A) = \det(S)\det(\Lambda)\det(S^{-1}) = \det(\Lambda) = \lambda_1\cdots\lambda_n$, we get

That identity is a quick check without forming $A^k$ at all.

Worked power. For the same $A$ with $\lambda_1 = 5$, $\lambda_2 = 2$,

In particular $\det(A^3) = 5^3 \cdot 2^3 = 125 \cdot 8 = 1000$, matching $\det(A)^3 = 10^3 = 1000$.

Markov Matrices#

A Markov matrix (also called a stochastic matrix or transition matrix) encodes one step of a discrete-time chain on $n$ states. The standard linear-algebra convention here is:

• every entry of $A$ is nonnegative: $a_{ij} \ge 0$;
• every column sums to $1$: $\sum_{i=1}^{n} a_{ij} = 1$ for each $j$.

Entry $a_{ij}$ is the probability of moving from state $j$ to state $i$ in one step, so column $j$ is a probability distribution over the next state given that you start in $j$. A state vector $x$ is a column vector of nonnegative entries that sum to $1$; after one transition the new distribution is $Ax$.

Why $\lambda = 1$ is always an eigenvalue. The column-sum condition is equivalent to

where $\mathbf{1} = (1,\ldots,1)^\top$ is the all-ones vector. Taking the transpose, $A^\top \mathbf{1} = \mathbf{1}$, so $A^\top$ has eigenvalue $1$ with eigenvector $\mathbf{1}$. Eigenvalues of $A$ and $A^\top$ coincide (transposition leaves the characteristic polynomial unchanged), so $A$ also has eigenvalue $1$.

No eigenvalue of a Markov matrix can exceed $1$ in magnitude. The max-component argument needs a matrix whose rows sum to $1$, so apply it to $A^\top$ (which is row-stochastic, since the columns of $A$ sum to $1$). Write $(A^\top)_{ij} = a_{ji}$, and for an eigenvalue $\lambda$ of $A^\top$ with eigenvector $w$, let $i$ index the component of $w$ largest in absolute value:

because every $|w_j| \le |w_i|$ and row $i$ of $A^\top$ sums to $1$. Hence $|\lambda| \le 1$ for every eigenvalue of $A^\top$, and transposition leaves the characteristic polynomial unchanged, so the same bound holds for $A$. (The 1-norm gives the same result directly: $\|Ax\|_1 \le \|x\|_1$ for every $x$, so $\|A\|_1 = 1$.) The strict version — that $\lambda = 1$ is simple and every other eigenvalue satisfies $|\lambda| < 1$ — needs the chain to be irreducible and aperiodic (“you can eventually reach any state from any other, and periods do not trap you”); it is the Perron–Frobenius theorem (Strang §8.3).

Example.

has nonnegative entries; column sums are $0.9+0.1 = 1$ and $0.2+0.8 = 1$. This is a two-state Markov matrix: state 1 tends to stay put (probability $0.9$), and state 2 returns to state 1 with probability $0.2$.

Steady State#

A steady-state (or stationary) distribution $x_\infty$ is a probability vector that does not change under the transition:

That is exactly the eigenvector equation for $\lambda = 1$. So find any eigenvector for $\lambda = 1$, then normalize so the components sum to $1$ (and are nonnegative — which they will be for a Markov matrix under the conditions above).

Convergence from any start. Suppose $A$ is diagonalizable with eigenvalues $\lambda_1 = 1$, $\lambda_2, \ldots, \lambda_n$ and $|\lambda_j| < 1$ for $j \ge 2$. Write the initial distribution in the eigenbasis:

with $v_1$ the steady-state eigenvector (or any multiple, before normalization). Then

As $k \to \infty$, every term with $|\lambda_j| < 1$ dies: $\lambda_j^k \to 0$. The limit is $c_1 v_1$, and because each $x_k$ is a probability vector (nonnegative entries summing to $1$), the limit is the unique steady-state distribution. Diagonalization explains the long-run behavior: repeated multiplication by $A$ is dominated by the eigenvalue of largest magnitude, which for a Markov matrix is $1$.

You could iterate $x \mapsto Ax$ 50 times (as the browser lab below does), but diagonalization gives you $x_k$ in closed form — the same reason $A^k = S\Lambda^k S^{-1}$ beats repeated multiplication, now applied to the evolution of the distribution itself.

Worked steady state. For

solve $(A - I)x = 0$:

The two rows are multiples; the single equation is $-0.1\, x_1 + 0.2\, x_2 = 0$, so $x_1 = 2 x_2$. With $x_1 + x_2 = 1$,

Thus $x_\infty = (2/3,\ 1/3)^\top$. The browser lab below runs 50 steps from $x_0 = (1, 0)^\top$ and compares the result to this normalized eigenvector.

Link forward. The same eigen-decoupling that turns $A^k$ into $\Lambda^k$ reappears in Week 11 for systems of differential equations $u' = Au$: solutions are linear combinations of $e^{\lambda_j t} v_j$. Diagonalization is the bridge between discrete powers and continuous exponentials.

Knowledge check#

Browser lab: Markov chain steady state#

Simulate a Markov chain converging to its steady state, and compare to the eigenvector for $\lambda = 1$.

import numpy as np

A = np.array([[0.9, 0.2],
              [0.1, 0.8]])

x0 = np.array([1.0, 0.0])
x = x0.copy()
for _ in range(50):
    x = A @ x

eigvals, eigvecs = np.linalg.eig(A)
steady_idx = np.argmin(np.abs(eigvals - 1))
steady_state = eigvecs[:, steady_idx]
steady_state = steady_state / steady_state.sum()

print("x after 50 steps =", x)
print("eigenvector steady state (normalized) =", steady_state.real)

print("Notice: x after 50 steps ≈ [0.667, 0.333] — it has converged to the normalized λ = 1 eigenvector.")

Done when#

You can diagonalize a matrix as $A = S\Lambda S^{-1}$, use it to compute $A^k$, and find a Markov chain's steady state as the $\lambda = 1$ eigenvector normalized to sum to 1. Check it against the browser lab: for $A=\begin{pmatrix}0.9&0.2\\0.1&0.8\end{pmatrix}$ the x after 50 steps and the normalized eigenvector both converge to [0.667, 0.333] (i.e. $2/3$ and $1/3$).

Further Reading#

• Strang, §6.2: Diagonalizing a Matrix — the classic exposition of eigen-decomposition and its use for powers.
• Brin & Page (1998): The Anatomy of a Large-Scale Hypertextual Web Search Engine — the original PageRank paper, which applies Markov chain theory to rank web pages.
• Lay, §5.3: Diagonalization — detailed worked examples with defectiveness checks.
• For the full MDP connection (Markov chains plus decisions and rewards), see Week 3: Markov Decision Processes.