Diagonalization of circulant matrices

Question

Why does the following hold?: $A$ circulant matrix iff it has a representation of the form $F^{-1}DF$ where $D$ is a diagonal matrix and $F$ is a discrete Fourier transformation. I get that $F^{-1}DF$ is circulant but what about the other direction?

Answer 1

I think the fastest way to see this is to decompose the circulant matrix into a linear combination of powers of the permutation matrix associated with long permutation, ie. $(n\,n-1\,\ldots\,1)$ (This is basically the definition of a circulant matrix). This permutation matrix obviously has eigenvectors $(\omega^k,\omega^{2\cdot k},\ldots,\omega^{(n-1)\cdot k} )$, so we can diagonalize the permutation matrix (and hence linear combinations of powers of this matrix) by conjugating by a matrix with these eigenvectors as columns, which is the discrete fourier matrix.

There might be a more elegant way to express this, but all my attempts basically boil down to definitions that expand the above.