42. Adv: Perron-Frobenius Theorem (intro, for nonnegative matrices)

§22.3 needed a strictly dominant eigenvalue for power iteration to converge — an assumption that just had to be taken on faith there. This closing lesson of Module 22 identifies a large, practically important class of matrices where that assumption is guaranteed: matrices with every entry \ge0.

The theorem (basic form)

Theorem (Perron-Frobenius). If A is a square matrix with every entry strictly positive, then:

1. A has a real eigenvalue \lambda_{\max}>0 that is strictly greater in absolute value than every other eigenvalue.
2. The eigenvector for \lambda_{\max} can be chosen with every entry strictly positive.
3. \lambda_{\max} is a simple eigenvalue (algebraic multiplicity 1, so it's never defective there — §19.2).

This is a genuinely remarkable guarantee: nothing about eigenvalues has promised realness, positivity, or a dominance gap for a general matrix anywhere else in this course (§21.0's Spectral Theorem needed symmetry; this theorem needs only positivity of entries, an entirely different and often easier condition to check for real applications).

Extension to nonnegative matrices: if A's entries are merely \ge0 (some may be exactly 0) and A is irreducible (informally: its associated directed graph — an edge i\to j whenever a_{ij}>0 — is strongly connected, every node reachable from every other), the same conclusion holds. This weaker hypothesis is the one that actually matters in practice — Markov transition matrices (§24.0) and adjacency matrices of connected graphs (§24.2) are nonnegative but rarely strictly positive (most entries are 0), yet irreducibility still holds for any "everything connects to everything, eventually" system.

Why this guarantees power iteration works

Perron-Frobenius's part 1 is exactly §22.3's convergence hypothesis — stated there as an assumption, proven here (for this class of matrices) as a theorem. So for any positive (or irreducible nonnegative) matrix, power iteration from any positive starting vector is guaranteed to converge, with no need to check the gap condition by hand first. This is precisely why PageRank-style algorithms (§24.2) apply power iteration to web-graph or network matrices without worry — Perron-Frobenius is the theoretical guarantee running silently underneath.

Doing it in Python

import numpy as np

A = np.array([[2., 1., 3.], [1., 4., 1.], [3., 2., 1.]])   # all entries positive
eigvals, eigvecs = np.linalg.eig(A)

idx = np.argmax(np.abs(eigvals))
lam_max = eigvals[idx].real
v_max = eigvecs[:, idx].real

# Normalize sign so the Perron eigenvector reads as all-positive
if v_max[0] < 0:
    v_max = -v_max

print("all eigenvalues:", sorted([round(v.real, 4) for v in eigvals], reverse=True))
print("Perron eigenvalue:", round(float(lam_max), 4))
print("Perron eigenvector (should be all positive):", [round(v, 4) for v in v_max.tolist()])

all eigenvalues: [6.0, 2.5616, -1.5616]
Perron eigenvalue: 6.0
Perron eigenvector (should be all positive): [0.5774, 0.5774, 0.5774]

Confirming an irreducible nonnegative (not strictly positive) matrix still satisfies the theorem:

import numpy as np

# A 3-node cycle graph's transition-like matrix: mostly zeros, but irreducible
A = np.array([[0., 1., 0.], [0., 0., 1.], [1., 0., 0.]])
eigvals = np.linalg.eigvals(A)

print("eigenvalues:", sorted([round(abs(v), 4) for v in eigvals], reverse=True))
print("magnitudes tied -- NOT strictly dominant:",
      len(set(round(abs(v), 4) for v in eigvals)) == 1)

eigenvalues: [1.0, 1.0, 1.0]
magnitudes tied -- NOT strictly dominant: True

Worked example

Verify Perron-Frobenius for A=\begin{pmatrix}1&2\\3&2\end{pmatrix} (all entries positive).

\operatorname{tr}A=3, \det A=2-6=-4. \lambda^2-3\lambda-4=0\Rightarrow(\lambda-4)(\lambda+1)=0\Rightarrow\lambda=4,-1.

\lambda_{\max}=4: real ✓, and |4|>|-1|: strictly dominant ✓.

Eigenvector for \lambda=4: (A-4I)\vec v=\vec0: \begin{pmatrix}-3&2\\3&-2\end{pmatrix}\vec v=\vec0\Rightarrow 3v_1=2v_2\Rightarrow\vec v=(2,3) — both entries positive ✓.

\boxed{\lambda_{\max}=4,\ \vec v_{\max}=(2,3)\text{, all conditions confirmed}}

Sanity check. The other eigenvalue, -1, has eigenvector: from (A+I)\vec v=\vec0: \begin{pmatrix}2&2\\3&3\end{pmatrix}\vec v=\vec0\Rightarrow v_1=-v_2, giving (1,-1) — mixed signs, exactly as the theorem's part 2 implies by contrast: only the dominant eigenvalue is guaranteed an all-positive eigenvector; the others generally are not.

Your turn

1. Does the counterexample matrix from Section 22.3 ("your turn" question 2, \operatorname{diag}(5,5,1)) satisfy Perron-Frobenius's strict-positivity hypothesis? Would you expect a dominance gap?

2. Why does a matrix with a negative entry not automatically violate Perron-Frobenius?

3. True or false: Perron-Frobenius guarantees the dominant eigenvector is unique (not just its direction, but the exact vector).

Solutions

1. No — \operatorname{diag}(5,5,1) has off-diagonal entries equal to 0, not strictly positive (and it isn't irreducible either: node 3 has no path to nodes 1,2 in the associated graph, since every off-diagonal entry is zero). So Perron-Frobenius's hypotheses fail, and consistent with that, §22.3 found no dominance gap (|\lambda_1|=|\lambda_2|=5) — the theorem's guarantee simply doesn't apply here, and the example shows exactly what can go wrong without it.

2. The hypothesis only restricts A's own entries, not its eigenvalues or eigenvectors. A matrix can have every entry \ge0 and still be discussed by this lesson; the theorem says nothing at all about matrices with a negative entry — it simply doesn't apply to them, neither confirming nor denying a dominance gap (some nonnegative-entry requirement is essential to the proof, not an incidental restriction).

3. False — only up to scaling. Like every eigenvector claim in this course (§19.0), any positive multiple of the Perron eigenvector is equally valid; the theorem guarantees a positive direction is unique (via part 3's simple-multiplicity guarantee: a 1-dimensional eigenspace has only one direction in it, but infinitely many vectors along that direction), not a single canonical vector — normalizing (§20.4) is what pins down one specific representative, as done in the Python examples above.

Check yourself in code

For A=\begin{pmatrix}3&1\\2&4\end{pmatrix} (all entries positive), find the Perron eigenvalue and confirm its eigenvector has all positive entries.

Print exactly this:

Perron eigenvalue: 5.0
eigenvector: [0.4472, 0.8944]
all positive: True

import numpy as np

A = np.array([[3., 1.], [2., 4.]])
eigvals, eigvecs = np.linalg.eig(A)
idx = np.argmax(np.abs(eigvals))

lam_max = eigvals[idx].real
v_max = eigvecs[:, idx].real
if v_max[0] < 0:
    v_max = -v_max

print("Perron eigenvalue:", round(float(lam_max), 4))
# print the eigenvector (rounded to 4 dp) and whether all entries are positive

import numpy as np

A = np.array([[3., 1.], [2., 4.]])
eigvals, eigvecs = np.linalg.eig(A)
idx = np.argmax(np.abs(eigvals))

lam_max = eigvals[idx].real
v_max = eigvecs[:, idx].real
if v_max[0] < 0:
    v_max = -v_max

print("Perron eigenvalue:", round(float(lam_max), 4))
print("eigenvector:", [round(v, 4) for v in v_max.tolist()])
print("all positive:", bool(np.all(v_max > 0)))

Perron-Frobenius guarantees that any matrix with strictly positive (or irreducible nonnegative) entries has a real, strictly dominant, simple eigenvalue with an all-positive eigenvector — exactly the condition §22.3's power iteration needs, now proven rather than assumed for this large and practically common class of matrices.

This closes Module 22. The numerical machinery here — stable factorizations, condition numbers, iterative eigenvalue methods — is what makes Modules 16–21's exact theory usable on real, large-scale data. Module 23 turns to structures this course has used constantly without naming: dual spaces, bilinear forms, and a first glimpse of tensors.