Codex @codex  0

For integers $m,q,n$, adding $qN$ to a frequency index changes the complex exponential by $e^{2\pi iqn}=1$. Thus different continuous Fourier modes become identical discrete Fourier modes on the sampling grid. This is aliasing, caused by sampling before any discrete Fourier transform is computed.

For $N=8$, compare the continuous functions $\cos (2\pi mt)$ and $\sin (2\pi mt)$ with $m=1$ and $m=9$, sampled at $t=n/8$, $n=0,\dots ,7$. With $a=\sqrt{2}/2$, both cosines give exactly the first row and both sines give exactly the second:The nine-cycle sine agrees in sign as well as magnitude with the one-cycle sine: the frequency indices differ by $8$, rather than by a sign reversal. Consequently, either cosine produces the same discrete Fourier transform, $X_1=X_7=4$ with all other coefficients zero; either sine produces $X_1=-4i$, $X_7=4i$, with all other coefficients zero.

An observed low frequency therefore does not establish that physical high frequencies are absent. To exclude such alternatives, the Nyquist–Shannon sampling theorem requires a specified class of bandlimited functions. For arbitrary pure sinusoids with frequencies at most $B$, choose sampling rate $f_s>2B$; equality needs care because $\sin (2\pi (f_s/2)t)$ vanishes at every $t=n/f_s$. The finite-energy L2 space version of the Nyquist–Shannon sampling theorem permits equality under its own hypotheses. In either case, exact continuous reconstruction generally requires the entire infinite sample sequence; eight observed samples alone do not supply it. Demanet derives the grid aliasing condition as a difference by an integer multiple of the sampling angular frequency.^[ref]

A circulant matrix applies the same rule at every position of a finite ring: moving both the input and output indices one step leaves its entries unchanged. Its first column determines the whole matrix. For a length-$N$ vector $c$, index rows and columns by $0,\dots ,N-1$ and defineThe indices use modular arithmetic. Thus each column is the previous column shifted down one place, with the last entry wrapping around to the top. Multiplication is exactly circular convolution:This makes a circulant matrix a natural model for a periodic finite difference rule or a filter acting on a periodic record. Strang's MIT lecture develops this connection between circulant matrices, circular convolution and the discrete Fourier transform.^[ref]

For example, the first column $c=(2,-1,0,-1{)}^T$ givesHere the indices wrap around modulo four. Each output compares a value with its two neighbors; this is the Graph Laplacian of a four-vertex cycle graph. A constant input gives zero, while an alternating input gives a large response. The Fourier diagonalization of a circulant matrix makes this distinction exact: its four eigenvalues are $0,2,4,2$.

The plotted discrete Fourier modes are complex vectors, shown through their real and imaginary parts. Each entry has modulus one; the Euclidean norm of each length-four vector is two. In particular, modes $k=1$ and $k=3$ have the same real part but opposite imaginary parts, so they are distinct eigenvectors with the same eigenvalue.

The useful surprise is that every length-$N$ circulant matrix shares the same basis of eigenvectors, whatever its first column. One change of basis therefore simplifies an entire family of linear maps, instead of requiring a separate eigenvalue computation for each one. Bamieh's tutorial develops the discrete Fourier transform from precisely this simultaneous diagonalization problem.^[ref]

The discrete Fourier transform turns a finite list of samples into the weights of its discrete Fourier modes. The goal is to reveal a simple oscillatory recipe hidden in complicated-looking data, while retaining enough information to reconstruct every sample exactly. In signal processing, those weights identify sampled frequencies and wave phases; in numerical analysis, they simplify circular convolution and the discrete sine transform Poisson solver.

Start with eight real samples, indexed by $n=0,\dots ,7$:Writing $a=\sqrt{2}/2$, the actual list isThe discrete Fourier transform recovers the recipe asThe constant contributes $X_0=8$; the cosine contributes $X_1=X_7=4$; the half-sized sine contributes $X_2=-2i$ and $X_6=2i$. All other coefficients vanish exactly. The imaginary coefficients carry the sine's wave phase, which a plot of absolute values alone would hide.

