# Matrix irreducibility. Strongly connected graph

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?

• The matrix is irreducible. "I can not have a strictly positive matrix power". What matrix power? It's not $A$ that matters, it's $A+I$. – Git Gud May 25 '15 at 12:07
• I studied in class that if a positive matrix A (entries >=0) is irreducible (can be transformed in an upper-triangular form with permutation matrices) then there exist p > 0 for which A^p is strictly positive (entries > 0). I dont get then why you suggest powers of A+I. – Javier May 25 '15 at 13:12
• See 8.3.5 on page 672 here. Also note that $A^3$ is the identity matrix (triangular superior), so by definition $A$ is irreducible. – Git Gud May 25 '15 at 13:22
• According to the definition A is reducible precisely because A^3 is the identitity because you can divide your matrix leaving two zeros down – Javier May 25 '15 at 14:27
• @Rodrigo Check out the link from Git Gud, there's a really good explanation there. – dtldarek May 25 '15 at 14:45

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$

• so what would be your definition of irreducible matrix then? – Javier May 25 '15 at 13:18
• @Rodrigo See here. Matrix is reducible if it can be represented in block-upper-triangular form. The condition with $A^m$ is about irreducible matrix (no block-upper-triangular form). – dtldarek May 25 '15 at 14:23

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.