How to diagonalize this circulant matrix?

Question

I came across a matrix diagonalization problem in reading a physics paper, can someone tell me how to diagonalize this kind of matrix? \begin{equation} \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} \end{equation} in which $c_j = \exp{i2j\pi/n}$. Thank you very much!

Answer 1

You should check it but I think the idea is there :

---

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)}$