The eigenvalues of a circulant matrix $C$ can be extracted as $$
\Lambda=F^{-1} C F
$$


where the $F$ matrix is a discrete Fourier transform matrix and $\Lambda$ is a diagonal matrix of eigenvalues.


Since $F^{-1}F$=$FF^{-1}=I$, is it possible to write $$
\Lambda=FC F^{-1} 
?$$


For example, if our circulant matrix were:


$$C=\begin{pmatrix} 2& -1& 0& 0& 0& 0& -1\\ -1& 2& -1& 0& 0& 0& 0&\\ 0& -1& 2& -1& 0& 0& 0\\ 0& 0& -1& 2& -1& 0& 0\\
0& 0& 0& -1& 2& -1& 0\\ 0& 0& 0& 0& -1& 2& -1\\ -1& 0& 0& 0& 0& -1& 2
\end{pmatrix}$$


There is no practical difference in the numerical values of the eigenvalues from those two approaches, i.e., whether the position of the inverse Fourier matrix is first or the last, it does not seem to matter here.


Is there a mathematical basis for this observation and is this property true for all circulants? $C$ happens to be a symmetric matrix. I am looking for a reference to explain this.


I am not a mathematician, my interest is in signal deconvolution problems for chemistry.



Extracting eigenvalues of a circulant matrix using discrete Fourier matrix
The discrete Fourier transform matrix $F$ is special because it squares to a permutation matrix,$^\ast$ $F^2=P$ with $P^2=I$. I insert $I=F^2 P=P F^{-2}$,
$$F^{-1}\Lambda F= F^{-1}(F^2 P) \Lambda (P F^{-2})F=F(P\Lambda P)F^{-1}.$$
So you see that you can either write $\Lambda=FCF^{-1}$ or $\Lambda'=F^{-1}CF$, the difference is simply that $\Lambda'=P\Lambda P$ is a reordering of the eigenvalues on the diagonal.




---


$^{\ast}$ See, for example, the [DFT wiki page](https://en.wikipedia.org/wiki/Discrete_Fourier_transform#Eigenvalues_and_eigenvectors)




---


In special case of the matrix in the OP, the permutation matrix is

$$P=\left(
\begin{array}{ccccccc}
 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
 0 & 0 & 0 & 0 & 0 & 1 & 0 \\
 0 & 0 & 0 & 0 & 1 & 0 & 0 \\
 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
 0 & 0 & 1 & 0 & 0 & 0 & 0 \\
 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
\end{array}
\right),$$

which commutes with the circulant matrix $C$. Hence in this case $\Lambda$ and $\Lambda'$ are the same.


