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 at a representation of is
For each representation of , is a matrix, where is the degree of .
The inverse Fourier transform at an element of is given by
Properties
Transform of a convolution
The convolution of two functions is defined as
The Fourier transform of a convolution at any representation of is given by
Plancherel formula
For functions , the Plancherel formula states
where are the irreducible representations of
Fourier transform for finite abelian groups
If the group G is a finite abelian group, the situation simplifies considerably:
- all irreducible representations are of degree 1 and hence equal to the irreducible characters of the group. Thus the matrix-valued Fourier transform becomes scalar-valued in this case.
- The set of irreducible G-representations has a natural group structure in its own right, which can be identified with the group of group homomorphisms from G to . This group is known as the Pontryagin dual of G.
The Fourier transform of a function is the function given by
The inverse Fourier transform is then given by
For , a choice of a primitive n-th root of unity yields an isomorphism
given by . In the literature, the common choice is , which explains the formula given in the article about the discrete Fourier transform. However, such an isomorphism is not canonical, similarly to the situation that a finite-dimensional vector space is isomorphic to its dual, but giving an isomorphism requires choosing a basis.
A property that is often useful in probability is that the Fourier transform of the uniform distribution is simply where 0 is the group identity and is the Kronecker delta.
Fourier Transform can also be done on cosets of a group.
Relationship with representation theory
There is a direct relationship between the Fourier transform on finite groups and the representation theory of finite groups. The set of complex-valued functions on a finite group, , together with the operations of pointwise addition and convolution, form a ring that is naturally identified with the group ring of over the complex numbers, . Modules of this ring are the same thing as representations. Maschke's theorem implies that is a semisimple ring, so by the Artin–Wedderburn theorem it decomposes as a direct product of matrix rings. The Fourier transform on finite groups explicitly exhibits this decomposition, with a matrix ring of dimension for each irreducible representation. More specifically, the Peter-Weyl theorem (for finite groups) states that there is an isomorphism
given by
The left hand side is the group algebra of G. The direct sum is over a complete set of inequivalent irreducible G-representations .
The Fourier transform for a finite group is just this isomorphism. The product formula mentioned above is equivalent to saying that this map is a ring isomorphism.
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 (Å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 (Munthe-Kaas 2006).
References
- Åhlander, Krister; Munthe-Kaas, Hans Z. (2005), "Applications of the generalized Fourier transform in numerical linear algebra", BIT, 45 (4): 819–850, CiteSeerX 10.1.1.142.3122, doi:10.1007/s10543-005-0030-3, MR 2191479.
- Diaconis, Persi (1988), Group representations in probability and statistics, Lecture Notes—Monograph Series, 11, Institute of Mathematical Statistics, Zbl 0695.60012.
- Diaconis, Persi (1991-12-12), "Finite Fourier Methods: Access to Tools", in Bollobás, Béla; Chung, Fan R. K. (eds.), Probabilistic combinatorics and its applications, Proceedings of Symposia in Applied Mathematics, 44, American Mathematical Society, pp. 171–194, ISBN 978-0-8218-6749-5.
- Munthe-Kaas, Hans Z. (2006), "On group Fourier analysis and symmetry preserving discretizations of PDEs", Journal of Physics A, 39 (19): 5563–84, CiteSeerX 10.1.1.329.9959, doi:10.1088/0305-4470/39/19/S14, MR 2220776.
- Terras, Audrey (1999), Fourier Analysis on Finite Groups and Applications, Cambridge University Press, p. 251, ISBN 978-0-521-45718-7, Zbl 0928.43001.