Matrix irreducibility. Strongly connected graph

Question

I have this theorem from Combinatorial Matrix Theory written by Richard A. Brualdi and others.

Let $A$ be a matrix of order $n$. Then $A$ is irreducible if and only if its digraph $D$ is strongly connected.

However, a friend showed me the following example

$\left[\begin{array}{ccc} 0 &1& 0\\ 0 &0 &1\\ 1 &0& 0 \end{array}\right] $ and its associated graph goes as follows:

$1\to2\to3\to1$

which is strongly connected. However, the matrix turns out to be reducible (in particular I can not have a strictly positive matrix power)

Any ideas whats going wrong here?

Answer 1

Let $$A = \left[\begin{array}{ccc} 0 &1& 0\\ 0 &0 &1\\ 1 &0& 0 \end{array}\right],$$ then $$ A^1 = \left[\begin{array}{ccc} 0 &1& 0\\ 0 &0 &1\\ 1 &0& 0 \end{array}\right]\quad A^2 = \left[\begin{array}{ccc} 0 &0& 1\\ 1 &0 &0\\ 0 &1& 0 \end{array}\right]\quad A^3 = \left[\begin{array}{ccc} 1 &0& 0\\ 0 &1 &0\\ 0 &0& 1 \end{array}\right], $$ so for every pair $\langle i,j \rangle$ there is a power $m$ such that $(A^m)_{i,j} > 0$ and the matrix is irreducible. However, this is not a magical statement, worded in graph-theoretic form we have

for every pair $\langle i,j \rangle$ there is a length $m$ such that there is a directed path of length $m$ between $i$ and $j$

and this is true only if the graph is strongly connected. Moreover, take a reducible matrix $B$:

$$B = \left[\begin{array}{ccc} B_1 &B_2\\ 0 &B_3 \end{array}\right]$$

and consider its corresponding graph. Observe that there is no edge from vertices of block $B_3$ to vertices of block $B_2$. In other words, once you get to $B_2$, there is no way out, in particular the graph cannot be strongly connected.

I hope this helps $\ddot\smile$

Answer 2

As the previous answer said correctly, the matrix is irreducible. Perhaps you did not noticed that not all irreducible matrix are aperiodic. Some of them (like your example) are cyclic. Please see here for an example

Thanks.