Periods of Connected Networks and Powers of Nonnegative Matrices
Eric V. Denardo · Mathematics of Operations Research · 1977
Let P be an irreducible N × N matrix having nonnegative entries, and consider the (directed) network containing arc (i, j) if and only if P ij is positive. Theorem 1 expresses the period of this network in terms of any of its arborescences. Theorem 2 shows that if the network's period is one and if node i is contained in a cycle of length n, then the ith row and column of P t are positive for t ≥ (N − 1)n. Theorem 3 shows how to compute the network's period with work proportional to the number of its arcs.