19.3 The Perron–Frobenius Theorem

Section 1 proved Perron’s theorem (Theorem 19.1.5): a matrix with every entry positive has its spectral radius as a simple eigenvalue, with an eigenvector whose entries are all positive. That hypothesis is rarely met in practice. A Markov chain whose states can only step to their neighbors has a transition matrix full of zeros, and so does the matrix of almost any network. This section asks which of Perron’s conclusions survive when zeros are allowed. There are two answers. For every nonnegative matrix, the spectral radius is still an eigenvalue with a nonnegative eigenvector, and of Perron’s conclusions nothing more survives. For an irreducible matrix, in the sense of Section 2, every conclusion survives except one: other eigenvalues may reach the spectral radius in modulus. The positivity of the spectral radius also needs $n \ge 2$ , because the $1 \times 1$ zero matrix counts as irreducible.

Throughout, matrices have real entries, and $\mathbf{A} \ge \mathbf{O}$ , $\mathbf{A} > \mathbf{O}$ , $\mathbf{x} \ge \mathbf{0}$ and $\mathbf{x} > \mathbf{0}$ are the entrywise order of Section 1. The spectrum is read in $\mathbb{C}$ , as in Definition 16.4.1, so $\rho(\mathbf{A})$ is the largest modulus of a complex eigenvalue. We write $\mathbf{J}$ for the $n \times n$ matrix with every entry $1$ , and $\mathbf{1}$ for the all-ones vector.

19.3.1. What survives for every nonnegative matrix

Start with the weakest hypothesis, $\mathbf{A} \ge \mathbf{O}$ , and see what can be rescued. Three small matrices show at once that most of Perron’s theorem is lost.

Example (Three nonnegative matrices that break Perron’s theorem)

