Register to reply

Perron formula for matrix powers

by bpet
Tags: formula, matrix, perron, powers
Share this thread:
bpet
#1
Oct13-10, 08:12 AM
P: 523
The following interesting result popped up in an old probability textbook (without proof or citations) and I'm curious to know how it can be derived.

The elements [tex]p_{ij}^{(n)}[/tex] of matrix [tex]P^n[/tex] (size m) are also determined by the Perron formula

[tex]p_{ij}^{(n)} = \sum_{s=1}^r \frac{1}{(v_s-1)!}\left\{\frac{d^{v_s-1}}{d\lambda^{v_s-1}}\left[\frac{\lambda^nA_{ji}(\lambda)(\lambda-\lambda_s)^{v_s}}{|\lambda I_m-P|}\right]\right\}_{\lambda=\lambda_s}[/tex]

where [tex]r[/tex] is the number of distinct eigenvalues, [tex]\lambda_s[/tex] are the distinct eigenvalues with multiplicity [tex]v_s[/tex] (so [tex]v_1+\ldots+v_s=m[/tex]) and [tex]A_{ji}(\lambda)[/tex] is the cofactor of the elements [tex]\lambda\delta_{ji}-p_{ji}[/tex] in the determinant [tex]|\lambda I_m-P|[/tex] and [tex]I_m[/tex] is the identity matrix of the same size as P.
It seems to work for any matrix (not just Markov transition probabilities) and as far as I can tell it's not related to the Perron formula of number theory.

The term [tex]A_{ji}(\lambda)/|\lambda I_m-P|[/tex] would hint that [tex](\lambda I_m-P)^{-1}[/tex] is involved, so I suspect it's done by finding the Laplace transform of [tex]e^{tP}[/tex] and somehow extracting the nth term of the Taylor series. Is this on the right track and if so, how would it be done? In particular, how do they turn the expression into a sum of derivatives at the eigenvalues?
Phys.Org News Partner Science news on Phys.org
Bees able to spot which flowers offer best rewards before landing
Classic Lewis Carroll character inspires new ecological model
When cooperation counts: Researchers find sperm benefit from grouping together in mice
Simon_Tyler
#2
Oct14-10, 09:42 PM
P: 313
Have you managed to derive the formula yet? If I had time I'd love to have a go...

Anyway, I did a little searching and found
http://crypto.mat.sbg.ac.at/~ste/diss/node12.html
There he cites pg 16 of
V. Romanovsky, Discrete Markov Chains.
but I couldn't get a copy of it.
bpet
#3
Oct15-10, 05:23 PM
P: 523
Quote Quote by Simon_Tyler View Post
Have you managed to derive the formula yet? If I had time I'd love to have a go...

Anyway, I did a little searching and found
http://crypto.mat.sbg.ac.at/~ste/diss/node12.html
There he cites pg 16 of
V. Romanovsky, Discrete Markov Chains.
but I couldn't get a copy of it.
Thanks, me neither. I haven't checked the details but think it can be done by finding the residue of [tex]\lambda^n(\lambda I-P)^{-1}[/tex] at [tex]\lambda=\infty[/tex] via Laurent series and partial fraction expansion.

The formula was in Sveshnikov's Problems in Probability (as a "basic formula", not an actual problem). The result might be discussed in Gantmakher's Theory of Matrices or Horn & Johnson's Matrix Analysis, possibly even for more general matrix functions, though I don't have copies of these to check.


Register to reply

Related Discussions
Powers of the Matrix M^n Precalculus Mathematics Homework 14
Matrix powers Calculus & Beyond Homework 6
Matrix powers Precalculus Mathematics Homework 6
Matrix Powers Calculus & Beyond Homework 1
Matrix powers Set Theory, Logic, Probability, Statistics 12