19.5 Primitive Matrices

The Perron–Frobenius theorem tells us what an irreducible non-negative matrix looks like at its spectral radius: $\rho(\mathbf{A})$ is an algebraically simple eigenvalue with a positive eigenvector. It says nothing about what the powers $\mathbf{A}^{m}$ do, and Chapter 9 §11 already met the obstacle. The swap $\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ is irreducible, has a positive eigenvector for $\rho = 1$ , and its powers alternate forever. This section finds the extra hypothesis that makes the powers settle down, proves that under it $(\mathbf{A}/\rho)^{m}$ converges to an explicit rank-one matrix, and explains what goes wrong without it: the eigenvalues of modulus $\rho$ are then spread evenly around a circle, and their number is read off the zero pattern of $\mathbf{A}$ .

Throughout, matrices are real and $\mathbf{A} \ge 0$ is meant entrywise, as are $\mathbf{A} > 0$ , $\mathbf{x} \ge \mathbf{0}$ and $\mathbf{x} > \mathbf{0}$ . The spectrum is taken over $\mathbb{C}$ , and $\rho(\mathbf{A})$ is the spectral radius (Definition 16.4.1).

19.5.1. Walks in a non-negative matrix

Whether a power $\mathbf{A}^{m}$ has a positive entry at position $(i, j)$ depends only on which entries of $\mathbf{A}$ are zero. The bookkeeping device is the directed graph $G(\mathbf{A})$ of §02 (Definition 19.2.1): it has an edge $j \to i$ for each non-zero entry $a_{ij}$ , and a walk of length $m$ from $j$ to $i$ is a list $j = i_0, i_1, \dots, i_m = i$ of vertices in which each $i_{t-1} \to i_t$ is an edge. The edge for $a_{ij}$ points from the column index to the row index, the direction in which a column-stochastic chain moves. A walk is closed if $i_0 = i_m$ and $m \ge 1$ .

By §02’s count of walks (Lemma 19.2.1 (a)), for $\mathbf{A} \ge 0$ and $m \ge 0$ , $(\mathbf{A}^{m})_{ij} > 0$ if and only if $G(\mathbf{A})$ has a walk of length $m$ from $j$ to $i$ . Everything in this section about zero patterns rests on that fact.

19.5.2. Primitive matrices

Here is the property the swap lacks. Its powers are $\mathbf{I}$ and the swap itself, and each of them has zero entries; no power ever mixes every state with every other.

A primitive matrix is one that, after enough steps, connects every index to every index at once.

Definition 19.5.1 (Primitive Matrix)

A matrix $\mathbf{A} \in M_n(\mathbb{R})$ , $n \ge 1$ , with $\mathbf{A} \ge 0$ is primitive if $\mathbf{A}^{k} > 0$ for some integer $k \ge 1$ , that is, if every entry of some power of $\mathbf{A}$ is strictly positive.

In words: we are allowed to wait, but only for a finite number $k$ of steps, and after those $k$ steps all $n^{2}$ entries must be positive together. By Lemma 19.2.1 (a), $\mathbf{A}$ is primitive exactly when there is one length $k$ such that every vertex of $G(\mathbf{A})$ has a walk of length $k$ to every vertex, including to itself.

Examples.

Positive matrices. If $\mathbf{A} > 0$ , take $k = 1$ . Perron’s theorem (Theorem 19.1.5) is about these.
A matrix with zeros. $\mathbf{A} = \begin{pmatrix} 1 & 1 \\ 2 & 0 \end{pmatrix}$ has a zero entry, but $\mathbf{A}^{2} = \begin{pmatrix} 3 & 1 \\ 2 & 2 \end{pmatrix} > 0$ . So $\mathbf{A}$ is primitive with $k = 2$ . In the graph: the edges are $1 \to 1$ , $1 \to 2$ and $2 \to 1$ , and $1 \to 1 \to 1$ , $1 \to 1 \to 2$ , $2 \to 1 \to 1$ , $2 \to 1 \to 2$ are walks of length $2$ between every ordered pair.
A slower one. $\mathbf{W} = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}$ . Its edges are $2 \to 1$ , $3 \to 2$ , $1 \to 3$ and $2 \to 3$ , so its closed walks include $1 \to 3 \to 2 \to 1$ of length $3$ and $2 \to 3 \to 2$ of length $2$ . Multiplying out, $\mathbf{W}^{4} = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 2 & 1 \end{pmatrix}$ still has a zero, and $\mathbf{W}^{5} = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 2 & 2 \end{pmatrix} > 0$ . So $\mathbf{W}$ is primitive, and the smallest $k$ is $5$ .
Degenerate case. A $1 \times 1$ matrix $(a)$ is primitive if and only if $a > 0$ . The zero $1 \times 1$ matrix is not, which is why the statements below exclude it.

Non-example by minimal change. Change the $(1,1)$ -entry of $\begin{pmatrix} 1 & 1 \\ 2 & 0 \end{pmatrix}$ to $0$ . The result $\mathbf{A}' = \begin{pmatrix} 0 & 1 \\ 2 & 0 \end{pmatrix}$ is still non-negative, and it is still irreducible, since $(\mathbf{I} + \mathbf{A}')^{1} > 0$ (Theorem 19.2.6). But $\mathbf{A}'^{2} = 2\mathbf{I}$ , so the even powers of $\mathbf{A}'$ are multiples of $\mathbf{I}$ and the odd powers multiples of $\mathbf{A}'$ , and every power has two zero entries: $\mathbf{A}'$ is not primitive. The clause that fails is “some power is positive”; what was lost is the loop $1 \to 1$ ; without it every edge joins $1$ and $2$ , so every closed walk has even length. More generally, the powers of a permutation matrix are permutation matrices (Lemma 3.4.7), and for $n \ge 2$ a permutation matrix has zeros; so no permutation matrix of size $n \ge 2$ is primitive.

Why this definition. Asking for $\mathbf{A} > 0$ itself would be too strong: it excludes the matrices above, whose powers behave exactly like those of a positive matrix. Asking only that each position $(i, j)$ be positive in some power, possibly a different power for each position, is too weak: that is irreducibility, and the swap satisfies it. Primitivity sits between the two. It asks for a single power that is positive everywhere.

Warning. Irreducible does not mean primitive. Irreducibility asks that each $j$ be reachable from each $i$ by a walk of some length; primitivity asks for walks of one common length. For the swap, every walk from $1$ to $2$ has odd length and every walk from $1$ to $1$ has even length, so no single power is positive at both $(1,1)$ and $(1,2)$ .

Quick check. Is $\mathbf{A} = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}$ primitive? Is $\mathbf{B} = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$ ?

Solution. $\mathbf{A}^{2} = \begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix} > 0$ , so $\mathbf{A}$ is primitive. For $\mathbf{B}$ , every power is upper triangular, $\mathbf{B}^{m} = \begin{pmatrix} 1 & m \\ 0 & 1 \end{pmatrix}$ , so the $(2,1)$ -entry is always $0$ and $\mathbf{B}$ is not primitive: $G(\mathbf{B})$ has no walk from $1$ to $2$ at all.

The first consequences of the definition come straight from the graph and from Perron’s theorem applied to the positive power.

Proposition 19.5.1 (First Properties of Primitive Matrices)

Let $\mathbf{A} \in M_n(\mathbb{R})$ be primitive, with $\mathbf{A}^{k} > 0$ . Then:

(a) $\mathbf{A}^{m} > 0$ for every $m \ge k$ ;
(b) $\mathbf{A}$ is irreducible;
(c) $\rho(\mathbf{A}) > 0$ , and $\rho(\mathbf{A})$ is the only eigenvalue of $\mathbf{A}$ of modulus $\rho(\mathbf{A})$ .

Idea.

(a) Multiplying a positive matrix by a non-negative matrix with no zero column keeps it positive. (b) A positive power gives walks between all vertices, which is strong connectivity. (c) The eigenvalues of $\mathbf{A}^{k}$ are the $k$ -th powers of those of $\mathbf{A}$ . A second eigenvalue of $\mathbf{A}$ on the circle of radius $\rho$ would land, after raising to the $k$ -th power, on the circle where Perron’s theorem allows only the simple eigenvalue $\rho(\mathbf{A}^{k})$ .

