Fourier transform on finite groups

Definitions

The Fourier transform of a function f : G → C at a representation ϱ : G → G L ( d ϱ , C ) of G is

For each representation ϱ of G , f ^ ( ϱ ) is a d ϱ × d ϱ matrix, where d ϱ is the degree of ϱ .

Let ϱ i be a complete set of inequivalent irreducible representations of G . Then the matrix entries of the ϱ i are mutually orthogonal functions on G . Since the dimension of the transform space is equal to | G | , it follows that ∑ i d ϱ i 2 = | G | .

The inverse Fourier transform at an element a of G is given by

Transform of a convolution

The convolution of two functions f , g : G → C is defined as

The Fourier transform of a convolution at any representation ϱ of G is given by

Plancherel formula

For functions f , g : G → C , the Plancherel formula states

where ϱ 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.

Let G ^ be the set of group homomorphisms G → C ∗ . This forms a group under point-wise multiplication. We may define the Fourier transform for finite abelian groups for an element f ∈ G ^ as the function f ^ : G ^ → C given by

Note that the right-hand side is simply ⟨ f , χ ⟩ for the inner product on the vector space of functions from G to C defined by

The inverse Fourier transform is then given by

Since G is finite abelian, the irreducible characters of a group may be put into one-to one correspondence with elements of the group. If we fix an isomorphism of G ^ → G for each g ∈ G , we may write χ g for the character corresponding to g . Thus the Fourier transform can be rewritten as a function f ^ : G → C .

and the inverse is given by

Note that the inverse fourier transform is technically an element of G ^ ^ , but using the isomorphism from G to G ^ , we get an element of G ^ that equals f

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

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, G , together with the operations of pointwise addition and convolution, form a ring that is naturally identified with the group ring of G over the complex numbers, C [ G ] . Modules of this ring are the same thing as representations. Maschke's theorem implies that C [ G ] 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 d ϱ for each irreducible representation.

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