$\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)
a)
(1)Let $\omega_{(k)}$ denote the $2^k$'th root of unity:
Observe that $\omega_{(k)}$ has the following properties:
(2)The entries of the $2^k \times 2^k$ Fourier Transform matrix $F^{(k)}$ are
(3)If $k<l$ then $F^{(k)}_{ij} = \omega_{(l)}^{ij2^{(l-k)}}$. In particular, for $l=k+1$ this means
(4)b)
(5)If we set $m = 2^k/2 = 2^{k-1}$ then for all $j \in \mathbb{Z}$
c)
(6)Let
Then the $2^{k-1} \times 2^{k-1}$ matrix product $D^{(k-1)}F^{(k-1)}$ has entries
(7)In terms of submatrices, we now have the following $2^k \times 2^k$ matrix product:
(8)If we let $i' = i + 2^{k-1}$ and $j' = j + 2^{k-1}$, then
(9)Hence, we can write (8) as
(10)d)
(11)The permutation matrix $R^{(k)}$ has entries $R^{(k)}_{ij} = 1$ if $j = 2i$ for $i=0,\ldots,2^{k-1}-1$, and $R^{(k)}_{ij} = 1$ if $j = 2(i - 2^{k-1}) + 1$ for $i=2^{k-1},\ldots,2^{k}-1$. Entries are zero otherwise. For example, for $k=3$:
Consider the product $AR^{(k)}$ where $A$ is a $2^k \times 2^k$ matrix. The upper half of $R^{(k)}$ will work on the left half of $A$ and send column number $j$ to column position $j' = 2j$, for $j = 0,\ldots,2^{k-1}-1$.
The lower half of $R^{(k)}$ will work on the right half of $A$ and send column number $j$ (for $j = 2^{k-1},\ldots,2^{k}-1$) to column position $j' = 2(j - 2^{k-1}) + 1$.
e)
(12)Now, letting $R^{(k)}$ act on (10) from the right, we see that for $j = 0,\ldots,2^{k-1}-1$ the $j$'th column is mapped to position $j' = 2j$ with entries
and for $j = 2^{k-1},\ldots,2^{k}-1$ the $j$'th column is mapped to position $j' = 2(j - 2^{k-1}) + 1$ with entries
(13)In conclusion, the result is a $2^k \times 2^k$ matrix with entries $\omega_{(k)}^{ij}$ for $i,j = 0,\ldots,2^k-1$. which indeed are the entries of the $2^k$-dimensional Fourier Transform matrix $F^{(k)}$.