Irreducible Nonnegative Matrices and Graph Connectivity

From Matrix Entries to Reachability

For a nonnegative matrix, the locations of its positive entries encode directed steps between indices. Irreducibility asks whether those steps allow every index to reach every other one. This makes irreducibility a natural matrix condition for graph theory: in an undirected graph, each edge supplies a step in both directions, so connectedness becomes the corresponding reachability condition.

Throughout, matrices are finite and square, and a nonnegative matrix means a real matrix whose entries are all at least zero. We take its order $n$ to be positive. The directed graphs used below have no loops or multiple arcs unless explicitly stated. For a directed graph, a directed walk follows arcs in their indicated direction; it is strongly connected if every vertex can reach every other vertex by a directed walk.

Definition: A nonnegative $n\times n$ matrix $A$ is reducible if a simultaneous permutation of its rows and columns puts it in block upper triangular form $$ \begin{pmatrix} B&C\\ 0&D \end{pmatrix}, $$ where $B$ and $D$ are square blocks of positive order. A simultaneous permutation means using the same reordering of row and column indices. The matrix is irreducible if it is not reducible.

The zero block condition concerns entries in one direction across the partition of the indices: if the indices are reordered into sets $I$ followed by $J$, the lower-left zero block says $a_{ji}=0$ for every $j\in J$ and $i\in I$. The upper-right block $C$ need not be zero. For order $1$, there is no partition into two nonempty sets, so every nonnegative $1\times1$ matrix is irreducible, including the zero matrix.

Associate to $A$ a directed graph with vertices $1,\ldots,n$ and an arc $i\to j$ exactly when $a_{ij}>0$. In particular, the row index is the starting vertex and the column index is the ending vertex. The graph may have a loop if a diagonal entry is positive. This convention lets matrix multiplication record directed walks.

Theorem: A nonnegative matrix is irreducible if and only if its associated directed graph is strongly connected.

Proof. Let the associated directed graph have vertex set $\{1,\ldots,n\}$. Suppose first that it is strongly connected. If $A$ were reducible, some ordering would give nonempty index sets $I,J$ with $a_{ji}=0$ for every $j\in J$, $i\in I$. Thus no arc goes from $J$ into $I$. Choose $j\in J$ and $i\in I$. Strong connectivity gives a directed walk from $j$ to $i$. Along that walk, the first vertex in $I$ is reached from a preceding vertex in $J$, so an arc from $J$ into $I$ must exist. This contradicts the zero block. Therefore $A$ is irreducible.

Conversely, suppose the directed graph is not strongly connected. There are vertices $u,v$ such that no directed walk goes from $u$ to $v$. Let $I$ be the set of vertices from which $v$ can be reached, allowing a walk of length zero; then $v\in I$ and $u\notin I$, so $I$ is nonempty and proper. Let $J$ be its complement. There can be no arc $j\to i$ with $j\in J$ and $i\in I$, because that arc followed by a walk from $i$ to $v$ would show that $j$ can reach $v$, putting $j$ in $I$. Hence $a_{ji}=0$ for all $j\in J$, $i\in I$. Order $I$ first and $J$ second. The resulting matrix has a zero lower-left block, so $A$ is reducible. This proves both directions. $\square$

A Walk Criterion from Matrix Powers

The reachability interpretation can also be read directly from powers of $A$. For a positive integer $k$, the entry $(A^k)_{ij}$ is a sum over all sequences of $k-1$ intermediate indices. Each summand is a product of $k$ entries of $A$. Since the entries are nonnegative, this entry is positive exactly when at least one such product is positive.

Proposition: For a nonnegative matrix $A$, $(A^k)_{ij}>0$ if and only if its directed graph has a directed walk of length $k$ from $i$ to $j$. Consequently, $A$ is irreducible if and only if, for every pair $i,j$, there is some $k\geq 0$ such that $(A^k)_{ij}>0$, where $A^0$ is the identity matrix.