Proof.

(a) Column $j$ of $\mathbf{A}^{k}$ is $\mathbf{A}^{k-1}$ times column $j$ of $\mathbf{A}$ (Theorem 0.9.2; for $k = 1$ read $\mathbf{A}^{0} = \mathbf{I}$ ). Since $\mathbf{A}^{k} > 0$ , no column of $\mathbf{A}$ is zero. Now suppose $\mathbf{A}^{m} > 0$ for some $m \ge k$ . Then $(\mathbf{A}^{m+1})_{ij} = \sum_l (\mathbf{A}^{m})_{il}a_{lj}$ is a sum of non-negative terms, and the term for an $l$ with $a_{lj} > 0$ is positive. So $\mathbf{A}^{m+1} > 0$ , and (a) follows by induction on $m$ .
(b) For every ordered pair $(j, i)$ , $(\mathbf{A}^{k})_{ij} > 0$ , so Lemma 19.2.1 (a) gives a walk from $j$ to $i$ in $G(\mathbf{A})$ . So $G(\mathbf{A})$ is strongly connected (Definition 19.2.2), and $\mathbf{A}$ is irreducible by Theorem 19.2.5.
(c) Over $\mathbb{C}$ , write $p_{\mathbf{A}} = (x - \lambda_1)\cdots(x - \lambda_n)$ , with each eigenvalue repeated according to its algebraic multiplicity. By the Spectral Mapping Theorem (Theorem 9.10.1) with $q = x^{k}$ , $p_{\mathbf{A}^{k}} = (x - \lambda_1^{k})\cdots(x - \lambda_n^{k}) .$ So $\rho(\mathbf{A}^{k}) = \max_i\lvert\lambda_i\rvert^{k} = \rho(\mathbf{A})^{k}$ . By Theorem 19.1.5 applied to $\mathbf{A}^{k} > 0$ , $\rho(\mathbf{A}^{k}) > 0$ is an algebraically simple eigenvalue of $\mathbf{A}^{k}$ , and every other eigenvalue of $\mathbf{A}^{k}$ has modulus less than $\rho(\mathbf{A}^{k})$ . In particular $\rho(\mathbf{A})^{k} > 0$ , so $\rho(\mathbf{A}) > 0$ .

By (b) and Theorem 19.3.2, $\rho \mathrel{:=} \rho(\mathbf{A})$ is an eigenvalue of $\mathbf{A}$ ; say $\lambda_1 = \rho$ . Suppose some $\lambda_s$ with $s \ge 2$ had $\lvert\lambda_s\rvert = \rho$ but $\lambda_s \ne \rho$ . Then $\lambda_s^{k}$ is an eigenvalue of $\mathbf{A}^{k}$ of modulus $\rho^{k} = \rho(\mathbf{A}^{k})$ , so by Perron’s theorem it is not an “other” eigenvalue: $\lambda_s^{k} = \rho^{k}$ . Then $\rho^{k}$ occurs at least twice in the list $\lambda_1^{k}, \dots, \lambda_n^{k}$ , at positions $1$ and $s$ , so $a_{\mathbf{A}^{k}}(\rho^{k}) \ge 2$ , contradicting simplicity. Hence $\rho$ is the only eigenvalue of modulus $\rho$ .

Part (c) is the whole spectral content of primitivity, and the rest of the section shows that it is also enough. Part (a) says that once the powers become positive they stay positive, so the least such $k$ , the exponent of $\mathbf{A}$ , is well defined and marks a permanent change.

19.5.3. The limit theorem

For the swap, $\rho = 1$ and the powers do not converge. We now show that primitivity is exactly what makes $(\mathbf{A}/\rho)^{m}$ converge, and we identify the limit. The answer involves eigenvectors on both sides.

If $\mathbf{A} \ge 0$ is irreducible, then Theorem 19.3.2 (a) and Corollary 19.3.3 (a)–(c) provide $\mathbf{v} > \mathbf{0}$ and $\mathbf{w} > \mathbf{0}$ with $\mathbf{A}\mathbf{v} = \rho(\mathbf{A})\mathbf{v}$ , $\mathbf{w}^{\top}\mathbf{A} = \rho(\mathbf{A})\mathbf{w}^{\top}$ and $\mathbf{w}^{\top}\mathbf{v} > 0$ , and the right and left Perron vectors of Definition 19.3.1 are the pair scaled so that $\mathbf{1}^{\top}\mathbf{v} = 1$ and $\mathbf{w}^{\top}\mathbf{v} = 1$ . Each of $\mathbf{v}, \mathbf{w}$ is determined up to a positive factor, because $\rho(\mathbf{A})$ is algebraically simple (Theorem 19.3.2 (b)), so its eigenspaces for $\mathbf{A}$ and $\mathbf{A}^{\top}$ are lines (Theorem 9.3.1, Proposition 9.10.5 (b)).

Theorem 19.5.2 (Limit Theorem for Primitive Matrices)

Let $\mathbf{A} \in M_n(\mathbb{R})$ be primitive, $\rho = \rho(\mathbf{A})$ , and let $\mathbf{v} > \mathbf{0}$ and $\mathbf{w} > \mathbf{0}$ satisfy $\mathbf{A}\mathbf{v} = \rho\mathbf{v}$ and $\mathbf{w}^{\top}\mathbf{A} = \rho\mathbf{w}^{\top}$ , for instance the right and left Perron vectors of $\mathbf{A}$ . Then, entrywise, $\Big(\frac{1}{\rho}\mathbf{A}\Big)^{m} \longrightarrow \frac{\mathbf{v}\mathbf{w}^{\top}}{\mathbf{w}^{\top}\mathbf{v}} \qquad (m \to \infty).$ The limit is a positive matrix of rank one, and it does not depend on how $\mathbf{v}$ and $\mathbf{w}$ are scaled. The same conclusion holds for every irreducible $\mathbf{A} \ge 0$ with $\rho(\mathbf{A}) > 0$ whose only eigenvalue of modulus $\rho(\mathbf{A})$ is $\rho(\mathbf{A})$ itself.

Idea. Divide by $\rho$ , so that the Perron eigenvalue becomes $1$ and every other eigenvalue lies strictly inside the unit circle. Chapter 10 §10 then says the powers converge, with no diagonalizability needed, because it works with the Jordan form. It remains to name the limit $\mathbf{L}$ . Three identities pin it down: $\mathbf{B}\mathbf{L} = \mathbf{L}$ puts every column of $\mathbf{L}$ on the line through $\mathbf{v}$ ; $\mathbf{L}\mathbf{B} = \mathbf{L}$ puts every row on the line through $\mathbf{w}^{\top}$ ; and $\mathbf{L}\mathbf{v} = \mathbf{v}$ fixes the scale.

Proof. It suffices to prove the last sentence, since a primitive matrix is irreducible with $\rho(\mathbf{A}) > 0$ and has $\rho(\mathbf{A})$ as its only eigenvalue of modulus $\rho(\mathbf{A})$ , by Proposition 19.5.1 (b) and (c).

So let $\mathbf{A} \ge 0$ be irreducible with $\rho > 0$ the only eigenvalue of modulus $\rho$ , and put $\mathbf{B} = \rho^{-1}\mathbf{A}$ . By Theorem 9.10.1 with $q = x/\rho$ , the eigenvalues of $\mathbf{B}$ are the numbers $\lambda/\rho$ , $\lambda \in \operatorname{spec}(\mathbf{A})$ , with the same algebraic multiplicities. So $1$ is an eigenvalue of $\mathbf{B}$ with $a_{\mathbf{B}}(1) = a_{\mathbf{A}}(\rho) = 1$ by Theorem 19.3.2, and every other eigenvalue of $\mathbf{B}$ has modulus less than $1$ . Since the $1$ -blocks in a Jordan form of $\mathbf{B}$ have total size $a_{\mathbf{B}}(1) = 1$ (Corollary 10.3.2 (a)), there is a single $1$ -block, of size $1$ . By Theorem 10.10.4, $\mathbf{B}^{m}$ converges to some $\mathbf{L} \in M_n(\mathbb{C})$ .

