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 rightarrow mathbb{C},

at a representation

rho,

G,

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

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

Let $rho_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_i d_i text{Tr}left(rho_i(a^{-1})widehat{f}(rho_i)right),>

where $d_i,$ is the degree of the representation $rho_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 $rho,$ of $G,$ is given by

widehat{f ast g}(rho) = widehat{f}(rho)widehat{g}(rho).

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}

sum_i d_i text{Tr}left(widehat{f}(rho_i)widehat{g}(rho_i)right),>

where $rho_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_srangle$ 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}

> 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 . These algorithms can be used for the construction of numerical methods for solving partial differential equations that preserve the symmetries of the equations .

References

.
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.).
.