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.