How does one show a matrix is irreducible and reducible? How does one show a matrix is irreducible and reducible? An example would also be great.
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?
 A: 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.
A: 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.
A: 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. 
A: 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).
A: 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$.


*

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

*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$.

*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}$$
