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 formula_1 at a representation formula_2 of formula_3 is
For each representation formula_5 of formula_3, formula_7 is a formula_8 matrix, where formula_9 is the degree of formula_5.
The inverse Fourier transform at an element formula_11 of formula_3 is given by
Properties.
Transform of a convolution.
The convolution of two functions formula_14 is defined as
The Fourier transform of a convolution at any representation formula_5 of formula_3 is given by
Plancherel formula.
For functions formula_14, the Plancherel formula states
where formula_21 are the irreducible representations of formula_3.
Fourier transform for finite abelian groups.
If the group "G" is a finite abelian group, the situation simplifies considerably:
The Fourier transform of a function formula_26 is the function formula_27 given by
The inverse Fourier transform is then given by
For formula_30, a choice of a primitive "n"-th root of unity formula_31 yields an isomorphism
given by formula_33. In the literature, the common choice is formula_34, 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 formula_35, where 0 is the group identity and formula_36 is the Kronecker delta.
Fourier Transform can also be done on cosets of a group.
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, formula_3, together with the operations of pointwise addition and convolution, form a ring that is naturally identified with the group ring of formula_3 over the complex numbers, formula_39. Modules of this ring are the same thing as representations. Maschke's theorem implies that formula_39 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 formula_9 for each irreducible representation.
More specifically, the Peter-Weyl theorem (for finite groups) states that there is an isomorphism
given by
The left hand side is the group algebra of "G". The direct sum is over a complete set of inequivalent irreducible "G"-representations formula_44.
The Fourier transform for a finite group is just this isomorphism. The product formula mentioned above is equivalent to saying that this map is a ring isomorphism.
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 .
When applied to the Boolean group formula_45, the Fourier transform on this group is the Hadamard transform, which is commonly used in quantum computing and other fields. Shor's algorithm uses both the Hadamard transform (by applying a Hadamard gate to every qubit) as well as the quantum Fourier transform. The former considers the qubits as indexed by the group formula_45 and the later considers them as indexed by formula_47 for the purpose of the Fourier transform on finite groups.