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?

https://en.wikipedia.org/wiki/DFT_matrix https://en.wikipedia.org/wiki/Discrete_Fourier_transform#The_unitary_DFT

  • $\begingroup$ 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. $\endgroup$ – abhi01nat Sep 17 at 6:32
  • $\begingroup$ @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$. $\endgroup$ – Parth Tamane Sep 17 at 6:34
  • $\begingroup$ $\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$. $\endgroup$ – Gerry Myerson Sep 17 at 7:33
  • $\begingroup$ @GerryMyerson I thought the $F$ matrix was the same for all circulant matrix $𝐶$? $\endgroup$ – Parth Tamane Sep 17 at 16:17
  • $\begingroup$ 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? $\endgroup$ – Gerry Myerson Sep 17 at 22:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.