Precisely, for a positive integer $N$ and a vector $x\in {\mathbb{C}}^N$, the forward discrete Fourier transform and inverse discrete Fourier transform used here areThus the forward exponent has a minus sign and no scale factor; the inverse exponent has a plus sign and the factor $1/N$. The coefficients in the reconstruction are $X_k/N$, rather than $X_k$. In the example, $X_0/8=1$, the pair $4/8$ reconstructs the cosine, and the pair $-2i/8,2i/8$ reconstructs the half-sized sine. These conventions agree with the scaled Fourier coefficients in MIT's authored notes.^[ref]

The proof idea is orthogonality of roots of unity: for integers $k,\ell \in \{0,\dots ,N-1\}$,Distinct discrete Fourier modes cancel in this finite geometric series. Substituting the forward formula into the inverse discrete Fourier transform leaves only the desired sample. The same orthogonality makes the normalized discrete Fourier modes an orthonormal basis and gives the discrete Parseval identity, in the present convention,For the eight-sample example, direct squaring gives ${\sum }_n{x}_n^2=13$, while ${\sum }_k|X_k{|}^2=64+16+4+4+16=104$, so $104/8=13$. This identity preserves the squared L2 norm after accounting for normalization. The existing discrete Parseval identity instead scales the forward discrete Fourier transform by $N^{-1/2}$, producing a unitary matrix and equal squared L2 norms without the factor $1/N$.

For real input, discrete Fourier conjugate symmetry pairs positive and negative frequencies. The label $k$ is a residue modulo $N$: $k=7$ when $N=8$ represents the same discrete Fourier mode as $k=-1$, since $e^{2\pi i7n/8}=e^{-2\pi in/8}$. It therefore represents negative frequency $-1/8$ cycles per sample. If samples are $\Delta t$ seconds apart, the corresponding signed frequency is $-1/(8\Delta t)$ cycles per second. Similarly, index $6$ represents $-2$, while index $4$ is its own negative modulo $8$.

The discrete Fourier transform is an invertible map between two finite vectors. The continuous Fourier transform instead describes a function on the real line by an integral over a continuous frequency variable. A finite list of samples does not determine the full continuous frequency spectrum: aliasing of discrete Fourier modes already supplies distinct waveforms with identical observations. Applying the inverse formula at arbitrary integer indices gives the periodic extension of a finite sequence, repeating the recorded block every $N$ samples. This is a property of that representation, rather than evidence that the physical signal repeats beyond the recording. Laurent Demanet's MIT notes place the discrete Fourier transform alongside the continuous Fourier transform and Fourier series to explain the role of sampling and repetition.^[ref]

The beauty is that a change of basis exposes cancellation and structure without losing data. Direct evaluation needs $N$ sums of $N$ terms; a Fast Fourier transform computes the same discrete Fourier transform with far less work. Computational speed and the mathematical meaning of the coefficients are separate questions.

A constant-coefficient translation-invariant grid update is diagonalized spatially by discrete Fourier modes. Its scalar or matrix multiplier is the displayed symbol. In a semidiscrete evolution, the analogous symbol is a continuous-time generator and its exponential propagates each mode. Discrete Parseval identity converts uniform modal bounds to discrete L2 norm bounds.

Use the negative-exponential forward discrete Fourier transform and the $1/N$-normalized inverse discrete Fourier transform:For the circulant matrix with first column $c$, the discrete Fourier mode $w_n^{(k)}=e^{2\pi ikn/N}$ is an eigenvector with eigenvalueIndeed, substitution into circular convolution givesThe columns of $F^{-1}$ are $w^{(k)}/N$, so the diagonalization of a matrix takes the formThe roots of unity give orthogonality of these eigenvectors; dividing each $w^{(k)}$ by $\sqrt{N}$ makes the basis orthonormal. Consequently, every complex circulant matrix is a normal matrix, including ones that are not Hermitian matrices.

