19.2 Irreducibility and Graphs

Perron’s theorem (Theorem 19.1.5) asks for every entry to be positive, and most matrices that arise in practice do not oblige. The bicycle chain of Chapter 9 §11 has a zero entry, since a bicycle at station $3$ never reaches station $1$ in one night; the Leslie matrix of the same section is mostly zeros; the swap has only two nonzero entries. Some zeros are harmless and some are fatal: the swap keeps $\rho = 1$ as a simple eigenvalue with a positive eigenvector, while for $\mathbf{I}_2$ the eigenvalue $1$ is double and its positive eigenvectors are no longer all multiples of one. This section finds the dividing line. It depends only on where the zero entries are, and the right way to read that pattern is as a map of one-step moves between the indices: a directed graph. The matrices on the good side of the line are the irreducible ones, and §03 proves that they enjoy nearly all of Perron’s conclusions.

Throughout, $F$ is $\mathbb{R}$ or $\mathbb{C}$ . The definitions of this section use only whether an entry is zero, so they make sense for any matrix. The statements about powers and positivity need $\mathbf{A} \ge \mathbf{O}$ , and say so.

19.2.1. The graph of a matrix

The question that recurs is this: which entries of $\mathbf{A}^{k}$ are nonzero? For a nonnegative matrix, $(\mathbf{A}^2)_{ij} = \sum_l a_{il}a_{lj}$ is positive exactly when some $a_{il}$ and $a_{lj}$ are both positive, that is, when one can go from $j$ to some $l$ and from $l$ to $i$ along nonzero entries. In a Markov chain (Definition 9.11.2), $a_{lj}$ is the probability of moving from state $j$ to state $l$ in one step, and the sentence says that state $i$ can be reached from $j$ in two steps. So we draw an arrow from $j$ to $i$ for each nonzero entry $a_{ij}$ and count routes.

The graph of a matrix has a vertex for each index and an arrow from $j$ to $i$ whenever the entry $a_{ij}$ is not zero.

Definition 19.2.1 (Directed Graph of a Matrix; Walks and Paths)

Let $n \ge 1$ and $\mathbf{A} = (a_{ij}) \in M_n(F)$ .

(a) The directed graph $G(\mathbf{A})$ of $\mathbf{A}$ has vertices $1, 2, \dots, n$ , and an edge from $j$ to $i$ , written $j \to i$ , for each pair $(i, j)$ with $a_{ij} \ne 0$ . An edge $j \to j$ , from a nonzero diagonal entry, is a loop.
(b) A walk of length $k \ge 0$ from $j$ to $i$ is a list of vertices $j = i_0, i_1, \dots, i_k = i$ such that $i_{t-1} \to i_t$ is an edge for every $t = 1, \dots, k$ .
(c) A path is a walk whose vertices $i_0, \dots, i_k$ are distinct.

In words: (a) turns each nonzero entry into an arrow, and the arrow for $a_{ij}$ points from the column index to the row index. That is the direction in which $\mathbf{A}$ moves things: in $\mathbf{x} \mapsto \mathbf{A}\mathbf{x}$ , entry $j$ of $\mathbf{x}$ contributes $a_{ij}x_j$ to entry $i$ of the image, and in a column-stochastic chain $a_{ij}$ is the probability of the move from $j$ to $i$ . Clause (b) allows $k = 0$ : the one-vertex list $(j)$ is a walk of length $0$ from $j$ to itself, whatever the matrix. A walk may revisit vertices and use an edge several times; a path may not.

Remark. Many books draw the arrow for $a_{ij} \ne 0$ from $i$ to $j$ . The two graphs differ by reversing every edge, and nothing below depends on the choice except the wording “from $j$ to $i$ ”. We take the direction that matches $\mathbf{x}_{k+1} = \mathbf{A}\mathbf{x}_k$ and the column-stochastic convention of Chapter 9 §11.

Examples, simplest first.

