Proving an identity for circulant matrices

Question

In my studies of linear algebra, I have encountered this exercise

Let $A$ be a circulant matrix defined as $$ A_{jl} = \left\{\begin{array}{cc} r_{l-j} & l\ge j, \\ r_{N+l-j} & l<j\end{array}\right\} $$ and we index our matrices starting from zero. We define \begin{equation*} U_{jl} = e^{2\pi i j l/N}, \qquad \left(\begin{array}{c} 0\le j\le N-1 \\ 0\le l\le N-1\end{array}\right), \qquad \Lambda = \begin{pmatrix} \lambda_0 \\ & \ddots \\ & & \lambda_{N-1} \end{pmatrix}\end{equation*} and $\lambda_l = \sum_{j=0}^{N-1} r_j e^{2\pi i jl/N}$. We are asked to show that $$AU=U\Lambda$$

I have no idea how to actually show this. I think this is a diagonalization argument where $U$ are eigenvectors and $\Lambda$ are the eigenvalues. Can someone please show me how to do this? I thank all helpers.

Answer 1

An $N\times N$ circulant matrix $A$ whose first zeroth row is $(r_0,r_1,\ldots,r_{N-1})$ can be written as a polynomial $p(C)=r_0I+r_1C+\cdots+r_{N-1}C^{N-1}$ where $C$ is the cyclic permutation matrix $$ C=\pmatrix{0&1\\ &\ddots&\ddots\\ &&\ddots&1\\ 1&&&0}. $$ So, once you obtain a diagonalisation $UDU^{-1}$ of $C$, you automatically obtain a diagonalisation $A=p(C)=p(UDU^{-1})=Up(D)U^{-1}$ of every circulant matrix $A$.

$C$ is the companion matrix of the polynomial $x^N-1$. Its eigenvalues are therefore $1,\omega,\omega^2,\ldots,\omega^{N-1}$ where $\omega=e^{2\pi i/N}$ is the primitive $N$-th root of unity. It is very easy to find an eigenvector $x$ corresponding to the eigenvalue $\omega^l$. Let $x=(x_0,x_1,\ldots,x_{N-1})^\top$. The characteristic equation $Cx=\omega^l x$ implies that $$ x_1=\omega^lx_0,\ x_2=\omega^lx_1,\,\ldots\tag{1} $$ and so on. Therefore $x_0$ cannot be zero, or else $x$ is a zero vector. So, we can take $x_0=1$ and the recurrence relation $(1)$ gives $x_j=\omega^{jl}$ and $x=\left(1,\omega^l,\omega^{2l},\ldots,\omega^{(N-1)l}\right)^\top$. Take this as the $l$-th column of $U$, we obtain the $U$ in question and $C=UDU^{-1}$ where $D=\operatorname{diag}(1,\omega,\omega^2,\ldots,\omega^{N-1})$. Now $Up(D)U^{-1}$ is a diagonalisation of $A$ where the $l$-th eigenvalue along the diagonal of $\Lambda=p(D)$ is $$ \lambda_l=p(\omega^l)=\sum_{j=0}^{N-1}r_j(\omega^l)^j=\sum_{j=0}^{N-1}r_je^{2\pi ijl/N},\ l\in\{0,1,\ldots,N-1\}. $$