Three identities. By the algebra of limits, (B3) of Chapter 10 §10, applied entry by entry, $\mathbf{B}^{m+1} = \mathbf{B}\,\mathbf{B}^{m} \to \mathbf{B}\mathbf{L}$ and $\mathbf{B}^{m+1} = \mathbf{B}^{m}\mathbf{B} \to \mathbf{L}\mathbf{B}$ ; but $(\mathbf{B}^{m+1})$ is a tail of $(\mathbf{B}^{m})$ , so it also tends to $\mathbf{L}$ . Hence $\mathbf{B}\mathbf{L} = \mathbf{L} = \mathbf{L}\mathbf{B}$ . Also $\mathbf{B}\mathbf{v} = \mathbf{v}$ , so $\mathbf{B}^{m}\mathbf{v} = \mathbf{v}$ for every $m$ , and letting $m \to \infty$ gives $\mathbf{L}\mathbf{v} = \mathbf{v}$ .

The columns. $\mathbf{B}\mathbf{L} = \mathbf{L}$ says that every column of $\mathbf{L}$ lies in $E_1(\mathbf{B}) = E_{\rho}(\mathbf{A})$ , which is the line $\operatorname{span}(\mathbf{v})$ , as noted before the theorem. So column $j$ of $\mathbf{L}$ is $u_j\mathbf{v}$ for some $u_j \in \mathbb{C}$ , that is, $\mathbf{L} = \mathbf{v}\mathbf{u}^{\top}$ with $\mathbf{u} = (u_1, \dots, u_n)$ .

The rows. $\mathbf{L}\mathbf{B} = \mathbf{L}$ reads $\mathbf{v}(\mathbf{u}^{\top}\mathbf{B}) = \mathbf{v}\mathbf{u}^{\top}$ . Choose $r$ with $v_r \ne 0$ and compare row $r$ : $\mathbf{u}^{\top}\mathbf{B} = \mathbf{u}^{\top}$ , so $\mathbf{B}^{\top}\mathbf{u} = \mathbf{u}$ , and $\mathbf{u}$ lies in the eigenspace of $\mathbf{A}^{\top}$ for $\rho$ . That eigenspace is the line through $\mathbf{w}$ , so $\mathbf{u} = c\mathbf{w}$ for some $c \in \mathbb{C}$ .

The scale. Now $\mathbf{v} = \mathbf{L}\mathbf{v} = c\,\mathbf{v}(\mathbf{w}^{\top}\mathbf{v})$ , and comparing entry $r$ gives $c\,\mathbf{w}^{\top}\mathbf{v} = 1$ . Since $\mathbf{w}^{\top}\mathbf{v} > 0$ , $c = 1/(\mathbf{w}^{\top}\mathbf{v})$ , and $\mathbf{L} = \mathbf{v}\mathbf{w}^{\top}/(\mathbf{w}^{\top}\mathbf{v})$ .

Finally, $\mathbf{v}\mathbf{w}^{\top}$ has $(i,j)$ -entry $v_iw_j > 0$ and every column a multiple of $\mathbf{v}$ , so the limit is positive of rank one; replacing $\mathbf{v}, \mathbf{w}$ by $s\mathbf{v}, t\mathbf{w}$ with $s, t > 0$ multiplies numerator and denominator by $st$ . This proves the theorem.

Note what the proof did not use: no eigenvector basis, no computation of the other eigenvalues. Chapter 10’s Jordan-form criterion did the analysis once and for all; Perron–Frobenius supplied the simple eigenvalue and the two positive eigenvectors. With the normalization $\mathbf{w}^{\top}\mathbf{v} = 1$ of §03, the limit is simply the idempotent $\mathbf{v}\mathbf{w}^{\top}$ . §06 turns the theorem into the long-run theorem for Markov chains.

Example (A Limit Computed Two Ways)

Let $\mathbf{A} = \begin{pmatrix} 1 & 1 \\ 2 & 0 \end{pmatrix}$ , which is primitive since $\mathbf{A}^{2} > 0$ . Find $\lim_m (\mathbf{A}/\rho)^{m}$ from Theorem 19.5.2, and confirm it with an exact formula for $\mathbf{A}^{m}$ .

Solution. The theorem. $p_{\mathbf{A}} = x^{2} - x - 2 = (x - 2)(x + 1)$ , so $\rho = 2$ . A positive right eigenvector solves $(\mathbf{A} - 2\mathbf{I})\mathbf{v} = \mathbf{0}$ , that is, $-v_1 + v_2 = 0$ : take $\mathbf{v} = (1, 1)$ . A positive left eigenvector solves $(\mathbf{A}^{\top} - 2\mathbf{I})\mathbf{w} = \mathbf{0}$ , with $\mathbf{A}^{\top} - 2\mathbf{I} = \begin{pmatrix} -1 & 2 \\ 1 & -2 \end{pmatrix}$ : take $\mathbf{w} = (2, 1)$ . Then $\mathbf{w}^{\top}\mathbf{v} = 3$ , and $\Big(\frac{1}{2}\mathbf{A}\Big)^{m} \longrightarrow \mathbf{L} = \frac13\begin{pmatrix} 1 \\ 1 \end{pmatrix}\begin{pmatrix} 2 & 1 \end{pmatrix} = \frac13\begin{pmatrix} 2 & 1 \\ 2 & 1 \end{pmatrix} .$ The formula. $\mathbf{L}^{2} = \mathbf{L}$ , because $\mathbf{w}^{\top}\mathbf{v}/3 = 1$ , and $\mathbf{L}(\mathbf{I} - \mathbf{L}) = \mathbf{0}$ . A direct check gives $3\mathbf{L} - \mathbf{I} = \begin{pmatrix} 1 & 1 \\ 2 & 0 \end{pmatrix} = \mathbf{A}$ , so $\mathbf{A} = 2\mathbf{L} - (\mathbf{I} - \mathbf{L})$ . Since $\mathbf{L}$ and $\mathbf{I} - \mathbf{L}$ are complementary projections, induction on $m$ gives $\begin{aligned} \mathbf{A}^{m} &= 2^{m}\mathbf{L} + (-1)^{m}(\mathbf{I} - \mathbf{L}), \\ \Big(\frac12\mathbf{A}\Big)^{m} &= \mathbf{L} + \Big(-\frac12\Big)^{m}\frac13\begin{pmatrix} 1 & -1 \\ -2 & 2 \end{pmatrix} . \end{aligned}$ For $m = 2$ this is $\frac13\begin{pmatrix} 2 & 1 \\ 2 & 1 \end{pmatrix} + \frac1{12}\begin{pmatrix} 1 & -1 \\ -2 & 2 \end{pmatrix} = \frac14\begin{pmatrix} 3 & 1 \\ 2 & 2 \end{pmatrix}$ , which is $\mathbf{A}^{2}/4$ . The error term is $(-\frac12)^{m}$ times a fixed matrix: it decays at the rate $\lvert\lambda_2\rvert/\rho = \frac12$ and changes sign at every step.

Warning. The limit uses the left eigenvector, not the transpose of the right one. For the matrix above, $\mathbf{v}\mathbf{v}^{\top}/(\mathbf{v}^{\top}\mathbf{v}) = \frac12\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}$ , which is not the limit. The two agree when $\mathbf{A}$ is symmetric, since then $\mathbf{w} = \mathbf{v}$ ; in general $\mathbf{w}$ carries the information about how much each starting index contributes in the long run.

The limit theorem also gives the converse of Proposition 19.5.1 (c).

Theorem 19.5.3 (Primitivity from the Spectrum)

Let $\mathbf{A} \in M_n(\mathbb{R})$ , $\mathbf{A} \ge 0$ , be irreducible with $\rho(\mathbf{A}) > 0$ . Then $\mathbf{A}$ is primitive if and only if $\rho(\mathbf{A})$ is the only eigenvalue of $\mathbf{A}$ of modulus $\rho(\mathbf{A})$ .

Idea. One direction is already proved. For the other, the limit theorem gives a positive limit, and a sequence that converges to a positive number is eventually positive. There are only $n^{2}$ entries to wait for, so some single power is positive everywhere.

