Eigenvalues of circulant matrices

A circulant matrix is defined as
$$C=\left[\begin{array}{ccccc}{c}_0& c_{n-1}& \dots & c_2& c_1\\ c_1& c_0& c_{n-1}& & c_2\\ ⋮& c_1& c_0& \ddots & ⋮\\ c_{n-2}& & \ddots & \ddots & c_{n-1}\\ c_{n-1}& c_{n-2}& \dots & c_1& c_0\end{array}\right]$$
where $C_{j,k}=c_{j-k\mathrm{mod}n}$, the $k$-th eigenvalue ${\lambda }_k$ and eigenvector $x_k$ satisfy $C\cdot x_k={\lambda }_k{x}_k$, or, equivalently, $n$ equations as:
$$\sum _{j=0}^{m-1}{c}_{m-j}{x}_j+\sum _{j=m}^{n-1}{c}_{n-j+m}{x}_j={\lambda }_k{x}_{m}m=0,1,\dots ,n-1$$
with $c_n=c_0$, $x_m$ is the $m$-th compoent of an eigenvector $x_k$. Changing the dummy summing ($j\to m-j$ and $j\to n-j+m$) variables yields
$$\sum _{j=1}^m{c}_j{x}_{m-j}+\sum _{j=m+1}^n{c}_j{x}_{n+m-j}={\lambda }_k{x}_m$$
with $m=0,1,2,\dots ,n-1$. One can "guess" a solution that $x_j={\omega }^j$, therefore the equation above turns into
$$\begin{array}{rl}& \sum _{j=1}^m{c}_j{\omega }^{m-j}+\sum _{j=m+1}^n{c}_j{\omega }^{n+m-j}={\lambda }_k{\omega }^m\\ \leftrightarrow & \sum _{j=1}^m{c}_j{\omega }^{-j}+{\omega }^n\sum _{j=m+1}^n{c}_j{\omega }^{-j}={\lambda }_k\end{array}$$
Let $\omega$ be one of the $n$-th square root of unity, i.e., $\omega =\exp (-2\pi \mathbb{i}/n)$,  then ${\omega }^n=1$; we have an eigenvalue
$$\lambda =\sum _{j=0}^{n-1}{\omega }^{-j}{c}_j$$
with corresponding eigenvector
$$x=(1,\exp (2\pi \mathbb{i}/n),\exp (2\pi \mathbb{i}/n{)}^2,\dots ,\exp (2\pi \mathbb{i}/n{)}^{n-1}{)}^T$$
The $k$-th eigenvalue is generated from ${\omega }^{-k}=\exp (2\pi k\mathbb{i}/n)$ with $k\in [0,n-1]$, yields the $k$-th eigenvalue and eigenvector:
$${\lambda }_k=\sum _{j=0}^{n-1}{c}_j\exp (2\pi k\mathbb{i}/n)$$
and
$$x_k=(1,\exp (2\pi k\mathbb{i}/n),\exp (2\pi k\mathbb{i}/n{)}^2,\dots ,\exp (2\pi k\mathbb{i}/n{)}^{n-1}{)}^T$$
The eigenspace is just the DFT matrix, and ALL circulant matrices share same eigenspace, it is easily to verify that circulant matrices have following properties:
If $A$ and $B$ are circulant matrices, then

1. $AB=BA=W^{\ast }\mathrm{\Gamma }W$ with $W$ is the DFT matrix and $\mathrm{\Gamma }={\mathrm{\Gamma }}_A{\mathrm{\Gamma }}_B$, ${\mathrm{\Gamma }}_i$ represents diagonal matrix consists of eigenvalues of $i$; ${\mathrm{\Gamma }}_A=WA{W}^{\ast }$;
2. $B+A=A+B=W^{\ast }\mathrm{\Omega }W$, $\mathrm{\Omega }={\mathrm{\Gamma }}_A+{\mathrm{\Gamma }}_B$;
3. If $\det (A)\ne 0$, then $A^{-1}=W^{\ast }{\mathrm{\Gamma }}_A^{-1}W$;

The proof is straightforward:

1. $AB=W^{\ast }{\mathrm{\Gamma }}_{A}W{W}^{\ast }{\mathrm{\Gamma }}_{B}W=$
   $W^{\ast }{\mathrm{\Gamma }}_A{\mathrm{\Gamma }}_{B}W=W^{\ast }{\mathrm{\Gamma }}_B{\mathrm{\Gamma }}_{A}W=BA$
2. $W(A+B)W^{\ast }={\mathrm{\Gamma }}_A+{\mathrm{\Gamma }}_B$; 
3. $A{W}^{\ast }{\mathrm{\Gamma }}_A^{-1}W=W^{\ast }{\mathrm{\Gamma }}_{A}W{W}^{\ast }{\mathrm{\Gamma }}_A^{-1}W=\mathbb{I}$