Fourier transform on finite groups


Fourier transform on finite groups

In mathematics, the Fourier transform on finite groups is a generalization of the discrete Fourier transform from cyclic to arbitrary finite groups.

Definitions

The Fourier transform of a function f : G ightarrow mathbb{C},at a representation ho, of G, is

:widehat{f}( ho) = sum_{a in G} f(a) ho(a).

So for each representation ho, of G,, widehat{f}( ho), is a d_ ho imes d_ ho, matrix, where d_ ho, is the degree of ho,.

Let ho_i, be the irreducible representations of G. Then the inverse Fourier transform at an element a, of G, is given by

:f(a) = frac{1} sum_{s in G} widehat{f}(s) chi_s(a).

A property that is often useful in probability is that the Fourier transform of the uniform distribution is simply delta_{a,0},, where 0 is the group identity and delta_{i,j}, is the Kronecker delta.

Applications

This generalization of the discrete Fourier transform is used in numerical analysis. A circulant matrix is a matrix where every column is a cyclic shift of the previous one. Circulant matrices can be diagonalized quickly using the fast Fourier transform, and this yields a fast method for solving systems of linear equations with circulant matrices. Similarly, the Fourier transform on arbitrary groups can be used to give fast algorithms for matrices with other symmetries harv|Åhlander|Munthe-Kaas|2005. These algorithms can be used for the construction of numerical methods for solving partial differential equations that preserve the symmetries of the equations harv|Munthe-Kaas|2006.

ee also

*Fourier transform
*Discrete Fourier transform
*Representation theory of finite groups
*Character theory

References

* | year=2005 | journal=BIT | issn=0006-3835 | volume=45 | issue=4 | pages=819–850.
* Diaconis, P. (1988). "Group Representations in Probability and Statistics." Lecture Notes — Monograph Series, Vol. 11. Hayward, California: Institute of Mathematical Statistics.
* Diaconis, P. (1991). "Finite Fourier Methods: Access to Tools." In "Probabilistic Combinatorics and its Applications," Proceedings of Symposia in Applied Mathematics, Vol. 44. Bollobás, B., and Chung, F. R. K. (ed.).
* | year=2006 | journal=Journal of Physics A | issn=0305-4470 | volume=39 | issue=19 | pages=5563–5584.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Fourier transform — Fourier transforms Continuous Fourier transform Fourier series Discrete Fourier transform Discrete time Fourier transform Related transforms The Fourier transform is a mathematical operation that decomposes a function into its constituent… …   Wikipedia

  • Representation theory of finite groups — In mathematics, representation theory is a technique for analyzing abstract groups in terms of groups of linear transformations. See the article on group representations for an introduction. This article discusses the representation theory of… …   Wikipedia

  • Discrete Fourier transform — Fourier transforms Continuous Fourier transform Fourier series Discrete Fourier transform Discrete time Fourier transform Related transforms In mathematics, the discrete Fourier transform (DFT) is a specific kind of discrete transform, used in… …   Wikipedia

  • Discrete Fourier transform (general) — See also: Fourier transform on finite groups This article is about the discrete Fourier transform (DFT) over any field (including finite fields), commonly called a number theoretic transform (NTT) in the case of finite fields. For specific… …   Wikipedia

  • Fast Fourier transform — A fast Fourier transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. There are many distinct FFT algorithms involving a wide range of mathematics, from simple complex number arithmetic to group …   Wikipedia

  • Fourier series — Fourier transforms Continuous Fourier transform Fourier series Discrete Fourier transform Discrete time Fourier transform Related transforms …   Wikipedia

  • Fourier algebra — Fourier and related algebras occur naturally in the harmonic analysis of locally compact groups. They play an important role in the duality theories of these groups. The Fourier–Stieltjes algebra and the Fourier algebra of a locally compact group …   Wikipedia

  • Fourier analysis — In mathematics, Fourier analysis is a subject area which grew out of the study of Fourier series. The subject began with trying to understand when it was possible to represent general functions by sums of simpler trigonometric functions. The… …   Wikipedia

  • List of Fourier analysis topics — This is an alphabetical list of Fourier analysis topics. See also the list of Fourier related transforms, and the list of harmonic analysis topics. Almost periodic function ATS theorem Autocorrelation Autocovariance Banach algebra Bessel function …   Wikipedia

  • Multiplier (Fourier analysis) — In Fourier analysis, a multiplier operator is a type of linear operator, or transformation of functions. These operators act on a function by altering its Fourier transform. Specifically they multiply the Fourier transform of a function by a… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.