Decomposing Toeplitz Matrix with "Half" Fourier Transform. 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$
 A: 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