For each matrix, find $\rho$ , its algebraic multiplicity, and all the nonnegative eigenvectors, and say which conclusion of Theorem 19.1.5 fails: $\mathbf{N} = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}, \qquad \mathbf{A}_c = \begin{pmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & c \end{pmatrix} \quad\text{with } c = 2 \text{ and with } c = 1 .$

Solution. The nilpotent matrix. $\mathbf{N}$ is upper triangular with zero diagonal, so its only eigenvalue is $0$ , with algebraic multiplicity $2$ (Theorem 9.7.4 (b)), and $\rho(\mathbf{N}) = 0$ . The eigenvectors are the nonzero solutions of $\mathbf{N}\mathbf{x} = \mathbf{0}$ , that is, of $x_2 = 0$ : the nonzero multiples of $\mathbf{e}_1$ . So $\rho = 0$ is not positive, it is not simple, and no eigenvector is positive. What does survive is that $\rho(\mathbf{N}) = 0$ is an eigenvalue with the nonnegative eigenvector $\mathbf{e}_1$ .

The block matrix. $\mathbf{A}_c$ is block diagonal, with the $2 \times 2$ block $\begin{psmallmatrix} 1 & 1 \\ 1 & 1 \end{psmallmatrix}$ and the $1 \times 1$ block $(c)$ . The $2 \times 2$ block has trace $2$ and determinant $0$ , so its eigenvalues are $2$ and $0$ , with eigenvectors $(1, 1)$ and $(1, -1)$ . Hence $p_{\mathbf{A}_c}(t) = t(t - 2)(t - c)$ , and the eigenvectors of $\mathbf{A}_c$ are built from those of the blocks: $(1, 1, 0)$ for $2$ , $(1, -1, 0)$ for $0$ , and $\mathbf{e}_3$ for $c$ .

For $c = 2$ : $\rho = 2$ has algebraic multiplicity $2$ . Its eigenspace is spanned by $(1, 1, 0)$ and $\mathbf{e}_3$ , which are nonnegative and not proportional, so the nonnegative eigenvector is not unique up to scale. (It does contain the positive vector $(1, 1, 1)$ , their sum.)

For $c = 1$ : $\rho = 2$ is simple, but its eigenvectors are the multiples of $(1, 1, 0)$ , none of them positive. And $\mathbf{e}_3 \ge \mathbf{0}$ is an eigenvector for the eigenvalue $1 < \rho$ : a nonnegative eigenvector for a smaller eigenvalue, which Theorem 19.1.5 rules out for positive matrices.

In each case $\rho$ was still an eigenvalue with a nonnegative eigenvector. That is the part that survives in general, and of Perron’s conclusions it is all that survives. The proof is the first real use in the book of a limiting auxiliary matrix with a nonnegative matrix in the limit. Perron’s theorem applies to $\mathbf{A} + \varepsilon\mathbf{J}$ , which is positive for every $\varepsilon > 0$ ; let $\varepsilon \to 0^{+}$ and keep whatever passes to the limit.

Theorem 19.3.1 (The Spectral Radius of a Nonnegative Matrix Is an Eigenvalue)

Let $\mathbf{A} \in M_n(\mathbb{R})$ with $n \ge 1$ and $\mathbf{A} \ge \mathbf{O}$ . Then $\rho(\mathbf{A})$ is an eigenvalue of $\mathbf{A}$ , and there is a vector $\mathbf{x} \in \mathbb{R}^n$ with $\mathbf{x} \ge \mathbf{0}$ , $\mathbf{x} \neq \mathbf{0}$ and $\mathbf{A}\mathbf{x} = \rho(\mathbf{A})\mathbf{x}$ .

Idea. ① Perturb: $\mathbf{A}_k = \mathbf{A} + \frac1k\mathbf{J}$ is positive, so Theorem 19.1.5 gives it an eigenvalue $\rho(\mathbf{A}_k)$ with a positive eigenvector $\mathbf{v}_k$ , which we scale into the simplex $\Delta_n$ . ② The matrices $\mathbf{A}_k$ decrease as $k$ grows, so by monotonicity the numbers $\rho(\mathbf{A}_k)$ decrease and stay $\ge \rho(\mathbf{A})$ ; by monotone convergence they have a limit $r \ge \rho(\mathbf{A})$ . ③ The $\mathbf{v}_k$ need not converge, but they live in a closed bounded set, so a subsequence does. ④ Pass to the limit in $\mathbf{A}_k\mathbf{v}_k = \rho(\mathbf{A}_k)\mathbf{v}_k$ : the limit equation makes $r$ an eigenvalue of $\mathbf{A}$ , so $r \le \rho(\mathbf{A})$ , and $r = \rho(\mathbf{A})$ . The scaling into $\Delta_n$ is what stops the limit vector from being $\mathbf{0}$ : its entries still add up to $1$ .

Proof. Let $\rho = \rho(\mathbf{A})$ , and for each integer $k \ge 1$ put $\mathbf{A}_k = \mathbf{A} + \frac1k\mathbf{J}$ . Every entry of $\mathbf{A}_k$ is at least $\frac1k > 0$ , so $\mathbf{A}_k > \mathbf{O}$ . By Theorem 19.1.5, $\rho_k \mathrel{:=} \rho(\mathbf{A}_k)$ is an eigenvalue of $\mathbf{A}_k$ with an eigenvector $\mathbf{v}_k > \mathbf{0}$ . Dividing $\mathbf{v}_k$ by the sum of its entries, which is positive, we may assume $\mathbf{v}_k \in \Delta_n$ (Definition 18.1.2).

Step 1: $\rho_k$ converges to some $r \ge \rho$ . Since $\frac{1}{k+1} < \frac1k$ and $\mathbf{J} \ge \mathbf{O}$ , we have $\mathbf{O} \le \mathbf{A} \le \mathbf{A}_{k+1} \le \mathbf{A}_k$ entrywise for every $k$ . By Proposition 19.1.4 (a), applied to each of these two inequalities, $\rho \le \rho_{k+1} \le \rho_k$ . So the sequence $(-\rho_k)$ is increasing and bounded above by $-\rho$ . By monotone convergence, fact (A2) of Chapter 16’s introduction, it converges to its least upper bound, which is $\le -\rho$ because $-\rho$ is an upper bound. Hence $\rho_k \to r$ for some real number $r \ge \rho$ .

Step 2: a convergent subsequence. The set $\Delta_n$ is bounded, since every entry of a point of $\Delta_n$ lies in $[0, 1]$ . It is closed: if points of $\Delta_n$ converge to $\mathbf{v}$ , then each entry of $\mathbf{v}$ is a limit of numbers $\ge 0$ , hence $\ge 0$ , and the entries of $\mathbf{v}$ add up to a limit of sums equal to $1$ . By the compactness of closed bounded sets, fact (A3) of Chapter 16’s introduction, the sequence $(\mathbf{v}_k)$ has a subsequence $(\mathbf{v}_{k_j})$ converging to some $\mathbf{v} \in \Delta_n$ . In particular $\mathbf{v} \ge \mathbf{0}$ , and $\mathbf{v} \ne \mathbf{0}$ because its entries add up to $1$ .

Step 3: the limit. For every $j$ we have $\mathbf{A}_{k_j}\mathbf{v}_{k_j} = \rho_{k_j}\mathbf{v}_{k_j}$ . Convergence in the Euclidean norm is entrywise convergence (Corollary 16.2.4), and $\mathbf{A}_{k_j} \to \mathbf{A}$ entrywise. Each entry of $\mathbf{A}_{k_j}\mathbf{v}_{k_j}$ is a sum of products of entries of $\mathbf{A}_{k_j}$ and of $\mathbf{v}_{k_j}$ , so by the algebra of limits it converges to the corresponding entry of $\mathbf{A}\mathbf{v}$ ; likewise $\rho_{k_j} \to r$ by Step 1, since a subsequence of a convergent sequence has the same limit, and so $\rho_{k_j}\mathbf{v}_{k_j} \to r\mathbf{v}$ . Limits are unique, so $\mathbf{A}\mathbf{v} = r\mathbf{v}$ with $\mathbf{v} \ne \mathbf{0}$ ; $r$ is an eigenvalue of $\mathbf{A}$ , hence $r \le \rho$ by Definition 16.4.1; with $r \ge \rho$ , $r = \rho$ . So $\mathbf{A}\mathbf{v} = \rho\mathbf{v}$ , and $\mathbf{v} \ge \mathbf{0}$ is the required eigenvector. This proves the theorem.

Two imported facts were used, both named where they act: (A2) in Step 1 and (A3) in Step 2. No statement about the roots of polynomials is needed.

Remark. Alternatively, $\rho_k \to \rho$ also follows from the continuity of eigenvalues proved in Chapter 16 §07, but that rests on a theorem about the roots of polynomials which Chapter 16 quotes without proof; the route above needs nothing of the kind.

The theorem is sharp, in the sense that each of Perron’s further conclusions fails for some nonnegative matrix. Example (Three nonnegative matrices that break Perron’s theorem) shows that $\rho$ can be $0$ , it can be a repeated eigenvalue, the nonnegative eigenvector can fail to be positive or unique, and another eigenvalue can have a nonnegative eigenvector; and the swap matrix below shows that another eigenvalue can reach $\lvert \lambda \rvert = \rho$ . The positive conclusions of Theorem 19.1.5 are strict statements — an entry is $> 0$ , a multiplicity is $1$ , an inequality $\lvert \lambda \rvert < \rho$ is strict — and strict inequalities do not survive limits. Positive numbers can tend to $0$ ; two simple eigenvalues can merge.

Warning. A nonnegative eigenvector does not identify $\rho$ for a general nonnegative matrix. In $\mathbf{A}_1$ of Example (Three nonnegative matrices that break Perron’s theorem) the vector $\mathbf{e}_3 \ge \mathbf{0}$ is an eigenvector, but its eigenvalue is $1$ , while $\rho(\mathbf{A}_1) = 2$ . To find $\rho$ from an eigenvector, you need either irreducibility (next subsection) or a positive eigenvector, which Exercise C1 at the end of this section shows is enough.

19.3.2. The theorem for irreducible matrices

What goes wrong in Example (Three nonnegative matrices that break Perron’s theorem) is visible in the zero pattern: $\mathbf{A}_c$ splits into two blocks that do not talk to each other, and $\mathbf{N}$ passes mass from one coordinate to the other but never back. Section 2 made “every coordinate eventually talks to every other” precise. A nonnegative matrix is irreducible (Definition 19.2.3) when no simultaneous permutation of its rows and columns brings it to block upper triangular form, and by Theorem 19.2.6 this happens exactly when $(\mathbf{I} + \mathbf{A})^{n-1} > \mathbf{O}$ . That criterion is the bridge we need: it turns an irreducible matrix into a positive one, to which Theorem 19.1.5 applies.

Theorem 19.3.2 (Perron–Frobenius Theorem)

Let $\mathbf{A} \in M_n(\mathbb{R})$ with $n \ge 1$ be nonnegative and irreducible, and put $\rho = \rho(\mathbf{A})$ . Then:

(a) $\rho$ is an eigenvalue of $\mathbf{A}$ with an eigenvector $\mathbf{v} > \mathbf{0}$ ;
(b) $\rho$ is algebraically simple: $a_{\mathbf{A}}(\rho) = 1$ ;
(c) every nonnegative eigenvector of $\mathbf{A}$ , for any eigenvalue, is a positive multiple of $\mathbf{v}$ ; in particular its eigenvalue is $\rho$ , and the nonnegative eigenvector is unique up to scale;
(d) if $n \ge 2$ , then $\rho > 0$ .

Idea. There are two ways to reach a positive matrix, and we take the one that keeps strict information. The perturbation $\mathbf{A} + \varepsilon\mathbf{J}$ of the last proof needs a limit, and a limit cannot certify strict conclusions; Exercise C2 at the end of this section shows them lost when the limit matrix is reducible. So instead we use $\mathbf{B} = (\mathbf{I} + \mathbf{A})^{n-1}$ , which is positive by Theorem 19.2.6 and needs no limit. Step roadmap:

① Theorem 19.3.1 gives $\mathbf{A}\mathbf{x} = \rho\mathbf{x}$ with $\mathbf{x} \ge \mathbf{0}$ , $\mathbf{x} \ne \mathbf{0}$ .

② $\mathbf{B}\mathbf{x} = (1 + \rho)^{n-1}\mathbf{x}$ , and a positive matrix times a nonzero nonnegative vector is positive; so $\mathbf{x} > \mathbf{0}$ .

③ Every eigenvector of $\mathbf{A}$ is an eigenvector of $\mathbf{B} = q(\mathbf{A})$ , and the Spectral Mapping Theorem transports multiplicities. So a nonnegative eigenvector of $\mathbf{A}$ , or a repeated $\rho$ , would be a nonnegative eigenvector of $\mathbf{B}$ , or a repeated $\rho(\mathbf{B})$ — both of which Theorem 19.1.5 controls.

④ If $\rho = 0$ , then $\mathbf{A}\mathbf{x} = \mathbf{0}$ with $\mathbf{x} > \mathbf{0}$ forces $\mathbf{A} = \mathbf{O}$ , which is not irreducible for $n \ge 2$ .

Proof. Let $q(t) = (1 + t)^{n-1}$ and $\mathbf{B} = q(\mathbf{A}) = (\mathbf{I} + \mathbf{A})^{n-1}$ . Since $\mathbf{A}$ is irreducible, $\mathbf{B} > \mathbf{O}$ by Theorem 19.2.6.

Step 1: an eigenvector $\mathbf{v} > \mathbf{0}$ for $\rho$ . By Theorem 19.3.1 there is $\mathbf{x} \ge \mathbf{0}$ , $\mathbf{x} \ne \mathbf{0}$ , with $\mathbf{A}\mathbf{x} = \rho\mathbf{x}$ . Then $(\mathbf{I} + \mathbf{A})\mathbf{x} = (1 + \rho)\mathbf{x}$ , and applying this $n - 1$ times gives $\mathbf{B}\mathbf{x} = (1 + \rho)^{n-1}\mathbf{x}$ . Choose $j_0$ with $x_{j_0} > 0$ , possible because $\mathbf{x} \ge \mathbf{0}$ and $\mathbf{x} \ne \mathbf{0}$ . For every $i$ , $(\mathbf{B}\mathbf{x})_i = \sum_{j=1}^{n} b_{ij}x_j \ge b_{ij_0}x_{j_0} > 0 ,$ since every term is $\ge 0$ and $b_{ij_0} > 0$ . So $\mathbf{B}\mathbf{x} > \mathbf{0}$ . As $1 + \rho \ge 1$ , we may divide: $\mathbf{x} = (1 + \rho)^{-(n-1)}\mathbf{B}\mathbf{x} > \mathbf{0}$ . Put $\mathbf{v} = \mathbf{x}$ . This proves (a).

Step 2: eigenvectors of $\mathbf{A}$ are eigenvectors of $\mathbf{B}$ . If $\mathbf{A}\mathbf{y} = \mu\mathbf{y}$ with $\mathbf{y} \ne \mathbf{0}$ , then, exactly as in Step 1, $\mathbf{B}\mathbf{y} = q(\mu)\mathbf{y}$ . In particular $\mathbf{B}\mathbf{v} = q(\rho)\mathbf{v}$ with $\mathbf{v} > \mathbf{0}$ . By Theorem 19.1.5 (d), a nonnegative eigenvector of the positive matrix $\mathbf{B}$ belongs to the eigenvalue $\rho(\mathbf{B})$ ; hence $q(\rho) = (1 + \rho)^{n-1} = \rho(\mathbf{B}) .$

Step 3: simplicity. Over $\mathbb{C}$ , write $p_{\mathbf{A}}(t) = (t - \lambda_1)\cdots(t - \lambda_n)$ with each eigenvalue repeated according to its algebraic multiplicity (Corollary 6.5.5). By the Spectral Mapping Theorem (Theorem 9.10.1), $p_{\mathbf{B}}(t) = \bigl(t - q(\lambda_1)\bigr)\cdots\bigl(t - q(\lambda_n)\bigr) .$ Suppose $a_{\mathbf{A}}(\rho) \ge 2$ , say $\lambda_1 = \lambda_2 = \rho$ . Then $q(\rho) = \rho(\mathbf{B})$ occurs at least twice in this factorization (other eigenvalues mapping to $\rho(\mathbf{B})$ could only increase this count), so $a_{\mathbf{B}}(\rho(\mathbf{B})) \ge 2$ , contradicting the simplicity of $\rho(\mathbf{B})$ in Theorem 19.1.5. Hence $a_{\mathbf{A}}(\rho) = 1$ , which is (b).

Step 4: nonnegative eigenvectors. Let $\mathbf{y} \ge \mathbf{0}$ , $\mathbf{y} \ne \mathbf{0}$ , with $\mathbf{A}\mathbf{y} = \mu\mathbf{y}$ for some $\mu \in \mathbb{C}$ . By Step 2, $\mathbf{y}$ is a nonnegative eigenvector of $\mathbf{B}$ , so by Theorem 19.1.5 (d) it belongs to $\rho(\mathbf{B})$ . So $\mathbf{y}$ and $\mathbf{v}$ both lie in the eigenspace $E_{\rho(\mathbf{B})}(\mathbf{B})$ . Since $\rho(\mathbf{B})$ is algebraically simple, Theorem 9.3.1 gives $\dim E_{\rho(\mathbf{B})}(\mathbf{B}) = 1$ , so $\mathbf{y} = c\mathbf{v}$ for some scalar $c \ne 0$ . Choosing $i$ with $y_i > 0$ gives $c = y_i/v_i > 0$ . Finally $\mathbf{A}\mathbf{y} = c\mathbf{A}\mathbf{v} = \rho\,c\mathbf{v} = \rho\mathbf{y}$ , so $\mu = \rho$ . This proves (c).

Step 5: $\rho > 0$ when $n \ge 2$ . Suppose $\rho = 0$ . Then $\mathbf{A}\mathbf{v} = \mathbf{0}$ , so for each $i$ the sum $\sum_j a_{ij}v_j$ of nonnegative terms is $0$ , which forces $a_{ij}v_j = 0$ and hence $a_{ij} = 0$ for every $j$ , as $v_j > 0$ . So $\mathbf{A} = \mathbf{O}$ and $\mathbf{B} = \mathbf{I}_n$ . For $n \ge 2$ the matrix $\mathbf{I}_n$ has a zero entry off the diagonal, so it is not positive, contradicting $\mathbf{B} > \mathbf{O}$ . This proves (d), and the theorem.

The first sentence of the proof is where irreducibility did its work, and irreducibility was used only there. Note also what the theorem does not claim. For positive matrices, Theorem 19.1.5 adds that every other eigenvalue has modulus strictly less than $\rho$ . For irreducible matrices this is false.

Warning. Irreducible does not make $\rho$ strictly dominant. The swap $\mathbf{P} = \begin{psmallmatrix} 0 & 1 \\ 1 & 0 \end{psmallmatrix}$ is irreducible, since $\mathbf{I} + \mathbf{P} = \mathbf{J}$ is positive (Theorem 19.2.6 with $n = 2$ ). Its eigenvalues are $1$ and $-1$ , with eigenvectors $(1, 1)$ and $(1, -1)$ . The theorem holds as stated: $\rho = 1$ is simple with the positive eigenvector $(1, 1)$ , and $(1, -1)$ is not nonnegative. But $\lvert -1 \rvert = \rho$ . Section 5 identifies the irreducible matrices for which $\rho$ is strictly dominant.

The case $n = 1$ is worth one sentence. A $1 \times 1$ matrix $(a)$ with $a \ge 0$ has $\rho = a$ , simple, with the positive eigenvector $(1)$ , so clauses (a)–(c) hold for it outright; clause (d) must exclude $n = 1$ , since $\mathbf{O}_1$ has $\rho = 0$ . For $n \ge 2$ the zero matrix is the one thing (d) had to rule out, and irreducibility does.

Example (The theorem on a matrix with zeros)

Let $\mathbf{A} = \begin{pmatrix} 0 & 1 & 0 \\ 2 & 0 & 1 \\ 2 & 1 & 0 \end{pmatrix} .$ Show that $\mathbf{A}$ is irreducible, find $\rho(\mathbf{A})$ and a positive eigenvector, and check clause (c) of Theorem 19.3.2 against the other eigenvalue.

Solution. Irreducible. We have $\mathbf{I} + \mathbf{A} = \begin{psmallmatrix} 1 & 1 & 0 \\ 2 & 1 & 1 \\ 2 & 1 & 1 \end{psmallmatrix}$ and, multiplying out, $(\mathbf{I} + \mathbf{A})^2 = \begin{pmatrix} 3 & 2 & 1 \\ 6 & 4 & 2 \\ 6 & 4 & 2 \end{pmatrix} > \mathbf{O} ,$ so $\mathbf{A}$ is irreducible by Theorem 19.2.6 with $n = 3$ . Note that $\mathbf{A}$ itself has four zero entries and is not positive, so Theorem 19.1.5 does not apply to it directly.

The spectrum. Expanding $\det(t\mathbf{I} - \mathbf{A})$ along the first row, $\begin{aligned} p_{\mathbf{A}}(t) &= t\,(t^2 - 1) + (-2t - 2) \\ &= t^3 - 3t - 2 = (t - 2)(t + 1)^2 . \end{aligned}$ So the eigenvalues are $2$ and $-1$ , the latter with algebraic multiplicity $2$ , and $\rho(\mathbf{A}) = 2$ , algebraically simple as clause (b) says. A repeated eigenvalue elsewhere in the spectrum is no contradiction: the theorem speaks only about $\rho$ .

The eigenvector. $(\mathbf{A} - 2\mathbf{I})\mathbf{x} = \mathbf{0}$ reads $-2x_1 + x_2 = 0$ , $2x_1 - 2x_2 + x_3 = 0$ , $2x_1 + x_2 - 2x_3 = 0$ . The first gives $x_2 = 2x_1$ , the second then $x_3 = 2x_1$ , and the third is satisfied: $2 + 2 - 4 = 0$ . So $\mathbf{v} = (1, 2, 2) > \mathbf{0}$ and $\mathbf{A}\mathbf{v} = (2, 4, 4) = 2\mathbf{v}$ .

The other eigenvalue. $\mathbf{A} + \mathbf{I} = \begin{psmallmatrix} 1 & 1 & 0 \\ 2 & 1 & 1 \\ 2 & 1 & 1 \end{psmallmatrix}$ has rank $2$ , and its null space is spanned by $(1, -1, -1)$ : the first row gives $x_2 = -x_1$ , the second $x_3 = -2x_1 - x_2 = -x_1$ . Every eigenvector for $-1$ is a multiple of $(1, -1, -1)$ and has entries of both signs, as clause (c) predicts.

Quick check. For which values of $c \ge 0$ is the matrix $\mathbf{A}_c$ of Example (Three nonnegative matrices that break Perron’s theorem) irreducible? Is the answer consistent with what the example found?

Solution. For none. Whatever $c$ is, $\mathbf{I} + \mathbf{A}_c$ is block diagonal with blocks of sizes $2$ and $1$ , so every power of it is block diagonal too, and $(\mathbf{I} + \mathbf{A}_c)^2$ has zeros in positions $(1, 3)$ , $(2, 3)$ , $(3, 1)$ , $(3, 2)$ . By Theorem 19.2.6, $\mathbf{A}_c$ is reducible. This is consistent: the example found conclusions of Theorem 19.3.2 failing for $c = 1$ and $c = 2$ , which is possible only for a reducible matrix.

19.3.3. The left Perron vector

Everything so far concerned the equation $\mathbf{A}\mathbf{v} = \rho\mathbf{v}$ . A nonnegative matrix acts on rows as well: in a Markov chain, the row $\mathbf{1}^{\top}$ is a left eigenvector of every stochastic matrix (Proposition 9.11.3 (c)). Left eigenvectors of $\mathbf{A}$ are eigenvectors of $\mathbf{A}^{\top}$ (Proposition 9.10.5 (a)), and irreducibility passes to the transpose, so the theorem applies to rows at no extra cost.

Corollary 19.3.3 (The Left Perron Vector)

Let $\mathbf{A} \in M_n(\mathbb{R})$ be nonnegative and irreducible, with $\rho = \rho(\mathbf{A})$ and $\mathbf{v} > \mathbf{0}$ as in Theorem 19.3.2. Then:

(a) $\mathbf{A}^{\top}$ is nonnegative and irreducible, and $\rho(\mathbf{A}^{\top}) = \rho$ ;
(b) there is $\mathbf{w} > \mathbf{0}$ with $\mathbf{w}^{\top}\mathbf{A} = \rho\,\mathbf{w}^{\top}$ , and every nonnegative left eigenvector of $\mathbf{A}$ is a positive multiple of $\mathbf{w}$ ;
(c) $\mathbf{w}^{\top}\mathbf{v} > 0$ , so $\mathbf{w}$ can be scaled to make $\mathbf{w}^{\top}\mathbf{v} = 1$ .

Idea. Apply Theorem 19.3.2 to $\mathbf{A}^{\top}$ and read the answer back as rows. Two things must be checked first: that $\mathbf{A}^{\top}$ meets the hypotheses, which holds because the test $(\mathbf{I} + \mathbf{A})^{n-1} > \mathbf{O}$ survives transposition, and that $\mathbf{A}^{\top}$ has the same spectral radius, which holds because it has the same characteristic polynomial. Positivity of both vectors then makes $\mathbf{w}^{\top}\mathbf{v}$ a sum of positive terms.

Proof.

(a) The entries of $\mathbf{A}^{\top}$ are those of $\mathbf{A}$ , so $\mathbf{A}^{\top} \ge \mathbf{O}$ . Transposition reverses products and fixes $\mathbf{I}$ (Theorem 0.9.5), so $(\mathbf{I} + \mathbf{A}^{\top})^{n-1} = \bigl((\mathbf{I} + \mathbf{A})^{n-1}\bigr)^{\top}$ , which is positive because $(\mathbf{I} + \mathbf{A})^{n-1}$ is; hence $\mathbf{A}^{\top}$ is irreducible by Theorem 19.2.6. By Proposition 9.10.5 (b), $p_{\mathbf{A}^{\top}} = p_{\mathbf{A}}$ , so $\mathbf{A}$ and $\mathbf{A}^{\top}$ have the same eigenvalues and $\rho(\mathbf{A}^{\top}) = \rho$ .
(b) By (a) and Theorem 19.3.2 (a) applied to $\mathbf{A}^{\top}$ , there is $\mathbf{w} > \mathbf{0}$ with $\mathbf{A}^{\top}\mathbf{w} = \rho\mathbf{w}$ , which by Proposition 9.10.5 (a) says $\mathbf{w}^{\top}\mathbf{A} = \rho\mathbf{w}^{\top}$ . A nonnegative left eigenvector of $\mathbf{A}$ is a nonnegative eigenvector of $\mathbf{A}^{\top}$ , hence a positive multiple of $\mathbf{w}$ by Theorem 19.3.2 (c) applied to $\mathbf{A}^{\top}$ .
(c) $\mathbf{w}^{\top}\mathbf{v} = \sum_i w_iv_i$ is a sum of positive numbers, so it is positive, and $\mathbf{w}/(\mathbf{w}^{\top}\mathbf{v})$ has the stated property.

This makes the following names well defined, since each vector is pinned down by (c) of the theorem or (b) of the corollary together with its normalization.

Definition 19.3.1 (Perron Root, Perron Vectors)

This definition extends Definition 19.1.2 from positive matrices to irreducible ones. Let $\mathbf{A} \in M_n(\mathbb{R})$ be nonnegative and irreducible. Its Perron root is $\rho(\mathbf{A})$ . Its (right) Perron vector is the unique $\mathbf{v} > \mathbf{0}$ with $\mathbf{A}\mathbf{v} = \rho(\mathbf{A})\mathbf{v}$ and $\mathbf{1}^{\top}\mathbf{v} = 1$ . Its left Perron vector is the unique $\mathbf{w} > \mathbf{0}$ with $\mathbf{w}^{\top}\mathbf{A} = \rho(\mathbf{A})\mathbf{w}^{\top}$ and $\mathbf{w}^{\top}\mathbf{v} = 1$ .

The two normalizations are chosen for what they do. $\mathbf{1}^{\top}\mathbf{v} = 1$ makes $\mathbf{v}$ a probability vector, which is what a Markov chain wants; $\mathbf{w}^{\top}\mathbf{v} = 1$ makes the rank-one matrix $\mathbf{v}\mathbf{w}^{\top}$ idempotent, since $(\mathbf{v}\mathbf{w}^{\top})(\mathbf{v}\mathbf{w}^{\top}) = \mathbf{v}\,(\mathbf{w}^{\top}\mathbf{v})\,\mathbf{w}^{\top} = \mathbf{v}\mathbf{w}^{\top} .$

Section 5 shows that, for a large class of irreducible matrices, the powers $(\mathbf{A}/\rho)^k$ converge to exactly this matrix.

A positive matrix is irreducible, since then $(\mathbf{I} + \mathbf{A})^{n-1} \ge \mathbf{I} + \mathbf{A} > \mathbf{O}$ for $n \ge 2$ : expand $(\mathbf{I} + \mathbf{A})^{n-1}$ by the binomial theorem, which applies because $\mathbf{I}$ and $\mathbf{A}$ commute, and note that every term is $\ge \mathbf{O}$ and two of them are $\mathbf{I}$ and $(n - 1)\mathbf{A} \ge \mathbf{A}$ . So this definition covers the positive matrices of Section 1. For them the Perron root and both Perron vectors are those of Definition 19.1.2.

For the matrix of Example (The theorem on a matrix with zeros), the left eigenvector is $(3, 2, 1)$ : indeed $(3, 2, 1)\mathbf{A} = (0 + 4 + 2,\ 3 + 0 + 1,\ 0 + 2 + 0) = (6, 4, 2)$ . The right Perron vector is $\mathbf{v} = \frac15(1, 2, 2)$ , and $(3, 2, 1) \cdot \frac15(1, 2, 2) = \frac95$ , so the left Perron vector is $\mathbf{w} = \frac59(3, 2, 1)$ .

Example (An irreducible stochastic matrix)

Let $\mathbf{A} = \begin{pmatrix} 0 & 1/2 & 1 \\ 1 & 0 & 0 \\ 0 & 1/2 & 0 \end{pmatrix} .$ Show that $\mathbf{A}$ is stochastic and irreducible, and find its Perron root and its right and left Perron vectors.

Solution. Each column is a probability vector, so $\mathbf{A}$ is stochastic (Definition 9.11.1). Multiplying out, $(\mathbf{I} + \mathbf{A})^2 = \begin{pmatrix} 3/2 & 3/2 & 2 \\ 2 & 3/2 & 1 \\ 1/2 & 1 & 1 \end{pmatrix} > \mathbf{O} ,$ so $\mathbf{A}$ is irreducible (Theorem 19.2.6).

Perron root. By Proposition 9.11.3 (c), $1$ is an eigenvalue. Every column sum is $1$ , so $\left\| \mathbf{A} \right\|_1 = 1$ and $\rho(\mathbf{A}) \le 1$ by Corollary 16.4.2. Hence $\rho(\mathbf{A}) = 1$ .

Left Perron vector. $\mathbf{1}^{\top}\mathbf{A} = \mathbf{1}^{\top}$ with $\mathbf{1} > \mathbf{0}$ , so by Corollary 19.3.3 (b) the left Perron vector is a multiple of $\mathbf{1}$ .

Right Perron vector. $\mathbf{A}\mathbf{x} = \mathbf{x}$ reads $\tfrac12x_2 + x_3 = x_1$ , $x_1 = x_2$ , $\tfrac12x_2 = x_3$ . With $x_3 = 1$ this gives $x_2 = 2$ , $x_1 = 2$ , and the first equation holds: $1 + 1 = 2$ . So $\mathbf{v} = \frac15(2, 2, 1)$ . Then $\mathbf{1}^{\top}\mathbf{v} = 1$ , and the left Perron vector is $\mathbf{w} = \mathbf{1}$ itself.

By Theorem 19.3.2 (c), $\mathbf{v}$ is the only probability vector with $\mathbf{A}\mathbf{v} = \mathbf{v}$ : this chain has exactly one steady state, and every state has positive probability in it. The other two eigenvalues are the roots of $2t^2 + 2t + 1$ , namely $\frac{-1 \pm i}{2}$ , of modulus $1/\sqrt2 < 1$ ; the factorization is $p_{\mathbf{A}}(t) = (t - 1)(t^2 + t + \frac12)$ , which the reader can confirm by expanding $\det(t\mathbf{I} - \mathbf{A})$ along the first column.

For every irreducible stochastic matrix the same three lines apply, and they show that the left Perron vector is always $\mathbf{1}$ and the steady state always unique and positive. Section 6 draws the consequences for Markov chains.

19.3.4. Exercises

A. Check your understanding

Exercise (A1)

(a) State the Perron–Frobenius theorem for irreducible nonnegative matrices.
(b) True or false: if $\mathbf{A} \ge \mathbf{O}$ , then $\rho(\mathbf{A}) > 0$ . Justify your answer.
(c) True or false: if $\mathbf{A} \ge \mathbf{O}$ is irreducible, then every eigenvalue $\lambda \ne \rho(\mathbf{A})$ has $\lvert \lambda \rvert < \rho(\mathbf{A})$ . Justify your answer.
(d) True or false: if $\mathbf{A} \ge \mathbf{O}$ and $\mathbf{A}\mathbf{y} = \mu\mathbf{y}$ with $\mathbf{y} \ge \mathbf{0}$ , $\mathbf{y} \ne \mathbf{0}$ , then $\mu = \rho(\mathbf{A})$ . Justify your answer.
(e) Which positive matrix does the proof of Theorem 19.3.2 apply Theorem 19.1.5 to, and why not to $\mathbf{A} + \varepsilon\mathbf{J}$ ?

Solution.

(a) See Theorem 19.3.2: for $\mathbf{A} \ge \mathbf{O}$ irreducible, $\rho(\mathbf{A})$ is an algebraically simple eigenvalue with a positive eigenvector, every nonnegative eigenvector is a positive multiple of that one, and $\rho(\mathbf{A}) > 0$ when $n \ge 2$ .
(b) False. $\mathbf{N} = \begin{psmallmatrix} 0 & 1 \\ 0 & 0 \end{psmallmatrix} \ge \mathbf{O}$ has $\rho(\mathbf{N}) = 0$ (Example (Three nonnegative matrices that break Perron’s theorem)). It is reducible, so this does not contradict Theorem 19.3.2 (d).
(c) False. The swap $\begin{psmallmatrix} 0 & 1 \\ 1 & 0 \end{psmallmatrix}$ is irreducible with eigenvalues $1 = \rho$ and $-1$ , and $\lvert -1 \rvert = \rho$ .
(d) False in general: $\mathbf{A}_1$ of Example (Three nonnegative matrices that break Perron’s theorem) has $\mathbf{A}_1\mathbf{e}_3 = \mathbf{e}_3$ but $\rho(\mathbf{A}_1) = 2$ . It is true when $\mathbf{A}$ is irreducible, by Theorem 19.3.2 (c).
(e) To $\mathbf{B} = (\mathbf{I} + \mathbf{A})^{n-1}$ , which is positive by Theorem 19.2.6. The perturbation $\mathbf{A} + \varepsilon\mathbf{J}$ requires a limit $\varepsilon \to 0^{+}$ , and a limit cannot certify strict conclusions — positivity of the eigenvector and simplicity of $\rho$ — which are exactly what the theorem asserts; Exercise C2 shows them lost when the limit matrix is reducible.

B. Practice

Exercise (B1: Does the theorem apply?)

For each matrix, determine whether Theorem 19.3.2 applies. Where it does, find $\rho$ and a positive eigenvector; where it does not, say which hypothesis fails and whether the conclusion fails too. Justify your answers. $\text{(a)}\ \begin{pmatrix} 0 & 2 \\ 8 & 0 \end{pmatrix} \qquad \text{(b)}\ \begin{pmatrix} 1 & 2 \\ 0 & 3 \end{pmatrix} \qquad \text{(c)}\ \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix} \qquad \text{(d)}\ \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}$