Proof. $(\Rightarrow)$ This is Proposition 19.5.1 (c).

$(\Leftarrow)$ By the last sentence of Theorem 19.5.2, $(\mathbf{A}/\rho)^{m} \to \mathbf{L}$ with $\mathbf{L} > 0$ . Each of the $n^{2}$ entries of $(\mathbf{A}/\rho)^{m}$ converges to a positive number $c_{ij}$ , so it is positive for all $m$ beyond some $m_{ij}$ : this is the definition of the limit with $\varepsilon = c_{ij}/2$ . For $m$ larger than the largest of these finitely many $m_{ij}$ , $(\mathbf{A}/\rho)^{m} > 0$ , and hence $\mathbf{A}^{m} = \rho^{m}(\mathbf{A}/\rho)^{m} > 0$ . So $\mathbf{A}$ is primitive.

The hypothesis $\rho(\mathbf{A}) > 0$ excludes only the $1 \times 1$ zero matrix: for $n \ge 2$ it holds for every irreducible $\mathbf{A} \ge 0$ by Theorem 19.3.2 (d), and for $n = 1$ , $\rho((a)) = a$ .

19.5.4. The peripheral spectrum and the period

What does an irreducible, non-primitive matrix look like? The eigenvalues of modulus $\rho(\mathbf{A})$ are called the peripheral eigenvalues of $\mathbf{A}$ , and the theorem just proved says that a non-primitive irreducible matrix, other than the $1 \times 1$ zero matrix, has more than one of them. For the swap they are $\pm 1$ . For the $3 \times 3$ cyclic permutation they are the three cube roots of unity, as we shall compute. The pattern is general, and it is controlled by a number read off the walks.

The period is the common step size of all round trips.

Definition 19.5.2 (Period)

Let $\mathbf{A} \in M_n(\mathbb{R})$ , $\mathbf{A} \ge 0$ , be irreducible and not the $1 \times 1$ zero matrix. The period of $\mathbf{A}$ is the greatest common divisor of the lengths of all closed walks in $\mathbf{A}$ .

There is at least one closed walk, so the definition makes sense. If $n = 1$ , then $\mathbf{A} = (a)$ with $a > 0$ , and the loop $1 \to 1$ is a closed walk of length $1$ . If $n \ge 2$ , then $G(\mathbf{A})$ is strongly connected (Theorem 19.2.5), so there are walks from $1$ to $2$ and from $2$ to $1$ , and one followed by the other is a closed walk. For the swap, every edge joins $1$ and $2$ , so closed walks have even length, and $1 \to 2 \to 1$ has length $2$ : the period is $2$ . For $\mathbf{W}$ above, closed walks of lengths $3$ and $2$ give period $1$ . A single positive diagonal entry $a_{ii}$ is a loop $i \to i$ , a closed walk of length $1$ , and forces period $1$ .

The main theorem of this part says that the period counts the peripheral eigenvalues, and that they sit at the corners of a regular polygon. As in §01, $\lvert\mathbf{z}\rvert = (\lvert z_1\rvert, \dots, \lvert z_n\rvert)$ is the entrywise absolute value of $\mathbf{z} \in \mathbb{C}^{n}$ .

Theorem 19.5.4 (The Peripheral Spectrum)

Let $\mathbf{A} \in M_n(\mathbb{R})$ , $\mathbf{A} \ge 0$ , be irreducible and not the $1 \times 1$ zero matrix. Put $\rho = \rho(\mathbf{A})$ , let $h$ be the number of distinct eigenvalues of $\mathbf{A}$ of modulus $\rho$ , and let $\omega = e^{2\pi i/h}$ . Then:

(a) the eigenvalues of $\mathbf{A}$ of modulus $\rho$ are exactly $\rho, \rho\omega, \rho\omega^{2}, \dots, \rho\omega^{h-1}$ , and each is algebraically simple;
(b) $\mathbf{A}$ is similar to $\omega\mathbf{A}$ ; in particular $\operatorname{spec}(\mathbf{A})$ is unchanged by multiplication by $\omega$ , with algebraic multiplicities;
(c) $h$ equals the period of $\mathbf{A}$ .

Idea. Step roadmap. ① Take an eigenvector $\mathbf{z}$ for a peripheral eigenvalue $\rho e^{i\theta}$ . The triangle inequality (Theorem 0.6.4) gives $\mathbf{A}\lvert\mathbf{z}\rvert \ge \rho\lvert\mathbf{z}\rvert$ , and superinvariance (Proposition 19.4.2) forces equality, so $\lvert\mathbf{z}\rvert$ is a positive multiple of $\mathbf{v}$ . Equality in the triangle inequality then says all terms of each row sum point in the same direction, and that is a similarity $\mathbf{D}^{-1}\mathbf{A}\mathbf{D} = e^{i\theta}\mathbf{A}$ with $\mathbf{D}$ diagonal. ② So the spectrum is invariant under rotation by every peripheral angle, the peripheral points form a finite group of rotations, and a finite group of $h$ points on the unit circle must be the $h$ -th roots of unity. ③ The diagonal matrix $\mathbf{D}$ records a phase at each vertex, and each edge advances the phase by one step; going round a closed walk returns the phase, which ties $h$ to walk lengths.

Proof. Recall that $\rho > 0$ (the remark after Theorem 19.5.3), and let $\mathbf{v} > \mathbf{0}$ be an eigenvector of $\mathbf{A}$ for $\rho$ (Theorem 19.3.2 (a)).

Step 1. Let $\lambda = \rho e^{i\theta}$ be an eigenvalue. Then there are real numbers $\varphi_1, \dots, \varphi_n$ such that $e^{i\varphi_j} = e^{i\theta}e^{i\varphi_i}$ whenever $a_{ij} > 0$ ; consequently, with $\mathbf{D} = \operatorname{diag}(e^{i\varphi_1}, \dots, e^{i\varphi_n})$ , we have $\mathbf{D}^{-1}\mathbf{A}\mathbf{D} = e^{i\theta}\mathbf{A}$ .

Let $\mathbf{A}\mathbf{z} = \lambda\mathbf{z}$ with $\mathbf{z} \ne \mathbf{0}$ . By Lemma 19.1.2 (a), with $\lvert\mathbf{A}\rvert = \mathbf{A}$ since $\mathbf{A} \ge 0$ , in each row $\rho\,\lvert z_i\rvert = \lvert\lambda z_i\rvert = \Big\lvert\sum_j a_{ij}z_j\Big\rvert \le \sum_j a_{ij}\lvert z_j\rvert = (\mathbf{A}\lvert\mathbf{z}\rvert)_i .$ So $\mathbf{A}\lvert\mathbf{z}\rvert \ge \rho\lvert\mathbf{z}\rvert$ , where $\lvert\mathbf{z}\rvert \ge \mathbf{0}$ and $\lvert\mathbf{z}\rvert \ne \mathbf{0}$ . If $\mathbf{A}\lvert\mathbf{z}\rvert \ne \rho\lvert\mathbf{z}\rvert$ , then Proposition 19.4.2 (b) with $s = \rho$ would give $\rho > \rho$ ; hence $\mathbf{A}\lvert\mathbf{z}\rvert = \rho\lvert\mathbf{z}\rvert$ . So $\lvert\mathbf{z}\rvert$ is a non-negative eigenvector of $\mathbf{A}$ , and by Theorem 19.3.2 (c) it is a positive multiple of $\mathbf{v}$ . Therefore $\lvert\mathbf{z}\rvert > \mathbf{0}$ , and we may write $z_j = \lvert z_j\rvert e^{i\varphi_j}$ in polar form.

