Linear Algebra Done Right · Problem 7D.19

Operators on Inner Product Spaces — Sheldon Axler

Mathematics — Linear Algebra · discrete-fourier-transform

Problem

Suppose nn is a positive integer. For this exercise, we adopt the notation that a typical element zz of Cn\mathbf{C}^n is denoted by z=(z0,z1,…,zn−1)z = (z_0, z_1, \ldots, z_{n-1}). Define linear functionals ω0,ω1,…,ωn−1\omega_0, \omega_1, \ldots, \omega_{n-1} on Cn\mathbf{C}^n by ωj(z0,z1,…,zn−1)=1n∑m=0n−1zme−2πijm/n.\omega_j(z_0, z_1, \ldots, z_{n-1}) = \frac{1}{\sqrt{n}} \sum_{m=0}^{n-1} z_m e^{-2\pi i j m/n}. The discrete Fourier transform is the operator F:Cn→Cn\mathcal{F} : \mathbf{C}^n \to \mathbf{C}^n defined by Fz=(ω0(z),ω1(z),…,ωn−1(z)).\mathcal{F}z = (\omega_0(z), \omega_1(z), \ldots, \omega_{n-1}(z)). (a) Show that F\mathcal{F} is a unitary operator on Cn\mathbf{C}^n. (b) Show that if (z0,…,zn−1)∈Cn(z_0, \ldots, z_{n-1}) \in \mathbf{C}^n and znz_n is defined to equal z0z_0, then F−1(z0,z1,…,zn−1)=F(zn,zn−1,…,z1).\mathcal{F}^{-1}(z_0, z_1, \ldots, z_{n-1}) = \mathcal{F}(z_n, z_{n-1}, \ldots, z_1). (c) Show that F4=I\mathcal{F}^4 = I. The discrete Fourier transform has many important applications in data analysis. The usual Fourier transform involves expressions of the form ∫−∞∞f(x)e−2πitx dx\int_{-\infty}^{\infty} f(x)e^{-2\pi itx}\,dx for complex-valued integrable functions ff defined on R\mathbf{R}.

Related theory

Browse the problem library