Solution.

(a) Nonnegative, and $\mathbf{I} + \mathbf{A} = \begin{psmallmatrix} 1 & 2 \\ 8 & 1 \end{psmallmatrix} > \mathbf{O}$ , so irreducible by Theorem 19.2.6 with $n = 2$ . The theorem applies. $p_{\mathbf{A}}(t) = t^2 - 16$ , so the eigenvalues are $\pm 4$ and $\rho = 4$ . From $-4x_1 + 2x_2 = 0$ , $\mathbf{v} = (1, 2) > \mathbf{0}$ ; check: $\mathbf{A}\mathbf{v} = (4, 8) = 4\mathbf{v}$ . As with the swap, $-4$ has the same modulus as $\rho$ .
(b) Nonnegative, but $(\mathbf{I} + \mathbf{A})^1 = \begin{psmallmatrix} 2 & 2 \\ 0 & 4 \end{psmallmatrix}$ has a zero entry, so $\mathbf{A}$ is reducible and the theorem does not apply. The eigenvalues are $1$ and $3$ (Theorem 9.7.4 (b)), so $\rho = 3$ . Here $(\mathbf{A} - 3\mathbf{I})\mathbf{x} = \mathbf{0}$ reads $-2x_1 + 2x_2 = 0$ , so $(1, 1) > \mathbf{0}$ is an eigenvector for $\rho$ : conclusions (a) and (b) happen to hold. Conclusion (c) fails: $\mathbf{e}_1 \ge \mathbf{0}$ is an eigenvector for $1 \ne \rho$ .
(c) Nonnegative. With $\mathbf{C}$ this matrix, $\mathbf{C}\mathbf{e}_1 = \mathbf{e}_3$ , $\mathbf{C}\mathbf{e}_3 = \mathbf{e}_2$ , $\mathbf{C}\mathbf{e}_2 = \mathbf{e}_1$ , and $\mathbf{I} + \mathbf{C} + \mathbf{C}^2 = \mathbf{J}$ ; so $(\mathbf{I} + \mathbf{C})^2 = \mathbf{I} + 2\mathbf{C} + \mathbf{C}^2 \ge \mathbf{I} + \mathbf{C} + \mathbf{C}^2 = \mathbf{J} > \mathbf{O}$ , and $\mathbf{C}$ is irreducible. The theorem applies. $\mathbf{C}^3 = \mathbf{I}$ , and $p_{\mathbf{C}}(t) = t^3 - 1$ (expand along the first column), so the eigenvalues are the three cube roots of unity, all of modulus $1$ , and $\rho = 1$ with $\mathbf{v} = \mathbf{1}$ , since every row of $\mathbf{C}$ has a single $1$ .
(d) Not nonnegative, so the theorem does not apply, and its conclusion fails: $p(t) = t^2 + 1$ , the eigenvalues are $\pm i$ , and $\rho = 1$ is not an eigenvalue at all.