Now every inequality in the display is an equality. Fix $i$ . The number $S = \sum_j a_{ij}z_j = \lambda z_i = \rho\lvert z_i\rvert e^{i(\theta + \varphi_i)}$ (Theorem 0.6.5) is non-zero, since $\rho > 0$ and $\lvert z_i\rvert > 0$ , and $\lvert S\rvert = \sum_j\lvert a_{ij}z_j\rvert$ . So Lemma 19.1.3, applied to the $n$ numbers $a_{ij}z_j$ , with $S/\lvert S\rvert = e^{i(\theta + \varphi_i)}$ , gives $a_{ij}z_j = a_{ij}\lvert z_j\rvert e^{i(\theta + \varphi_i)}$ for every $j$ . If $a_{ij} > 0$ , dividing by $a_{ij}\lvert z_j\rvert > 0$ gives $e^{i\varphi_j} = e^{i(\theta + \varphi_i)} = e^{i\theta}e^{i\varphi_i}$ . This is the first statement. For the second, the $(i,j)$ -entry of $\mathbf{D}^{-1}\mathbf{A}\mathbf{D}$ is $e^{-i\varphi_i}a_{ij}e^{i\varphi_j}$ , which is $e^{i\theta}a_{ij}$ when $a_{ij} > 0$ and $0 = e^{i\theta}a_{ij}$ when $a_{ij} = 0$ .

Step 2. Proof of (a) and (b). Write $p_{\mathbf{A}} = (x - \lambda_1)\cdots(x - \lambda_n)$ over $\mathbb{C}$ . For every peripheral $\lambda = \rho e^{i\theta}$ , Step 1 and Theorem 7.10.3 give $p_{\mathbf{A}} = p_{e^{i\theta}\mathbf{A}}$ , and by Theorem 9.10.1 with $q = e^{i\theta}x$ , $\begin{aligned} (x - \lambda_1)\cdots(x - \lambda_n) &= p_{\mathbf{A}} = p_{e^{i\theta}\mathbf{A}} \\ &= (x - e^{i\theta}\lambda_1)\cdots(x - e^{i\theta}\lambda_n) . \end{aligned}$ So multiplication by $e^{i\theta}$ permutes the eigenvalues listed with multiplicity: $a_{\mathbf{A}}(e^{i\theta}\mu) = a_{\mathbf{A}}(\mu) \qquad \text{for every } \mu \in \mathbb{C} .$

Let $G = \{\lambda/\rho : \lambda \in \operatorname{spec}(\mathbf{A}),\ \lvert\lambda\rvert = \rho\}$ , a set of $h$ complex numbers of modulus $1$ containing $1$ , because $\rho \in \operatorname{spec}(\mathbf{A})$ by Theorem 19.3.2. If $g = e^{i\theta}$ and $g'$ lie in $G$ , then $\rho g' \in \operatorname{spec}(\mathbf{A})$ , so $g\rho g' \in \operatorname{spec}(\mathbf{A})$ by the invariance just proved, and it has modulus $\rho$ : thus $gg' \in G$ . For fixed $g \in G$ , the map $G \to G$ , $x \mapsto gx$ , is injective, since $g \ne 0$ ; as $G$ is finite it is a bijection. Hence the product $\Pi$ of all elements of $G$ satisfies $\Pi = \prod_{x \in G} gx = g^{h}\,\Pi$ , and $\Pi \ne 0$ , so $g^{h} = 1$ . So $G$ is contained in the set of $h$ -th roots of unity, which has exactly $h$ elements $1, \omega, \dots, \omega^{h-1}$ (Example (Roots of Unity)). Both sets have $h$ elements, so they are equal. This proves the first half of (a).

Each $\rho\omega^{j}$ has $a_{\mathbf{A}}(\rho\omega^{j}) = a_{\mathbf{A}}(\rho) = 1$ , by the invariance with $e^{i\theta} = \omega^{j}$ and Theorem 19.3.2. This proves (a). Taking $\lambda = \rho\omega$ in Step 1 gives (b).

Step 3. Proof of (c). Let $d$ be the period.

$h$ divides $d$ . Apply Step 1 to $\lambda = \rho\omega$ , so $e^{i\theta} = \omega$ . Along a closed walk $i_0 \to i_1 \to \dots \to i_L = i_0$ each entry $a_{i_ti_{t-1}}$ is positive, so Step 1 gives $e^{i\varphi_{i_{t-1}}} = \omega e^{i\varphi_{i_t}}$ for each $t$ , and chaining these $L$ equations gives $e^{i\varphi_{i_0}} = \omega^{L}e^{i\varphi_{i_L}} = \omega^{L}e^{i\varphi_{i_0}}$ . So $\omega^{L} = 1$ , and $h$ divides $L$ (Example (Roots of Unity)). As this holds for every closed walk, $h$ divides $d$ .

$d$ divides $h$ . If $n = 1$ then $d = 1$ . Let $n \ge 2$ . Since $G(\mathbf{A})$ is strongly connected (Theorem 19.2.5), every vertex $j$ is joined to vertex $1$ by walks in both directions; for $j = 1$ this includes the walk of length $0$ . Choose for each $j$ the length $\ell_j$ of some walk from $1$ to $j$ , with $\ell_1 = 0$ . Any two walks from $1$ to $j$ , of lengths $\ell$ and $\ell'$ , have lengths congruent modulo $d$ : following either by a fixed walk from $j$ back to $1$ , of length $s$ , gives closed walks of lengths $\ell + s$ and $\ell' + s$ (or length $0$ , trivially a multiple of $d$ ), both multiples of $d$ . Now if $a_{ij} > 0$ , a walk from $1$ to $j$ followed by the edge $j \to i$ is a walk from $1$ to $i$ of length $\ell_j + 1$ , so $\ell_i \equiv \ell_j + 1 \pmod d$ . Put $\zeta = e^{2\pi i/d}$ and $\mathbf{E} = \operatorname{diag}(\zeta^{-\ell_1}, \dots, \zeta^{-\ell_n})$ . Then the $(i,j)$ -entry of $\mathbf{E}^{-1}\mathbf{A}\mathbf{E}$ is $\zeta^{\ell_i - \ell_j}a_{ij} = \zeta a_{ij}$ when $a_{ij} > 0$ , since $\zeta^{d} = 1$ , and $0$ otherwise. So $\mathbf{E}^{-1}\mathbf{A}\mathbf{E} = \zeta\mathbf{A}$ . As in Step 2, $\operatorname{spec}(\mathbf{A}) = \zeta\operatorname{spec}(\mathbf{A})$ , so $\zeta\rho \in \operatorname{spec}(\mathbf{A})$ , with modulus $\rho$ . By (a), $\zeta = \omega^{j}$ for some $j$ , so $\zeta^{h} = (\omega^{h})^{j} = 1$ , and $d$ divides $h$ : $e^{2\pi ih/d} = 1 = e^{2\pi i\cdot 0/d}$ , and two integers $k, l$ give the same number $e^{2\pi ik/d} = e^{2\pi il/d}$ only when $d$ divides $k - l$ (Example (Roots of Unity)).

Both $h$ and $d$ are positive, so $h = d$ . This proves the theorem.

The two halves of Step 3 are mirror images. The diagonal similarity attached to a peripheral eigenvalue is a consistent labeling of the indices by $h$ phases, with every positive entry advancing the phase by one; the walks of $\mathbf{A}$ build such a labeling with $d$ phases.

Combining (c) with Theorem 19.5.3 gives a test that needs no eigenvalues at all.

Corollary 19.5.5 (Primitivity from Walks)

Let $\mathbf{A} \in M_n(\mathbb{R})$ , $\mathbf{A} \ge 0$ , be irreducible and not the $1 \times 1$ zero matrix. Then $\mathbf{A}$ is primitive if and only if its period is $1$ . In particular, an irreducible $\mathbf{A} \ge 0$ with at least one positive diagonal entry is primitive.

Proof. Since $\mathbf{A}$ is not the $1 \times 1$ zero matrix, $\rho(\mathbf{A}) > 0$ by the remark after Theorem 19.5.3. So by that theorem, $\mathbf{A}$ is primitive if and only if $h = 1$ , and $h$ is the period by Theorem 19.5.4 (c). A positive diagonal entry is a closed walk of length $1$ , so the period divides $1$ .

19.5.5. The cyclic permutation

The standard irreducible matrix that is not primitive is the cyclic shift. It generalizes Chapter 9’s swap, and it shows every part of Theorem 19.5.4 at once.

Example (The Cyclic Permutation)

