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 Ak 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 Cr = {j | a1j(dn+r) > 0 for some n ≥ 0}. Then

  1. Cr = Cs if r ≡ s (mod d).
  2. The cyclic classes C0,...,Cd-1 partition {1,2,...,n}.
  3. Also if aij > 0 and i ∈ Cr, then j ∈ Cr+1. (This follows as a1j(n+1) ≥ a1i(n)aij).
Consequently if Cr = {ir 1,...,ir nr} and P is the permutation matrix whose columns are i0 1,...,i0 n0, ...,id-1 1,...,id-1 nd-1, then permuting the rows and columns of A will convert it to cyclic form PtAP:

0A0······0
00A1···0
············0
00······Ad-2
Ad-10···00

Then PtAdP = B0 ⊕ ··· ⊕ Bd-1, a direct sum of primitive matrices.
We find the cyclic classes Cr and the cyclic form as follows:
Define row vectors u1,...,ud: u1 is the first row of A, ur+1 = urA, 1 ≤ r < d.

We update uu1=u1,...,uud=ud by forming boolean sums uu1→uu1⊕ud+1,uu2→uu2⊕ud+2,...
until the boolean sum of the uur consists entirely of 1's.
Then Cr = {j | uur[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

VERBOSE
NON-VERBOSE

Last modified 9th May 2006
Return to main page