### Finding the period and cyclic classes of an irreducible Markov matrix

Some definitions and lemmas.
Our algorithm for finding the period comes from *Dynamic Programming*, by A. Kaufmann and R. Cruon, Academic Press, NY. 1967:

If A is an irreducible n × n Markov matrix, we replace the non-zero entries by 1's and form the boolean k-th powers of A for 1 ≤ k ≤ n.

Suppose d is the gcd of those k for which the boolean trace of A^{k} is 1.

If d = 1, the matrix is *aperiodic* (or *regular* or *primitive*) and a suitable power of A will be positive.

If d > 1, A is periodic with period d.

(See explanation.)

For each r, we let C_{r} = {j | a_{1j}^{(dn+r)} > 0 for some n ≥ 0}. Then

- C
_{r} = C_{s} if r ≡ s (mod d).
- The cyclic classes C
_{0},...,C_{d-1} partition {1,2,...,n}.
- Also if a
_{ij} > 0 and i ∈ C_{r}, then j ∈ C_{r+1}. (This follows as a_{1j}^{(n+1)} ≥ a_{1i}^{(n)}a_{ij}).

Consequently if C_{r} = {i_{r 1},...,i_{r nr}} and P is the permutation matrix whose columns are i_{0 1},...,i_{0 n0}, ...,i_{d-1 1},...,i_{d-1 nd-1}, then permuting the rows and columns of A will convert it to cyclic form P^{t}AP:

0 | A_{0} | ··· | ··· | 0 |

0 | 0 | A_{1} | ··· | 0 |

··· | ··· | ··· | ··· | 0 |

0 | 0 | ··· | ··· | A_{d-2} |

A_{d-1} | 0 | ··· | 0 | 0 |

Then P^{t}A^{d}P = B_{0} ⊕ ··· ⊕ B_{d-1}, a direct sum of primitive matrices.

We find the cyclic classes C_{r} and the cyclic form as follows:

Define row vectors u_{1},...,u_{d}: u_{1} is the first row of A, u_{r+1} = u_{r}A, 1 ≤ r < d.

We update uu_{1}=u_{1},...,uu_{d}=u_{d} by forming boolean sums uu_{1}→uu_{1}⊕u_{d+1},uu_{2}→uu_{2}⊕u_{d+2},...

until the boolean sum of the uu_{r} consists entirely of 1's.

Then C_{r} = {j | uu_{r}[j] = 1}.
Note: This is a departure from Pullman's algorithm, on page 110, which employs pattern repetition rather than "exhaustion".

See pages 18-22, *Non-negative Matrices and Markov Chains*, Eugene Seneta, Springer 1981.

Also see *Matrix theory and its applications: selected topics*, by N. J. Pullman, Pure and Applied Mathematics **35**, Marcel Dekker 1976

*Last modified 9th May 2006*

Return to main page