Discrete Fourier transform and FFT

Suppose $n$ is a positive integer. For this exercise, we adopt the notation that a typical element $z$ of $\mathbb {C}^{n}$ is denoted by $z = (z_{0}, z_{1}, \ldots , z_{n-1})$. Define linear functionals $\omega_{0}, \omega_{1}, \ldots , \omega_{n-1}$ on $\mathbb {C}^{n}$ by

The discrete Fourier transform is the operator $\mathcal{F} : \mathbb {C}^{n} \rightarrow \mathbb {C}^{n}$ defined by

Compute $\left|\mathbf{A}_{363}\right|$ for $\omega = e^{2\pii / 3}$. $\mathbf{A}_{363} = \left[\begin{smallmatrix} 1 & 1 & 1 \\ 1 & \omega & \omega^{2} \\ 1 & \omega^{2} & \omega \end{smallmatrix}\right]$.

Evaluate the following convolutions (using the convolution $\odot$ of two vectors, as defined in this section: for $a = (\alpha_{0},\ldots ,\alpha_{n-1})^{T}$, $b=(\beta_{0},\ldots ,\beta_{n-1})^{T}$, the vector $a \odot b$ of size $2n$ whose $k$th entry is $\sum_{j=0}^{k} \alpha_{j}\beta_{k-j}$, padding $\alpha_{i},\beta_{i}=0$ for $i \geq n$).

Verify directly that $F_{4} = \begin{pmatrix} F_{2} & D_{2}F_{2} \\ F_{2} & -D_{2}F_{2} \end{pmatrix} P_{4}$, where $F_{4}, P_{4}, D_{2}$ are as defined in the Fourier-matrix decomposition (5.8.15): for $n=2^{r}$, $F_{n} = \begin{pmatrix} F_{n/2} & D_{n/2}F_{n/2} \\ F_{n/2} & -D_{n/2}F_{n/2} \end{pmatrix}P_{n}$, where $D_{n/2} = \operatorname {diag}(1,\xi ,\xi^{2},\ldots ,\xi^{n/2-1})$ ($\xi$ the primitive $n$th root of unity used throughout this section) and $P_{n}^{T} = \left[e_{0}\; e_{2}\; e_{4}\; \cdots \; e_{n-2} \mid e_{1}\; e_{3}\; e_{5}\; \cdots \; e_{n-1}\right]$ is the even-odd permutation matrix.

Use the following vectors to perform the indicated computations: $a = \begin{pmatrix} \alpha_{0} \\ \alpha_{1} \end{pmatrix}$, $b = \begin{pmatrix} \beta_{0} \\ \beta_{1} \end{pmatrix}$, $\hat{a} = \begin{pmatrix} \alpha_{0} \\ \alpha_{1} \\ 0 \\ 0 \end{pmatrix}$, $\hat{b} = \begin{pmatrix} \beta_{0} \\ \beta_{1} \\ 0 \\ 0 \end{pmatrix}$.

For $p(x) = 2x-3$ and $q(x) = 3x-4$, compute the product $p(x)q(x)$ by using the convolution theorem.

Use convolutions to form the following products.

Let $a$ and $b$ be $n \times 1$ vectors, where $n$ is a power of 2.

A waveform given by a finite sum $x(\tau ) = \sum_{k} (\alpha_{k}\cos 2\pi f_{k}\tau + \beta_{k}\sin 2\pi f_{k}\tau )$, in which the $f_{k}$'s are integers and $\max \left\{ f_{k}\right\} \leq 3$, is sampled at eight equally spaced points between $\tau =0$ and $\tau =1$. Let $x = \begin{pmatrix} x(0/8) & x(1/8) & x(2/8) & x(3/8) & x(4/8) & x(5/8) & x(6/8) & x(7/8) \end{pmatrix}^{T}$, and suppose that

What is the equation of the waveform?

Prove that $a \odot b = b \odot a$ for all $a, b \in \mathbb {C}^{n}$ — i.e., convolution is a commutative operation.

For $p(x) = \sum_{k=0}^{n-1} \alpha_{k}x^{k}$ and the $n$th roots of unity $\xi^{k}$, let $a = \begin{pmatrix} \alpha_{0} & \alpha_{1} & \cdots & \alpha_{n-1} \end{pmatrix}^{T}$ and $p = \begin{pmatrix} p(1) & p(\xi ) & \cdots & p(\xi^{n-1}) \end{pmatrix}^{T}$. Explain why $F_{n}a = p$ and $a = F_{n}^{-1}p$.

For two polynomials $p(x) = \sum_{k=0}^{n-1}\alpha_{k}x^{k}$ and $q(x) = \sum_{k=0}^{n-1}\beta_{k}x^{k}$, let $p = \begin{pmatrix} p(1) & p(\xi ) & \cdots & p(\xi^{2n-1}) \end{pmatrix}^{T}$ and $q = \begin{pmatrix} q(1) & q(\xi ) & \cdots & q(\xi^{2n-1}) \end{pmatrix}^{T}$, where $1,\xi ,\xi^{2},\ldots ,\xi^{2n-1}$ are now the $2n$th roots of unity. Explain why the coefficients in the product $p(x)q(x) = \gamma_{0}+\gamma_{1}x+\cdots +\gamma_{2n-2}x^{2n-2}$ must be given by