$n = 1$ . $G((a))$ has one vertex, with a loop if $a \ne 0$ and no edge if $a = 0$ . In either case there is the walk of length $0$ from $1$ to $1$ .
The zero matrix $\mathbf{O} \in M_n(F)$ has $n$ vertices and no edges at all. A positive matrix has every possible edge, loops included.
A cycle. The permutation matrix $\mathbf{C} = \begin{psmallmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{psmallmatrix}$ has $c_{21} = c_{32} = c_{13} = 1$ , so its edges are $1 \to 2$ , $2 \to 3$ and $3 \to 1$ .
A path. $\begin{psmallmatrix} 0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{psmallmatrix}$ has the edges $1 \to 2$ and $2 \to 3$ only. There is a walk from $1$ to $3$ , and none from $3$ to anywhere but $3$ itself.
$\mathbf{A} = \begin{psmallmatrix} 0 & 2 & 0 \\ 0 & 0 & 1 \\ 3 & 0 & 1 \end{psmallmatrix}$ has the edges $2 \to 1$ , $3 \to 2$ , $1 \to 3$ and the loop $3 \to 3$ , drawn below. The values of the entries play no part in the graph.

Diagram. Labels: a_31, a_23, a_12, a_33, 1, 2, 3

Nonexample by minimal change. The graph records whether an entry is zero, not how large it is. Change the entry $3$ of the last matrix to $10^{-9}$ : the graph is unchanged. Change it to $0$ : the edge $1 \to 3$ disappears, and with it every walk out of vertex $1$ other than the one of length $0$ .

The graph was built to count routes, and it does, for nonnegative matrices. The same lemma handles $\mathbf{I} + \mathbf{A}$ , whose graph is that of $\mathbf{A}$ with a loop added at every vertex; a loop lets a walk wait, so walks of length at most $k$ become walks of length exactly $k$ .

Lemma 19.2.1 (Powers Count Walks)

Let $\mathbf{A} \in M_n(\mathbb{R})$ be nonnegative, and let $k \ge 0$ and $i, j \in \{1, \dots, n\}$ .

(a) $(\mathbf{A}^{k})_{ij} > 0$ if and only if $G(\mathbf{A})$ has a walk of length $k$ from $j$ to $i$ .
(b) $\bigl((\mathbf{I} + \mathbf{A})^{k}\bigr)_{ij} > 0$ if and only if $G(\mathbf{A})$ has a walk of length at most $k$ from $j$ to $i$ .

Idea. Induction on $k$ , peeling off the first step of a walk. Expanding $(\mathbf{A}^{k+1})_{ij} = \sum_l (\mathbf{A}^{k})_{il}a_{lj}$ gives a sum of nonnegative terms, so it is positive exactly when one term is: a first step $j \to l$ followed by a walk of length $k$ from $l$ to $i$ . For $\mathbf{I} + \mathbf{A}$ the diagonal $1$ adds the option of waiting at $j$ instead of stepping.

Proof.

(a) Induction on $k$ . For $k = 0$ , $(\mathbf{I})_{ij} > 0$ exactly when $i = j$ , which is exactly when there is a walk of length $0$ from $j$ to $i$ . Suppose (a) holds for $k$ . By Lemma 19.1.1 (c), $\mathbf{A}^{k} \ge \mathbf{O}$ , so $(\mathbf{A}^{k+1})_{ij} = \sum_{l=1}^{n}(\mathbf{A}^{k})_{il}\,a_{lj}$ is a sum of nonnegative terms. It is positive if and only if some term is, that is, if and only if there is an $l$ with $a_{lj} > 0$ and $(\mathbf{A}^{k})_{il} > 0$ . By the definition of $G(\mathbf{A})$ and the induction hypothesis, this says: there is an edge $j \to l$ and a walk of length $k$ from $l$ to $i$ . Putting $j$ in front of that walk gives a walk of length $k + 1$ from $j$ to $i$ , and every such walk arises this way, with $l$ its second vertex.
(b) Induction on $k$ , with the same base case, since $(\mathbf{I} + \mathbf{A})^0 = \mathbf{I}$ . Suppose (b) holds for $k$ . As $(\mathbf{I} + \mathbf{A})^{k} \ge \mathbf{O}$ and $\mathbf{I} + \mathbf{A} \ge \mathbf{O}$ , $\bigl((\mathbf{I} + \mathbf{A})^{k+1}\bigr)_{ij} = \sum_{l=1}^{n}\bigl((\mathbf{I} + \mathbf{A})^{k}\bigr)_{il}\,(\delta_{lj} + a_{lj})$ is positive if and only if there is an $l$ with $((\mathbf{I} + \mathbf{A})^{k})_{il} > 0$ and either $l = j$ or $a_{lj} > 0$ . By the induction hypothesis this says: there is a walk of length at most $k$ from $l$ to $i$ , where either $l = j$ or $j \to l$ is an edge. In the first case we have a walk of length at most $k$ from $j$ to $i$ ; in the second, putting $j$ in front gives one of length at most $k + 1$ . Conversely, let a walk of length $m \le k + 1$ from $j$ to $i$ be given. If $m \le k$ , take $l = j$ . If $m = k + 1 \ge 1$ , take $l$ to be its second vertex, so that $j \to l$ is an edge and the rest of the walk has length $k$ . This proves the lemma.

For the matrix drawn above, $\mathbf{A}^2 = \begin{psmallmatrix} 0 & 0 & 2 \\ 3 & 0 & 1 \\ 3 & 6 & 1 \end{psmallmatrix}$ . Its $(1, 1)$ entry is $0$ , and indeed the shortest walk from $1$ back to $1$ is $1 \to 3 \to 2 \to 1$ , of length $3$ . Its $(1, 3)$ entry is $2$ , from the walk $3 \to 2 \to 1$ .

A long walk can always be shortened to a path, and a path is short.

Lemma 19.2.2 (Shortening a Walk to a Path)

Let $\mathbf{A} \in M_n(F)$ . If $G(\mathbf{A})$ has a walk from $j$ to $i$ , then it has a path from $j$ to $i$ , and every path has length at most $n - 1$ .

Idea. Take a shortest walk. If it visited some vertex twice, the loop between the two visits could be cut out, leaving a shorter walk; so a shortest walk is a path. A path visits distinct vertices, and there are only $n$ of them.

Proof. Among the walks from $j$ to $i$ , choose one of least length $k$ (Theorem 0.2.11), say $j = i_0, i_1, \dots, i_k = i$ . Suppose two of its vertices coincide, $i_s = i_t$ with $s < t$ . Deleting $i_{s+1}, \dots, i_t$ leaves the list $i_0, \dots, i_s, i_{t+1}, \dots, i_k$ , which is still a walk, because the edge $i_t \to i_{t+1}$ (if $t < k$ ) is the edge $i_s \to i_{t+1}$ . It has length $k - (t - s) < k$ , contradicting the choice of $k$ . So the vertices are distinct, and the walk is a path. A path of length $k$ has $k + 1$ distinct vertices among the $n$ vertices of $G(\mathbf{A})$ , so $k + 1 \le n$ .

19.2.2. Strong connectivity

Positivity of $\mathbf{A}$ says every vertex has an edge to every vertex. The useful weakening is to ask only for a walk.

A graph is strongly connected when every vertex can be reached from every vertex.

Definition 19.2.2 (Strongly Connected)

Let $\mathbf{A} \in M_n(F)$ . The graph $G(\mathbf{A})$ is strongly connected if, for every ordered pair $(j, i)$ of vertices, there is a walk from $j$ to $i$ .

In words: whichever vertex we start from, every vertex can be reached, and the pair is ordered, so a walk from $j$ to $i$ and a walk from $i$ back to $j$ are both required. By Lemma 19.2.2, the walks may be taken to be paths of length at most $n - 1$ . For $n = 1$ the walk of length $0$ suffices, so the graph of every $1 \times 1$ matrix, $\mathbf{O}_1$ included, is strongly connected.

The cycle $\mathbf{C}$ above is strongly connected: from any vertex, follow the arrows round. So is the graph drawn above, since it contains the cycle $1 \to 3 \to 2 \to 1$ , and so is the graph of every positive matrix. The path is not: there is no walk from $3$ to $1$ . Removing one edge from the cycle, by changing $c_{13} = 1$ to $0$ , gives exactly the path, so the clause that fails is the one for the pair $(3, 1)$ ; the walks from $1$ to $2$ , from $1$ to $3$ , and from $2$ to $3$ survive.

19.2.3. Irreducible matrices

Now the notion this chapter is built on. We want to single out the matrices whose eigenvalue problem cannot be split into two smaller ones. For a matrix with a zero block in the lower left, it can: $\mathbf{A} = \begin{pmatrix} \mathbf{B} & \mathbf{C} \\ \mathbf{O} & \mathbf{D} \end{pmatrix} \quad\Longrightarrow\quad p_{\mathbf{A}} = p_{\mathbf{B}}\,p_{\mathbf{D}} ,$ by Theorem 7.8.4 applied to $x\mathbf{I} - \mathbf{A}$ , and the subspace spanned by the first few standard basis vectors is mapped into itself. For such a matrix Perron’s conclusions fail in general: $\mathbf{I}_2$ and $\operatorname{diag}(2, 1)$ are of this shape. In this chapter a change of basis must preserve nonnegativity, and the ones that do so while keeping the entries themselves are the relabelings of the coordinates. So the definition asks whether a relabeling produces the zero block.

A matrix is irreducible if no relabeling of the coordinates puts it in block upper triangular form.

Definition 19.2.3 (Irreducible Matrix)

Let $\mathbf{A} \in M_n(F)$ .

(a) For $n \ge 2$ , $\mathbf{A}$ is reducible if there are a permutation matrix $\mathbf{P}$ and an integer $k$ with $1 \le k \le n - 1$ such that $\mathbf{P}^{\top}\mathbf{A}\mathbf{P} = \begin{pmatrix} \mathbf{B} & \mathbf{C} \\ \mathbf{O} & \mathbf{D} \end{pmatrix}, \qquad \mathbf{B} \in M_k(F),\ \mathbf{D} \in M_{n-k}(F) ,$ with $\mathbf{O}$ the $(n - k) \times k$ zero matrix. It is irreducible if it is not reducible.
(b) For $n = 1$ , every matrix $(a) \in M_1(F)$ is irreducible, including $\mathbf{O}_1$ .

In words: by Lemma 3.4.7 (b), $\mathbf{P}^{\top} = \mathbf{P}^{-1}$ , so $\mathbf{P}^{\top}\mathbf{A}\mathbf{P}$ is similar to $\mathbf{A}$ . It is the matrix of $T_{\mathbf{A}}$ in the standard basis taken in another order, and in (a) we ask whether some order has a zero block below the diagonal with both diagonal blocks nonempty, which is what $1 \le k \le n - 1$ says. Irreducible means that no order does. Clause (b) is a convention, justified below.

To see what relabeling does to the entries, we compute it once.

Lemma 19.2.3 (Relabeling the Coordinates)

Let $\sigma \in S_n$ and $\mathbf{A} \in M_n(F)$ . Then $(\mathbf{P}_\sigma^{\top}\mathbf{A}\mathbf{P}_\sigma)_{st} = a_{\sigma(s)\sigma(t)}$ for all $s, t$ . Consequently $t \to s$ is an edge of $G(\mathbf{P}_\sigma^{\top}\mathbf{A}\mathbf{P}_\sigma)$ if and only if $\sigma(t) \to \sigma(s)$ is an edge of $G(\mathbf{A})$ .

Proof. By Definition 3.4.2, $\mathbf{P}_\sigma\mathbf{e}_t = \mathbf{e}_{\sigma(t)}$ . The $(s, t)$ entry of a matrix $\mathbf{M}$ is $\mathbf{e}_s^{\top}\mathbf{M}\mathbf{e}_t$ , so by Theorem 0.9.5, $(\mathbf{P}_\sigma^{\top}\mathbf{A}\mathbf{P}_\sigma)_{st} = \mathbf{e}_s^{\top}\mathbf{P}_\sigma^{\top}\mathbf{A}\mathbf{P}_\sigma\mathbf{e}_t = (\mathbf{P}_\sigma\mathbf{e}_s)^{\top}\mathbf{A}(\mathbf{P}_\sigma\mathbf{e}_t) = \mathbf{e}_{\sigma(s)}^{\top}\mathbf{A}\,\mathbf{e}_{\sigma(t)} = a_{\sigma(s)\sigma(t)} .$ The statement about edges is the statement that one of these entries is nonzero exactly when the other is.

So the graph of $\mathbf{P}_\sigma^{\top}\mathbf{A}\mathbf{P}_\sigma$ is $G(\mathbf{A})$ with the vertex $\sigma(s)$ renamed $s$ . In particular, Definition 19.2.2 holds for one exactly when it holds for the other. The zero block of Definition 19.2.3 becomes a statement about a set of vertices that no edge leaves.

Lemma 19.2.4 (Reducible Means a Set of Vertices With No Exit)

Let $n \ge 2$ and $\mathbf{A} \in M_n(F)$ . Then $\mathbf{A}$ is reducible if and only if there is a set $S \subseteq \{1, \dots, n\}$ with $S \ne \emptyset$ and $S \ne \{1, \dots, n\}$ such that $a_{ij} = 0 \qquad\text{whenever } j \in S \text{ and } i \notin S ,$ that is, such that no edge of $G(\mathbf{A})$ goes from a vertex in $S$ to a vertex outside $S$ .

Idea. The zero block of Definition 19.2.3 sits in the columns of the first $k$ relabeled vertices and the rows of the others. So take $S$ to be the first $k$ vertices in the new order; conversely, given $S$ , choose the order that lists $S$ first. Lemma 19.2.3 translates between the entries and the vertices.

Proof. $(\Leftarrow)$ Let $k$ be the number of elements of $S$ , so $1 \le k \le n - 1$ , and choose $\sigma \in S_n$ listing the elements of $S$ first: $\sigma(1), \dots, \sigma(k)$ are the elements of $S$ and $\sigma(k+1), \dots, \sigma(n)$ the others. For $t \le k < s$ we have $\sigma(t) \in S$ and $\sigma(s) \notin S$ , so by Lemma 19.2.3, $(\mathbf{P}_\sigma^{\top}\mathbf{A}\mathbf{P}_\sigma)_{st} = a_{\sigma(s)\sigma(t)} = 0$ . That is, the lower-left $(n - k) \times k$ block of $\mathbf{P}_\sigma^{\top}\mathbf{A}\mathbf{P}_\sigma$ is zero, and $\mathbf{A}$ is reducible.

$(\Rightarrow)$ Let $\mathbf{P}$ and $k$ be as in Definition 19.2.3 (a). By Definition 3.4.2, $\mathbf{P} = \mathbf{P}_\sigma$ for some $\sigma \in S_n$ . Put $S = \{\sigma(1), \dots, \sigma(k)\}$ , which has $k$ elements, so it is neither empty nor everything. If $j \in S$ and $i \notin S$ , then $j = \sigma(t)$ with $t \le k$ and $i = \sigma(s)$ with $s > k$ , and $a_{ij} = (\mathbf{P}_\sigma^{\top}\mathbf{A}\mathbf{P}_\sigma)_{st} = 0$ because $(s, t)$ lies in the zero block.

The condition says that the coordinate subspace $\operatorname{span}\{\mathbf{e}_j : j \in S\}$ is mapped into itself by $\mathbf{A}$ , since column $j$ of $\mathbf{A}$ is $\mathbf{A}\mathbf{e}_j$ and its entries outside $S$ vanish. So a reducible matrix is one with an invariant subspace spanned by some of the standard basis vectors, other than $\{\mathbf{0}\}$ and $F^n$ , and Theorem 9.1.3 is the source of the block form.

Now some examples, simplest first.

$n = 1$ . Irreducible by (b).
Positive matrices are irreducible: no entry is $0$ , so no set $S$ as in Lemma 19.2.4 exists.
The swap $\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ is irreducible. For $n = 2$ , the candidates are $S = \{1\}$ , which needs $a_{21} = 0$ , and $S = \{2\}$ , which needs $a_{12} = 0$ ; both entries are $1$ . So a matrix may have zeros, even mostly zeros, and be irreducible.
Triangular matrices with $n \ge 2$ are reducible. An upper triangular one already has the block form with $\mathbf{P} = \mathbf{I}$ and $k = 1$ . A lower triangular one, such as the path matrix, is reducible too, by Lemma 19.2.4 with $S = \{n\}$ : column $n$ has its only possible nonzero entry on the diagonal. Reversing the order of the coordinates, $\sigma(s) = n + 1 - s$ , turns the path matrix into $\mathbf{J}_3(0)$ , which is upper triangular.
The zero matrix of size $n \ge 2$ is reducible, and so is $\mathbf{I}_n$ : any $S$ will do.

Nonexample by minimal change. The cycle $\mathbf{C}$ is irreducible, as the next theorem will show. Change its entry $c_{13}$ from $1$ to $0$ : the result is the path matrix, and $S = \{3\}$ now has no exit, because the only nonzero entry of column $3$ outside row $3$ , the entry $c_{13}$ , has become $0$ . That single clause of Lemma 19.2.4 is what changed.

Example (A reducible matrix that does not look it)

Decide whether $\mathbf{A} = \begin{pmatrix} 1 & 0 & 2 \\ 3 & 4 & 5 \\ 6 & 0 & 7 \end{pmatrix}$ is irreducible, and if not, put it in block triangular form.

Solution. Column $2$ has its only nonzero entry in row $2$ , so $S = \{2\}$ has no exit: $a_{12} = a_{32} = 0$ . By Lemma 19.2.4, $\mathbf{A}$ is reducible. Following the proof, list $2$ first: $\sigma(1) = 2$ , $\sigma(2) = 1$ , $\sigma(3) = 3$ . By Lemma 19.2.3, the $(s, t)$ entry of $\mathbf{P}_\sigma^{\top}\mathbf{A}\mathbf{P}_\sigma$ is $a_{\sigma(s)\sigma(t)}$ , so $\mathbf{P}_\sigma^{\top}\mathbf{A}\mathbf{P}_\sigma = \begin{pmatrix} a_{22} & a_{21} & a_{23} \\ a_{12} & a_{11} & a_{13} \\ a_{32} & a_{31} & a_{33} \end{pmatrix} = \begin{pmatrix} 4 & 3 & 5 \\ 0 & 1 & 2 \\ 0 & 6 & 7 \end{pmatrix} .$ Hence $p_{\mathbf{A}}(x) = (x - 4)(x^2 - 8x - 5)$ , and the eigenvalues are $4$ and $4 \pm \sqrt{21}$ . In the graph, vertex $2$ has only a loop leaving it: a chain that reaches state $2$ stays there.

Why this definition, and why every $1 \times 1$ matrix is irreducible. The block form is the matrix picture of an invariant coordinate subspace, and it is exactly what splits $p_{\mathbf{A}}$ into two factors and lets the conclusions of Perron’s theorem fail, as $\mathbf{I}_2$ shows. For $n = 1$ there is no room for two nonempty blocks, and a convention is needed. Some books call $\mathbf{O}_1$ reducible. We call every $1 \times 1$ matrix irreducible because that is the choice that makes the two theorems below true with no exception: the graph of a $1 \times 1$ matrix is always strongly connected, through the walk of length $0$ , and $(\mathbf{I} + \mathbf{A})^{1 - 1} = \mathbf{I} = (1)$ is always positive. The price is paid in §03: the irreducible matrix $\mathbf{O}_1$ has spectral radius $0$ , so the statement there that an irreducible nonnegative matrix has $\rho(\mathbf{A}) > 0$ carries the hypothesis $n \ge 2$ .

Warning. Irreducibility depends only on which entries are zero, never on their size. For every $t \ne 0$ , however small, $\mathbf{A}_t = \begin{pmatrix} 1 & t \\ 1 & 1 \end{pmatrix}$ is irreducible, and for $t > 0$ its eigenvalues $1 \pm \sqrt t$ are distinct, with the positive eigenvector $(\sqrt t, 1)$ for $1 + \sqrt t$ . At $t = 0$ it is lower triangular, hence reducible, and $1$ becomes a double eigenvalue with the eigenvector $\mathbf{e}_2$ only. An entry of $10^{-9}$ and an entry of $10^{9}$ count the same; an entry of $0$ is different in kind. The property is not preserved by powers either: the swap is irreducible and its square is $\mathbf{I}_2$ , which is not.

The first theorem says that irreducibility, defined through relabelings, is exactly strong connectivity of the graph.

Theorem 19.2.5 (Irreducible If and Only If Strongly Connected)

Let $n \ge 1$ and $\mathbf{A} \in M_n(F)$ . Then $\mathbf{A}$ is irreducible if and only if $G(\mathbf{A})$ is strongly connected.

Idea. Both sides are about a set of vertices with no exit. If some vertex $i$ cannot be reached from $j$ , the set of vertices that can be reached from $j$ contains $j$ , misses $i$ , and has no exit, since an exit would reach one more vertex. Conversely, a set with no exit traps every walk that starts inside it.

Proof. If $n = 1$ , both sides hold, by Definition 19.2.3 (b) and the walk of length $0$ . Let $n \ge 2$ . By Lemma 19.2.4 it suffices to show: $G(\mathbf{A})$ fails to be strongly connected if and only if there is a set $S$ , neither empty nor all of $\{1, \dots, n\}$ , from which no edge leaves.

$(\Rightarrow)$ Suppose there are $j$ and $i$ with no walk from $j$ to $i$ . Let $S$ be the set of vertices $l$ such that there is a walk from $j$ to $l$ . Then $j \in S$ , by the walk of length $0$ , and $i \notin S$ . If $l \in S$ and $l \to m$ is an edge, then appending $m$ to a walk from $j$ to $l$ gives a walk from $j$ to $m$ , so $m \in S$ . Hence no edge leaves $S$ .

$(\Leftarrow)$ Suppose no edge leaves $S$ , and choose $j \in S$ and $i \notin S$ . Let $j = i_0, i_1, \dots, i_k$ be any walk from $j$ . Then every $i_t$ lies in $S$ , by induction on $t$ : $i_0 = j \in S$ , and if $i_{t-1} \in S$ , the edge $i_{t-1} \to i_t$ does not leave $S$ , so $i_t \in S$ . Hence no walk from $j$ ends at $i$ , and $G(\mathbf{A})$ is not strongly connected. This proves the theorem.

So the cycle $\mathbf{C}$ is irreducible, and so is the matrix drawn earlier: their graphs are strongly connected. Deciding irreducibility from the definition means looking at $n!$ relabelings; deciding it from the graph means following arrows.

Quick check. Is $\mathbf{M} = \begin{psmallmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{psmallmatrix}$ irreducible? Every row and every column of $\mathbf{M}$ contains a nonzero entry off the diagonal.

Solution. No. The edges of $G(\mathbf{M})$ are $1 \to 2$ , $2 \to 1$ , $3 \to 4$ and $4 \to 3$ , so there is no walk from $1$ to $3$ , and $\mathbf{M}$ is reducible by Theorem 19.2.5. Directly, $S = \{1, 2\}$ has no exit, and indeed $\mathbf{M} = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \oplus \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ is already block diagonal, with $\mathbf{P} = \mathbf{I}$ and $k = 2$ . Having an off-diagonal entry in every row and column is necessary for irreducibility when $n \ge 2$ (Exercise C1), but it is not sufficient.

19.2.4. A test by one matrix power

For a nonnegative matrix, Lemma 19.2.1 turns strong connectivity into positivity of a single matrix, and that is the bridge back to Perron’s theorem.

Theorem 19.2.6 (Irreducibility Through a Power of

\mathbf{I} + \mathbf{A}

)

Let $n \ge 1$ and let $\mathbf{A} \in M_n(\mathbb{R})$ be nonnegative. Then $\mathbf{A}$ is irreducible if and only if $(\mathbf{I} + \mathbf{A})^{n-1} > \mathbf{O} .$

Idea. Read both sides as statements about walks. Positivity of $(\mathbf{I} + \mathbf{A})^{n-1}$ asks for a walk of length at most $n - 1$ between every ordered pair of vertices, and strong connectivity asks for a walk of any length. The two agree because a walk can always be shortened to a path, and a path has at most $n - 1$ edges.

Proof. By Lemma 19.2.1 (b), $(\mathbf{I} + \mathbf{A})^{n-1} > \mathbf{O}$ if and only if, for every ordered pair $(j, i)$ , there is a walk of length at most $n - 1$ from $j$ to $i$ . By Lemma 19.2.2, if there is any walk from $j$ to $i$ then there is one of length at most $n - 1$ , namely a path; so the condition is equivalent to asking for a walk of any length from $j$ to $i$ , for every ordered pair. That is Definition 19.2.2, and by Theorem 19.2.5 it is equivalent to irreducibility.

Both sides always hold for $n = 1$ , as the convention intends. The hypothesis $\mathbf{A} \ge \mathbf{O}$ cannot be dropped: $\begin{pmatrix} -1 & 1 \\ 1 & -1 \end{pmatrix}$ is irreducible, but adding $\mathbf{I}$ cancels its diagonal and leaves the swap, which is not positive. Cancellation is exactly what nonnegativity rules out, since a sum of nonnegative terms is zero only when every term is.

Example (The cycle, by one power)

For the cycle $\mathbf{C} = \begin{pmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}$ , compute $(\mathbf{I} + \mathbf{C})^2$ , and compare with the powers $\mathbf{C}^{k}$ .

Solution. $\mathbf{C}$ is the permutation matrix of $1 \mapsto 2 \mapsto 3 \mapsto 1$ , so $\mathbf{C}^2 = \begin{psmallmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{psmallmatrix}$ and $\mathbf{C}^3 = \mathbf{I}$ by Lemma 3.4.7 (a). As $\mathbf{I}$ and $\mathbf{C}$ commute, $(\mathbf{I} + \mathbf{C})^2 = \mathbf{I} + 2\mathbf{C} + \mathbf{C}^2 = \begin{pmatrix} 1 & 1 & 2 \\ 2 & 1 & 1 \\ 1 & 2 & 1 \end{pmatrix} > \mathbf{O} ,$ so $\mathbf{C}$ is irreducible by Theorem 19.2.6, as the graph already showed. On the other hand every power $\mathbf{C}^{k}$ is $\mathbf{I}$ , $\mathbf{C}$ or $\mathbf{C}^2$ , each with six zero entries, so no power of $\mathbf{C}$ is positive. In the graph, the walks from $j$ have lengths forced modulo $3$ by where they end. The loops of $\mathbf{I} + \mathbf{C}$ let a walk wait, which is what $\mathbf{C}$ alone cannot do. §05 returns to this difference; it is the difference between irreducible and primitive.

The theorem is the reason irreducibility is enough for most of Perron’s conclusions. If $\mathbf{A} \ge \mathbf{O}$ is irreducible, then $\mathbf{B} = (\mathbf{I} + \mathbf{A})^{n-1}$ is positive, so Theorem 19.1.5 applies to $\mathbf{B}$ , and $\mathbf{B}$ is a polynomial in $\mathbf{A}$ , so every eigenvector of $\mathbf{A}$ is an eigenvector of $\mathbf{B}$ . §03 turns this observation into the Perron–Frobenius theorem.

19.2.5. The reducible normal form

A reducible matrix splits into two diagonal blocks, and each block may be reducible again. Splitting until nothing splits gives a normal form.

Theorem 19.2.7 (Reducible Normal Form)

Let $n \ge 1$ and $\mathbf{A} \in M_n(F)$ .

(a) There are a permutation matrix $\mathbf{P}$ and an integer $m \ge 1$ such that $\mathbf{P}^{\top}\mathbf{A}\mathbf{P} = \begin{pmatrix} \mathbf{A}_{11} & \mathbf{A}_{12} & \cdots & \mathbf{A}_{1m} \\ \mathbf{O} & \mathbf{A}_{22} & \cdots & \mathbf{A}_{2m} \\ \vdots & & \ddots & \vdots \\ \mathbf{O} & \cdots & \mathbf{O} & \mathbf{A}_{mm} \end{pmatrix} ,$ block upper triangular, with every diagonal block $\mathbf{A}_{ii}$ square and irreducible.
(b) In that case $p_{\mathbf{A}} = p_{\mathbf{A}_{11}}\,p_{\mathbf{A}_{22}}\cdots p_{\mathbf{A}_{mm}}$ , so the eigenvalues of $\mathbf{A}$ , with their algebraic multiplicities, are those of the diagonal blocks taken together.
(c) $\rho(\mathbf{A}) = \max_i \rho(\mathbf{A}_{ii})$ ; if $\mathbf{A} \ge \mathbf{O}$ , every $\mathbf{A}_{ii} \ge \mathbf{O}$ .

Idea. Strong induction on $n$ : if $\mathbf{A}$ is irreducible there is nothing to do, and otherwise one relabeling gives two smaller diagonal blocks, which the induction hypothesis puts in normal form. The only work is to check that the two relabelings of the blocks combine into one relabeling of $\mathbf{A}$ , and block multiplication does that.

Proof.

(a) Strong induction on $n$ (Theorem 0.2.10). If $\mathbf{A}$ is irreducible, which includes the case $n = 1$ , take $\mathbf{P} = \mathbf{I}$ and $m = 1$ . Otherwise $n \ge 2$ , and there are a permutation matrix $\mathbf{P}_0$ and $1 \le k \le n - 1$ with $\mathbf{P}_0^{\top}\mathbf{A}\mathbf{P}_0 = \begin{pmatrix} \mathbf{B} & \mathbf{C} \\ \mathbf{O} & \mathbf{D} \end{pmatrix}, \qquad \mathbf{B} \in M_k(F),\ \mathbf{D} \in M_{n-k}(F) .$ Both sizes are less than $n$ , so by the induction hypothesis there are permutation matrices $\mathbf{Q}_1 = \mathbf{P}_\alpha$ ( $\alpha \in S_k$ ) and $\mathbf{Q}_2 = \mathbf{P}_\beta$ ( $\beta \in S_{n-k}$ ) such that $\mathbf{Q}_1^{\top}\mathbf{B}\mathbf{Q}_1$ and $\mathbf{Q}_2^{\top}\mathbf{D}\mathbf{Q}_2$ are block upper triangular with square irreducible diagonal blocks. The direct sum $\mathbf{Q} = \mathbf{Q}_1 \oplus \mathbf{Q}_2$ (Definition 8.1.2) is the permutation matrix $\mathbf{P}_\gamma$ of the permutation $\gamma$ with $\gamma(t) = \alpha(t)$ for $t \le k$ and $\gamma(k + q) = k + \beta(q)$ for $q \le n - k$ , since its columns are $\mathbf{e}_{\gamma(1)}, \dots, \mathbf{e}_{\gamma(n)}$ . By Proposition 8.1.2, $\mathbf{Q}^{\top} = \mathbf{Q}_1^{\top} \oplus \mathbf{Q}_2^{\top}$ , and by Theorem 8.1.1, $\mathbf{Q}^{\top}\bigl(\mathbf{P}_0^{\top}\mathbf{A}\mathbf{P}_0\bigr)\mathbf{Q} = \begin{pmatrix} \mathbf{Q}_1^{\top}\mathbf{B}\mathbf{Q}_1 & \mathbf{Q}_1^{\top}\mathbf{C}\mathbf{Q}_2 \\ \mathbf{O} & \mathbf{Q}_2^{\top}\mathbf{D}\mathbf{Q}_2 \end{pmatrix} .$ This is block upper triangular, and its diagonal blocks are those of $\mathbf{Q}_1^{\top}\mathbf{B}\mathbf{Q}_1$ followed by those of $\mathbf{Q}_2^{\top}\mathbf{D}\mathbf{Q}_2$ , all square and irreducible. With $\mathbf{P} = \mathbf{P}_0\mathbf{Q}$ , which is a permutation matrix by Lemma 3.4.7 (a), the left side is $\mathbf{P}^{\top}\mathbf{A}\mathbf{P}$ by Theorem 0.9.5. This proves (a).
(b) $\mathbf{P}^{\top} = \mathbf{P}^{-1}$ by Lemma 3.4.7 (b), so $\mathbf{P}^{\top}\mathbf{A}\mathbf{P}$ is similar to $\mathbf{A}$ , and $p_{\mathbf{A}} = p_{\mathbf{P}^{\top}\mathbf{A}\mathbf{P}}$ by Theorem 7.10.3. The matrix $x\mathbf{I} - \mathbf{P}^{\top}\mathbf{A}\mathbf{P}$ is block upper triangular with diagonal blocks $x\mathbf{I} - \mathbf{A}_{ii}$ . Applying Theorem 7.8.4 over $F[x]$ , as the paragraph after it notes, to the first diagonal block and the rest, and then to the rest by induction on $m$ , gives $p_{\mathbf{A}} = \prod_i p_{\mathbf{A}_{ii}}$ . The roots of a product, with multiplicities, are those of the factors together.
(c) By (b), $\operatorname{spec}(\mathbf{A}) = \bigcup_i\operatorname{spec}(\mathbf{A}_{ii})$ , and the largest modulus over a union is the largest of the largest moduli. If $\mathbf{A} \ge \mathbf{O}$ , then by Lemma 19.2.3 the entries of $\mathbf{P}^{\top}\mathbf{A}\mathbf{P}$ are entries of $\mathbf{A}$ , so they are $\ge 0$ , and so are those of each $\mathbf{A}_{ii}$ .

The diagonal blocks of the normal form correspond to groups of vertices of $G(\mathbf{A})$ that can all reach one another. The first block is a group with no exit, and each later block can send edges only to the blocks before it. In a Markov chain the first block is therefore a set of states that the chain, once inside, never leaves; §06 uses exactly this. The blocks are unique up to their order and up to relabeling within each block, but we shall not need this and do not prove it.

Example (A normal form with three blocks)

Put $\mathbf{A} = \begin{pmatrix} 0 & 0 & 1 & 0 \\ 1 & 2 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 3 \end{pmatrix}$ in reducible normal form, and find $\rho(\mathbf{A})$ .

Solution. Read the edges column by column. Column $1$ gives $1 \to 2$ and $1 \to 3$ ; column $2$ gives the loop $2 \to 2$ ; column $3$ gives $3 \to 1$ and $3 \to 4$ ; column $4$ gives $4 \to 2$ and the loop $4 \to 4$ . So $1$ and $3$ reach each other, and from them one can go to $4$ and then to $2$ , but never back. The groups are $\{2\}$ , $\{4\}$ and $\{1, 3\}$ . Vertex $2$ has no exit, so it comes first; the edges from $4$ go only to $2$ and $4$ , so $4$ comes next; then $1, 3$ . With $\sigma = (2, 4, 1, 3)$ , that is $\sigma(1) = 2$ , $\sigma(2) = 4$ , $\sigma(3) = 1$ , $\sigma(4) = 3$ , Lemma 19.2.3 gives $\mathbf{P}_\sigma^{\top}\mathbf{A}\mathbf{P}_\sigma = \begin{pmatrix} 2 & 1 & 1 & 0 \\ 0 & 3 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix} ,$ with diagonal blocks $(2)$ , $(3)$ and the swap $\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ , each irreducible. By Theorem 19.2.7 (b), $p_{\mathbf{A}}(x) = (x - 2)(x - 3)(x^2 - 1)$ , so the eigenvalues are $2, 3, 1, -1$ , and $\rho(\mathbf{A}) = 3$ , the spectral radius of the second block.

19.2.6. Exercises

A. Check your understanding

Exercise (A1)

(a) Define the directed graph $G(\mathbf{A})$ , a walk, and strong connectivity. Which way does the edge for $a_{ij} \ne 0$ point?
(b) Define irreducible, including the case $n = 1$ , and state Theorem 19.2.6.
(c) True or false: a matrix with a zero entry is reducible. Justify your answer.
(d) True or false: if $\mathbf{A} \ge \mathbf{O}$ is irreducible, then so is $\mathbf{A}^2$ . Justify your answer.
(e) True or false: $\mathbf{A}$ is irreducible if and only if $\mathbf{A}^{\top}$ is. Justify your answer.
(f) True or false: the $2 \times 2$ zero matrix is irreducible. Justify your answer.

Solution.

(a) $G(\mathbf{A})$ has vertices $1, \dots, n$ and an edge $j \to i$ for each $a_{ij} \ne 0$ , pointing from the column index to the row index. A walk of length $k$ from $j$ to $i$ is a list $j = i_0, \dots, i_k = i$ with each $i_{t-1} \to i_t$ an edge. $G(\mathbf{A})$ is strongly connected if there is a walk from $j$ to $i$ for every ordered pair $(j, i)$ .
(b) For $n \ge 2$ , $\mathbf{A}$ is reducible if $\mathbf{P}^{\top}\mathbf{A}\mathbf{P} = \begin{psmallmatrix} \mathbf{B} & \mathbf{C} \\ \mathbf{O} & \mathbf{D} \end{psmallmatrix}$ for some permutation matrix $\mathbf{P}$ and square blocks $\mathbf{B}$ , $\mathbf{D}$ of sizes $k$ and $n - k$ , $1 \le k \le n - 1$ ; irreducible means not reducible. Every $1 \times 1$ matrix is irreducible. The theorem: a nonnegative $\mathbf{A} \in M_n(\mathbb{R})$ is irreducible if and only if $(\mathbf{I} + \mathbf{A})^{n-1} > \mathbf{O}$ .
(c) False. The swap $\begin{psmallmatrix} 0 & 1 \\ 1 & 0 \end{psmallmatrix}$ has two zero entries and is irreducible, since its graph $1 \to 2 \to 1$ is strongly connected (Theorem 19.2.5).
(d) False. The swap is irreducible and its square $\mathbf{I}_2$ is reducible, being triangular.
(e) True. $G(\mathbf{A}^{\top})$ is $G(\mathbf{A})$ with every edge reversed, since $(\mathbf{A}^{\top})_{ij} = a_{ji}$ . Reversing a walk from $j$ to $i$ in $G(\mathbf{A})$ gives a walk from $i$ to $j$ in $G(\mathbf{A}^{\top})$ , so one graph is strongly connected exactly when the other is, and Theorem 19.2.5 finishes.
(f) False. With $n = 2$ , the zero matrix is already upper triangular, so it is reducible with $\mathbf{P} = \mathbf{I}$ , $k = 1$ . Only the $1 \times 1$ zero matrix is irreducible, and that by convention.

B. Practice

Exercise (B1: Deciding irreducibility)

Determine which of the following matrices are irreducible. Justify your answers, and for each reducible one give a permutation matrix that puts it in block upper triangular form.

(a) $\begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}$
(b) $\begin{pmatrix} 1 & 2 & 0 \\ 0 & 3 & 0 \\ 4 & 5 & 6 \end{pmatrix}$
(c) $\begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \end{pmatrix}$
(d) $\begin{pmatrix} 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \end{pmatrix}$

Solution.

(a) The nonzero entries $a_{12}, a_{23}, a_{31}$ give the edges $2 \to 1$ , $3 \to 2$ , $1 \to 3$ : the cycle $1 \to 3 \to 2 \to 1$ , which is strongly connected. Irreducible, by Theorem 19.2.5.
(b) Column $3$ has its only nonzero entry in row $3$ , so $S = \{3\}$ has no exit, and the matrix is reducible by Lemma 19.2.4. With $\sigma(1) = 3$ , $\sigma(2) = 1$ , $\sigma(3) = 2$ , Lemma 19.2.3 gives $\mathbf{P}_\sigma^{\top}\mathbf{A}\mathbf{P}_\sigma = \begin{psmallmatrix} 6 & 4 & 5 \\ 0 & 1 & 2 \\ 0 & 0 & 3 \end{psmallmatrix}$ , which is even triangular.
(c) The edges are $1 \to 4$ (from $a_{41}$ ), $2 \to 1$ and $2 \to 4$ (from $a_{12}, a_{42}$ ), $3 \to 2$ (from $a_{23}$ ) and $4 \to 3$ (from $a_{34}$ ). The walk $1 \to 4 \to 3 \to 2 \to 1$ passes through every vertex and returns, so any vertex reaches any other by following it. Irreducible.
(d) Columns $3$ and $4$ have zeros in rows $1$ and $2$ , so $S = \{3, 4\}$ has no exit: reducible. With $\sigma = (3, 4, 1, 2)$ , $\mathbf{P}_\sigma^{\top}\mathbf{A}\mathbf{P}_\sigma = \begin{psmallmatrix} 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \end{psmallmatrix}$ . The edge $2 \to 3$ goes into $S$ , which is allowed; only edges out of $S$ are forbidden.

Exercise (B2: One power decides)

For each matrix, compute $(\mathbf{I} + \mathbf{A})^2$ and decide whether $\mathbf{A}$ is irreducible. For the reducible one, read off from $(\mathbf{I} + \mathbf{A})^2$ a set of vertices with no exit.

(a) $\mathbf{A} = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}$
(b) $\mathbf{A} = \begin{pmatrix} 1 & 0 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}$

