Fourier transform on finite groups

See also: Discrete Fourier transform (general)

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 \rightarrow \mathbb{C}\,$ at a representation $\varrho : G \rightarrow GL(d_\varrho, \mathbb{C})\,$ of $G\,$ is

$\widehat{f}(\varrho) = \sum_{a \in G} f(a) \varrho(a).$

So for each representation $\varrho\,$ of $G\,$, $\widehat{f}(\varrho)\,$ is a $d_\varrho \times d_\varrho\,$ matrix, where $d_\varrho\,$ is the degree of $\varrho\,$.

Let $\varrho_i\,$ be a complete set of inequivalent irreducible representations of G. Then, $|G| = \sum_i d_{\varrho_i}^2$. Then the inverse Fourier transform at an element $a\,$ of $G\,$ is given by

$f(a) = \frac{1}{|G|} \sum_i d_{\varrho_i} \text{Tr}\left(\varrho_i(a^{-1})\widehat{f}(\varrho_i)\right),$

where $d_{\varrho_i}\,$ is the degree of the representation $\varrho_i.\,$

Properties

Transform of a convolution

The convolution of two functions $f, g : G \rightarrow \mathbb{C}\,$ is defined as

$(f \ast g)(a) = \sum_{b \in G} f(ab^{-1}) g(b).$

The Fourier transform of a convolution at any representation $\varrho\,$ of $G\,$ is given by

$\widehat{f \ast g}(\varrho) = \widehat{f}(\varrho)\widehat{g}(\varrho).$

Plancherel formula

For functions $f, g : G \rightarrow \mathbb{C}\,$, the Plancherel formula states

$\sum_{a \in G} f(a^{-1}) g(a) = \frac{1}{|G|} \sum_i d_{\varrho_i} \text{Tr}\left(\widehat{f}(\varrho_i)\widehat{g}(\varrho_i)\right),$

where $\varrho_i\,$ are the irreducible representations of $G.\,$

Fourier transform on finite abelian groups

Since the irreducible representations of finite abelian groups are all of degree 1 and hence equal to the irreducible characters of the group, Fourier analysis on finite abelian groups is significantly simplified. For instance, the Fourier transform yields a scalar- and not matrix-valued function.

Furthermore, the irreducible characters of a group may be put in one-to-one correspondence with the elements of the group.

Therefore, we may define the Fourier transform for finite abelian groups as

$\widehat{f}(s) = \sum_{a \in G} f(a) \bar{\chi_s}(a).$

Note that the right-hand side is simply $\langle f, \chi_s\rangle$ for the inner product on the vector space of functions from $G\,$ to $\mathbb{C}\,$ defined by

$\langle f, g \rangle = \sum_{a \in G} f(a) \bar{g}(a).$

The inverse Fourier transform is then given by

$f(a) = \frac{1}{|G|} \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 (Å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).

See also

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

References

• Åhlander, Krister; Munthe-Kaas, Hans Z. (2005), "Applications of the generalized Fourier transform in numerical linear algebra", BIT 45 (4): 819–850, doi:10.1007/s10543-005-0030-3, MR2191479 .
• 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.).
• Munthe-Kaas, Hans Z. (2006), "On group Fourier analysis and symmetry preserving discretizations of PDEs", Journal of Physics A 39 (19): 5563–5584, doi:10.1088/0305-4470/39/19/S14, MR2220776 .
• Terras, A. (1999). Fourier Analysis on Finite Groups and Applications. Cambridge: Cambridge University Press.