Criteria and algorithms for irreducibility and aperiodicity of nonnegative matrices (Q1801768)

To any nonnegative \(k \times k\) matrix \(A = [a_{ij}]\) a directed graph \(G(A)\) is associated as follows: to any positive entry \(a_{ij}\) of \(A\) it corresponds a vertex of \(G(A)\); for two vertices \(a_{ij}\) and \(a_{pm}\) there exists a directed arc if \(j=p\). Two criteria are given in this framework: 1) The matrix \(A\) is irreducible iff \(G(A)\) has a directed loop running through all vertices. 2) \(A\) is aperiodic (primitive) iff \(A\) is irreducible and \(G(A)\) has two directed loops whose lengths are coprime. A consequence of these criteria is the possibility of constructing feasible algorithms to determine if a nonnegative matrix is irreducible or primitive.