Solution.

(a) $\mathbf{I} + \mathbf{A} = \begin{psmallmatrix} 1 & 1 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \end{psmallmatrix}$ , and multiplying out, $(\mathbf{I} + \mathbf{A})^2 = \begin{pmatrix} 2 & 3 & 2 \\ 2 & 2 & 1 \\ 1 & 2 & 1 \end{pmatrix} > \mathbf{O} .$ Hence $\mathbf{A}$ is irreducible by Theorem 19.2.6.
(b) $\mathbf{I} + \mathbf{A} = \begin{psmallmatrix} 2 & 0 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 1 \end{psmallmatrix}$ , and $(\mathbf{I} + \mathbf{A})^2 = \begin{pmatrix} 4 & 0 & 0 \\ 3 & 2 & 2 \\ 1 & 2 & 2 \end{pmatrix} ,$ which has zero entries, so $\mathbf{A}$ is reducible. By Lemma 19.2.1 (b), column $j$ of $(\mathbf{I} + \mathbf{A})^{2}$ is positive exactly in the rows $i$ reachable from $j$ . Column $2$ is positive in rows $2, 3$ only, so the vertices reachable from $2$ form $S = \{2, 3\}$ , and by the proof of Theorem 19.2.5 no edge leaves it. Indeed $a_{12} = a_{13} = 0$ .

