Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)... –  J. M. May 9 '12 at 3:16
1  
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
3  
...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}$$ –  J. M. May 9 '12 at 6:18
3  
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
1  
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

1 Answer 1

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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