Exercise (B2: Both Perron vectors)

Let $\mathbf{A} = \begin{pmatrix} 0 & 1 & 0 \\ 2 & 0 & 2 \\ 1 & 0 & 1 \end{pmatrix} .$ Show that $\mathbf{A}$ is irreducible, and find its Perron root, its right Perron vector, and its left Perron vector (Definition 19.3.1). Hence write down the matrix $\mathbf{v}\mathbf{w}^{\top}$ and check that it is idempotent.

Solution. Irreducible. $\mathbf{I} + \mathbf{A} = \begin{psmallmatrix} 1 & 1 & 0 \\ 2 & 1 & 2 \\ 1 & 0 & 2 \end{psmallmatrix}$ , and $(\mathbf{I} + \mathbf{A})^2 = \begin{pmatrix} 3 & 2 & 2 \\ 6 & 3 & 6 \\ 3 & 1 & 4 \end{pmatrix} > \mathbf{O} ,$ so $\mathbf{A}$ is irreducible by Theorem 19.2.6.

Perron root. Expanding $\det(t\mathbf{I} - \mathbf{A})$ along the first row, $\begin{aligned} p_{\mathbf{A}}(t) &= t\bigl(t(t - 1) - 0\bigr) + \bigl(-2(t - 1) - 2\bigr) \\ &= t^3 - t^2 - 2t = t(t - 2)(t + 1) , \end{aligned}$ so the eigenvalues are $2, 0, -1$ and $\rho = 2$ .

