Fourier transform on finite groups

See also: Discrete Fourier transform (general)

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 ${\displaystyle f:G\to \mathbb {C} }$ at a representation ${\displaystyle \varrho :G\to \mathrm {GL} _{d_{\varrho }}(\mathbb {C} )}$ of ${\displaystyle G}$ is

$${\displaystyle {\widehat {f}}(\varrho )=\sum _{a\in G}f(a)\varrho (a).}$$

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

Let ${\displaystyle {\widehat {G}}}$ be the complete set of inequivalent irreducible representations of ${\displaystyle G}$. Then the inverse Fourier transform at an element ${\displaystyle a}$ of ${\displaystyle G}$ is given by

$${\displaystyle f(a)={\frac {1}{|G|}}\sum _{\varrho \in {\widehat {G}}}d_{\varrho }{\text{Tr}}\left(\varrho (a^{-1}){\widehat {f}}(\varrho )\right).}$$

Properties

Transform of a convolution

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

$${\displaystyle (f\ast g)(a)=\sum _{b\in G}f\!\left(ab^{-1}\right)g(b).}$$

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

$${\displaystyle {\widehat {f\ast g}}(\varrho )={\hat {f}}(\varrho ){\hat {g}}(\varrho ).}$$

Plancherel formula

For functions ${\displaystyle f,g:G\to \mathbb {C} }$, the Plancherel formula states

$${\displaystyle \sum _{a\in G}f(a^{-1})g(a)={\frac {1}{|G|}}\sum _{i}d_{\varrho _{i}}{\text{Tr}}\left({\hat {f}}(\varrho _{i}){\hat {g}}(\varrho _{i})\right),}$$

where ${\displaystyle \varrho _{i}}$ are the irreducible representations of ${\displaystyle G}$.

Fourier transform for finite abelian groups

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

• all irreducible representations ${\displaystyle \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 ${\displaystyle {\widehat {G}}:=\mathrm {Hom} (G,S^{1})}$ of group homomorphisms from G to ${\displaystyle S^{1}=\{z\in \mathbb {C} ,|z|=1\}}$. This group is known as the Pontryagin dual of G.

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

$${\displaystyle {\widehat {f}}(\chi )=\sum _{a\in G}f(a){\bar {\chi }}(a).}$$

The inverse Fourier transform is then given by

$${\displaystyle f(a)={\frac {1}{|G|}}\sum _{\chi \in {\widehat {G}}}{\widehat {f}}(\chi )\chi (a).}$$

For ${\displaystyle G=\mathbb {Z} /n}$, a choice of a primitive n-th root of unity ${\displaystyle \zeta }$ yields an isomorphism

$${\displaystyle G\to {\widehat {G}},}$$

given by ${\displaystyle m\mapsto (r\mapsto \zeta ^{mr})}$. In the literature, the common choice is ${\displaystyle \zeta =e^{2\pi i/n}}$, 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 ${\displaystyle \delta _{a,0}}$, where 0 is the group identity and ${\displaystyle \delta _{i,j}}$ 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, ${\displaystyle G}$, together with the operations of pointwise addition and convolution, form a ring that is naturally identified with the group ring of ${\displaystyle G}$ over the complex numbers, ${\displaystyle \mathbb {C} [G]}$. Modules of this ring are the same thing as representations. Maschke's theorem implies that ${\displaystyle \mathbb {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 ${\displaystyle d_{\varrho }}$ for each irreducible representation. More specifically, the Peter-Weyl theorem (for finite groups) states that there is an isomorphism

$${\displaystyle \mathbb {C} [G]\cong \bigoplus _{i}\mathrm {End} (V_{i})}$$

given by

$${\displaystyle \sum _{g\in G}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 ${\displaystyle \varrho _{i}:G\to \mathrm {GL} (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 ( Å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 ).

When applied to the Boolean group ${\displaystyle (\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 ${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$ and the later considers them as indexed by ${\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} }$ for the purpose of the Fourier transform on finite groups. ^[1]

See also

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

References

1. Lecture 5: Basic quantum algorithms, Rajat Mittal, pp. 4-9

• Åhlander, Krister; Munthe-Kaas, Hans Z. (2005), "Applications of the generalized Fourier transform in numerical linear algebra", BIT, 45 (4): 819–850, CiteSeerX   10.1.1.142.3122 , doi:10.1007/s10543-005-0030-3, MR   2191479 .
• Diaconis, Persi (1988), Group representations in probability and statistics, Lecture Notes—Monograph Series, vol. 11, Institute of Mathematical Statistics, Zbl   0695.60012 .
• Diaconis, Persi (1991-12-12), "Finite Fourier Methods: Access to Tools", in Bollobás, Béla; Chung, Fan R. K. (eds.), Probabilistic combinatorics and its applications, Proceedings of Symposia in Applied Mathematics, vol. 44, American Mathematical Society, pp. 171–194, ISBN   978-0-8218-6749-5 .
• Munthe-Kaas, Hans Z. (2006), "On group Fourier analysis and symmetry preserving discretizations of PDEs", Journal of Physics A , 39 (19): 5563–84, CiteSeerX   10.1.1.329.9959 , doi:10.1088/0305-4470/39/19/S14, MR   2220776 .
• Terras, Audrey (1999), Fourier Analysis on Finite Groups and Applications, Cambridge University Press, p. 251, ISBN   978-0-521-45718-7, Zbl   0928.43001 .