TITLE: Does this matrix sequence always converge?
QUESTION [4 upvotes]: 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.

REPLY [2 votes]: 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.
{"set_name": "stack_exchange", "score": 4, "question_id": 2907338}