Let $n \ge 2$ and let $\sigma \in S_n$ send $j \mapsto j + 1$ for $j < n$ and $n \mapsto 1$ . Its permutation matrix $\mathbf{P} = \mathbf{P}_\sigma$ (Definition 3.4.2) has columns $\mathbf{e}_2, \mathbf{e}_3, \dots, \mathbf{e}_n, \mathbf{e}_1$ . Show that $\mathbf{P}$ is irreducible with period $n$ , find its peripheral eigenvalues, and show that $\mathbf{P}^{m}$ does not converge.

Solution. Walks. The non-zero entries of $\mathbf{P}$ are $p_{j+1,\,j}$ for $j < n$ and $p_{1n}$ , so the edges of $G(\mathbf{P})$ are $j \to j + 1$ for $j < n$ and $n \to 1$ : the graph is the cycle $1 \to 2 \to \dots \to n \to 1$ . Every walk runs round it, and a closed walk goes round a whole number of times, so its length is a multiple of $n$ ; the walk $1 \to 2 \to \dots \to n \to 1$ has length $n$ . So the period is $n$ . Following the cycle, every vertex reaches every vertex, so $G(\mathbf{P})$ is strongly connected and $\mathbf{P}$ is irreducible (Theorem 19.2.5).

Eigenvalues. Since $\mathbf{P}\mathbf{e}_j = \mathbf{e}_{\sigma(j)}$ and $\sigma^{n}$ is the identity, $\mathbf{P}^{n}\mathbf{e}_j = \mathbf{e}_j$ for every $j$ , so $\mathbf{P}^{n} = \mathbf{I}$ . If $\mathbf{P}\mathbf{z} = \lambda\mathbf{z}$ with $\mathbf{z} \ne \mathbf{0}$ , then $\mathbf{z} = \mathbf{P}^{n}\mathbf{z} = \lambda^{n}\mathbf{z}$ , so $\lambda^{n} = 1$ and $\lvert\lambda\rvert = 1$ . Hence $\rho(\mathbf{P}) = 1$ and every eigenvalue is peripheral. By Theorem 19.5.4, $h = n$ , so the peripheral eigenvalues are the $n$ numbers $1, \omega, \dots, \omega^{n-1}$ , $\omega = e^{2\pi i/n}$ , each algebraically simple. That accounts for all $n$ eigenvalues, and $p_{\mathbf{P}} = (x - 1)(x - \omega)\cdots(x - \omega^{n-1}) = x^{n} - 1$ , the last equality because both sides are monic of degree $n$ with the same $n$ distinct roots.

Powers. $\mathbf{P}^{n} = \mathbf{I}$ , so the sequence $\mathbf{P}, \mathbf{P}^{2}, \dots$ repeats with period $n$ , and $\mathbf{P}^{m}$ runs through $n$ distinct permutation matrices. A sequence that returns to each of two different matrices infinitely often has no limit, so $\mathbf{P}^{m}$ does not converge. Starting a chain at $\mathbf{e}_1$ , $\mathbf{P}^{m}\mathbf{e}_1$ runs round $\mathbf{e}_1, \mathbf{e}_2, \dots, \mathbf{e}_n, \mathbf{e}_1, \dots$ forever, although $\mathbf{P}$ has the steady state $\frac1n\mathbf{1}$ .

For $n = 2$ this is exactly the warning in Chapter 9 §11: the swap has the eigenvalue $-1 = e^{2\pi i/2}$ , and Chapter 10 §10 identified an eigenvalue of modulus $1$ other than $1$ as the only obstruction to convergence (Corollary 10.10.5). We now know where that eigenvalue comes from. It is forced by the period: every closed walk has even length. §06 shows that the chain still settles down on average.

19.5.6. How large a power is needed

The definition of primitivity asks for some $\mathbf{A}^{k} > 0$ but gives no bound on $k$ , so a direct check might seem to require computing powers without end. By Lemma 19.2.1 (a), the zero pattern of $\mathbf{A}^{m}$ depends only on the zero pattern of $\mathbf{A}$ , and there are finitely many patterns, so in principle the question is finite. The sharp answer is classical.

Theorem 19.5.6 (Wielandt’s Bound)

If $\mathbf{A} \in M_n(\mathbb{R})$ is primitive, then $\mathbf{A}^{(n-1)^{2}+1} > 0$ . The bound cannot be improved: for $n \ge 2$ the matrix $\mathbf{W}_n$ with ones at the positions $(i, i+1)$ for $i < n$ and at $(n, 1)$ and $(n, 2)$ , and zeros elsewhere, is primitive and $\mathbf{W}_n^{(n-1)^{2}}$ has a zero entry.

This theorem is due to H. Wielandt (1950). We state it without proof; the proof is a careful count of walk lengths, and nothing in this book depends on it. The matrix $\mathbf{W}_3$ is the matrix $\mathbf{W}$ of the examples, where we saw that $\mathbf{W}^{4}$ has a zero at position $(1, 1)$ and $\mathbf{W}^{5} > 0$ ; here $(n-1)^{2} + 1 = 5$ . In the walks: a closed walk at $1$ must leave by $1 \to 3$ and return by $2 \to 1$ , so it is made of $3$ -cycles $1 \to 3 \to 2 \to 1$ and detours round $3 \to 2 \to 3$ , and its length $3 + 3a + 2b$ , with $a, b \ge 0$ , is never $4$ . For $n = 4$ the bound is $10$ , and $\mathbf{W}_4^{9}$ is not positive while $\mathbf{W}_4^{10}$ is.

Remark. The bound is quadratic in $n$ , not $n - 1$ as for $(\mathbf{I} + \mathbf{A})^{n-1}$ in Theorem 19.2.6. Adding $\mathbf{I}$ puts a loop at every vertex, which lets walks wait; a primitive matrix may have no such loops, and then the walks must make up lengths from long cycles, as $\mathbf{W}_n$ does with its cycles of lengths $n$ and $n - 1$ .

19.5.7. Exercises

A. Check your understanding

Exercise (A1)

(a) Define a primitive matrix, and state the limit theorem for primitive matrices.
(b) True or false: every primitive matrix is irreducible. Justify your answer.
(c) True or false: every irreducible non-negative matrix is primitive. Justify your answer.
(d) True or false: if $\mathbf{A} \ge 0$ is irreducible and $a_{11} > 0$ , then $\mathbf{A}$ is primitive. Justify your answer.
(e) An irreducible $\mathbf{A} \ge 0$ has $\rho(\mathbf{A}) = 2$ and period $4$ . Which of its eigenvalues can you name without further information?
(f) Name the two ingredients from earlier chapters that the proof of Theorem 19.5.2 combines.

Solution.

(a) $\mathbf{A} \in M_n(\mathbb{R})$ , $\mathbf{A} \ge 0$ , is primitive if $\mathbf{A}^{k} > 0$ for some $k \ge 1$ (Definition 19.5.1). Theorem 19.5.2: if $\mathbf{A}$ is primitive with $\rho = \rho(\mathbf{A})$ , and $\mathbf{v} > \mathbf{0}$ , $\mathbf{w} > \mathbf{0}$ satisfy $\mathbf{A}\mathbf{v} = \rho\mathbf{v}$ and $\mathbf{w}^{\top}\mathbf{A} = \rho\mathbf{w}^{\top}$ , then $(\mathbf{A}/\rho)^{m} \to \mathbf{v}\mathbf{w}^{\top}/(\mathbf{w}^{\top}\mathbf{v})$ entrywise.
(b) True, by Proposition 19.5.1 (b).
(c) False. The swap $\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ is irreducible, but each of its powers is $\mathbf{I}$ or the swap, and both have zero entries.
(d) True, by Corollary 19.5.5: the loop $1 \to 1$ is a closed walk of length $1$ , so the period is $1$ . (If $n = 1$ , then $\mathbf{A} = (a_{11})$ with $a_{11} > 0$ is primitive directly.)
(e) By Theorem 19.5.4, $h = 4$ , so the eigenvalues of modulus $2$ are $2, 2i, -2, -2i$ , each algebraically simple. The others cannot be named, but they come in orbits of multiplication by $i$ , by part (b) of that theorem.
(f) The Jordan-form convergence criterion of Chapter 10 §10 (Theorem 10.10.4), which gives convergence of $(\mathbf{A}/\rho)^{m}$ ; and the Perron–Frobenius theorem (Theorem 19.3.2), which gives the simple eigenvalue $\rho$ and the positive vectors $\mathbf{v}, \mathbf{w}$ that identify the limit.

