Diagonalization of circulant matrices 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?
 A: 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.
A: In case anyone's looking for a detailed proof of diagonalization of circulant matrices and their eigenvalues and eigenvectors, below powerpoint has a great explanation between slides 37-45:
www.cs.uoi.gr/~cnikou/Courses/Digital_Image_Processing/2010-2011/Chapter_04c_Frequency_Filtering_(Circulant_Matrices).ppt