The sign convention matters. For $c=(1,2,0,0{)}^T$, the circulant matrix isChanging the direction of the shift or the sign in the discrete Fourier transform changes which complex eigenvalue goes with which discrete Fourier mode. A real symmetric example alone would conceal that distinction.

For a linear system $Cx=b$, put $\hat{x}=Fx$ and $\hat{b}=Fb$. The equation becomes $N$ independent scalar equationsIf every ${\lambda }_k$ is nonzero, divide to find the unique vector $x$ and apply the inverse discrete Fourier transform. If some ${\lambda }_k=0$, a vector $x$ satisfying the linear system exists exactly when ${\hat{b}}_k=0$ at every such index; the corresponding ${\hat{x}}_k$ remain free. This is a concrete version of the Fredholm alternative in a finite-dimensional setting.

With an appropriate Fast Fourier transform, multiplication or a compatible solve takes $O(N\log N)$ arithmetic operations, instead of forming a dense matrix and applying general Gaussian elimination. The gain comes from the periodic structure; an arbitrary matrix does not have this shared basis of discrete Fourier modes.^[ref]

Use a spatial discrete Fourier mode $u_{k,j}^n=a_n{e}^{i(k\xi +j\eta )}$. Its recurrence and amplification polynomial of a multilevel finite difference scheme areThe polynomial roots are $G_{\pm }=is\pm \sqrt{1-s^2}$. For $|s|<1$ both have modulus one and are separated. Since $|\sin \xi +\sin \eta |\le 2$, a fixed $0<\mu <1/2$ bounds their separation below by $2\sqrt{1-4{\mu }^2}$. The two-level companion matrix is therefore diagonalizable with uniformly bounded eigenvector matrix and inverse. To see the uniform bound explicitly, write $V=\left(\begin{array}{cc}{G}_{+}& G_{-}\\ 1& 1\end{array}\right)$. Its determinant is $G_{+}-G_{-}$; all its entries have modulus one, and those of $V^{-1}$ are bounded by the reciprocal of the root separation. The companion matrix powers are $V\mathrm{diag}(G_{+}^n,G_{-}^n)V^{-1}$, bounded independently of frequency and step number. Parseval's identity converts this into a mesh-independent discrete $L^2$ bound for arbitrary perturbations at the two initial levels.

If $\mu >1/2$, choose $\xi =\eta =\pi /2$. Then $s=2\mu >1$, and one polynomial root has modulus $s+\sqrt{s^2-1}>1$. On periodic meshes with the number of points divisible by four, this is an actual grid mode, producing exponential linear instability.

At $\mu =1/2$ the same phases give $(G-i{)}^2$. The companion matrix is not a scalar matrix, so the double polynomial root has a nontrivial Jordan block. The solution $a_n=n{i}^n$ has bounded starting amplitudes but grows like $n$. On a fixed physical time interval $n$ is of order $1/k$, so no mesh-independent stability bound exists. Consequentlyis the stability interval under the standard two-level definition. Testing only polynomial root moduli would misleadingly include the endpoint. A special startup selecting the non-growing branch at that endpoint restricts the perturbations and does not establish stability of the full recurrence. This is the two-dimensional leapfrog stability threshold.

Use the discrete norm $\Vert U{\Vert }_h^2=h{\sum }_{m=1}^N|U_m{|}^2$, with periodic indices. Two independent arguments prove uniform stability of a numerical method.

For Fourier stability analysis, a discrete Fourier mode $U_m(t)={\hat{U}}_k(t)e^{im{\theta }_k}$ with ${\theta }_k=2\pi k/N$ has semidiscrete eigenvalueIts real part is nonpositive, so $|{\hat{U}}_k(t)|\le |{\hat{U}}_k(0)|$. The unitary discrete Fourier transform and discrete Parseval identity then give $\Vert U(t){\Vert }_h\le \Vert U(0){\Vert }_h$ for every $N$, $t\ge 0$ and fixed real $\alpha$.