Right. $(\mathbf{A} - 2\mathbf{I})\mathbf{x} = \mathbf{0}$ : the first row gives $x_2 = 2x_1$ , the third $x_1 - x_3 = 0$ . So $\mathbf{x} = (1, 2, 1)$ ; check the second row: $2 - 4 + 2 = 0$ . Normalizing, $\mathbf{v} = \frac14(1, 2, 1)$ .

Left. $(\mathbf{A}^{\top} - 2\mathbf{I})\mathbf{y} = \mathbf{0}$ , with $\mathbf{A}^{\top} = \begin{psmallmatrix} 0 & 2 & 1 \\ 1 & 0 & 0 \\ 0 & 2 & 1 \end{psmallmatrix}$ : the second row gives $y_1 = 2y_2$ , the third $2y_2 - y_3 = 0$ . So $\mathbf{y} = (2, 1, 2)$ ; check the first row: $-4 + 2 + 2 = 0$ . Then $\mathbf{y}^{\top}\mathbf{v} = \frac14(2 + 2 + 2) = \frac32$ , so $\mathbf{w} = \frac23(2, 1, 2)$ .

The product. $\mathbf{v}\mathbf{w}^{\top} = \frac14 \cdot \frac23 \begin{pmatrix} 2 & 1 & 2 \\ 4 & 2 & 4 \\ 2 & 1 & 2 \end{pmatrix} = \frac16 \begin{pmatrix} 2 & 1 & 2 \\ 4 & 2 & 4 \\ 2 & 1 & 2 \end{pmatrix} .$ It is idempotent because $(\mathbf{v}\mathbf{w}^{\top})^2 = \mathbf{v}(\mathbf{w}^{\top}\mathbf{v})\mathbf{w}^{\top} = \mathbf{v}\mathbf{w}^{\top}$ , as $\mathbf{w}^{\top}\mathbf{v} = 1$ . Directly: call the displayed integer matrix $\mathbf{M}$ . Row $i$ of $\mathbf{M}^2$ is row $i$ of $\mathbf{M}$ times $\mathbf{M}$ ; the first row gives $2(2, 1, 2) + 1(4, 2, 4) + 2(2, 1, 2) = 6(2, 1, 2)$ , and the other rows are multiples of the first, so $\mathbf{M}^2 = 6\mathbf{M}$ . Hence $\bigl(\frac16\mathbf{M}\bigr)^2 = \frac{1}{36}\cdot 6\mathbf{M} = \frac16\mathbf{M}$ .

