# How does one show a matrix is irreducible and reducible?

How does one show a matrix is irreducible and reducible? Please explain and an example would be great as well.

I know that a matrix is reducible if and only if it can be placed into block upper-triangular form. How do you find block upper-triangular form?

-
Maybe you can remind us --- what does irreducible mean, in the context of matrices? what does reducible mean? – Gerry Myerson Feb 27 '13 at 2:01

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.

-
Please what is an associated directed graph of a matrix? – npisinp Apr 11 '14 at 14:04
@npisinp Let the matrix in question be $A$ and let $B=(b_{ij})$ be the matrix such that $b_{ij}=1$ if $a_{ij}\ne0$, and $b_{ij}=0$ if $a_{ij}=0$. Then $B$ is the adjacency matrix of a directed graph, and $A$ is reducible iff this directed graph has proper strongly connected components. – user1551 Apr 13 '14 at 12:23

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.

-
In my opinion this answer is a bit broad, because the provided wiki link links to a theorem that uses the irreducibilty of a Matrix. That is, there is no algorithm outlined to solve the reduciblity question. – kiltek Dec 3 '14 at 9:46

There is another simple criterion for the irreducibility of a matrix with non negative 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 then 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}$$

-
Could you site the reference which gives this result ? – Shailesh Mar 18 at 22:09