Proof. For $k=1$, the statement is the definition of an arc. For $k\geq2$, matrix multiplication gives $(A^k)_{ij}=\sum_{i_1,\ldots,i_{k-1}}a_{i i_1}a_{i_1 i_2}\cdots a_{i_{k-1}j}$. Every product in this sum is nonnegative. The sum is positive exactly when at least one product is positive, which holds exactly when all entries along the corresponding sequence of $k$ steps are positive. Those steps are a directed walk from $i$ to $j$. For $k=0$, $A^0$ is the identity, so $(A^0)_{ij}>0$ exactly when $i=j$; this records the length-zero walk. Thus every ordered pair has a directed walk between it exactly when the graph is strongly connected. The preceding theorem identifies this condition with irreducibility. $\square$

The exponent $k$ may depend on the ordered pair. Irreducibility does not say that one particular power has all positive entries, nor that every power does.

Adjacency Matrices and Connected Graphs

For a finite simple undirected graph $G=(V,E)$, order the vertices as $v_1,\ldots,v_n$. Its adjacency matrix $\mathbf{A}(G)$ has entry $1$ in position $i,j$ when $v_iv_j\in E$, and $0$ otherwise. It is nonnegative and symmetric. An undirected edge gives arcs in both directions in the directed graph associated with this matrix.

Theorem: If $G$ is a nonempty finite simple undirected graph, then $\mathbf{A}(G)$ is irreducible if and only if $G$ is connected. A graph is connected when every pair of vertices can be joined by a path; a single-vertex graph is connected.

Proof. Suppose $G$ is connected. For any two vertices $u,v$, a path from $u$ to $v$ gives a directed walk from $u$ to $v$ in the associated directed graph, because each edge gives an arc in either direction. Thus that directed graph is strongly connected, so the matrix is irreducible by the preceding theorem.

Now suppose $G$ is disconnected. Its vertices split into at least two connected components; choose the vertex set $I$ of one component and let $J=V\setminus I$. Both sets are nonempty, and no edge joins a vertex in $I$ to a vertex in $J$. Consequently all adjacency-matrix entries across these two sets are zero. Ordering $I$ first and $J$ second gives a block diagonal matrix, which is block upper triangular with two positive-order diagonal blocks. Hence the adjacency matrix is reducible. If $G$ has just one vertex, its adjacency matrix has order $1$ and is irreducible by definition, in agreement with the stated connectivity convention. $\square$

Worked Example: Testing a Path Graph with Powers

Let $G=(V,E)$ have $V=\{1,2,3,4\}$ and $E=\{12,23,34\}$. In the vertex order $1,2,3,4$, its adjacency matrix is $$ A=\begin{pmatrix} 0&1&0&0\\ 1&0&1&0\\ 0&1&0&1\\ 0&0&1&0 \end{pmatrix}. $$

Multiplying the matrix gives $$ A^2=\begin{pmatrix} 1&0&1&0\\ 0&2&0&1\\ 1&0&2&0\\ 0&1&0&1 \end{pmatrix}, \qquad A^3=\begin{pmatrix} 0&2&0&1\\ 2&0&3&0\\ 0&3&0&2\\ 1&0&2&0 \end{pmatrix}. $$ For example, $(A^2)_{24}=1$ counts the walk $2,3,4$, and $(A^3)_{14}=1$ counts $1,2,3,4$. Adding the identity matrix, $A$, $A^2$, and $A^3$ gives $$ I+A+A^2+A^3=\begin{pmatrix} 2&2&1&1\\ 2&3&2&1\\ 1&2&3&2\\ 1&1&2&2 \end{pmatrix}. $$ Every entry is positive, so for every ordered pair of vertices there is a walk of some length from the first to the second. The power criterion proves that $A$ is irreducible.

Check: the edge sequence $1,2,3,4$ is a path through all four vertices, so $G$ is connected. The adjacency-matrix theorem gives the same conclusion: $A$ is irreducible.

Worked Example: A Disconnected Graph Gives a Reducible Matrix

