Take the 2-minute tour ×

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$)?

share|improve this question
There might be; the Fourier transform of a diagonal matrix has nice structure, being complex-symmetric and constant along its antidiagonals (Hankel)... –  Ｊ. Ｍ. May 9 '12 at 3:16
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. –  copper.hat May 9 '12 at 5:22
...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}$$ –  Ｊ. Ｍ. May 9 '12 at 6:18
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] –  tibL May 9 '12 at 8:33
I think that, up to a normalisation, the (a,b) element of the product is the DFT of u at a-b. –  dmuir May 9 '12 at 9:18
show 10 more comments

1 Answer

up vote 1 down vote accepted

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
share|improve this answer
Thanks! It is very clear that a circulant matrix can be diagonalized via DFT, and vice-versa. –  John Smith May 9 '12 at 15:19
add comment

Your Answer


