$\lim_{n\to\infty}\frac{1}{n}\sum_{j=1}^n T^j$

Question

How to solve the following:

Let $T$ be $d\times d$ permutation matrix. Prove that $\frac{1}{n}\sum_{j=1}^n T^j$ converges as $n\to\infty$ and determine the limit.

Any help is welcome. Thanks in advance.

Answer 1

The problem reduces to calculating $\frac{1}{n}\sum_i\omega^i$ where $\omega$ is a $k$th root of unity. Since the sum is periodic and $1+\omega+\cdots+\omega^{k-1}=0$, the sum reduces to $0$ in the limit $n\to\infty$. With one exception, when $\omega=1$, in which case, the sum is identically $1$.

Since $T^d=I$, the eigenvalues of $T$ satisfy $\omega^d=1$. By diagonalisation of $T$, $$\frac{1}{n}\sum_{j=1}^nT^j=P^{-1}\left(\frac{1}{n}\sum_{j=1}^nD^j\right)P\to P^{-1}AP$$ where $D$ consists of the eigenvalues $\omega$ of $T$, and $A$ is the diagonal matrix with diagonal $(1,\ldots,1,0,\ldots,0)$ (depending on how many $1$ eigenvalues there are).

Answer 2

For background about permutation matrices, see https://en.wikipedia.org/wiki/Permutation_matrix.

From there, we get that, if $S_d$ denotes the symmetric group on the set $\{1,\ldots d \}$, then for every permutation $\pi \in S_d$, there is a certain permutation matrix $T_\pi$ which has exactly one $1$ in every row and column, and $0$ elsewhere.

The assignment $\pi \mapsto T_\pi$ is a group homomorphism $\varphi: S_d \rightarrow GL_n(\mathbb Z)$. In fact, it's easy to see that $\varphi$ is injective, but we don't need that.

The important thing for us is that, $\varphi$ being a homomorphism, $$ \forall \pi,\rho \in S_d:T_\pi T_\rho = T_{\pi\rho}. $$ In particular, with $\mathbb N_0 = \{0, 1, 2, \ldots \}$ $$ \forall \pi \in S_d: \forall n \in \mathbb N_0 : (T_\pi)^n = T_{\pi^n}. $$ Now, let's fix $\pi \in S_d$.

Since $S_d$ is a finite group (in fact $|S_d| = d!$), $\pi$ has finite order, that is, if we write $\mathbb N = \{1, 2, 3, \ldots \}$ and denote by $id \in S_d$ the neutral element, the identity permutation, then $$ \exists m \in \mathbb N: \pi^m = id. \qquad\qquad(i) $$ If you're not familiar with this, see, for example, https://en.wikipedia.org/wiki/Order_(group_theory).

Now, let's fix $m \in \mathbb N$ with property (i). We could pick $m$ minimal with property (i), but we don't have to.

The equation $\pi^m = id$ implies $$ \forall j \in \mathbb N_0 : \pi^{j + m} = \pi^j \pi^m = \pi^j id = \pi^j. $$ This is also valid for the permutation matrix $T_\pi$. $$ \forall j \in \mathbb N_0 : (T_\pi)^{j + m} = T_{\pi^{j + m}} = T_{\pi^j} = (T_\pi)^j. $$ Now, we fix $n \in \mathbb N$ and write $$ n = k(n) m + r(n) \quad with\ unique\ integers\quad k(n) \in \mathbb N_0 \quad and \quad r(n) \in \{0, \ldots, m - 1 \}. $$ $k(n)$ and $r(n)$ are functions of $n$. Of course $$ k(n) = floor(n / m) \qquad and \qquad r(n) = n\ mod\ m. $$ Observe that, as $n \rightarrow \infty$, $k(n) \rightarrow \infty$ monotonically, and $r(n)$ is bounded. This implies $$ \lim_{n \rightarrow \infty} \frac{k(n)}n = \lim_{n \rightarrow \infty} \frac{k(n)}{k(n)m + r(n)} = \lim_{n \rightarrow \infty} \frac1{m + \frac{r(n)}{k(n)}} = \frac1m. \qquad\qquad(ii) $$ We will need that later.

With all this, we get $$ \sum_{j=0}^n (T_\pi)^j = k(n)\sum_{a = 0}^{m - 1} (T_\pi)^a + \sum_{b = 0}^{r(n)} (T_\pi)^b. \qquad \qquad (iii) $$ Put $$ B(n) = \sum_{b = 0}^{r(n)} (T_\pi)^b $$ and observe that, since each $(T_\pi)^b = T_{\pi^b}$ is a matrix with entries from $\{0, 1 \}$, and $r(n) \in \{0, \ldots, m - 1 \}$, $B(n)$ is a matrix with entries from $\{0, \ldots m \}$, in symbols $$ B(n) \in \{0, \ldots, m \}^{d\times d}. $$ This implies that $$ \lim_{n \rightarrow \infty} \frac1n B(n) = 0. \qquad \qquad (iv) $$ Next, put $$ A(m) = \sum_{a = 0}^{m - 1} (T_\pi)^a. $$ Note that $A$ depends on $m$, but not on $n$, and observe, using (iii) $$ \lim_{n \rightarrow \infty} (\frac{k(n)}n A(m)) = (\lim_{n \rightarrow \infty} \frac{k(n)}n) A(m) = \frac1m A(m). \qquad \qquad (v) $$ From (iii), (iv), and (v), we conclude $$ \lim_{n \rightarrow \infty} \frac1n \sum_{j=0}^n (T_\pi)^j = \frac1m A(m), $$ and finally $$ \lim_{n \rightarrow \infty} \frac1n \sum_{j=1}^n (T_\pi)^j = \lim_{n \rightarrow \infty} \frac1n \sum_{j=0}^n (T_\pi)^j - \lim_{n \rightarrow \infty} \frac1n (T_\pi)^0 = \frac1m A(m) - 0= \frac1m A(m). $$ This answers your question.

Observe that $\frac1m A(m)$ is the average of all possible powers of $T_\pi$ under equidistribution. I'm not an expert on ergodic theory, but I think that's important there.

Also observe that the average $\frac1m A(m)$ does not depend on the particular choice of $m$. That is, if we pick different $m$ and $m'$, both with property (i), then $$ \frac1m A(m) = \frac1{m'} A(m'). $$