Next: Frequency Analysis Up: Spectral Analysis of Markov Previous: Spectral Analysis of Markov

## Perron's Formula

Perron's Formula expresses the elements ai j(n) of the n-th power An of a square matrix A in terms of the eigenvalues and minor determinants of A. An eigenvalue with multiplicity of A is a root with multiplicity of the characteristic polynomial2.3 , where Im is the identity matrix. Denote the minor of a matrix A which arises from deleting the i-th row and j-th column by Ai j and denote the so-called minor of the determinant which equals (-1)i+j times the determinant of the minor of by . Note the correct order of i and j in the latter definition. From [49, p. 16] we cite the following theorem:

Theorem 2.15 (Perron's Formula)   Let be the eigenvalues of a matrix A with multiplicities , respectively. Define for every a polynomial of degree by . Then for all , and for all ,

As we will see below, Perron's formula is particularly useful if the matrix A has a maximal eigenvalue with multiplicity 1 and if all other eigenvalues satisfy . This justifies the following definition and lemma which we cite from [49, pp. 21 and 46].

Definition 2.10   A chain is called regular if has a maximal eigenvalue with multiplicity 1 and all other eigenvalues satisfy . The chain is called positively regular if, in addition, all the numbers Pj are strictly positive.

Lemma 2.16   A chain is regular (positively regular) if and only if there exists an integer nsuch that for at least one (for all ) and for all the probability p(n)i j>0. If a regular chain is irreducible, it is positively regular.

For a proof see [49, Theorem 14.I and 14.II]. The next corollary, which follows trivially from the definitions of irreducibility and aperiodicity, gives an important class of positively regular chains.

Corollary 2.17   Irreducible aperiodic chains are positively regular.

By Corollary 2.17 the transition matrix of an irreducible aperiodic chain has an eigenvalue with multiplicity 1and satisfies for all . In this case, Perron's formula for the n'th power of assumes the following form, see [49, p. 19]:

 (2.6)

where

 (2.7)

Here as since the remaining term

 (2.8)

tends to zero on behalf of , , see [49, p. 21].

Since the irreducible aperiodic chain has a finite state space here, we already know from Lemma 2.8 that for all pairs of states the n'th order transition probabilities p(n)i j tend to the probabilities Pj of the stable distribution , i.e. it holds . By Lemma 2.7, the stable distribution is representable as Pi = 1/Ei[Ti]. Thus we get the following two representations for the stable distribution :

 (2.9)

Moreover, in [49, Chapter 3] it is shown that (2.7) also represents the stable distribution in the case of a periodic irreducible chain although the remaining term (2.8) will not tend to zero in this case due to the existence of eigenvalues with , recall Theorem 2.14.

Next: Frequency Analysis Up: Spectral Analysis of Markov Previous: Spectral Analysis of Markov
Stefan Wegenkittl
1998-05-19