On the sequence of power of a stochastic matrix with large exponent (Q1978120)

An \(n\times n\) matrix \(A\) with nonnegative entries is primitive provided that for some positive integer \(m\), each entry of \(A^m\) is positive. The smallest such \(m\) is called the exponent of \(A\), denoted by \(\exp(A)\). There is a good deal of work on exponents of primitive matrices [cf. \textit{R. Brualdi} and \textit{H. Ryser}, Combinatorial Matrix Theory, Cambridge University Press (1991; Zbl 0746.05002)]. In particular, a celebrated result of \textit{H. Wielandt} [Math. Z. 52, 642-648 (1950; Zbl 0035.29101)] states that \(\exp(A)\leq n^2-2n+2\equiv \omega_n\). Assume that \(\exp(A)\geq [\frac 12\omega_n]+2\). It is known that for such an \(A\), the associated directed graph has cycles of just two different lengths, say \(k\) and \(j\) with \(k>j\), and that there is an \(\alpha\) with \(0 < \alpha < 1\) such that the characteristic polynomial of \(A\) is \(\lambda^n-\alpha\lambda^{n-j}-(1-\alpha)\lambda^{n-k}\). In the paper under review, the author proves: (a) For any \(m\geq n\), if \(\alpha\leq\frac 12\), then \(\|A^{m+k}-A^m\|_{\infty}\leq \|A^m-\mathbf{1} w^T\|_{\infty}\), where \(\mathbf{1}\) is the all-ones vector and \(w^T\) is the left-Perron vector for \(A\), normalized so that \(w^T\mathbf{1}=1\); (b) If \(j\geq\frac n2\), \(k\geq 31\) and \(\alpha >\frac {-9+3\sqrt{17}}4\), then \(\|A^{m+j}-A^m\|_{\infty}\leq \|A^m-\mathbf{1} w^T\|_{\infty}\) for all sufficiently large \(m\). Both (a) and (b) lead to lower bounds on the rate of convergence of the sequence \(\{A^m\}\).