How does one show a matrix is irreducible and reducible?

Solution 1:

A square matrix is reducible iff the associated directed graph has smaller strongly connected components. So you may use a strong component algorithm to solve your problem.

Solution 2:

There is another simple criterion for the irreducibility of a matrix with nonnegative entries. Such an $n\times n$-matrix $A$ is irreducible if and only if all entries of $$\sum\limits_{i=0}^{n}A^i$$ are greater than $0$.

Since I do not have a reference, I will briefly sketch a proof, using the definition that $A$ is irreducible iff for all indices $i,j$ there is an exponent $e_{i,j}$, such that entry $[A^{e_{i,j}}]_{ij}$ is positive (where $[C]_{ij}$ denotes the entry at $i,j$ of a matrix $C$).

Let $B$ be the matrix obtained from $A$ by replacing all non zero entries by $1$.

1. Show that $A$ is irreducible iff B is irreducible.

2. Show that $\sum\limits_{i=0}^{n}A^i$ has only positive entries iff this is true for $\sum\limits_{i=0}^{n}B^i$.

3. Let $G$ be the directed graph with vertices $\{1,2,\ldots,n\}$, where there is an edge from $i$ to $j$ iff $b_{ij}>0$. Show, by induction on $m$, that the entry of $[B^m]_{ij}$ corresponds to the number of directed paths from $i$ to $j$.

According to 3., for $m\in\mathbb{N}$ the number of directed paths from $i$ to $j$ of length at most $m$ is $\left[\sum\limits_{k=0}^mB^k\right]_{ij}$. Now the claim follows form the following equivalences: $$\begin{array}{rl} &\text{$B$ is an irreducible matrix.}\\ \Leftrightarrow&\text{For all $i,j\in\{1,2,\ldots,n\}$, there is a directed path in $G$ from $i$ to $j$.}\\ \Leftrightarrow&\text{For all $i,j\in\{1,2,\ldots,n\}$, there is a directed path in $G$ from $i$ to $j$ of length at most $n$}\\ &\text{(note that this graph has exactly $n$ vertices).}\\ \Leftrightarrow&\text{For all $i,j\in\{1,2,\ldots,n\}$ holds $\left[\sum\limits_{k=0}^{n}B^k\right]_{ij}>0$.} \end{array}$$

Solution 3:

A theorem may help you:

Let $A ∈ M_n$. The following are equivalent:
(a) A is irreducible.
(b) $(I + |A|)^{n-1} > 0$.
(c) $(I + M(A))^{n−1} > 0$.
(d) $\Gamma(A)$ is strongly connected.

It is Theorem 6.2.24 in Matrix Analysis, 2nd edition. Go check it if you need a complete proof.

Solution 4:

The best place to look is this wiki link. To add to the other answer, another equivalent condition is that for every index $[i,j]$, there should be a $m$ such that $(A^m)_{ij}>0$ which is naturally satisfied if the matrix entries are all positive. If it is non-negative, then one needs to check other things.

Solution 5:

Let $A=[a_{i,j}]\in M_n(\mathbb{R})$ and $|A|=[|a_{i,j}|]$. $A$ is irreducible IFF $|A|$ is too. Then we may assume that the $a_{i,j}$ are $\geq 0$. We have a look at the complexity of the problem: "decide whether $A$ is irreducible or not".

Of course, we do not look for a permutation of the basis vectors that triangularizes $A$ (the complexity is $O(n!)$).

We can use the test (cf. Renko Usami) $(I+A)^{n-1}>0$. Yet, the complexity is $O(n^3\log(n))$.

The best is to use the "strong component algorithm" (cf user1551). Its complexity is $O(n)$ (that is extraordinary fast, even for a $10^6\times 10^6$ matrix).