\documentclass[12pt]{article}
\input{../macros.tex}
\begin{document}

\thispagestyle{plain}

\setcounter{session}{26}
\begin{center}
\textbf{Exercises on complex matrices; fast Fourier transform}
\end{center}


\begin{problem}  Compute the matrix $F_2$.
\end{problem}

\solution{
$F_2 = \small \twobytwo 1 1 1 w, \text{ where } w = e^{i2\pi / 2} = -1$.  Hence $$F_2 = \twobytwo 1 1 1 {-1}.$$
}

\begin{problem}   Find the matrices $D$ and $P$ used in the factorization: 
$$F_4 = \twobytwo I D I{-D} \twobytwo {F_2}{}{}{F_2}  P $$ 
Hint: $D$ is created using fourth roots, not square roots, of $1$. Check your answer by multiplying. 

\end{problem}

\solution{
We computed $F_2 =\small \twobytwo 1 1 1 {-1}$ in the previous problem.

$$D = \twobytwo  1 0 0 i.$$

$P$ is a permutation matrix that arranges the components of the
  incoming vector so that its even components come first. For $F_4$,
that means swapping the first and second components:
$$P \fourbyone {x_0}{x_1}{x_2}{x_3} = \fourbyone {x_0}{x_2}{x_1}{x_3}.$$
$$\text{So, } P = \left [ \begin{array}{rrrr} 
1& 0 &  0&  0\\
0 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\  \end{array} \right ].$$

Finally, we check our work by multiplying:
\begin{scriptsize}
\begin{eqnarray*}
\twobytwo I D I{-D} \twobytwo {F_2}{}{}{F_2}  P 
&=&  \left [ \begin{array}{rrrr} 
1 & 0 & 1 & 0 \\
0 & 1 & 0 & i \\
1 & 0 & -1 & 0 \\
0 & 1 & 0 & -i \\  \end{array} \right ] \left [ \begin{array}{rrrr} 
1 & 1 & 0 & 0 \\
1 & -1 & 0 &0  \\
0 & 0 & 1 & 1 \\
0 & 0 & 1 & -1 \\  \end{array} \right ] \left [ \begin{array}{rrrr} 
1& 0 &  0&  0\\
0 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\  \end{array} \right ]\\
&=&  \left [ \begin{array}{rrrr} 
1 & 0 & 1 & 0 \\
0 & 1 & 0 & i \\
1 & 0 & -1 & 0 \\
0 & 1 & 0 & -i \\  \end{array} \right ] \left 
[ \begin{array}{rrrr} 
1 & 0 & 1 & 0 \\
1 & 0 &-1 & 0  \\
0 & 1 & 0 & 1 \\
0 & 1 & 0 &-1 \\  \end{array} \right ]\\
&=& \left [ \begin{array}{rrrr} 
1 & 1 & 1 & 1 \\
1 & i & -1 & -i \\
1 & -1 & 1 & -1 \\
1 & -i & -1 & i \\  \end{array} \right ]\\
&=& \left [ \begin{array}{cccc} 
1 & 1 & 1 & 1 \\
1 & i & i^2 & i^3 \\
1 & i^2 & i^4 & i^6 \\
1 & i^3 & i^6 & i^9 \\  \end{array} \right ] = F_4. \hspace{4pt} \checkmark
\end{eqnarray*}
\end{scriptsize}
}

\end{document}