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.

Over other fields

The above representation theoretic decomposition can be generalized to fields ${\displaystyle k}$ other than ${\displaystyle \mathbb {C} }$ as long as ${\displaystyle {\text{char}}(k)\nmid |G|}$ via Maschke's theorem. That is, the group algebra ${\displaystyle k[G]}$ is semisimple. The same formulas may be used for the Fourier transform and its inverse, as crucially ${\displaystyle {\frac {1}{|G|}}}$ is defined in ${\displaystyle k}$.

Modular case

When ${\displaystyle {\text{char}}(k)\mid |G|}$, ${\displaystyle k[G]}$ is no longer semisimple and one must consider the modular representation theory of ${\displaystyle G}$ over ${\displaystyle k}$. We can still decompose the group algebra into blocks via the Peirce decomposition using idempotents. That is

${\displaystyle k[G]\cong \bigoplus _{i}k[G]e_{i}}$

and ${\displaystyle 1=\sum _{i}e_{i}}$ is a decomposition of the identity into central, primitive, orthogonal idempotents. Choosing a basis for the blocks ${\displaystyle {\text{span}}_{k}\{ge_{i}|g\in G\}}$ and writing the projection maps ${\displaystyle v\mapsto ve_{i}}$ as a matrix yields the modular DFT matrix. ^[1]

For example, for the symmetric group the idempotents of ${\displaystyle F_{p}[S_{n}]}$ are computed in Murphy ^[2] and explicitly in SageMath. ^[3]

Unitarity

One can normalize the above definition to obtain

${\displaystyle {\hat {f}}(\rho )={\sqrt {\frac {d_{\rho }}{|G|}}}\sum _{g\in G}f(g)\rho (g)}$

with inverse

${\displaystyle f(g)={\frac {1}{\sqrt {|G|}}}\sum _{\rho \in {\widehat {G}}}{\sqrt {d_{\rho }}}Tr({\hat {f}}(\rho )\rho ^{-1}(g))}$. ^[4]

Two representations are considered equivalent if one may be obtained from the other by a change of basis. This is an equivalence relation, and each equivalence class contains a unitary representation. The unitary representations can be obtained via Weyl's unitarian trick in characteristic zero. If ${\displaystyle {\widehat {G}}}$ consists of unitary representations, then the corresponding DFT will be unitary.

Over finite fields ${\displaystyle F_{q^{2}}}$, it is possible to find a change of basis in certain cases, for example the symmetric group, by decomposing the matrix ${\displaystyle U}$ associated to a ${\displaystyle G}$-invariant symmetric bilinear form as ${\displaystyle U=AA^{*}}$, where ${\displaystyle ^{*}}$ denotes conjugate-transpose with respect to ${\displaystyle x\mapsto x^{q}}$ conjugation. The unitary representation is given by ${\displaystyle A^{*}\rho (g)A^{*-1}}$. To obtain the unitary DFT, note that as defined above ${\displaystyle DFT.DFT^{*}=S}$, where ${\displaystyle S}$ is a diagonal matrix consisting of +1's and -1's. We can factor ${\displaystyle S=RR^{*}}$ by factoring each sign ${\displaystyle c_{i}=z_{i}z_{i}^{*}}$. ${\displaystyle uDFT=R^{-1}.DFT}$ is unitary.

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. ^[5]

See also

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

References

1. Walters, Jackson (2024). "What is the Modular Fourier Transform?". arXiv: 2404.05796 .
2. Murphy, G.E. "The idempotents of the symmetric group and Nakayama's conjecture". Journal of Algebra. 81 (1): 258–265. doi:10.1016/0021-8693(83)90219-3.
3. SageMath, the Sage Mathematics Software System (Version 10.4.0), The Sage Developers, 2024, https://www.sagemath.org.
4. Beals, Robert (1997). "Quantum computation of Fourier transforms over symmetric groups". Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97. pp. 48–53. doi:10.1145/258533.258548. ISBN   0-89791-888-6.
5. 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 .
• Luong, Bao (2009), Fourier Analysis on Finite Abelian Groups, Birkhäuser, ISBN 978-0-8176-4916-6.
• 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 .