Fourier transform on finite groups

Short description: Generalization of the discrete Fourier transform

See also: Discrete Fourier transform (general)

Template:Fourier transforms In mathematics, the Fourier transform on finite groups is a generalization of the discrete Fourier transform from cyclic to arbitrary finite groups.

## Contents

* 1 Definitions
* 2 Properties
* 2.1 Transform of a convolution
* 2.2 Plancherel formula
* 3 Fourier transform for finite abelian groups
* 4 Relationship with representation theory
* 5 Over other fields
* 6 Modular case
* 7 Unitarity
* 8 Applications
* 9 See also
* 10 References
* 11 Further reading

## Definitions

The Fourier transform of a function f:G->ℂ at a representation ϱ:G->GLdϱ(ℂ) of G is

f^(ϱ)=∑a∈Gf(a)ϱ(a).

For each representation ϱ of G, f^(ϱ) is a dϱ×dϱ matrix, where dϱ is the degree of ϱ.

Let 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)=1|G|∑ϱ∈G^dϱTr(ϱ(a−1)f^(ϱ)).

## Properties

### Transform of a convolution

The convolution of two functions f,g:G->ℂ is defined as

(f∗g)(a)=∑b∈Gf(ab−1)g(b).

The Fourier transform of a convolution at any representation ϱ of G is given by

f∗g^(ϱ)=f^(ϱ)g^(ϱ).

### Plancherel formula

For functions f,g:G->ℂ, the Plancherel formula states

∑a∈Gf(a−1)g(a)=1|G|∑idϱiTr(f^(ϱi)g^(ϱi)),

where ϱ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 ϱ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 G^:=Hom(G,S1) of group homomorphisms from G to S1={z∈ℂ,|z|=1}. This group is known as the Pontryagin dual of G.

The Fourier transform of a function f:G->ℂ is the function f^:G^->ℂ given by

f^(χ)=∑a∈Gf(a)χ¯(a).

The inverse Fourier transform is then given by

f(a)=1|G|∑χ∈G^f^(χ)χ(a). For G=ℤ/nℤ, a choice of a primitive n-th root of unity ζ yields an isomorphism

G->G^,

given by m↦(r↦ζmr). In the literature, the common choice is ζ=e2π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 δa,0, where 0 is the group identity and δ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, ℂ[G]. Modules of this ring are the same thing as representations. Maschke's theorem implies that ℂ[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ϱ for each irreducible representation. More specifically, the Peter-Weyl theorem (for finite groups) states that there is an isomorphism ℂ[G]≅⨁iEnd(Vi) given by ∑g∈Gagg↦(∑agρi(g):Vi->Vi) The left hand side is the group algebra of G. The direct sum is over a complete set of inequivalent irreducible G-representations ϱi:G->GL(Vi).

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 ℂ as long as char(k)∤|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 1|G| is defined in k.

## Modular case

When char(k)∣|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]≅⨁ik[G]ei

and 1=∑iei is a decomposition of the identity into central, primitive, orthogonal idempotents. Choosing a basis for the blocks spank{gei|g∈G} and writing the projection maps v↦vei as a matrix yields the modular DFT matrix.[1]

For example, for the symmetric group the idempotents of Fp[Sn] are computed in Murphy[2] and explicitly in SageMath.[3]

## Unitarity

One can normalize the above definition to obtain

f^(ρ)=dρ|G|∑g∈Gf(g)ρ(g)

with inverse

f(g)=1|G|∑ρ∈G^dρTr(f^(ρ)ρ−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 G^ consists of unitary representations, then the corresponding DFT will be unitary.

Over finite fields Fq2, 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↦xq conjugation. The unitary representation is given by A*ρ(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 ci=zizi*. 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). 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 (ℤ/2ℤ)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 (ℤ/2ℤ)n and the later considers them as indexed by ℤ/2nℤ 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), "The Modular DFT of the Symmetric Group", arXiv:2404.05796 [math.RT]
2. ↑ Murphy, G.E. (1983). "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. https://dx.doi.org/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

## Further reading

* Åhlander, Krister; Munthe-Kaas, Hans Z. (2005), "Applications of the generalized Fourier transform in numerical linear algebra", BIT 45 (4): 819–850, doi:10.1007/s10543-005-0030-3 .
* Diaconis, Persi (1988), Group representations in probability and statistics, Lecture Notes—Monograph Series, 11, Institute of Mathematical Statistics, http://projecteuclid.org/euclid.lnms/1215467407 .
* Diaconis, Persi (1991-12-12), "Finite Fourier Methods: Access to Tools", in Bollobás, Béla; Chung, Fan R. K., Probabilistic combinatorics and its applications, Proceedings of Symposia in Applied Mathematics, 44, American Mathematical Society, pp. 171–194, ISBN 978-0-8218-6749-5, https://books.google.com/books?id=SHe1bNqIt38C&pg=PA171 .
* 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, doi:10.1088/0305-4470/39/19/S14, Bibcode: 2006JPhA...39.5563M .
* Terras, Audrey (1999), Fourier Analysis on Finite Groups and Applications, Cambridge University Press, p. 251, ISBN 978-0-521-45718-7, https://books.google.com/books?id=-B2TA669dJMC&pg=PA251 .

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Fourier transform on finite groups. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Fourier_transform_on_finite_groups&oldid=3986562"