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.
 A: $A$ is a so-called circulant matrix, which can be denoted as ${\rm circ}(a_0,a_1,a_2)$. Let $\alpha = \exp{2\pi i/3}$; $\alpha$ is a 3rd root of unity, and satisfies $\alpha^3 = 1$ and $1 + \alpha + \alpha^2 = 0$ (as does its conjugate). By the general theory of circulants, we can diagonalize $A$ as follows:
$$ A = U \,{\rm diag}(d_0,d_1,d_2)\, U^*,$$ where
$U$ is the unitary matrix:
$$ U = \frac{1}{\sqrt{3}}\,\pmatrix{1 &1 & 1 \\ 1 &\alpha &\alpha^2 \\ 1 &\alpha^2 &\alpha^4},$$ and $d = \sqrt{3}\,U^* a$. We recover $a$ from the inverse transformation: $a = \frac{1}{\sqrt{3}} U d.$
We can now calculate
\begin{align}
 A^n &= (U D U^*)^n \\
   &= U D^n U^* \\
   &= U\, {\rm diag}(d_0^n, d_1^n, d_2^n)\, U^*\\
   &= {\rm circ}(a^{(n)}_0, a^{(n)}_1, a^{(n)}_2),
\end{align}
where $a^{(n)} = \frac{1}{\sqrt{3}} U\cdot (d^n_0,d^n_1,d^n_2)^T.$
A: 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}
$$
A: I think you've reached a decent result and by just using the multinomial theorem you can obtain a generalized solution.
$A=a_0I+ a_1U + a_2 U^2 \\
A^n = (a_0I+ a_1U + a_2 U^2)^n\\$
Then the coeffecients of $U^3$, $U^2$ and $U^1$ are determined using the multinomial theorem and just plugged back into the result matrix.
$$
\begin{matrix}
\sum_{a+b+c=n,\\ b+2c =3k} \frac{n!}{a!b!c!}(a_0)^ a(a_1)^b(a_2)^c & \sum_{a+b+c=n,\\ b+2c =3k+2} \frac{n!}{a!b!c!}(a_0)^ a(a_1)^b(a_2)^c & \sum_{a+b+c=n,\\ b+2c =3k+1} \frac{n!}{a!b!c!}(a_0)^ a(a_1)^b(a_2)^c \\
\sum_{a+b+c=n,\\ b+2c =3k+1} \frac{n!}{a!b!c!}(a_0)^ a(a_1)^b(a_2)^c & \sum_{a+b+c=n,\\ b+2c =3k} \frac{n!}{a!b!c!}(a_0)^ a(a_1)^b(a_2)^c & \sum_{a+b+c=n,\\ b+2c =3k+2} \frac{n!}{a!b!c!}(a_0)^ a(a_1)^b(a_2)^c \\
\sum_{a+b+c=n,\\ b+2c =3k+2} \frac{n!}{a!b!c!}(a_0)^ a(a_1)^b(a_2)^c & \sum_{a+b+c=n,\\ b+2c =3k+1} \frac{n!}{a!b!c!}(a_0)^ a(a_1)^b(a_2)^c & \sum_{a+b+c=n,\\ b+2c =3k} \frac{n!}{a!b!c!}(a_0)^ a(a_1)^b(a_2)^c \\
\end{matrix}
$$
The answer may seem obvious but unfortunately the multinomial expansion can't be simplified further (as per my knowledge). Even if it could it would just be a huge mess.
