Does this matrix sequence always converge?

Question

Suppose $a_0, a_1, ... , a_{n-1}$ are real numbers from $(0; 1)$, such that $\sum_{k=0}^{n-1} a_k=1$. Suppose $A = (c_{ij})$ is a $n \times n$ matrix with entries $c_{ij} = a_{(i-j)\%n}$, where $\%$ is modulo operation. Is it always true that $\lim_{m \to \infty} A^m = \frac{1}{n} \begin{pmatrix} 1 & 1 & \cdots & 1 \\1 & 1 & \cdots & 1 \\ \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & \cdots & 1 \end{pmatrix}$?

This statement is true for $n = 2$: Suppose $A = \begin{pmatrix} a_0 & {1 - a_0} \\ {1 - a_0} & a_0 \end{pmatrix} = \begin{pmatrix} 1 & -1 \\ 1 & 1\end{pmatrix}^{-1}\begin{pmatrix} 1 & 0 \\ 0 & {1-2a_0} \end{pmatrix}\begin{pmatrix} 1 & -1 \\ 1 & 1 \end{pmatrix}$. Because $a_0$ is in $(0; 1)$, $1-2a_0$ is in $(-1;1)$. Thus $$\lim_{m \to \infty} A^m = \begin{pmatrix} 1 & -1 \\ 1 & 1\end{pmatrix}^{-1}\begin{pmatrix} 1 & 0 \\ 0 & 0\end{pmatrix}\begin{pmatrix} 1 & -1 \\ 1 & 1 \end{pmatrix} = \frac{1}{2}\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}$$

However, I do not know how to prove this statement for arbitrary $n$.

Any help will be appreciated.

Answer 1

This follows directly from the Perron-Frobenius theorem.

Answer 2

Your matrix $A$ is a circulant matrix:

$$A = \begin{bmatrix} a_0 & a_1 & \cdots & a_{n-1}\\ a_{n-1} & a_0 & \cdots & a_{n-2}\\ \vdots & \vdots & \cdots & \vdots \\ a_1 & a_2 & \cdots & a_0\\ \end{bmatrix}$$

$A$ is known to have eigenvalues equal to $\lambda_j = \sum_{k=0}^{n-1} a_k\omega_j^k$ with eigenvectors $\begin{bmatrix} 1 \\ \omega_j \\ \omega_j^2 \\ \vdots \\ \omega_j^{n-1}\end{bmatrix}$, where $\omega_j = e^{\frac{2\pi ij}{n}}$ for $j = 0, \ldots n-1$.

Therefore we can diagonalize $A$ as follows:

$$A = P^{-1}DP = \begin{bmatrix} 1 & 1 & \cdots & 1\\ \omega_0 & \omega_1 & \cdots & \omega_{n-1}\\ \vdots & \vdots & \cdots & \vdots \\ \omega_0^{n-1} & \omega_1^{n-1} & \cdots & \omega_{n-1}^{n-1} \end{bmatrix}^{-1} \begin{bmatrix} \lambda_0 & 0 & \cdots & 0 \\ 0 & \lambda_1 & \cdots & 0\\ \vdots & \vdots & \cdots & \vdots \\ 0 & 0 & \cdots & \lambda_{n-1}\\ \end{bmatrix} \begin{bmatrix} 1 & 1 & \cdots & 1\\ \omega_0 & \omega_1 & \cdots & \omega_{n-1}\\ \vdots & \vdots & \cdots & \vdots \\ \omega_0^{n-1} & \omega_1^{n-1} & \cdots & \omega_{n-1}^{n-1} \end{bmatrix}$$

The triangle inequality for the eigenvalues gives

$$|\lambda_j| = \left|\sum_{k=0}^{n-1} a_k\omega_j^k\right| \le \sum_{k=0}^{n-1} a_k |\omega_j|^k = \sum_{k=0}^{n-1} a_k = 1$$

with equality holding if and only if $\{a_0, a_1\omega_j, \ldots, a_{n-1}\omega_j^{n-1}\}$ lie on the same side of a single line through the origin. Clearly this is true iff $j = 0$ so the eigenvalues satisfy $\lambda_0 = 1$ and $|\lambda_j| < 1$ for $j = 1, \ldots, n-1$.

Hence letting $m\to\infty$ in $A^m = P^{-1}D^mP$ gives

\begin{align} \lim_{m\to\infty} A^m &= \begin{bmatrix} 1 & 1 & \cdots & 1\\ \omega_0 & \omega_1 & \cdots & \omega_{n-1}\\ \vdots & \vdots & \cdots & \vdots \\ \omega_0^{n-1} & \omega_1^{n-1} & \cdots & \omega_{n-1}^{n-1} \end{bmatrix}^{-1} \begin{bmatrix} 1 & 0 & \cdots & 0 \\ 0 & 0 & \cdots & 0\\ \vdots & \vdots & \cdots & \vdots \\ 0 & 0 & \cdots & 0\\ \end{bmatrix} \begin{bmatrix} 1 & 1 & \cdots & 1\\ \omega_0 & \omega_1 & \cdots & \omega_{n-1}\\ \vdots & \vdots & \cdots & \vdots \\ \omega_0^{n-1} & \omega_1^{n-1} & \cdots & \omega_{n-1}^{n-1} \end{bmatrix}\\ &= \begin{bmatrix} 1 & 1 & \cdots & 1\\ \omega_0 & \omega_1 & \cdots & \omega_{n-1}\\ \vdots & \vdots & \cdots & \vdots \\ \omega_0^{n-1} & \omega_1^{n-1} & \cdots & \omega_{n-1}^{n-1} \end{bmatrix}^{-1} \begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1\end{bmatrix} \end{align}

You can calculate this by hand, or notice that the columns of $\lim_{m\to\infty} A^m$ satisfy the system $Px = \begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1\end{bmatrix}$, which you can solve.

The sum $\sum_{k=0}^{n-1} \omega_k^j$ is equal to $0$ here, which would suggest that the limit doesn't have to be of the form you specified.