Finite Markov closed-class graph decomposition

Graph convention. For any finite real column-stochastic matrix $P$ on $S=\{1,\dots ,n\}$, the positive-transition graph has a directed edge $j\to i$ exactly when $P_{ij}>0$. This defines the communicating classes and closed classes for real matrices, whether or not their entries can be computed exactly.

Algorithm input. An exact finite real matrix $P\in {\mathbb{R}}^{n\times n}$ with indexed state set $S=\{1,\dots ,n\}$ and $n\ge 1$, represented in an exact arithmetic model that terminates on the required comparisons with zero. If an entry is negative or any column sum differs from one, return invalid-input. Rational entries provide an effective instance of this exact-comparison interface. A rounded input without certified sign and column-sum decisions is outside this procedure's input contract.

Output. A partition of $S$ into the strongly connected components of the directed graph of positive transitions, the list of closed communicating classes, and the remaining transient states.

Procedure. Form the usual row-transition matrix $K=P^{\mathsf{T}}$. Initialize a Boolean relation $R_{ij}$ to true exactly when $i=j$ or $K_{ij}>0$. For $k=1,\dots ,n$, and then for every $i,j$, replace $R_{ij}$ by $R_{ij}\vee (R_{ik}\wedge R_{kj})$. Place $i,j$ in the same component exactly when both $R_{ij}$ and $R_{ji}$ are true. Mark a component $C$ closed exactly when $K_{ij}=0$ for every $i\in C$ and $j\mathrm{\notin }C$. Return the closed components, the nonclosed components, and their state labels in increasing order. The procedure uses finitely many exact comparisons and Boolean updates; no sparse storage format or cost bound is asserted. It is a graph computation under the exact-comparison interface, not a claim that positivity of arbitrary unrepresented real numbers can be decided from rounded approximations.