Exercise (B3: A reducible matrix, clause by clause)

Let $\mathbf{A} = \begin{pmatrix} 2 & 0 & 0 \\ 1 & 3 & 0 \\ 0 & 1 & 2 \end{pmatrix} .$ Show that $\mathbf{A}$ is reducible. Find $\rho(\mathbf{A})$ and every nonnegative eigenvector of $\mathbf{A}$ . Hence decide which of the four conclusions of Theorem 19.3.2 hold for $\mathbf{A}$ and which fail.

Solution. Reducible. $\mathbf{I} + \mathbf{A}$ is lower triangular, so $(\mathbf{I} + \mathbf{A})^2$ is lower triangular and has zero entries above the diagonal; by Theorem 19.2.6, $\mathbf{A}$ is reducible.

Spectrum. $\mathbf{A}$ is lower triangular, so its eigenvalues are $2, 3, 2$ (Theorem 9.7.4 (b), applied to $\mathbf{A}^{\top}$ , which has the same characteristic polynomial by Proposition 9.10.5 (b)). So $\rho = 3$ , with $a_{\mathbf{A}}(3) = 1$ .

Eigenvectors for 3. $(\mathbf{A} - 3\mathbf{I})\mathbf{x} = \mathbf{0}$ reads $-x_1 = 0$ , $x_1 = 0$ , $x_2 - x_3 = 0$ ; the solutions are the multiples of $(0, 1, 1)$ . Eigenvectors for 2. $(\mathbf{A} - 2\mathbf{I})\mathbf{x} = \mathbf{0}$ reads $x_1 + x_2 = 0$ , $x_2 = 0$ ; the solutions are the multiples of $(0, 0, 1)$ . So the nonnegative eigenvectors are the positive multiples of $(0, 1, 1)$ and of $\mathbf{e}_3$ .

