2
$\begingroup$

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

  • 0
    There might be; the Fourier transform of a diagonal matrix has nice structure, being complex-symmetric and constant along its antidiagonals (Hankel)...2012-05-09
  • 0
    Yeah, I think so. I found that $F\cdot U \cdot F^*$ is always a real matrix.2012-05-09
  • 0
    Are you sure? Trying it out on a random diagonal matrix gave me a complex matrix...2012-05-09
  • 0
    We assume that $U$ is a real diagonal matrix with all positive diagonal elements. Under this assumption, I think it's true.2012-05-09
  • 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.2012-05-09
  • 0
    What if the real diagonal elements of $U$ are not the same ?2012-05-09
  • 0
    Let's be concrete. Consider the $3\times 3$ normalized Fourier matrix $$\mathbf U=\begin{pmatrix}\frac1{\sqrt 3}&\frac1{\sqrt 3}&\frac1{\sqrt 3}\\\frac1{\sqrt 3}&-\frac{i}{2}-\frac1{2\sqrt 3}&\frac{i}{2}-\frac1{2\sqrt 3}\\\frac1{\sqrt 3}&\frac{i}{2}-\frac1{2\sqrt 3}&-\frac{i}{2}-\frac1{2\sqrt 3}\end{pmatrix}$$ which is unitary. Take $\mathbf D=\mathrm{diag}(-1,0,1)$...2012-05-09
  • 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}$$2012-05-09
  • 0
    Nicely Hermitian, but most assuredly not real.2012-05-09
  • 0
    Okay, but is there some method to compute this in a fast way?2012-05-09
  • 0
    Doesn't change a thing. Recall that if $\lambda$ is an eigenvalue of $\mathbf A$, then $\lambda+c$ is an eigenvalue of $\mathbf A+c\mathbf I$...2012-05-09
  • 0
    It depends on if there is some suitable relationship among the $U_{ii}$. Perhaps look at the Cooley–Tukey implementation to see if you can do things more efficiently? (I presume by efficiently, you mean order $n \log n$.)2012-05-09
  • 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]2012-05-09
  • 1
    I think that, up to a normalisation, the (a,b) element of the product is the DFT of u at a-b.2012-05-09
  • 0
    Yeah, the reusltant matrix $FUF^*$ is circulant. So now my question would be (1) Under which condition of the diagonal matrix $U$, will the matrix $FUF^*$ become circulant? (2) Is there some tricks to compute $FUF^*$ for the given $F$ and $U$ in $n log n$ time ?2012-05-09

1 Answers 1

1

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 
  • 0
    Thanks! It is very clear that a circulant matrix can be diagonalized via DFT, and vice-versa.2012-05-09