**Remark 1**. a_{ij}^{(k)} > 0 if and only if there exist j_{1},...,j_{k-1} such that a_{ij1}a_{j1j2} ··· a_{jk-1j} > 0.

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

This leads to another necessary and sufficient condition for irreducibility, namely that the boolean sum A + ··· A^{n} 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 a_{1},a_{2},... be a sequence of positive integers with gcd equal to d.

Let d_{n} = gcd(a_{1},...,a_{n}). Then d_{n+1} ≥ d_{n}. Hence there exist an m such that d_{n} = d_{m} if n ≥ m. Then d_{m} = 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 {n_{1},...,n_{s}} of T with greatest common divisor 1.

Then there exist integers {c_{1},...,c_{s}} such that

c_{1}n_{1}+ ···+c_{s}n_{s} = 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 | a_{ii}^{(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 a_{ii}^{(m)} > 0 and a_{ii}^{(n)} > 0.

Then

a_{ii}^{(m+n)} = &sum_{k}a_{ik}^{(m)}a_{ki}^{(n)} ≥ a_{ii}^{(m)}a_{ii}^{(n)} > 0.

4. Proof of d(i)=d(j) (Seneta, page 17.)

Let t_{ij}^{(M)} > 0 and t_{ji}^{(N)} > 0. Then for any positive integer s such that t_{jj}^{(s)} > 0,

t_{ii}^{(M + s + N)} ≥ t_{ij}^{(M)} t_{jj}^{(s)} t_{ji}^{(N)} > 0.

t_{ii}^{(M + 2s + N)} > 0.

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 A^{k} is 1.

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

L_{i} = {t | a_{ii}^{(t)} > 0}.

L = ∪_{i}L_{i} = {t | ∃ a circuit of length t}.

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

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

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

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

gcd(L^{′}) = gcd(L^{″}) = gcd(L) = d.