Reference: Fourier basis diagonalises matrix iff circulant? I believe that a (finite) square matrix is diagonalised by the DFT basis $F$ iff it is circulant
$$
A \text{ is circulant}
\quad \Leftrightarrow \quad
F^{-1} A F \text{ is diagonal}
$$
as described in the question Diagonalization of circulant matrices. However, I do not have a reference for this. Is it true? Which source can I reference for this fact?
 A: From the wikipedia article

In numerical analysis, circulant matrices are important because they
  are diagonalized by a discrete Fourier transform, and hence linear
  equations that contain them may be quickly solved using a fast Fourier
  transform.[1]

[1]: Davis, Philip J., Circulant Matrices, Wiley, New York, 1970 ISBN 0471057711
http://www-ee.stanford.edu/~gray/toeplitz.pdf
In simple terms, why this holds is that:


*

*A circulant matrix has all its rows being cyclic permutations (cyclic shifts) of the same row.

*The fourier transform (DFT) is circular, meaning its basis is polynomials on the roots of unity which are invariant under cyclic shifts (on the unit circle).

*Thus if expressed on the DFT basis, each row of the matrix is only a shift away from the reference (original) row. But a shift, in DFT terms, is simple multiplication by a root of unity, thus only the diagonal elements need be non-zero, to describe the appropriate shift (think of a clock, and shifting as changing the angle of the pointer, i.e simple multiplication by a root of unity)

