View source for Finite Fourier Analysis

== Motivation ==

(This is what I currently think of as motivation for finite Fourier analysis.  If anyone can improve on this, please do.)


Consider the set <math>S</math> of functions <math>f:[0,1] \to \mathbb{C}</math> such that <math>f</math> is infinitely differentiable (using limits from the right or from the left at the endpoints) and such that <math>f(0) = f(1)</math> and <math>\frac{d^m f}{dx^m}(0) = \frac{d^m f}{dx^m}(1)</math> for all <math>m \in \mathbb{Z}^+</math> .  <math>S</math> is a vector space under the ordinary operations of function addition and scalar multiplication.


Consider the one-dimensional Laplace operator, <math>\frac{d^2}{dx^2}: S \to S</math>.  Integration by parts shows that this operator is self-adjoint.  Therefore, from our experience with the spectral theorem from finite-dimensional linear algebra, we might hope that the eigenfunctions of the Laplace operator in some sense form a basis for <math>S</math>.


What are the eigenfunctions (and eigenvalues) of the Laplace operator <math>\frac{d^2}{dx^2}:S \to S</math> ?  We need to find all the functions <math>f</math> in <math>S</math> such that <math>\frac{d^2f}{dx^2} = \lambda f</math> for some constant <math>\lambda</math>.  Using basic ODE stuff, and using the boundary conditions, it can be shown that the eigenfunctions are <math>F_n(x) = e^{i 2 n \pi x}</math>, where <math>n \in \mathbb{Z}</math>.  The corresponding eigenvalues are <math>\Lambda_n = -(2 n \pi)^2</math>.  In Fourier analysis, it can be proved that these eigenfunctions do in some sense form a basis of <math>S</math>.


Let <math>N \in \mathbb{Z}^+</math>.  Every function <math>G</math> in <math>S</math> can be associated with a column vector <math>g</math> in <math>\mathbb{C}^N</math> by sampling <math>G</math> at the <math>N</math> points <math>x=0</math>, <math>x=\frac1N</math>, <math>x=\frac2N</math>, <math>\ldots</math>, <math>x=\frac{N-1}N </math>.  For each <math>n \in \mathbb{Z}</math>, let <math>f_n</math> be the column vector in <math>\mathbb{C}^N</math> obtained by sampling the eigenfunction <math>F_n</math> at these <math>N</math> points.


It may seem that there are infinitely many vectors <math>f_n</math> here, one for each <math>n \in \mathbb{Z}</math>.  However, there is some redundancy.  The vectors <math>f_n</math> where <math>n=0</math>, <math>\ldots</math>, <math>N-1</math> are indeed distinct, but for example <math>f_N=f_0</math>, <math>f_{N+1}=f_1</math>, and so on.  So we really only have <math>N</math> distinct vectors here, corresponding to <math>n=0</math>, <math>\ldots</math> , <math>n=N-1</math>.


These vectors <math>f_n</math> have some properties that are, in a very nice and very cool way, analogous to certain properties of the eigenfunctions <math>F_n</math>.


Just as the <math>F_n</math> are eigenfunctions of the Laplace operator, the vectors <math>f_n</math> are eigenvectors of something called the "discrete Laplace operator", which is a self-adjoint operator, and which arises by approximating <math>G''</math> with something called a "second-order centered difference" from numerical analysis.  The eigenvalue <math>\lambda_n</math> corresponding to <math>f_n</math> is <math>-4 N^2 \sin^2(\frac{n \pi}N )</math> , which is approximately equal to <math>\Lambda_n</math> when <math>N</math> is much larger than <math>n</math>.  By directly taking dot products and using the formula for the sum of a finite geometric series, you can prove that the set of eigenvectors {<math>{f_n : n=0,\ldots, N-1}</math>} is orthogonal, and that the norm of <math>f_n</math> is <math>\sqrt{N}</math>.  We can normalize <math>f_n</math> by dividing it by <math>\sqrt{N}</math> and so obtain an orthonormal basis of eigenvectors of the discrete Laplace operator for <math>\mathbb{C}^N</math>.


In ordinary Fourier analysis, we may for example take a function in <math>S</math> and write it as an infinite linear combination of the functions <math>F_n.</math>  In finite Fourier analysis, we may take a vector in <math>\mathbb{C}^N</math> and write it as a linear combination of the vectors <math>f_n</math>.