Exercise (B3: Eigenvalues from the normal form)

Let $\mathbf{A} = \begin{pmatrix} 1 & 0 & 2 \\ 1 & 3 & 0 \\ 4 & 0 & 5 \end{pmatrix}$ . Put $\mathbf{A}$ in reducible normal form, and hence find its eigenvalues and $\rho(\mathbf{A})$ .

Solution. The edges are $1 \to 1$ , $1 \to 2$ , $1 \to 3$ (column $1$ ), the loop $2 \to 2$ (column $2$ ), and $3 \to 1$ , $3 \to 3$ (column $3$ ). Vertex $2$ has no exit, and $1$ , $3$ reach each other. List $2$ first: $\sigma(1) = 2$ , $\sigma(2) = 1$ , $\sigma(3) = 3$ . By Lemma 19.2.3, $\mathbf{P}_\sigma^{\top}\mathbf{A}\mathbf{P}_\sigma = \begin{pmatrix} 3 & 1 & 0 \\ 0 & 1 & 2 \\ 0 & 4 & 5 \end{pmatrix} .$ The blocks $(3)$ and $\begin{psmallmatrix} 1 & 2 \\ 4 & 5 \end{psmallmatrix}$ are irreducible, the second because both its off-diagonal entries are nonzero. By Theorem 19.2.7 (b), $p_{\mathbf{A}}(x) = (x - 3)(x^2 - 6x - 3)$ , so the eigenvalues are $3$ and $3 \pm 2\sqrt3$ , and by (c), $\rho(\mathbf{A}) = 3 + 2\sqrt3 \approx 6.46$ , coming from the second block.

