Infinite power of a row stochastic matrix

Question

Let $A=[a_{ij}]$ be an $n \times n$ row-stochastic matrix (rows sum up to one and elements are non-negative). Is the assumption $a_{ii}>0$ for all $i=1, \ldots, n$ sufficient to conclude that $\lim_{t \to \infty} A^t$ exists?

Answer 1

Let $\lambda_i$ denote $i$-th eigenvalue of $A$. From the Gershgorin circle theorem we have $|\lambda_i| \leq 1$ for all $i$ and if $|\lambda_j| = 1$ for some $j$, then $\lambda_j = 1$ (this results from assumption $a_{ii} > 0$ for all $i$). By direct calculation we may check that $1$ is an eigevalue of $A$ with associated eigenvector $[1,\dots, 1]^T$.

Assume, that the geometric and algebraic multiplicity of the eigenvalue $1$ is equal. Then the Jordan decomposition of $A$ takes the form $$A = V\times(I\oplus\bigoplus_j J_j)\times V^{-1} \tag{1}$$ for some invertible matrix $V$ and $J_j$ denoting the Jordan block associated with and eigenvalue $\mu_j$, $|\mu_j| < 1$. Since $\lim_{k\rightarrow \infty} J_j^k = 0$, (1) proves, that $\lim_{k\rightarrow \infty} A^k$ exists.

$\mathbf{Theorem \ 1}$. Let $A \in R^{n\times n}$ be such that $\rho(A) = 1$. If the sequence $\{\|A^k\|\}$ is uniformly bounded for some matrix norm $\|\cdot\|$, then then the eigenvalue $1$ has the same algebraic and geometric multiplicity.

$\rho(A) = \max \{|\lambda_i| : \lambda_i \text{ is an eigenvalue of } A\}$ denotes the spectral radius of $A$. This theorem is proven in Ding, Jiu, and Noah H. Rhee. "On the equality of algebraic and geometric multiplicities of matrix eigenvalues." Applied Mathematics Letters 24.12 (2011): 2211-2215. The proof is quite simple but long.

We already know, that $\rho(A) = 1$. Observe, that $A^k$ is a stochastic matrix for any $k$, therefore $\|A^k\|_{\infty} = 1$. By the theorem 1 we have, that the geometric and algebraic multiplicity of the eigenvalue $1$ is equal.

Answer 2

We may assume without loss of generality that $A$ is irreducible, that is, for each $1\leqslant i,j,\leqslant n$ there exists $m>0$ such that $a_{ij}^m>0$ (otherwise we consider the irreducible stochastic submatrices of $A$). Then $A$ is an irreducible, aperiodic stochastic matrix, which is the transition matrix of an ergodic Markov chain. Indeed, there is a unique row vector $\pi$ which satisfies $\pi A = \pi$ and $\sum_{i=1}^n \pi_i = 1$ such that each row in the limiting matrix $\lim_{m\to\infty}A^m$ is equal to $\pi$.

Answer 3

For every $k$, $A^k$ is stochastic and thus uniformly bounded ($tr({A^k}^TA^k)\leq n^2$). Then the eigenvalues of $A$ of absolute value $1$ are all semi-simple. Then, it suffices to show that $1$ is the only eigenvalue of $A$ with absolute value $1$.

There is a permutation matrix $P$ s.t. $PAP^{-1}$ is block triangular with block diagonal $B_1,\cdots,B_k$ where, for every $i$, $B_i$ is $\geq 0$ irreducible and with positive diagonal. Let $B$ be such a matrix $B_i$.

EDIT. Note that $\rho(B)\leq 1$. If $\rho(B)<1$, then there is nothing to show. Thus assume that $\rho(B)=1$; it remains to show that $1$ is the only eigenvalue of $B$ with absolute value $1$.

Let $h$ be the period of $B$; if $h>1$ then there is a permutation matrix $P$ s.t. $PBP^{-1}$ has diagonal $0$, that is contradictory. Then $h=1$ and $B$ has only one eigenvalue $\lambda$, with absolute value $1$, that implies $\lambda=1$, and we are done;

PS . I see that @ Pawel Kowal gave a very quick proof (using Gershgorin) showing that $1$ is the only eigenvalue of $A$ of absolute value $1$.