Let $F$ be a $100 \times 100$ DFT matrix, and $U$ be a diagonal matrix with its diagonal entries being all positive, denoted by $U=\mathrm{diag}(u_1, u_2,\cdots, u_{100})$. My question is:

Under which conditions on $U$ will the resulting matrix $FUF^\ast$ be circulant (where $F^\ast$ is the conjugate transpose of $F$)?

  • $\begingroup$ There might be; the Fourier transform of a diagonal matrix has nice structure, being complex-symmetric and constant along its antidiagonals (Hankel)... $\endgroup$ – J. M. is a poor mathematician May 9 '12 at 3:16
  • 1
    $\begingroup$ Well, it is not too hard to show that if $U$ is diagonal with real elements, then $F U F^*$ is real iff all diagonal elements of $U$ are exactly the same, ie, $U$ is a real multiple of the identity. $\endgroup$ – copper.hat May 9 '12 at 5:22
  • 3
    $\begingroup$ ...and you have $$\mathbf U\mathbf D\mathbf U^\ast=\begin{pmatrix}0&-\frac12-\frac{i}{2\sqrt 3}&-\frac12+\frac{i}{2\sqrt 3}\\-\frac12+\frac{i}{2\sqrt 3}&0&-\frac12-\frac{i}{2\sqrt 3}\\-\frac12-\frac{i}{2\sqrt 3}&-\frac12+\frac{i}{2\sqrt 3}&0\end{pmatrix}$$ $\endgroup$ – J. M. is a poor mathematician May 9 '12 at 6:18
  • 3
    $\begingroup$ I might be wrong but I think that every circulant matrix is diagonalized by the DFT matrix so something like $F_n C F_n^* = D$. Using this I'm thinking that you can assume that the result of your computation will be circulant as well and hence you have essentially $n$ (=100) terms to compute. In J.M.'s example, the matrix is circulant. [c0 c1 c2; c2 c0 c1; c1 c2 c0] $\endgroup$ – tibL May 9 '12 at 8:33
  • 1
    $\begingroup$ I think that, up to a normalisation, the (a,b) element of the product is the DFT of u at a-b. $\endgroup$ – dmuir May 9 '12 at 9:18

After seeing this article, I see that one can in fact easily build a circulant matrix, given its eigenvalues, and vice-versa. (In short: $\mathrm F \mathrm U \mathrm F^\ast$ is always circulant.)

Briefly, given the eigenvalues $u_1,u_2,\dots,u_N$, one simply needs to take the inverse discrete Fourier transform

$$a_{1,j}=\frac1{N}\sum_{k=0}^{N-1}u_{k+1}\exp\left(\frac{2\pi i(j-1)k}{N}\right)$$

to yield the first row of the circulant matrix $\mathbf A=\mathrm F \mathrm U \mathrm F^\ast$, after which the successive rows of $\mathbf A$ are easily generated. Conversely, the eigenvalues of $\mathbf A$ are generated by taking the DFT of the first row of $\mathbf A$.

Here's a Mathematica demonstration:

n = 100;
vec = Sort[RandomReal[{0, 30}, {n}], Greater];
ma = NestList[RotateRight, 
   InverseFourier[vec, FourierParameters -> {1, -1}], n - 1];
Eigenvalues[ma] - vec // Chop
  • $\begingroup$ Thanks! It is very clear that a circulant matrix can be diagonalized via DFT, and vice-versa. $\endgroup$ – John Smith May 9 '12 at 15:19

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.