I read that a circulant matrix $$C$$ can be written as $$F \phi F^{-1}$$ where $$\phi$$ are $$C$$'s eigenvalues. Can someone give me more information about the $$F$$ matrix? Will it be the same for any circulant matrix $$C$$? Is there any condition when I can't split a real circulant matrix $$C$$ as $$F \phi F^{-1}$$?
I read somewhere that $$F$$ is a unitary discrete Fourier transform matrix, and looks like this $$[\omega^{i \cdot j}]_{NxN}$$. In some other place I saw $$F$$ defined as $$\frac{1}{\sqrt{N}}[\omega^{i \cdot j}]_{NxN}$$. Can someone explain this difference?
• A circulant matrix $C$ is the matrix representation of the circular convolution with respect to a given discrete periodic function $\psi$. Convolution with $\psi$ is equivalent to multiplying with $\hat \psi$ in the Fourier domain. Multiplication by $\psi$ is a linear map whose matrix is $\mathrm{diag}(\psi)$. So $C$ can be written as $F^{-1} \mathrm{diag}(\psi) F$, i.e., take the Fourier transform, multiply by $\psi$, and invert the Fourier transform. – abhi01nat Sep 17 at 6:32
• @abhi01nat some more context? I am confused... By discrete periodic function $\phi$, do you mean the vector $[a_0,..,a_n]$ that we rotate and use as columns of C? I thought $\phi$ was the eigen vector of $C$. – Parth Tamane Sep 17 at 6:34
• $\phi$ gives the eigenvalues of $C$, not the eigenvectors (according to the first sentence in your own statement of the problem). $\phi$ is a diagonal matrix whose diagonal entries are the eigenvalues, right? Then $F$ is a matrix whose columns are the eigenvectors of $C$. – Gerry Myerson Sep 17 at 7:33
• @GerryMyerson I thought the $F$ matrix was the same for all circulant matrix $𝐶$? – Parth Tamane Sep 17 at 16:17
• The difference you have found in the two formulas for $F$ is probably just a difference in normalization, just as there are different normalizations for the Fourier transform. You know that if $v$ is an eigenvector of a matrix $A$, then $kv$ is also an eigenvector for all nonzero constants $k$, right? – Gerry Myerson Sep 17 at 22:07