B. Practice

Exercise (B1: Which are primitive?)

Determine which of the following matrices are primitive. Justify your answer.

(a) $\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}$ .
(b) $\begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}$ .
(c) $\begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}$ .
(d) $\begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix}$ .

Solution.

(a) Primitive: its square is $\begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix} > 0$ .
(b) Not primitive. It is the cyclic permutation matrix of Example (The Cyclic Permutation) with $n = 3$ (columns $\mathbf{e}_3, \mathbf{e}_1, \mathbf{e}_2$ , the same shift run the other way), and every power of a permutation matrix is a permutation matrix (Lemma 3.4.7), which has zero entries.
(c) Not primitive. The positive entries are at $(1,2), (2,1), (2,3), (3,2)$ , so the edges of $G(\mathbf{A})$ are $1 \to 2$ , $2 \to 1$ , $2 \to 3$ and $3 \to 2$ , and every edge joins vertex $2$ to the set $\{1, 3\}$ . A closed walk therefore has even length, and $1 \to 2 \to 1$ has length $2$ : the matrix has period $2$ . It is irreducible, since every vertex reaches every other through $2$ , so $G(\mathbf{A})$ is strongly connected (Theorem 19.2.5). By Corollary 19.5.5 it is not primitive. (Directly: $\mathbf{A}^{m}$ has zero $(1,2)$ -entry for even $m$ and zero $(1,1)$ -entry for odd $m$ .)
(d) Not primitive. The positive entries sit at positions $(i, j)$ with $i \le j$ , so every edge $j \to i$ has $i \le j$ , vertex numbers never increase along a walk, and there is no walk from $1$ to $2$ . By Lemma 19.2.1 (a), the $(2,1)$ -entry of every power is $0$ .

Exercise (B2: A limit without diagonalizing)

Let $\mathbf{A} = \begin{pmatrix} 0 & 0 & 1 \\ 2 & 0 & 1 \\ 2 & 1 & 0 \end{pmatrix}$ .

(a) Show that $\mathbf{A}$ is primitive.
(b) Show that $p_{\mathbf{A}} = (x - 2)(x + 1)^{2}$ , and that $\mathbf{A}$ is not diagonalizable.
(c) Find positive right and left eigenvectors for $\rho(\mathbf{A})$ , and hence $\lim_m (\mathbf{A}/2)^{m}$ .

Solution.

(a) Compute $\mathbf{A}^{2} = \begin{pmatrix} 2 & 1 & 0 \\ 2 & 1 & 2 \\ 2 & 0 & 3 \end{pmatrix}, \qquad \mathbf{A}^{4} = (\mathbf{A}^{2})^{2} = \begin{pmatrix} 6 & 3 & 2 \\ 10 & 3 & 8 \\ 10 & 2 & 9 \end{pmatrix} > 0 .$ So $\mathbf{A}$ is primitive.
(b) Here $x\mathbf{I} - \mathbf{A} = \begin{pmatrix} x & 0 & -1 \\ -2 & x & -1 \\ -2 & -1 & x \end{pmatrix}$ , and expansion along the first row gives $\begin{aligned} p_{\mathbf{A}} &= x\bigl(x^{2} - 1\bigr) + (-1)\bigl((-2)(-1) - x(-2)\bigr) \\ &= x^{3} - x - 2 - 2x = x^{3} - 3x - 2 . \end{aligned}$ Since $(x - 2)(x + 1)^{2} = (x - 2)(x^{2} + 2x + 1) = x^{3} - 3x - 2$ , this is the claimed factorization. For $\lambda = -1$ , $\mathbf{A} + \mathbf{I} = \begin{pmatrix} 1 & 0 & 1 \\ 2 & 1 & 1 \\ 2 & 1 & 1 \end{pmatrix}$ has rank $2$ (rows 2 and 3 agree, rows 1 and 2 are independent), so $g_{\mathbf{A}}(-1) = 1 < 2 = a_{\mathbf{A}}(-1)$ , and $\mathbf{A}$ is not diagonalizable.
(c) $\mathbf{A} - 2\mathbf{I} = \begin{pmatrix} -2 & 0 & 1 \\ 2 & -2 & 1 \\ 2 & 1 & -2 \end{pmatrix}$ : the first row gives $v_3 = 2v_1$ , and then the second gives $2v_1 - 2v_2 + 2v_1 = 0$ , so $v_2 = 2v_1$ . Take $\mathbf{v} = (1, 2, 2)$ ; check: $\mathbf{A}\mathbf{v} = (2, 4, 4)$ . For the left vector, $\mathbf{A}^{\top} - 2\mathbf{I} = \begin{pmatrix} -2 & 2 & 2 \\ 0 & -2 & 1 \\ 1 & 1 & -2 \end{pmatrix}$ : the second row gives $w_3 = 2w_2$ , and the first gives $w_1 = w_2 + w_3 = 3w_2$ . Take $\mathbf{w} = (3, 1, 2)$ ; check: $\mathbf{w}^{\top}\mathbf{A} = (0 + 2 + 4,\ 0 + 0 + 2,\ 3 + 1 + 0) = (6, 2, 4) = 2\mathbf{w}^{\top}$ . Then $\mathbf{w}^{\top}\mathbf{v} = 3 + 2 + 4 = 9$ , and by Theorem 19.5.2 $\Big(\frac12\mathbf{A}\Big)^{m} \longrightarrow \frac19\begin{pmatrix} 1 \\ 2 \\ 2 \end{pmatrix}\begin{pmatrix} 3 & 1 & 2 \end{pmatrix} = \frac19\begin{pmatrix} 3 & 1 & 2 \\ 6 & 2 & 4 \\ 6 & 2 & 4 \end{pmatrix} .$ Part (b) shows that Chapter 9’s diagonalization method is unavailable here; the theorem does not need it.

Exercise (B3: Period and peripheral eigenvalues)

Let $\mathbf{A} = \begin{pmatrix} 0 & 1 & 0 \\ 2 & 0 & 2 \\ 0 & 1 & 0 \end{pmatrix}$ .

(a) Show that $\mathbf{A}$ is irreducible with period $2$ .
(b) Use Theorem 19.5.4 to predict the eigenvalues of modulus $\rho(\mathbf{A})$ in terms of $\rho(\mathbf{A})$ , then compute $p_{\mathbf{A}}$ and confirm.
(c) Hence explain why $(\mathbf{A}/\rho(\mathbf{A}))^{m}$ does not converge.

Solution.

(a) The positive entries are at $(1,2), (2,1), (2,3), (3,2)$ , the same pattern as in B1(c), so the argument there applies: $\mathbf{A}$ is irreducible with period $2$ .
(b) With $h = 2$ and $\omega = -1$ , the peripheral eigenvalues are $\rho$ and $-\rho$ , and the spectrum is symmetric under $\lambda \mapsto -\lambda$ . Expanding along the first row, $p_{\mathbf{A}} = \det\begin{pmatrix} x & -1 & 0 \\ -2 & x & -2 \\ 0 & -1 & x \end{pmatrix} = x(x^{2} - 2) + 1\cdot(-2x) = x(x - 2)(x + 2) .$ So $\rho = 2$ , the peripheral eigenvalues are $\pm 2$ , and the remaining eigenvalue $0$ is its own negative, as predicted.
(c) The vector $\mathbf{z} = (1, -2, 1)$ satisfies $\mathbf{A}\mathbf{z} = (-2, 4, -2) = -2\mathbf{z}$ , so $\mathbf{A}/2$ has the eigenvalue $-1$ . By Theorem 10.10.4, the powers of a matrix with an eigenvalue of modulus $1$ other than $1$ do not converge. Concretely, $(\mathbf{A}/2)^{m}\mathbf{z} = (-1)^{m}\mathbf{z}$ alternates in sign.

C. Going deeper

Exercise (C1: Shifting by the identity)

Let $\mathbf{A} \in M_n(\mathbb{R})$ , $\mathbf{A} \ge 0$ , be irreducible, with right and left Perron vectors $\mathbf{v}, \mathbf{w}$ , and let $t > 0$ .

