Deficiency of unit eigenvalues in a stochastic matrix

Question

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:

1. 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*} $$
2. 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*} $$
3. 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.

Answer 1

This is a partial answer, as we assume that all the entries of $A$ are positive, or more generally $A$ is irreducible.

By the Perron-Frobenius theorem the space $\ker(I-A)$ is one dimensional and consists of the multiples of the eigevector $(1,1,\ldots, 1)^T.$ By the same theorem the space $\ker(I-A^T)$ is one dimensional, hence ${\rm Im}(I-A)$ has dimension $n-1.$

We can treat the matrix $A$ as the operator $A:\ell^\infty(\mathbb{R}^n)\to \ell^\infty(\mathbb{R}^n).$ The matrix is row stochastic therefore $\|A\|=1.$ Hence $\|A^n\|=1$ for any $n.$ Let $$R_n={1\over n}\sum_{k=0}^{n-1}A^k$$ Then $\|R_n\|=1$ and $$(I-A)R_n=R_n(I-A)={1\over n}(I-A^n)\underset{n}{\longrightarrow} 0$$ As the sequence $R_n$ is bounded, every subsequence of $R_n$ contains a convergent subsequence $R_{n_k}.$ Let $P=\lim_k R_{n_k}.$ Then $$P(I-A)=(I-A)P=0$$ Hence $P$ vanishes on ${\rm Im}(I-A)$ and ${\rm Im}P\subset \ker (I-A).$ For $u\in \ker (I-A)$ we have $R_nu=u,$ hence $Pu=u.$ Therefore ${\rm Im}P= \ker (I-A).$ The intersection of $\ker(I-A)$ and ${\rm Im}(I-A)$ is trivial. Indeed, assume by contradiction that $$(I-A)v=(1,1,\ldots, 1)^T$$ Let $v_k$ be the smallest coordinate of $v.$ We have $$1=v_k-\sum_{j=1}^na_{kj}v_j\le v_k-\left (\sum_{j=1}^na_{kj}\right )v_k=0$$ We obtained a contradiction. Hence $$\mathbb{R}^n={\rm Im}(I-A)\oplus \ker (I-A)$$ The operator $P$ vanishes on the first subspace and acts as identity on the second space.

Summarizing every subsequence of $R_n$ contains a subsequence convergent to $P.$ Thus the whole sequence is convergent to $P.$

Answer 2

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:

• A (possibly empty) set of transient states;
• A positive finite number of non-empty communication classes of states.

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}

Answer 3

Here is a very short proof to OP's question about semi-simplicity of eigenvalues on the unit circle for stochastic matrix $A$. OP considered using Jordan Normal Form, so let $J=P^{-1}AP$ and suppose that $\lambda_i \in S^1$ is not semi-simple. Then letting $M:=\Big\Vert P^{-1}\big\Vert_F\cdot\big \Vert P\big\Vert_F$

$k \leq \Big\Vert J_i^k\big\Vert_F\leq \Big\Vert J^k\big\Vert_F=\Big\Vert P^{-1}A^kP\big\Vert_F\leq M \cdot \Big\Vert A^k\big\Vert_F$
$ = M\cdot \sqrt{ \sum_{i=1}^m\sum_{j=1}^m (a_{i,j}^{(k)}})^2\leq M\cdot \sum_{i=1}^m\sum_{j=1}^m a_{i,j}^{(k)}=M\cdot \mathbf 1^T\big(A^k\mathbf 1\big) = M\cdot m$
by direct calculation, submultiplicativity of the Frobenius norm and triangle inequality. Observe that the upper bound is constant but the lower bound may be made arbitrarily large, which is a contradiction. Conclude $\lambda_i$ is semi-simple.

Remark: if we first decompose $A$ into irreducibles, we can do this with less machinery than JNF -- e.g. Schur Triangularization and a little cleverness is enough.