# How to diagonalize this circulant matrix?

I came across a matrix diagonalization problem in reading a physics paper, can someone tell me how to diagonalize this kind of matrix? $$\begin{bmatrix} a_{1} & c_{1} & \ldots & c_{n-1}\\ c_{n-1} & a_{2} & \ldots & c_{n-2}\\ \vdots & \vdots & \ddots & \vdots\\ c_{1} & c_{2} &\ldots & a_{n} \end{bmatrix}$$ in which $c_j = \exp{i2j\pi/n}$. Thank you very much!

Let $c(n) =e^{-2i \pi (n-1) / N}\ \$ a $N \times 1$ column vector. Your matrix is $M = c c^H+A$ with $A$ diagonal $A_{n,n} = a_n-1$.
The eigenvalue equation $M x= b x$ becomes $\langle x,c\rangle c= (bI-A)x$ i.e. $x(n) = \frac{\langle x,c\rangle}{b+1-a(n)}c(n)$ and $\sum_{n=1}^N \frac{1}{b+1-a(n)} = 1$.
Assuming there are $N$ solutions $b(1),\ldots, b(N)$ for $\sum_{n=1}^N \frac{1}{b+1-a(n)} = 1$ you get $M = P \Lambda P^{-1}$ with $\Lambda_{n,n} = b(n)$ and $P_{n,m} = \frac{c(n)}{b(m)+1-a(n)}$