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 \to \Complex$ at a representation $\varrho : G \to \mathrm(d_\varrho, \Complex)$ of $G$ is

$\widehat(\varrho) = \sum_ f(a) \varrho(a).$

For each representation $\varrho$ of $G$, $\widehat(\varrho)$ is a $d_\varrho \times d_\varrho$ matrix, where $d_\varrho$ is the degree of $\varrho$.

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

$f(a) = \frac \sum_i d_ \text\left(\varrho_i(a^)\widehat(\varrho_i)\right).$

Properties

Transform of a convolution

The convolution of two functions $f, g : G \to \mathbb$ is defined as

$(f \ast g)(a) = \sum_ f\!\left(ab^\right) g(b).$

The Fourier transform of a convolution at any representation $\varrho$ of $G$ is given by

$\widehat(\varrho) = \hat(\varrho)\hat(\varrho).$

Plancherel formula

For functions $f, g : G \to \mathbb$, the Plancherel formula states

$\sum_ f(a^) g(a) = \frac \sum_i d_ \text\left(\hat(\varrho_i)\hat(\varrho_i)\right),$

where $\varrho_i$ are the irreducible representations of $G$.

Fourier transform for finite abelian groups

If the group ''G'' is a finite abelian group, the situation simplifies considerably:

* all irreducible representations $\varrho_i$ 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 $\widehat G := \mathrm(G, S^1)$ of group homomorphisms from ''G'' to $S^1 = \$. This group is known as the Pontryagin dual of ''G''.

The Fourier transform of a function $f : G \to \mathbb$ is the function $\widehat: \widehat\to \mathbb$ given by

$\widehat(\chi) = \sum_ f(a) \bar(a).$

The inverse Fourier transform is then given by

$f(a) = \frac \sum_ \widehat(\chi) \chi(a).$
For $G = \mathbb Z/n$, a choice of a primitive ''n''-th root of unity $\zeta$ yields an isomorphism

$G \to \widehat G,$

given by $m \mapsto (r \mapsto \zeta^)$. In the literature, the common choice is $\zeta = e^$, 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 $\delta_$, where 0 is the group identity and $\delta_$ 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, $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, \mathbb /math>. Modules of this ring are the same thing as representations. Maschke's theorem implies that \mathbb /math> 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_\varrho$ for each irreducible representation.
More specifically, the Peter-Weyl theorem (for finite groups) states that there is an isomorphism
\mathbb C \cong \bigoplus_ \mathrm(V_i)
given by
$\sum_ a_g g \mapsto \left(\sum a_g \rho_i(g): V_i \to V_i\right)$
The left hand side is the group algebra of ''G''. The direct sum is over a complete set of inequivalent irreducible ''G''-representations $\varrho_i : G \to \mathrm(V_i)$.

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 $(\mathbb Z / 2 \mathbb Z)^n$, 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 $(\mathbb Z / 2 \mathbb Z)^n$ and the later considers them as indexed by $\mathbb Z / 2^n \mathbb Z$ for the purpose of the Fourier transform on finite groups.Lecture 5: Basic quantum algorithms, Rajat Mittal, pp. 4-9
/ref>

See also

* Fourier transform
*Least-squares spectral analysis
*Representation theory of finite groups
*Character theory

References

* .
*.
*.
* .
*.

{{DEFAULTSORT:Fourier Transform On Finite Groups
Fourier analysis
Finite groups