Verdict. Conclusion (b) holds and (d) holds ( $\rho = 3 > 0$ ). Conclusion (a) fails in its strong form: $\rho$ is an eigenvalue, as Theorem 19.3.1 guarantees, but no eigenvector for it is positive. Conclusion (c) fails: $\mathbf{e}_3 \ge \mathbf{0}$ is an eigenvector for $2 \ne \rho$ .

C. Going deeper

Exercise (C1: A positive eigenvector always belongs to the spectral radius)

Let $\mathbf{A} \in M_n(\mathbb{R})$ with $\mathbf{A} \ge \mathbf{O}$ , not assumed irreducible.

(a) Prove that if $\mathbf{A}\mathbf{x} = \mu\mathbf{x}$ with $\mathbf{x} > \mathbf{0}$ , then $\mu = \rho(\mathbf{A})$ .
(b) Deduce that if every row of $\mathbf{A}$ has the same sum $s$ , then $\rho(\mathbf{A}) = s$ .
(c) Show by an example that (a) fails if $\mathbf{x} > \mathbf{0}$ is weakened to $\mathbf{x} \ge \mathbf{0}$ , $\mathbf{x} \ne \mathbf{0}$ .

Hint: apply Theorem 19.3.1 to $\mathbf{A}^{\top}$ .

Solution.

(a) Since $\mathbf{A}$ and $\mathbf{x}$ are real and $\mathbf{x} \ne \mathbf{0}$ , $\mu = (\mathbf{A}\mathbf{x})_i/x_i$ for any $i$ is real, and it is $\ge 0$ because $(\mathbf{A}\mathbf{x})_i \ge 0$ and $x_i > 0$ . By Proposition 9.10.5 (b), $\rho(\mathbf{A}^{\top}) = \rho(\mathbf{A}) = \rho$ , and $\mathbf{A}^{\top} \ge \mathbf{O}$ , so Theorem 19.3.1 gives $\mathbf{y} \ge \mathbf{0}$ , $\mathbf{y} \ne \mathbf{0}$ , with $\mathbf{A}^{\top}\mathbf{y} = \rho\mathbf{y}$ , that is, $\mathbf{y}^{\top}\mathbf{A} = \rho\mathbf{y}^{\top}$ . Compute $\mathbf{y}^{\top}\mathbf{A}\mathbf{x}$ two ways: $\rho\,\mathbf{y}^{\top}\mathbf{x} = (\mathbf{y}^{\top}\mathbf{A})\mathbf{x} = \mathbf{y}^{\top}(\mathbf{A}\mathbf{x}) = \mu\,\mathbf{y}^{\top}\mathbf{x} .$ Now $\mathbf{y}^{\top}\mathbf{x} = \sum_i y_ix_i > 0$ , as every term is $\ge 0$ and the terms with $y_i > 0$ are positive. Dividing, $\mu = \rho$ .
(b) Equal row sums $s$ say $\mathbf{A}\mathbf{1} = s\mathbf{1}$ , and $\mathbf{1} > \mathbf{0}$ , so $s = \rho(\mathbf{A})$ by (a).
(c) $\mathbf{A}_1$ of Example (Three nonnegative matrices that break Perron’s theorem) has $\mathbf{A}_1\mathbf{e}_3 = \mathbf{e}_3$ with $\mathbf{e}_3 \ge \mathbf{0}$ , $\mathbf{e}_3 \ne \mathbf{0}$ , but $\rho(\mathbf{A}_1) = 2 \ne 1$ .

