In mathematics, the Fourier transform on finite groups is a generalization of the discrete Fourier transform from cyclic to arbitrary finite groups.
be the complete set of inequivalent irreducible representations of
If the group G is a finite abelian group, the situation simplifies considerably: The Fourier transform of a function
, a choice of a primitive n-th root of unity
, which explains the formula given in the article about the discrete Fourier transform.
A property that is often useful in probability is that the Fourier transform of the uniform distribution is simply
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
The Fourier transform on finite groups explicitly exhibits this decomposition, with a matrix ring of dimension
More specifically, the Peter-Weyl theorem (for finite groups) states that there is an isomorphism
The left hand side is the group algebra of G. The direct sum is over a complete set of inequivalent irreducible G-representations
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.
The above representation theoretic decomposition can be generalized to fields
The same formulas may be used for the Fourier transform and its inverse, as crucially
is no longer semisimple and one must consider the modular representation theory of
We can still decompose the group algebra into blocks via the Peirce decomposition using idempotents.
is a decomposition of the identity into central, primitive, orthogonal idempotents.
[4] Two representations are considered equivalent if one may be obtained from the other by a change of basis.
The unitary representations can be obtained via Weyl's unitarian trick in characteristic zero.
, it is possible to find a change of basis in certain cases, for example the symmetric group, by decomposing the matrix
To obtain the unitary DFT, note that as defined above
This generalization of the discrete Fourier transform is used in numerical analysis.
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).
Shor's algorithm uses both the Hadamard transform (by applying a Hadamard gate to every qubit) as well as the quantum Fourier transform.
for the purpose of the Fourier transform on finite groups.