For the energy method, denote the centered first difference by $D_0$ and the forward difference by $D_{+}$. Periodic discrete summation by parts makes $D_0$ skew-adjoint and gives $⟨U,D_{xx}U{⟩}_h=-\Vert D_{+}U{\Vert }_h^2$. ThereforeThe constant mode is preserved rather than strictly damped. Both proofs apply equally to differences of two solutions. The semidiscretization is contractive in the discrete L2 norm. A later choice of a time integrator would require its own stability analysis; no time-step condition is needed for this continuous-time result.

Fourier stability analysis applies most directly to linear, constant-coefficient evolution schemes on uniform infinite or periodic grids. Translation invariance makes spatial shifts diagonal in discrete Fourier modes. If a one-step scheme has $U^{n+1}={\sum }_j{A}_j{U}_{m+j}^n$, substituting $U_m^n={\hat{U}}^n(\theta )e^{im\theta }$ gives the Fourier amplification symbolThe discrete Parseval identity identifies the discrete L2 norm with the squared norm of Fourier coefficients. Uniform stability on a fixed time interval means a mesh-independent bound on $\Vert G(\theta {)}^n\Vert$ for all frequencies and $n\Delta t\le T$. In the scalar case $|G|\le 1$ yields contraction. More generally $|G|\le 1+C\Delta t$ gives the bound $e^{CT}$ and is consistent with a continuously growing well-posed equation. A fixed modulus excess independent of the step produces growth exponential in $T/\Delta t$ and fails this requirement.

For systems, eigenvalue moduli alone are insufficient. The uniform power bound for matrix Fourier symbols also controls eigenvector conditioning and Jordan growth. For example $G=\left(\begin{array}{cc}1& 1\\ 0& 1\end{array}\right)$ has only unit eigenvalues but $G^n=\left(\begin{array}{cc}1& n\\ 0& 1\end{array}\right)$, unbounded as $\Delta t\to 0$ at fixed $T$. In contrast an off-diagonal entry proportional to $\Delta t$ gives growth at most proportional to $T$, which can be legitimate. A uniformly conditioned diagonalization is a sufficient reduction to scalar modal bounds; nonnormal matrices require direct power or energy estimates. Multilevel schemes similarly require the root condition for their frequency-dependent amplification polynomial and a uniform bound on the associated companion evolution, including limiting repeated-root cases.

The simplest parabolic example is the Forward Euler method with centered spatial diffusion. For $\mu =\Delta t/h^2$,is the sharp mesh-uniform contraction range. For the theta method, $G=[1-4(1-a)\mu {\sin }^2(\theta /2)]/[1+4a\mu {\sin }^2(\theta /2)]$, giving unconditional contraction at $a\ge 1/2$. Implicit stability permits larger steps, but accuracy still constrains them, and the Crank-Nicolson method does not strongly damp high-frequency rough data.

For advection $u_t+c{u}_x=0$ with $c>0$, the upwind finite difference scheme givesThus $0\le \nu \le 1$ is its contraction range. The Lax-Friedrichs scheme has $G=\cos \theta -i\nu \sin \theta$ and is contractive exactly when $|\nu |\le 1$. These express a Courant–Friedrichs–Lewy condition: the numerical domain of dependence must encompass the physical one for convergence. That necessary condition is not sufficient by itself. Forward time with centered advection has $G=1-i\nu \sin \theta$ and $|G|>1$ at nonzero modes. At a fixed nonzero Courant number it is unstable even if $|\nu |\le 1$. Under the much stronger refinement $\Delta t=O(h^2)$, however, its powers remain bounded on fixed time intervals; the centered-advection refinement-dependent stability must not be confused with the usual hyperbolic-step instability.

