Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Fourier transform on finite groups
Summary
In mathematics, the Fourier transform on finite groups is a generalization of the discrete Fourier transform from cyclic to arbitrary finite groups.
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
The convolution of two functions is defined as
The Fourier transform of a convolution at any representation of is given by
For functions , the Plancherel formula states
where are the irreducible representations of .
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.
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, .
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.