Exercise (C2: What the limit loses)

This exercise shows why the proof of Theorem 19.3.2 does not take the limit $\mathbf{A} + \varepsilon\mathbf{J} \to \mathbf{A}$ .

(a) For $\varepsilon > 0$ , find the eigenvalues of $\mathbf{I}_2 + \varepsilon\mathbf{J}$ . Show that $\rho$ is simple for every $\varepsilon > 0$ , but not at $\varepsilon = 0$ .
(b) For $\varepsilon > 0$ , let $\mathbf{N}_{\varepsilon} = \begin{psmallmatrix} \varepsilon & 1 + \varepsilon \\ \varepsilon & \varepsilon \end{psmallmatrix}$ , which is $\mathbf{N} + \varepsilon\mathbf{J}$ for the nilpotent $\mathbf{N}$ of Example (Three nonnegative matrices that break Perron’s theorem). Show that $\rho(\mathbf{N}_{\varepsilon}) = \varepsilon + \sqrt{\varepsilon(1 + \varepsilon)}$ with eigenvector $\bigl(\sqrt{1 + \varepsilon},\ \sqrt{\varepsilon}\bigr) > \mathbf{0}$ , and find the limit of this eigenvector as $\varepsilon \to 0^{+}$ .
(c) Which conclusions of Theorem 19.1.5 survive the limit in these two examples, and which do not? Explain in one sentence why this is to be expected.

Solution.

(a) $\mathbf{J}\mathbf{1} = 2\cdot\mathbf{1}$ and $\mathbf{J}(1, -1) = \mathbf{0}$ , so $\mathbf{I}_2 + \varepsilon\mathbf{J}$ has the eigenvalue $1 + 2\varepsilon$ on $(1, 1)$ and $1$ on $(1, -1)$ . For $\varepsilon > 0$ these are distinct, so $\rho = 1 + 2\varepsilon$ is simple. At $\varepsilon = 0$ the matrix is $\mathbf{I}_2$ and $\rho = 1$ has algebraic multiplicity $2$ .
(b) $\mathbf{N}_{\varepsilon} - \varepsilon\mathbf{I} = \begin{psmallmatrix} 0 & 1 + \varepsilon \\ \varepsilon & 0 \end{psmallmatrix}$ has characteristic polynomial $t^2 - \varepsilon(1 + \varepsilon)$ , so the eigenvalues of $\mathbf{N}_{\varepsilon}$ are $\varepsilon \pm \sqrt{\varepsilon(1 + \varepsilon)}$ , and $\rho(\mathbf{N}_{\varepsilon}) = \varepsilon + \sqrt{\varepsilon(1 + \varepsilon)}$ , which exceeds the modulus of the other one since $\varepsilon > 0$ . With $s = \sqrt{\varepsilon(1 + \varepsilon)}$ and $\mathbf{u} = \bigl(\sqrt{1 + \varepsilon}, \sqrt\varepsilon\bigr)$ , $(\mathbf{N}_{\varepsilon} - \varepsilon\mathbf{I})\mathbf{u} = \bigl((1 + \varepsilon)\sqrt\varepsilon,\ \varepsilon\sqrt{1 + \varepsilon}\bigr) = s\,\mathbf{u} ,$ since $(1 + \varepsilon)\sqrt\varepsilon = s\sqrt{1 + \varepsilon}$ and $\varepsilon\sqrt{1 + \varepsilon} = s\sqrt\varepsilon$ . So $\mathbf{N}_{\varepsilon}\mathbf{u} = (\varepsilon + s)\mathbf{u}$ with $\mathbf{u} > \mathbf{0}$ . As $\varepsilon \to 0^{+}$ , $\mathbf{u} \to (1, 0) = \mathbf{e}_1$ , which is nonnegative but not positive.
(c) What survives is that $\rho$ is an eigenvalue with a nonnegative eigenvector, which is Theorem 19.3.1. Simplicity is lost in (a), and positivity of the eigenvector in (b). This is expected because those conclusions are strict — a multiplicity equal to $1$ , entries $> 0$ — and a limit of positive numbers need only be $\ge 0$ , while two distinct eigenvalues can converge to one.

Exercise (C3: Uniqueness through the left Perron vector)

Let $\mathbf{A} \ge \mathbf{O}$ be irreducible, with left Perron vector $\mathbf{w}$ (Definition 19.3.1, Corollary 19.3.3).

(a) Using Theorem 9.10.6, give a second proof that if $\mathbf{A}\mathbf{y} = \mu\mathbf{y}$ with $\mathbf{y} \ge \mathbf{0}$ , $\mathbf{y} \ne \mathbf{0}$ , then $\mu = \rho(\mathbf{A})$ .
(b) Deduce that an irreducible stochastic matrix has exactly one steady state (Definition 9.11.2), and that it is positive.

Solution.

(a) Suppose $\mu \ne \rho(\mathbf{A})$ . The vector $\mathbf{w}$ is a left eigenvector for $\rho(\mathbf{A})$ and $\mathbf{y}$ a right eigenvector for $\mu$ , so Theorem 9.10.6 gives $\mathbf{w}^{\top}\mathbf{y} = 0$ . But $\mathbf{w} > \mathbf{0}$ , $\mathbf{y} \ge \mathbf{0}$ and $\mathbf{y} \ne \mathbf{0}$ , so $\mathbf{w}^{\top}\mathbf{y} = \sum_i w_iy_i \ge w_iy_i > 0$ for an index $i$ with $y_i > 0$ . This contradiction shows $\mu = \rho(\mathbf{A})$ .
(b) Let $\mathbf{A}$ be stochastic and irreducible. As in Example (An irreducible stochastic matrix), $\rho(\mathbf{A}) = 1$ : $1$ is an eigenvalue by Proposition 9.11.3 (c), and $\rho(\mathbf{A}) \le \left\| \mathbf{A} \right\|_1 = 1$ by Corollary 16.4.2. A steady state is a probability vector $\mathbf{x}$ with $\mathbf{A}\mathbf{x} = \mathbf{x}$ : a nonnegative eigenvector for $1 = \rho(\mathbf{A})$ , normalized by $\mathbf{1}^{\top}\mathbf{x} = 1$ . By Theorem 19.3.2 (c), every such $\mathbf{x}$ is a positive multiple of the Perron vector $\mathbf{v}$ , and the normalization forces $\mathbf{x} = \mathbf{v}$ . So there is exactly one steady state, namely $\mathbf{v} > \mathbf{0}$ .