Ex7 7

$\def\abs#1{|#1|}\def\i{\mathbf {i}}\def\ket#1{|{#1}\rangle}\def\bra#1{\langle{#1}|}\def\braket#1#2{\langle{#1}|{#2}\rangle}\def\tr{\mathord{\mbox{tr}}}\mathbf{Exercise\ 7.7}$ Fast Fourier Transform Decomposition

a) For $k < l$, write the entries $F_{ij}^{(k)}$ of the $2^k\times 2^k$ matrix for the Fourier transform ${U_F}^{(k)}$ in terms of $\omega_{(l)}$.

b) Find $m$ in terms of $k$ such that $-\omega_{(k)}^i = \omega_{(k)}^{m+i}$ for all $i\in {\bf Z}$.

c) Compute the product

(1)
\begin{align} \left(\begin{array}{cc}I^{(k-1)}& D^{(k-1)}\\ I^{(k-1)}& -D^{(k-1)}\\\end{array}\right) \left(\begin{array}{cc}{U_F}^{(k-1)}& 0\\ 0& {U_F}^{(k-1)}\\\end{array}\right) \end{align}

ultimately writing each entry as a power of $\omega_{(k)}$.

d) Let $A$ be any $2^k\times 2^k$ matrix with columns $A_j$. The product matrix $A R^{(k)}$ is just a permutation of the columns. Where does column $A_j$ end up in the product $A R^{(k)}$.

e) Verify that

(2)
\begin{align} {U_F}^{(k)} = \frac{1}{\sqrt{2}} \left(\begin{array}{cc}I^{(k-1)}& D^{(k-1)}\\ I^{(k-1)}& -D^{(k-1)}\\\end{array}\right) \left(\begin{array}{cc}{U_F}^{(k-1)}& 0\\ 0& {U_F}^{(k-1)}\\\end{array}\right) R^{(k)}. \end{align}