Find the $n$th power of a 3-by-3 circulant matrix Consider the matrix given as $$A=\begin{bmatrix}a_0 & a_2 & a_1\\ a_1 & a_0 & a_2\\ a_2 & a_1 & a_0\end{bmatrix}$$
Write down a formual for $A^n$ for $n\in\mathbb{N}$.
$$$$
My attempt: The first that comes to mind is to diagonalize it and hence find the formual for $A^n$, but that is very messy, so I tried to do something else it goes as:
bserve that $$A=\begin{bmatrix}a_0 & a_2 & a_1\\ a_1 & a_0 & a_2\\ a_2 & a_1 & a_0\end{bmatrix}=a_0\begin{bmatrix}1 & 0 & 0\\0 & 1 & 0\\0 & 0 & 1\end{bmatrix}+a_1\begin{bmatrix}0 & 0 & 1\\1 & 0 & 0\\0 & 1 & 0\end{bmatrix}+a_2\begin{bmatrix}0 & 1 & 0\\0 & 0 & 1\\1 & 0 & 0\end{bmatrix}$$
Let $U=\begin{bmatrix}0 & 0 & 1\\1 & 0 & 0\\0 & 1 & 0\end{bmatrix}$ then we will have that
$$\begin{matrix}U^2=\begin{bmatrix}0 & 1 & 0\\0 & 0 & 1\\1 & 0 & 0\end{bmatrix} & \text{ and } & U^3=\begin{bmatrix}1 & 0 & 0\\0 & 1 & 0\\0 & 0 & 1\end{bmatrix}\end{matrix}$$
Hence we have $A=a_0I+a_1U+a_2U^2 = a_0U^3+a_1U+a_2U^2=(a_0U^2+a_1I+a_2U)U$
This got me thinking that there might be an easy way to solve the above problem but, I was not able to make any further progress.
Please Help and thanks in advance.

Circulant matrices are related to Fourier transform.
Consider the DFT matrix of length $N=3$
$$
\mathbf{W}
=
\begin{pmatrix}
1 & 1 & 1 \\
1 & \Omega & \Omega^2 \\ 
1 & \Omega^2 & \Omega^4
\end{pmatrix}
$$
where
$\Omega
= e^{-2\pi i/N}$.
Consider now the DFT of the signal
$$
\mathbf{y}=
\mathbf{W}
\begin{pmatrix}
a_0 \\ a_1 \\ a_2
\end{pmatrix}
$$
From here, you can observe that
$$
\mathbf{WA}=
\mathbf{W}
\begin{pmatrix}
a_0 & a_2 & a_1 \\ a_1 & a_0 & a_2 \\ a_2 & a_1 & a_0
\end{pmatrix}
=
\mathrm{Diag}(\mathbf{y})
\mathbf{W}
$$
and thus
$$
\mathbf{A}
=
\mathbf{W}^{-1}
\mathrm{Diag}(\mathbf{y})
\mathbf{W}
=
\frac{1}{N} \mathbf{W}^{H}
\mathbf{D}
\mathbf{W}
$$
with $\mathbf{D}=\mathrm{Diag}(\mathbf{y})$.
Finally the $k$th power of $\mathbf{A}$ is
$$
\mathbf{A}^k
=
\frac{1}{N}
\mathbf{W}^{H} \mathbf{D}^k \mathbf{W}
$$
