$\lim_{n\to\infty}\frac{1}{n}\sum_{j=1}^n T^j$ 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.
 A: 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').
$$
A: 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).
