Fourier transform on finite groups#Fourier transform for finite abelian groups

{{Short description|Generalization of the discrete Fourier transform}}

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{GL}_{d_\varrho}(\Complex)$ of $G$ is

$\widehat{f}(\varrho) = \sum_{a \in G} f(a) \varrho(a).$

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

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

$f(a) = \frac{1}$

\sum_{\varrho \in \widehat{G}} d_{\varrho} \mathrm{Tr}\left(\varrho(a^{-1})\widehat{f}(\varrho)\right).

Properties

=Transform of a convolution=

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

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

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

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

=Plancherel formula=

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

$\sum_{a \in G} f(a^{-1}) g(a) = \frac{1}$

\sum_i d_{\varrho_i} \text{Tr}\left(\hat{f}(\varrho_i)\hat{g}(\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{Hom}(G, S^1)$ of group homomorphisms from G to $S^1 = \{z \in \mathbb C, |z|=1\}$ . This group is known as the Pontryagin dual of G.

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

$\widehat{f}(\chi) = \sum_{a \in G} f(a) \bar{\chi}(a).$

The inverse Fourier transform is then given by

$f(a) = \frac{1}$

\sum_{\chi \in \widehat{G}} \widehat{f}(\chi) \chi(a).

For $G = \mathbb Z/n \mathbb Z$ , 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^{mr})$ . In the literature, the common choice is $\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 $\delta_{a,0}$ , where 0 is the group identity and $\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, $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{C}[G]$ . Modules of this ring are the same thing as representations. Maschke's theorem implies that $\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 $d_\varrho$ for each irreducible representation.

More specifically, the Peter-Weyl theorem (for finite groups) states that there is an isomorphism

$\mathbb C[G] \cong \bigoplus_{i} \mathrm{End}(V_i)$

given by

$\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 $\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 $k$ other than $\mathbb{C}$ as long as $\text{char}(k) \nmid |G|$ via Maschke's theorem. That is, the group algebra $k[G]$ is semisimple. The same formulas may be used for the Fourier transform and its inverse, as crucially $\frac{1}$

is defined in

k

Modular case

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

$k[G] \cong \bigoplus_i k[G]e_i$

and $1 = \sum_i e_i$ is a decomposition of the identity into central, primitive, orthogonal idempotents. Choosing a basis for the blocks $\text{span}_k \{g e_i | g \in G\}$ and writing the projection maps $v \mapsto v e_i$ as a matrix yields the modular DFT matrix.{{cite arxiv|last=Walters|first=Jackson|title=The Modular DFT of the Symmetric Group |date=2024 |arxiv=2404.05796|class=math.RT}}

For example, for the symmetric group the idempotents of $F_p[S_n]$ are computed in Murphy{{cite journal |last1=Murphy |first1=G.E. |date= 1983|title=The idempotents of the symmetric group and Nakayama's conjecture |url=https://dx.doi.org/10.1016/0021-8693%2883%2990219-3 |journal=Journal of Algebra |volume=81 |issue=1 |pages=258–265 |doi=10.1016/0021-8693(83)90219-3 |access-date=}} and explicitly in SageMath.SageMath, the Sage Mathematics Software System (Version 10.4.0), The Sage Developers, 2024, https://www.sagemath.org.

Unitarity

One can normalize the above definition to obtain

$\hat{f}(\rho)=\sqrt{\frac{d_\rho}$

}\sum_{g \in G}f(g)\rho(g)

with inverse

$f(g)=\frac{1}{\sqrt$

}\sum_{\rho \in \widehat{G}}\sqrt{d_\rho}\mathrm{Tr}(\hat{f}(\rho)\rho^{-1}(g)).{{cite book |doi=10.1145/258533.258548 |chapter=Quantum computation of Fourier transforms over symmetric groups |title=Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 |date=1997 |last1=Beals |first1=Robert |pages=48–53 |isbn=0-89791-888-6 }}

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 $\widehat{G}$ consists of unitary representations, then the corresponding DFT will be unitary.

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

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.[https://www.cse.iitk.ac.in/users/rmittal/prev_course/s19/reports/5_algo.pdf Lecture 5: Basic quantum algorithms, Rajat Mittal, pp. 4-9]