A circulant matrix is defined to be a square matrix that has the form $C = \begin{pmatrix} c_{0} & c_{n-1} & c_{n-2} & \cdots & c_{1} \\ c_{1} & c_{0} & c_{n-1} & \cdots & c_{2} \\ c_{2} & c_{1} & c_{0} & \cdots & c_{3} \\ \vdots & \vdots & \vdots & & \vdots \\ c_{n-1} & c_{n-2} & c_{n-3} & \cdots & c_{0} \end{pmatrix}_{n\times n}$ — i.e., the entries in each column are the same as the previous column, but shifted one position downward and wrapped around at the top; the $(j,k)$-entry is $c_{jk} = c_{j-k \pmod{n}}$.

For a nonsingular circulant $C_{n\times n}$, explain how to use the FFT algorithm to efficiently perform the following operations.

For the vectors $a = \begin{pmatrix} \alpha_{0} \\ \alpha_{1} \\ \vdots \\ \alpha_{n-1} \end{pmatrix}$, $b = \begin{pmatrix} \beta_{0} \\ \beta_{1} \\ \vdots \\ \beta_{n-1} \end{pmatrix}$, $\hat{a} = \begin{pmatrix} \alpha_{0} \\ \vdots \\ \alpha_{n-1} \\ 0 \\ \vdots \\ 0 \end{pmatrix}_{2n \times 1}$, and $\hat{b} = \begin{pmatrix} \beta_{0} \\ \vdots \\ \beta_{n-1} \\ 0 \\ \vdots \\ 0 \end{pmatrix}_{2n \times 1}$, let $C$ be the $2n\times 2n$ circulant matrix (Exercise 5.8.12) whose first column is $\hat{a}$.

The Kronecker product of two matrices $A_{m\times n}$ and $B_{p\times q}$ is the $mp \times nq$ matrix $A \otimes B = \begin{pmatrix} a_{11}B & a_{12}B & \cdots & a_{1n}B \\ a_{21}B & a_{22}B & \cdots & a_{2n}B \\ \vdots & \vdots & & \vdots \\ a_{m1}B & a_{m2}B & \cdots & a_{mn}B \end{pmatrix}$, satisfying $A\otimes (B\otimes C) = (A\otimes B)\otimes C$ and $(A\otimes B)(C\otimes D) = AC\otimes BD$ (when $AC$ and $BD$ exist).

For $p(x) = \alpha_{0}+\alpha_{1}x+\alpha_{2}x^{2}+\cdots +\alpha_{n-1}x^{n-1}$, prove that

where $1,\xi ,\xi^{2},\ldots ,\xi^{n-1}$ are the $n$th roots of unity.

Consider a waveform given by a finite sum $x(\tau ) = \sum_{k}(\alpha_{k}\cos 2\pi f_{k}\tau + \beta_{k}\sin 2\pi f_{k}\tau )$, in which the $f_{k}$'s are distinct integers, and let $x = \sum_{k}(\alpha_{k}\cos 2\pi f_{k}t + \beta_{k}\sin 2\pi f_{k}t)$ be the vector containing the values of $x(\tau )$ at $n > 2\max \left\{ f_{k}\right\}$ equally spaced points between $\tau =0$ and $\tau =1$ (Example 5.8.3). Use the discrete Fourier transform to prove that

Let $\eta$ be an arbitrary scalar, and let $c = \begin{pmatrix} 1 \\ \eta \\ \eta^{2} \\ \vdots \\ \eta^{2n-1} \end{pmatrix}$ and $a = \begin{pmatrix} \alpha_{0} \\ \alpha_{1} \\ \vdots \\ \alpha_{n-1} \end{pmatrix}$. Prove that $c^{T}(a \odot a) = \left(c^{T}\hat{a}\right)^{2}$.

Apply the FFT algorithm to the vector $x_{8} = \begin{pmatrix} x_{0} \\ x_{1} \\ \vdots \\ x_{7} \end{pmatrix}$, and then verify that your answer agrees with the result obtained by computing $F_{8}x_{8}$ directly.

Let $\overrightarrow {v}_{0}, \overrightarrow {v}_{1}, \ldots , \overrightarrow {v}_{2^{n}-1}$ be an orthonormal basis in $\mathbb {C}^{2^{n}}$. We define

Show that $U$ is unitary. In other words show that $UU^{*} = I_{2^{n}}$, using the completeness relation

The numbers $1, i, -1, -i$ form a group under multiplication. Do the vectors

form an orthonormal basis in $\mathbb {C}^{4}$?

Let $n$ be a prime number and $j,k = 1,\ldots ,n$. Show that the matrices

are unitary.

In the Hilbert space $\mathbb {C}^{4}$ consider the Bell states

Let $\left\{ \left|a_{0}\right\rangle , \left|a_{1}\right\rangle , \ldots , \left|a_{n-1}\right\rangle \right\}$ be an orthonormal basis in the Hilbert space $\mathbb {C}^{n}$. The discrete Fourier transform

where $\omega := \mathrm{exp}\left(2\pi i/n\right)$ is the primitive $n$-th root of unity.