Proof of the Simon-Ando Theorem

Abstract:

In 1961, Simon and Ando wrote a classical paper describing the convergence properties of nearly completely decomposable matrices. Basically, their work concerned a partitioned stochastic matrix e.g. \[ A = \begin {bmatrix} A_1&E_1\ E_2&A_2\end {bmatrix}\] where $A_1$ and $A_2$ are square blocks whose entries are all larger than those of $E_1$ and $E_2$ respectively.

Setting \[ A^k=\begin {bmatrix} A^{(k)}_1&E^{(k)}_1\ E^{(k)}_2&A^{(k)}_2\end {bmatrix},\] partitioned as in $A$, they observed that for some, rather short, initial sequence of iterates the main diagonal blocks tended to matrices all of whose rows are identical, e.g. $A^{(k)}_1$ to $F_1$ and $A^{(k)}_2$ to $F_2$. After this initial sequence, subsequent iterations showed that all blocks lying in the same column as those matrices tended to a scalar multiple of them, e.g. \[ \lim _{k\to \infty }A^k=\begin {bmatrix} \alpha F_1&\beta F_2\ \alpha F_1&\beta F_2\end {bmatrix}\] where $\alpha \geq 0$ and $\beta \geq 0$.

The purpose of this paper is to give a qualitative proof of the Simon-Ando theorem.