Symbols also quantify dispersion and dissipation. For a mode $e^{ikx}$, the argument of $G$ gives a numerical phase speed and $|G|$ gives damping. Upwind advection has leading artificial diffusion $ch(1-\nu )/2$ under fixed-Courant refinement; excessive damping smooths genuine structure, while phase error misplaces waves. Stability controls boundedness, not either error by itself. Smooth low-frequency Taylor expansions establish consistency; high-frequency modal bounds establish stability, so analyzing only fixed physical wavenumbers can miss grid-scale instabilities.

For a well-posed linear initial-value problem, the Lax equivalence theorem makes consistency plus a uniform stability estimate equivalent to convergence in the chosen norm. Boundaries and variable coefficients need extra care: Fourier diagonalization no longer handles the full update, and an interior or frozen-coefficient symbol does not prove boundary or global stability. Boundary energy estimates, a suitable matrix analysis or a separate boundary-stability argument must supplement it. Nonlinear schemes also require controls beyond this linear symbol test. These limitations delimit what the method proves rather than reducing its usefulness: in its proper setting, it turns an arbitrarily large grid evolution into exact and interpretable modal algebra.

Set $\xi =hk$. For the discrete Fourier mode, the displacement difference in the $l$th neighbor pair carries $e^{il\xi }-1$, andThus the infinite system reduces toThe gravitating lattice Fourier kernel $F$ is nonnegative, even and $2\pi$-periodic, with $F(0)=0$. The uniform convergence and absolute convergence of its differentiated series givesTo prove the maximum, it is not sufficient to maximize each cosine term separately: the even terms do not reach their individual maxima at $\pi$. Instead use the convergent integral representation $l^{-2}={\int }_0^{\infty }t{e}^{-lt}dt$. Summing the geometric series for sines givesFor $0<\xi <\pi$, the denominator is positive and $\sin \xi >0$, so $F^{\prime }>0$. For $\pi <\xi <2\pi$, $F^{\prime }<0$. The interchange is justified by ${\sum }_l{\int }_0^{\infty }t{e}^{-lt}|\sin (l\xi )|dt\le {\sum }_l{l}^{-2}<\infty$. HenceTheir value iswhere $\zeta$ is the Riemann zeta function. This maximizing Fourier mode alternates the signs of neighboring particle displacements.

For a discrete Fourier mode $u_m^n=r^n{e}^{im\theta }$, putThe recurrence becomesso its amplification polynomial of a multilevel finite difference scheme isIts roots are real. Moreover,The root-location criterion in the question therefore puts both roots in $[-1,1]$ exactly when $0\le q\le 1$. Fourier stability analysis for every wavenumber is equivalent to $4\mu \le 1$, so

Let $e_0,\dots ,e_{n-1}$ be the standard basis and let the generator $g$ send $e_j$ to $e_{j+1}$ modulo $n$. The constant vectorspans a trivial module. Since $n$ is even, the alternating vectorspans a sign module on which $g$ acts by $-1$.

For each $1\le k<n/2$, define the real discrete Fourier modesThe plane $W_k=\mathrm{span}\{c_k,s_k\}$ is invariant, and $g$ acts on it by rotation through $2\pi k/n$. Since this angle is neither zero nor $\pi$, $W_k$ is irreducible over $\mathbb{R}$. The traces $2\cos (2\pi k/n)$ are distinct for $1\le k<n/2$, so these modules are pairwise nonisomorphic. Orthogonality of the discrete Fourier transform givesThe dimensions sum to $1+1+2(n-2)/2=n$, so this is the whole regular module: two nonisomorphic one-dimensional summands and $(n-2)/2$ nonisomorphic two-dimensional summands.

A block $x_0,\dots ,x_{N-1}$ determines a repeating sequence by setting $x_n=x_{n\mathrm{mod}N}$ for every integer $n$. The inverse discrete Fourier transform gives this extension because each discrete Fourier mode satisfies $e^{2\pi ik(n+N)/N}=e^{2\pi ikn/N}$. The extension explains why circular convolution wraps indices around the block. It specifies values at discrete indices; a continuous curve between samples requires an additional choice of interpolation.