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