(a) Prove that $\mathbf{A} + t\mathbf{I}$ is primitive, with $\rho(\mathbf{A} + t\mathbf{I}) = \rho(\mathbf{A}) + t$ and the same Perron vectors $\mathbf{v}, \mathbf{w}$ .
(b) Deduce that $\bigl((\mathbf{A} + t\mathbf{I})/(\rho(\mathbf{A}) + t)\bigr)^{m} \to \mathbf{v}\mathbf{w}^{\top}/(\mathbf{w}^{\top}\mathbf{v})$ , and apply this to the swap with $t = 1$ .

Solution.

(a) $\mathbf{A} + t\mathbf{I} \ge 0$ has the same off-diagonal pattern as $\mathbf{A}$ , so $(\mathbf{I} + \mathbf{A} + t\mathbf{I})^{n-1} \ge (\mathbf{I} + \mathbf{A})^{n-1} > 0$ entrywise, since each product of non-negative matrices can only grow when an entry grows; so $\mathbf{A} + t\mathbf{I}$ is irreducible (Theorem 19.2.6). Its diagonal entries are $\ge t > 0$ , so it is primitive by Corollary 19.5.5. By Theorem 9.10.1 with $q = x + t$ , its eigenvalues are $\lambda + t$ , $\lambda \in \operatorname{spec}(\mathbf{A})$ , and $\lvert\lambda + t\rvert \le \lvert\lambda\rvert + t \le \rho(\mathbf{A}) + t$ by Theorem 0.6.4, with $\rho(\mathbf{A}) + t$ itself an eigenvalue, since $\rho(\mathbf{A}) \in \operatorname{spec}(\mathbf{A})$ . So $\rho(\mathbf{A} + t\mathbf{I}) = \rho(\mathbf{A}) + t$ . Finally $(\mathbf{A} + t\mathbf{I})\mathbf{v} = (\rho(\mathbf{A}) + t)\mathbf{v}$ and $\mathbf{w}^{\top}(\mathbf{A} + t\mathbf{I}) = (\rho(\mathbf{A}) + t)\mathbf{w}^{\top}$ , with $\mathbf{v}, \mathbf{w} > \mathbf{0}$ .
(b) By (a) and Theorem 19.5.2 applied to $\mathbf{A} + t\mathbf{I}$ . For the swap $\mathbf{S}$ , $\rho = 1$ , and $\mathbf{1}$ is a positive right and left eigenvector, so the limit is $\mathbf{1}\mathbf{1}^{\top}/(\mathbf{1}^{\top}\mathbf{1}) = \mathbf{1}\mathbf{1}^{\top}/2$ . Directly, $(\mathbf{S} + \mathbf{I})/2 = \frac12\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}$ , whose powers are all equal to itself, in agreement.

Exercise (C2: Traces detect the period)

Let $\mathbf{A} \ge 0$ be irreducible, not the $1 \times 1$ zero matrix, with period $h$ .

(a) Prove that $\operatorname{tr}(\mathbf{A}^{m}) = 0$ for every $m \ge 1$ that is not a multiple of $h$ , in two ways: from Theorem 19.5.4 (b), and from Lemma 19.2.1 (a).
(b) Deduce that if $\operatorname{tr}(\mathbf{A}^{2}) > 0$ and $\operatorname{tr}(\mathbf{A}^{3}) > 0$ , then $\mathbf{A}$ is primitive.
(c) Check (b) on the matrix $\mathbf{W}$ of the examples.

Solution.

(a) Spectrum. Let $\omega = e^{2\pi i/h}$ and $p_{\mathbf{A}} = \prod_i(x - \lambda_i)$ . By Theorem 19.5.4 (c), the period $h$ is also the number of peripheral eigenvalues, so part (b) of that theorem applies with this $\omega$ . By Corollary 9.10.2, applied over $\mathbb{C}$ , $\operatorname{tr}(\mathbf{A}^{m}) = \sum_i\lambda_i^{m}$ . By Theorem 19.5.4 (b), the list $\omega\lambda_1, \dots, \omega\lambda_n$ is a rearrangement of $\lambda_1, \dots, \lambda_n$ , so $\sum_i\lambda_i^{m} = \sum_i(\omega\lambda_i)^{m} = \omega^{m}\sum_i\lambda_i^{m}$ . If $h \nmid m$ , then $\omega^{m} \ne 1$ (Example (Roots of Unity)), so $\operatorname{tr}(\mathbf{A}^{m}) = 0$ .
Walks. $\operatorname{tr}(\mathbf{A}^{m}) = \sum_i(\mathbf{A}^{m})_{ii}$ is a sum of non-negative terms, positive exactly when some $(\mathbf{A}^{m})_{ii} > 0$ , that is, by Lemma 19.2.1 (a), when there is a closed walk of length $m$ . Every closed walk has length a multiple of the period, so for $h \nmid m$ the trace is $0$ .
(b) By (a), $h \mid 2$ and $h \mid 3$ , so $h = 1$ , and $\mathbf{A}$ is primitive by Corollary 19.5.5.
(c) $\mathbf{W}^{2} = \begin{pmatrix} 0 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix}$ has trace $2$ , and $\mathbf{W}^{3} = \begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix}$ has trace $3$ ; so $\mathbf{W}$ is primitive, as found directly.

Exercise (C3: A finite test for primitivity)

Let $\mathbf{A} \in M_n(\mathbb{R})$ , $\mathbf{A} \ge 0$ , and let $\mathbf{Z}_m$ be the zero pattern of $\mathbf{A}^{m}$ : the $0/1$ matrix with a $1$ exactly where $\mathbf{A}^{m}$ is positive.

(a) Prove that $\mathbf{Z}_{m+1}$ is determined by $\mathbf{Z}_m$ and $\mathbf{Z}_1$ .
(b) Deduce that if $\mathbf{Z}_a = \mathbf{Z}_b$ with $a < b$ , then $\mathbf{Z}_{a+j} = \mathbf{Z}_{b+j}$ for every $j \ge 0$ .
(c) Prove that if $\mathbf{A}$ is primitive, then $\mathbf{A}^{k} > 0$ for some $k \le 2^{n^{2}}$ . Compare with Theorem 19.5.6.

Hint: there are only $2^{n^{2}}$ zero patterns; use Proposition 19.5.1 (a).

Solution.

(a) $(\mathbf{A}^{m+1})_{ij} = \sum_l(\mathbf{A}^{m})_{il}a_{lj}$ is a sum of non-negative terms, positive exactly when some $l$ has $(\mathbf{A}^{m})_{il} > 0$ and $a_{lj} > 0$ . So $(\mathbf{Z}_{m+1})_{ij} = 1$ if and only if $(\mathbf{Z}_m)_{il} = (\mathbf{Z}_1)_{lj} = 1$ for some $l$ , which depends only on $\mathbf{Z}_m$ and $\mathbf{Z}_1$ .
(b) By induction on $j$ : the case $j = 0$ is the hypothesis, and if $\mathbf{Z}_{a+j} = \mathbf{Z}_{b+j}$ , then (a) applied to both gives $\mathbf{Z}_{a+j+1} = \mathbf{Z}_{b+j+1}$ .
(c) Among $\mathbf{Z}_1, \dots, \mathbf{Z}_{N+1}$ , $N = 2^{n^{2}}$ , two agree, say $\mathbf{Z}_a = \mathbf{Z}_b$ with $a < b \le N + 1$ , so $a \le N$ . By (b), $\mathbf{Z}_{a + q(b-a)} = \mathbf{Z}_a$ for every $q \ge 0$ , by induction on $q$ . If $\mathbf{A}^{k} > 0$ , then by Proposition 19.5.1 (a) $\mathbf{A}^{m} > 0$ for all $m \ge k$ ; choosing $q$ with $a + q(b - a) \ge k$ shows that $\mathbf{Z}_a$ is the all-ones pattern, so $\mathbf{A}^{a} > 0$ with $a \le 2^{n^{2}}$ . Wielandt’s bound $(n-1)^{2} + 1$ is enormously smaller: for $n = 3$ it is $5$ against $512$ .