Statement
Let $A\in\mathbb{R}^{m\times m}$ be a (row) stochastic matrix.
It is known that the eigenvalues of such matrix lies in the complex unit disk.
Now I am only interested in the eigenvalues that lies on the complex unit circle: $\lvert \lambda \rvert = 1.$
Does its geometric multiplicity $\gamma_A(\lambda)$ equal its algebraic multiplicity $\mu_A(\lambda)$?:
$$
\lvert \lambda \rvert =1 \implies \gamma_A(\lambda)=\mu_A(\lambda) \quad ?
$$
Context
Let $u\in\mathbb{R}^m$
I am interested in the following limit:
$$
R=\lim_{n\rightarrow +\infty}\frac{1}{n} \sum_{k=0}^{n-1}A^k u
$$
I suspect that such limit must exists, as such equation appeared to me in the calculation of the average time reward of some markov reward process.
Reduction
- Let $A=PJP^{-1}$ the Jordan normal form of $A,$ and without a loss of generality, we will order the jordan blocks $J_{k}$ in decreasing order of the eigenvalue norms $\lvert \lambda_k \rvert$.
- Let $s_k$ be the size of the jordan block $J_k$
Now we analyse the convergence of a jordan block $J_k$ case by case:
- If $\lvert \lambda_k \rvert < 1,$ then:
$$
\begin{align*}
\lim_{n\rightarrow +\infty}\frac{1}{n} \sum_{r=0}^{n-1} J_k^r&=\lim_{n\rightarrow +\infty}\frac{1}{n} (I_{s_k}-J_k^n)\times (I_{s_k}-J_k)^{-1} \\
&= \mathbf{0}
\end{align*}
$$ - If $\lvert \lambda_k \rvert = 1$ and $s_k=1,$ then $J_k$ is a scalar and:
$$
\begin{align*}
\lim_{n\rightarrow +\infty}\frac{1}{n} \sum_{r=0}^{n-1} J_k^r&=\lim_{n\rightarrow +\infty}\frac{1}{n} \sum_{r=0}^{n-1}\lambda_k^r \\
&= \begin{cases}
1 & \text{if}\space \lambda_k=1 \\
0 & \text{otherwise}
\end{cases}
\end{align*}
$$ - Otherwise, if $\lvert \lambda_k\rvert=1$ and $s_k>1,$ I can prove that the limit does not exist.
Now, if I am not mistaken, my question is exactly that the case $3$ cannot occur.
Best Answer
That $\ \frac{1}{n}\sum_\limits{k=0}^{n-1}A^k\ $ always converges as $\ n\rightarrow\infty\ $ is a consequence of the structure of finite time-homogeneous Markov chains. The states of such a chain can always be partitioned into:
The matrix $\ A\ $ then has the form $$ A=U^{-1}\pmatrix{A_1&0_{n_1\times n_2}&\dots&0_{n_1\times n_c}&0_{n_1\times t}\\ 0_{n_2\times n_1}&A_2&\dots&0_{n_2\times n_c}&0_{n_2\times t}\\ \vdots&&\ddots&\vdots&\vdots\\ 0_{n_c\times n_1}&0_{n_c\times n_2}&\dots&A_c&0_{n_c\times t}\\ T_1&T_2&\dots&T_c&T_{c+1}}U\ , $$ for some suitable permutation matrix $\ U\ $, where $\ t\ $ is the number of transient states, $\ c\ $ the number of communication classes, $\ n_i\ $ the number of states in the $\ i^\text{th}\ $ communication class, each $\ A_i\ $ is an $\ n_i\times n_i\ $ irreducible (row) stochastic matrix, $\ T_{c+1}\ $ is a $\ t\times t\ $matrix, some positive integral power of which has all its row sums strictly less than $\ 1\ $, and $$ A^n=U^{-1}\pmatrix{A_1^n&0_{n_1\times n_2}&\dots&0_{n_1\times n_c}&0_{n_1\times t}\\ 0_{n_2\times n_1}&A_2^n&\dots&0_{n_2\times n_c}&0_{n_2\times t}\\ \vdots&&\ddots&\vdots&\vdots\\ 0_{n_c\times n_1}&0_{n_c\times n_2}&\dots&A_c^n&0_{n_c\times t}\\ X_{1n}&X_{2n}&\dots&X_{cn}&T_{c+1}^n}U $$ for $\ n\ge1\ $, where $\ X_{in}=\sum_\limits{k=0}^{n-1}T_{c+1}^kT_iA_i^{n-1-k}\ $. Because the row sums of $\ T_{c+1}^r\ $ are strictly less than $\ 1\ $ for some positive $\ r\ $, $\ \lim_\limits{n\rightarrow\infty}T_{c+1}^n=$$\,0_{t\times t}\ .$ If the $\ i^\text{th}\ $ communication class is aperiodic, then $\ A_i\ $ is primitive, $$ \lim_{n\rightarrow\infty}A_i^n=\mathbf{1}_{n_i\times1}\pi_i^T\ , $$ and $$ \lim_{n\rightarrow\infty}X_{in}=\big(I_{t\times t}-T_{c+1}\big)^{-1}T_i\mathbf{1}_{n_i\times1}\pi_i^T $$ where $\ \pi_i^T\ $ is the (unique) stationary distribution of the Markov chain with transition matrix $\ A_i\ $ (satisfying the equation $\ \pi_i^TA_i=\pi_i^T\ $). A fortiori, we therefore have \begin{align} \lim_{n\rightarrow\infty}\frac{1}{n}\sum_{k=0}^{n-1}T_{c+1}^k&=0_{t\times t}\ ,\\ \lim_{n\rightarrow\infty}\frac{1}{n}\sum_{k=0}^{n-1}A_i^k&=\mathbf{1}_{n_i\times1}\pi_i^T\ \ \text{, and}\\ \lim_{n\rightarrow\infty}\frac{1}{n}\sum_{k=0}^{n-1}X_{ik}&=\big(I_{t\times t}-T_{c+1}\big)^{-1}T_i\mathbf{1}_{n_i\times1}\pi_i^T \end{align} If the $\ i^\text{th}\ $ communication class is periodic with period $\ d\ $, then it can be partitioned into $\ d\ $ sets $\ \mathscr{S}_0,$$\,\mathscr{S}_1,$$\,\dots,$$\,\mathscr{S}_{d-1}\ $ of states such that if the chain ever enters a state in one of the sets $\ \mathscr{S}_j\ $, it will thereafter cycle through states in the sets $\ \mathscr{S}_{j+1},$$\,\mathscr{S}_{j+2},$$\,\dots$$\,\mathscr{S}_{d-1},$ $\,\mathscr{S}_0,$$\,\mathscr{S}_1,$$\,\dots,$$\,\mathscr{S}_{j-1},$$\,\mathscr{S}_j\ $ in that order. In this case, we can choose the matrix $\ U\ $ so that $\ A_i\ $ has the form $$ A_i=\pmatrix{0_{c_0\times c_0}&V_0&0_{c_0\times c_2}&\dots&0_{c_0\times c_{d-1}}\\ 0_{c_1\times c_0}&0_{c_1\times c_1}&V_1&\dots&0_{c_1\times c_{d-1}}\\ \vdots&\vdots&&\ddots&\vdots\\ 0_{c_{d-2}\times c_0}&0_{c_{d-2}\times c_1}& 0_{c_{d-2}\times c_2}&\dots&V_{d-2}\\ V_{d-1}&0_{c_{d-1}\times c_1}& 0_{c_{d-1}\times c_3}&\dots&0_{c_{d-1}\times c_{d-1}}}\ , $$ where $\ c_j=\big|\mathscr{S}_j\big|\ $. The matrix $\ V_j\ $ is a $\ c_j\times c_{j+1\pmod{d}}\ $ stochastic matrix whose rows and columns are indexed by the states in $\ \mathscr{S}_j\ $ and $\ \mathscr{S}_{j+1\pmod{d}}\ $ respectively. Although $\ A_i^n\ $ doesn't converge as $\ n\rightarrow\infty\ $ in this case, it's neverthelesss still true that $\ \frac{1}{n}\sum_\limits{k=0}^{n-1}A_i^k\ $ does converge.
First, note that $$ A_i^d=\pmatrix{W_0&0_{c_0\times c_1}&\dots&0_{c_0\times c_{d-1}}\\ 0_{c_1\times c_0}&W_1&\dots&0_{c_1\times c_{d-1}}\\ \vdots&\vdots&\ddots&\vdots\\ 0_{c_{d-1}\times c_0}&0_{c_{d-1}\times c_1}&\dots&W_{d-1}}\ , $$ where $\ W_j\stackrel{\text{def}}{=}\prod_\limits{k=0}^{d-1}V_{j+k\pmod{ d}}\ $ is a primitive $\ c_j\times c_j\ $ matrix. Therefore , \begin{align} A_i^{rd}&=\pmatrix{W_0^r&0_{c_0\times c_1}&\dots&0_{c_0\times c_{d-1}}\\ 0_{c_1\times c_0}&W_1^r&\dots&0_{c_1\times c_{d-1}}\\ \vdots&\vdots&\ddots&\vdots\\ 0_{c_{d-1}\times c_0}&0_{c_{d-1}\times c_1}&\dots&W_{d-1}^r}\\ &\rightarrow\pmatrix{\mathbf{1}_{c_0\times1}\omega_0^T&0_{c_0\times c_1}&\dots&0_{c_0\times c_{d-1}}\\ 0_{c_1\times c_0}&\mathbf{1}_{c_1\times1}\omega_1^T&\dots&0_{c_1\times c_{d-1}}\\ \vdots&\vdots&\ddots&\vdots\\ 0_{c_{d-1}\times c_0}&0_{c_{d-1}\times c_1}&\dots&\mathbf{1}_{c_{d-1}\times1}\omega_{d-1}^T} \end{align} as $\ r\rightarrow\infty\ $, where $\ \omega_j^T\ $ is the unique stationary distribution of the Markov chain with transition matrix $\ W_j\ $. It's then not difficult to show that $$ \lim_{n\rightarrow\infty}\frac{1}{n}\sum_{k=0}^{n-1}A_i^k=\frac{1}{d}\pmatrix{\mathbf{1}_{c_0\times1}\\\mathbf{1}_{c_1\times1}\\\vdots\\\mathbf{1}_{c_{d-1}\times1}}\pmatrix{\omega_0^T&\omega_1^T&\dots&\omega_{d-1}^T} $$ and \begin{align} \lim_{n\rightarrow\infty}&\frac{1}{n}\sum_{k=0}^{n-1}X_{ik}\\ &=\frac{1}{d}\big(I_{t\times t}-T_{c+1}\big)^{-1}T_i\pmatrix{\mathbf{1}_{c_0\times1}\\\mathbf{1}_{c_1\times1}\\\vdots\\\mathbf{1}_{c_{d-1}\times1}}\pmatrix{\omega_0^T&\omega_1^T&\dots&\omega_{d-1}^T} \end{align}
Therefore, now let $\ B_i\stackrel{\text{def}}{=}\lim_\limits{n\rightarrow\infty}\frac{1}{n}\sum_\limits{k=0}^{n-1}A_i^k\ $ and $\ Y_i\stackrel{\text{def}}{=}\lim_\limits{n\rightarrow\infty}\frac{1}{n}\sum_\limits{k=0}^{n-1}X_{ik}\ $ for $\ i=1,2,\dots,c\ $. Then \begin{align} \lim_{n\rightarrow\infty}&\frac{1}{n}\sum_{k=0}^{n-1}A^k\\ &=U^{-1}\pmatrix{B_1&0_{n_1\times n_2}&\dots&0_{n_1\times n_c}&0_{n_1\times t}\\ 0_{n_2\times n_1}&B_2&\dots&0_{n_2\times n_c}&0_{n_2\times t}\\ \vdots&&\ddots&\vdots&\vdots\\ 0_{n_c\times n_1}&0_{n_c\times n_2}&\dots&B_c&0_{n_c\times t}\\ Y_1&Y_2&\dots&Y_c&0_{t\times t}}U\ . \end{align}