Definition 1. A non-negative n × n matrix A is irreducible if for all i and j, 1 ≤ i,j, ≤ n, there exists k > 0 depending on i and j, such that aij(k) > 0.

Remark 1. aij(k) > 0 if and only if there exist j1,...,jk-1 such that aij1aj1j2 ··· ajk-1j > 0.

Remark 2. We can assume k ≤ n for without loss of generality we can assume, by coalescing any "cycles", that j1,...,jn-1,j are distinct.

This leads to another necessary and sufficient condition for irreducibility, namely that the boolean sum A + ··· An is positive.

Lemma 1. If T is a set of positive integers with greatest common divisor d, then there exists a finite subset of T for which d is the greatest common divisor.

Proof. Let a1,a2,... be a sequence of positive integers with gcd equal to d.
Let dn = gcd(a1,...,an). Then dn+1 ≥ dn. Hence there exist an m such that dn = dm if n ≥ m. Then dm = d.

Lemma 2. Let T be a non-empty set of positive integers which is closed under addition and which has greatest common divisor d. Then all sufficiently large multiples of d belong to T.

Proof. (From Denumerable Markov Chains, by J.G. Kemeny, J.L. Snell and A.W. Knapp, 1966, page 38.)
Without loss of generality, we can assume d = 1. Also by the previous lemma, there is a finite subset {n1,...,ns} of T with greatest common divisor 1.
Then there exist integers {c1,...,cs} such that

c1n1+ ···+csns = 1.

If we collect the positive terms and the negative terms and note that T is closed under addition, we see that T contains non-negative integers m and n with m - n = 1.
Suppose q ≥ n(n - 1). Then q = an + b, with a ≥ n - 1 and 0 ≤ b ≤ n - 1. Hence

q = (a - b)n + bm

and q ∈ T.

Lemma 3. Let A be an irreducible Markov matrix and let i be a fixed state.
Let T = {k > 0 | aii(k) > 0} and d(i) = gcd{t | t ∈ T}.
d(i) is called the period of state i. It is independent of i and is called the period of A.

Then
(a) T is non-empty and is closed under addition.
(b) T contains all sufficiently large multiples of d(i).

Proof
1. T is non-empty, as A is irreducible.
2. T is closed under addition. For suppose aii(m) > 0 and aii(n) > 0.
Then

aii(m+n) = ∑kaik(m)aki(n) ≥ aii(m)aii(n) > 0.

3.By Lemma 2, all sufficiently large multiples of d(i) belong to T.
4. Proof of d(i)=d(j) (Seneta, page 17.)

Let tij(M) > 0 and tji(N) > 0. Then for any positive integer s such that tjj(s) > 0,

tii(M + s + N) ≥ tij(M) tjj(s) tji(N) > 0.

For such an s we also have tjj(2s) > 0, so that

tii(M + 2s + N) > 0.

Hence d(i) divides (M + 2s + N) - (M + s + N) = s and hence d(i) ≤ d(j).

Reversing the roles of i and j gives d(j) ≤ d(i) and so d(i) = d(j).

Lemma 4. Let A be an irreducible Markov matrix and let d be the period of A.
Then d is the gcd of those k, 1 ≤ k ≤ n, for which the boolean trace of Ak is 1.

Proof. (Kaufmann and Cruon, 180-183). For 1 ≤ i ≤ n. let

Li = {t | aii(t) > 0}.

and

L = ∪iLi = {t | ∃ a circuit of length t}.

Then d = gcd(L).

But a moment's consideration involving elementary circuits, shows that if

L′ = {t | ∃ an elementary circuit of length t},

then gcd(L) = gcd(L′).

Now an elementary circuit must have length not greater than n. Hence if

L″ = {t | ∃ a circuit of length t ≤ n},

then L′ ⊆ L″ ⊆ L and so

gcd(L′) = gcd(L″) = gcd(L) = d.