C. Going deeper

Exercise (C1: A necessary condition that is not sufficient)

(a) Prove that if $n \ge 2$ and $\mathbf{A} \in M_n(F)$ is irreducible, then every row and every column of $\mathbf{A}$ contains a nonzero entry off the diagonal.
(b) Show that the converse fails for every even $n \ge 4$ .

Solution.

(a) Suppose column $j$ has no nonzero entry off the diagonal: $a_{ij} = 0$ for all $i \ne j$ . Then $S = \{j\}$ has no exit, and $S$ is neither empty nor everything because $n \ge 2$ , so $\mathbf{A}$ is reducible by Lemma 19.2.4. Suppose instead row $i$ has $a_{ij} = 0$ for all $j \ne i$ . Then $S = \{1, \dots, n\} \setminus \{i\}$ has no exit, since the only entries $a_{i'j}$ with $j \in S$ and $i' \notin S$ are the $a_{ij}$ with $j \ne i$ ; again $\mathbf{A}$ is reducible.
(b) Let $n = 2m$ with $m \ge 2$ , and let $\mathbf{M}$ be the direct sum of $m$ copies of the swap $\begin{psmallmatrix} 0 & 1 \\ 1 & 0 \end{psmallmatrix}$ . Every row and column has a $1$ off the diagonal. But $S = \{1, 2\}$ has no exit, since column $1$ and column $2$ are zero outside rows $1, 2$ , so $\mathbf{M}$ is reducible. The Quick check is the case $m = 2$ .

Exercise (C2: The exponent

n - 1

is sharp)

Let $n \ge 2$ and let $\mathbf{C}_n$ be the cyclic permutation matrix with $\mathbf{C}_n\mathbf{e}_j = \mathbf{e}_{j+1}$ for $j < n$ and $\mathbf{C}_n\mathbf{e}_n = \mathbf{e}_1$ .

(a) Prove that $\mathbf{C}_n$ is irreducible, but that $(\mathbf{I} + \mathbf{C}_n)^{n-2}$ is not positive.
(b) Prove that if $\mathbf{A} \ge \mathbf{O}$ is irreducible, then $(\mathbf{I} + \mathbf{A})^{k} > \mathbf{O}$ for every $k \ge n - 1$ .

Solution.

(a) The nonzero entries of $\mathbf{C}_n$ are $(\mathbf{C}_n)_{j+1,j} = 1$ for $j < n$ and $(\mathbf{C}_n)_{1n} = 1$ , so the edges of $G(\mathbf{C}_n)$ are $j \to j + 1$ and $n \to 1$ , and there are no others. Following them from any vertex visits every vertex, so $G(\mathbf{C}_n)$ is strongly connected and $\mathbf{C}_n$ is irreducible (Theorem 19.2.5). Each vertex has exactly one outgoing edge, so the only walk from $1$ of length $m \le n - 1$ is $1 \to 2 \to \dots \to m + 1$ . In particular the shortest walk from $1$ to $n$ has length $n - 1$ , and there is no walk of length at most $n - 2$ from $1$ to $n$ . By Lemma 19.2.1 (b), $\bigl((\mathbf{I} + \mathbf{C}_n)^{n-2}\bigr)_{n1} = 0$ .
(b) By Lemma 19.2.1 (b), $((\mathbf{I} + \mathbf{A})^{k})_{ij} > 0$ exactly when there is a walk of length at most $k$ from $j$ to $i$ . For $k \ge n - 1$ , a walk of length at most $n - 1$ is one of length at most $k$ , and such walks exist for every pair by the proof of Theorem 19.2.6. Hence $(\mathbf{I} + \mathbf{A})^{k} > \mathbf{O}$ .

Exercise (C3: Irreducibility as growth of supports)

Let $n \ge 2$ and $\mathbf{A} \in M_n(\mathbb{R})$ with $\mathbf{A} \ge \mathbf{O}$ . For $\mathbf{x} \ge \mathbf{0}$ , call $\{i : x_i > 0\}$ the support of $\mathbf{x}$ .

(a) Prove that the support of $(\mathbf{I} + \mathbf{A})\mathbf{x}$ is the support $S$ of $\mathbf{x}$ together with every vertex $i$ for which there is an edge $j \to i$ with $j \in S$ .
(b) Prove that $\mathbf{A}$ is irreducible if and only if, for every $\mathbf{x} \ge \mathbf{0}$ with at least one zero entry and at least one positive entry, $(\mathbf{I} + \mathbf{A})\mathbf{x}$ has more positive entries than $\mathbf{x}$ .
(c) Deduce, without using walks, that $(\mathbf{I} + \mathbf{A})^{n-1}\mathbf{x} > \mathbf{0}$ for every nonzero $\mathbf{x} \ge \mathbf{0}$ when $\mathbf{A}$ is irreducible, and hence that $(\mathbf{I} + \mathbf{A})^{n-1} > \mathbf{O}$ .

Hint for (b): use Lemma 19.2.4.

Solution.

(a) $((\mathbf{I} + \mathbf{A})\mathbf{x})_i = x_i + \sum_j a_{ij}x_j$ is a sum of nonnegative terms, so it is positive if and only if $x_i > 0$ or some $a_{ij}x_j > 0$ , that is, $i \in S$ or there is $j \in S$ with $a_{ij} > 0$ , which is an edge $j \to i$ .
(b) Let $\mathbf{x}$ be as stated, with support $S$ , which is neither empty nor everything. By (a), $(\mathbf{I} + \mathbf{A})\mathbf{x}$ has support containing $S$ , and strictly larger exactly when some edge goes from $S$ to a vertex outside $S$ . $(\Rightarrow)$ If $\mathbf{A}$ is irreducible, Lemma 19.2.4 says every such $S$ has an exit, so the support grows. $(\Leftarrow)$ If $\mathbf{A}$ were reducible, take $S$ with no exit from Lemma 19.2.4, and let $\mathbf{x}$ have entry $1$ on $S$ and $0$ elsewhere. Then $(\mathbf{I} + \mathbf{A})\mathbf{x}$ has support exactly $S$ , with the same number of positive entries, contradicting the hypothesis.
(c) Let $\mathbf{x} \ge \mathbf{0}$ , $\mathbf{x} \ne \mathbf{0}$ , and put $\mathbf{x}_k = (\mathbf{I} + \mathbf{A})^{k}\mathbf{x} \ge \mathbf{0}$ . By (a) the supports never shrink, and by (b) the support grows by at least one element at each step until it is everything. It starts with at least one element, so after at most $n - 1$ steps it has $n$ , and then stays so: $\mathbf{x}_{n-1} > \mathbf{0}$ . Applying this to $\mathbf{x} = \mathbf{e}_j$ shows that column $j$ of $(\mathbf{I} + \mathbf{A})^{n-1}$ is positive, for every $j$ .