Algorithms to determine irreducibility of a Markov chain wanted. As long as transition matrices are reasonably small, one can draw diagrams and see all there is to see. But in real life problems where the transition matrix could be of considerable size, are there algorithms to decide if a matrix is irreducible and if it is not, what are the closed subclasses?
I am aware that softwares like Mathematica or Matlab can do this and thus there surely is some algorithm to do it.
I thought that computing the eigenvalues of the transition matrix would work in not only detecting whether a Markov chain is irreducible or, if it is not, how many classes it has.
However, this seems to work, but not 100% of the times. It works if the matrix is truly irreducible (one eigenvalue = 1) or if the chain can be partitioned in $d $ closed classes (eigenvalue 1 has multiplicity $d $).  But it does not seem to work for all cases. For instance consider this transition matrix:
$$ P= \begin{pmatrix} 0 & 0.2 & 0.8 & 0 \\ 0.3 & 0.1 & 0 & 0.6 \\ 0.5 & 0 & 0 & 0.5 \\ 0 & 0 & 0 & 1 \end{pmatrix}
$$
which is built on purpose to have one absorbing state and transient and recurrent states. To me it is clear that this Markov chain is not irreducible, the communicating classes are  $\{1,2,3\} $ and $\{4\} $  with the latter being recurrent and the former transient. However, when I compute the eigenvalues for $P $ only one eigenvalue = 1.
Hence the question: what algorithm can specifically determine whether a transition matrix is associated with an irreducible Markov chain or not?
 A: The easiest approach is to count the number of strongly connected components in the transition graph (which for a Markov chain with $n$ states can be done easily in $O(n^2)$ time using e.g. Kosaraju's algorithm.)
You can then collapse each strongly connected component into a single vertex and look at the edges between components to classify the classes into transient vs. recurrent.
Probing the spectral properties of the transition matrix is not really the best way to go about determining irreducibility, since the spectrum of a matrix is invariant under conjugation by arbitrary matrices and the property of being a permutation of a block-diagonal matrix is not.
What you can say is that if a Markov chain is decomposable into $k$ recurrent classes, then there exists a set of $k$ mutually-orthogonal left eigenvectors of $P$ all of which are binary vectors and all of which have eigenvalue 1. But computing a spectral decomposition will not necessarily give you this set of eigenvectors. Even for instance for the trivial Markov process
$$P = \begin{bmatrix}1 & 0 \\ 0 & 1\end{bmatrix}$$
you might get $v_1 \propto (1,1), v_2 \propto (1,-1)$ as your eigenbasis rather than the desired $v_1 = (1,0), v_2 = (0,1)$.
