2
$\begingroup$

Let $A$ be an $n\times n$ matrix of nonnegative entries such that $A_{i1}+A_{i2}+\cdots+A_{in}=1$ for all $i\in\{1,2,\ldots,n\}$. What does $A$ have to satisfy so that the sequence

$M_m=\frac1m(I+A+A^2+\cdots+A^{m-1})$

converge?

I believe this converges for almost all $A$. It should converge to a matrix $M$ such that $MA=M$ and $M_{i1}+M_{i2}+\cdots+M_{in}=1$ for all $i\in\{1,2,\ldots,n\}$. I am pretty sure all of the rows of $M$ are equal most of the time, but I haven't found a rigorous proof. For what I need, I'm interested in something like $|M_m-M|<\epsilon\ll 1$ (for some norm $|\cdot|$, taxicab norm preferred). Thanks in advance!

  • 0
    @NateEldredge This also seems to be some type of Ergodic Theorem for Dynamical Systems.2011-11-20

1 Answers 1

5

Your matrix is stochastic, if it is also primitive then the largest eigenvalue is $1$, and all the other eigenvalues satisfy

$ | \lambda | <1 \,.$

What you need is $\#5$ from here: Properties of Perron-Frobenius Eigenvalue

What is says is the following:

Let $A$ be any primitive matrix and $r$ be the Perron-Frobenius eigenvalue (in your case $r=1$).

Then

$\frac{1}{m} \sum_{i=0}^m \frac{A^i}{r^i} \to vw^t$

where $v,w$ are the left and right PF-eigenvectors normalized by $w^t v=1$.

There is a reference to this result....

P.S. In order to be Primitive, all entries need to be positive. If this doesn't happen, just check the section "Perron projection as a limit: $A^k/r^k$", it actually have the idea of the proof of this result under pretty general settings....

  • 0
    edited, that's why I added the part about primitivity at the end, but forgot to change in the beginning...2011-11-20