Let $G=(V,E)$ have $V=\{1,2,3,4\}$ and $E=\{12,34\}$. In the displayed vertex order, $$ A=\begin{pmatrix} 0&1&0&0\\ 1&0&0&0\\ 0&0&0&1\\ 0&0&1&0 \end{pmatrix}. $$

Take $I=\{1,2\}$ and $J=\{3,4\}$. Each entry in the lower-left block, with row in $J$ and column in $I$, is zero. In fact, both off-diagonal blocks are zero, so the matrix is already block diagonal. Its associated directed graph has no walk from vertex $1$ to vertex $3$, for example, and is not strongly connected. Thus $A$ is reducible.

Check: $G$ has two components, $\{1,2\}$ and $\{3,4\}$, with no edge between them. It is disconnected, as the adjacency-matrix theorem predicts.

Worked Example: A Strongly Connected Directed Graph

Consider the directed graph with vertex set $V=\{1,2,3\}$ and arcs $1\to2$, $2\to3$, and $3\to1$. Its adjacency matrix, with rows as starting vertices, is $$ A=\begin{pmatrix} 0&1&0\\ 0&0&1\\ 1&0&0 \end{pmatrix}. $$

The directed walks around the cycle show reachability in both directions between every pair. The powers display the same fact: $$ A^2=\begin{pmatrix} 0&0&1\\ 1&0&0\\ 0&1&0 \end{pmatrix}, \qquad A^3=\begin{pmatrix} 1&0&0\\ 0&1&0\\ 0&0&1 \end{pmatrix}. $$ Therefore $$ I+A+A^2=\begin{pmatrix} 1&1&1\\ 1&1&1\\ 1&1&1 \end{pmatrix}. $$ For every ordered pair $i,j$, one of $I,A,A^2$ has a positive $i,j$ entry. By the walk criterion, the matrix is irreducible.

Check: $A^3=I$, so $A^3$ does not have every entry positive. This does not conflict with irreducibility: the criterion permits the length of the witnessing walk to vary with the ordered pair.

Why the Connectivity Condition Matters

For an undirected graph, connectedness is exactly the hypothesis that makes its adjacency matrix irreducible. This is why connectivity is the graph condition used when applying Perron–Frobenius theory to adjacency matrices in the next stage of spectral graph theory. The matrix condition also applies to directed graphs and to nonnegative matrices that are not adjacency matrices, where the relevant idea remains directed reachability.

Irreducibility is a statement about which entries are positive and how their positions link indices. It is not a statement that entries are large, that the matrix is symmetric, or that all entries are positive. A connected graph can have many zero entries in its adjacency matrix; those zeros simply record nonedges.

Common Pitfall: Nonzero Rows Do Not Ensure Irreducibility

Consider the nonnegative matrix $$ M=\begin{pmatrix} 0&1&0\\ 1&0&0\\ 0&0&1 \end{pmatrix}. $$ Every row and every column has a nonzero entry, but the third index has no connection to the first two in either direction. The displayed matrix is already block diagonal, with blocks of orders $2$ and $1$, so it is reducible. Checking only that rows and columns are nonzero is therefore insufficient; irreducibility requires reachability between every ordered pair of indices.

The same care applies to graph adjacency matrices. Seeing that each vertex has at least one neighbor does not establish connectedness: a graph can have several components, each containing edges. To prove irreducibility, establish reachability between every pair, or use the connectedness theorem for an undirected graph.

Check Your Understanding

Use the definitions and criteria in this tutorial to answer the following questions.

Write the adjacency matrix of the graph with $V=\{a,b,c\}$ and $E=\{ab,bc\}$, then explain why it is irreducible.
For a nonnegative matrix $A$, what does a positive entry $(A^k)_{ij}$ tell you about the associated directed graph?
Explain why a block diagonal matrix with two positive-order blocks is reducible.
Can an irreducible matrix have a power that is not entrywise positive? Use the directed 3-cycle example to justify your answer.
Prove that the adjacency matrix of a graph with an isolated vertex and at least one other vertex is reducible.