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
    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