TOPICS

# Danielson-Lanczos Lemma

The discrete Fourier transform of length (where is even) can be rewritten as the sum of two discrete Fourier transforms, each of length . One is formed from the even-numbered points; the other from the odd-numbered points. Denote the th point of the discrete Fourier transform by . Then

 (1) (2) (3)

where and . This procedure can be applied recursively to break up the even and odd points to their even and odd points. If is a power of 2, this procedure breaks up the original transform into transforms of length 1. Each transform of an individual point has for some . By reversing the patterns of evens and odds, then letting and , the value of in binary is produced. This is the basis for the fast Fourier transform.

Discrete Fourier Transform, Fast Fourier Transform, Fourier Transform

## Explore with Wolfram|Alpha

More things to try:

## References

Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 407-411, 1989.

## Referenced on Wolfram|Alpha

Danielson-Lanczos Lemma

## Cite this as:

Weisstein, Eric W. "Danielson-Lanczos Lemma." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Danielson-LanczosLemma.html