Decomposing Toeplitz Matrix with "Half" Fourier Transform.

Question

In a previous question [1] the author claims that

We can write a complex toeplitz matrix $A$ of size $M \times M$ as $$A = F^H_2 D F_2$$ Where $D$ is a diagonal matrix and $F_2$ contains the first $M$ columns of a $2M \times 2M$ DFT matrix.

Question 1. Why is this possible?

Question 2. Are there any efficient way to find $D$?

[1] Factorization of a Toeplitz-block Toeplitz matrix $A$ (Toeplitz Matrix with Toeplitz Blocks) as a product $A = Q^H D \, Q$ using a diagonal matrix $D$

Answer 1

Let $A$ be a Toeplitz matrix. It is then possible to construct matrices $B$ and $M$ so $M$ is a Circulant matrix: $$M = \begin{pmatrix} A & B \\ B & A \end{pmatrix} $$ This requires us to choose $B$ in a particular way (see [0] for details). Since $M$ is a Circulant matrix it can be decomposed as follows: $$ \begin{pmatrix} A & B \\ B & A \end{pmatrix} = \begin{pmatrix} F_{1,1} & F_{1,2} \\ F_{2,1} & F_{2,2} \end{pmatrix}^H\begin{pmatrix}D_1 & 0 \\ 0& D_2 \end{pmatrix} \begin{pmatrix} F_{1,1} & F_{1,2} \\ F_{2,1} & F_{2,2} \end{pmatrix} $$ By block matrix multiplication we can then get the wanted equation: $$ A = \begin{pmatrix}F_{1,1} \\ F_{2,1} \end{pmatrix} ^H \begin{pmatrix}D_1 & 0 \\ 0 & D_2 \end{pmatrix} \begin{pmatrix}F_{1,1} \\ F_{2,1} \end{pmatrix} =F_2^H \begin{pmatrix}D_1 & 0 \\ 0 & D_2 \end{pmatrix} F_2 $$

The diagonal matrices $D_1$ and $D_2$ can be efficiently computed using the FFT since $M$ is circulant [0].

[0] http://www.netlib.org/utk/people/JackDongarra/etemplates/node384.html