Fourier transform on finite groups

Last updated

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

Contents

Definitions

The Fourier transform of a function at a representation of is

For each representation of , is a matrix, where is the degree of .

Let be the complete set of inequivalent irreducible representations of . Then the inverse Fourier transform at an element of is given by

Properties

Transform of a convolution

The convolution of two functions is defined as

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

Plancherel formula

For functions , the Plancherel formula states

where are the irreducible representations of .

Fourier transform for finite abelian groups

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

The Fourier transform of a function is the function given by

The inverse Fourier transform is then given by

For , a choice of a primitive n-th root of unity yields an isomorphism

given by . In the literature, the common choice is , 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 , where 0 is the group identity and 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, , together with the operations of pointwise addition and convolution, form a ring that is naturally identified with the group ring of over the complex numbers, . Modules of this ring are the same thing as representations. Maschke's theorem implies that 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 for each irreducible representation. More specifically, the Peter-Weyl theorem (for finite groups) states that there is an isomorphism given by The left hand side is the group algebra of G. The direct sum is over a complete set of inequivalent irreducible G-representations .

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 other than as long as via Maschke's theorem. That is, the group algebra is semisimple. The same formulas may be used for the Fourier transform and its inverse, as crucially is defined in .

Modular case

When , is no longer semisimple and one must consider the modular representation theory of over . We can still decompose the group algebra into blocks via the Peirce decomposition using idempotents. That is

and is a decomposition of the identity into central, primitive, orthogonal idempotents. Choosing a basis for the blocks and writing the projection maps as a matrix yields the modular DFT matrix. [1]

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

Unitarity

One can normalize the above definition to obtain

with inverse

. [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. If consists of unitary representations, then the above transformations are unitary. The unitary representations can be obtained via Weyl's unitarian trick.

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 , 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 and the later considers them as indexed by for the purpose of the Fourier transform on finite groups. [5]

See also

Related Research Articles

<span class="mw-page-title-main">Group representation</span> Group homomorphism into the general linear group over a vector space

In the mathematical field of representation theory, group representations describe abstract groups in terms of bijective linear transformations of a vector space to itself ; in particular, they can be used to represent group elements as invertible matrices so that the group operation can be represented by matrix multiplication.

<span class="mw-page-title-main">Representation of a Lie group</span> Group representation

In mathematics and theoretical physics, a representation of a Lie group is a linear action of a Lie group on a vector space. Equivalently, a representation is a smooth homomorphism of the group into the group of invertible operators on the vector space. Representations play an important role in the study of continuous symmetry. A great deal is known about such representations, a basic tool in their study being the use of the corresponding 'infinitesimal' representations of Lie algebras.

In mathematics, the Peter–Weyl theorem is a basic result in the theory of harmonic analysis, applying to topological groups that are compact, but are not necessarily abelian. It was initially proved by Hermann Weyl, with his student Fritz Peter, in the setting of a compact topological group G. The theorem is a collection of results generalizing the significant facts about the decomposition of the regular representation of any finite group, as discovered by Ferdinand Georg Frobenius and Issai Schur.

In the field of representation theory in mathematics, a projective representation of a group G on a vector space V over a field F is a group homomorphism from G to the projective linear group where GL(V) is the general linear group of invertible linear transformations of V over F, and F is the normal subgroup consisting of nonzero scalar multiples of the identity transformation (see Scalar transformation).

In algebra, a group ring is a free module and at the same time a ring, constructed in a natural way from any given ring and any given group. As a free module, its ring of scalars is the given ring, and its basis is the set of elements of the given group. As a ring, its addition law is that of the free module and its multiplication extends "by linearity" the given group law on the basis. Less formally, a group ring is a generalization of a given group, by attaching to each element of the group a "weighting factor" from a given ring.

<span class="mw-page-title-main">Pontryagin duality</span> Duality for locally compact abelian groups

In mathematics, Pontryagin duality is a duality between locally compact abelian groups that allows generalizing Fourier transform to all such groups, which include the circle group, the finite abelian groups, and the additive group of the integers, the real numbers, and every finite-dimensional vector space over the reals or a p-adic field.

In mathematics, more specifically in harmonic analysis, Walsh functions form a complete orthogonal set of functions that can be used to represent any discrete function—just like trigonometric functions can be used to represent any continuous function in Fourier analysis. They can thus be viewed as a discrete, digital counterpart of the continuous, analog system of trigonometric functions on the unit interval. But unlike the sine and cosine functions, which are continuous, Walsh functions are piecewise constant. They take the values −1 and +1 only, on sub-intervals defined by dyadic fractions.

<span class="mw-page-title-main">Irreducible representation</span> Type of group and algebra representation

In mathematics, specifically in the representation theory of groups and algebras, an irreducible representation or irrep of an algebraic structure is a nonzero representation that has no proper nontrivial subrepresentation , with closed under the action of .

In mathematics, Schur's lemma is an elementary but extremely useful statement in representation theory of groups and algebras. In the group case it says that if M and N are two finite-dimensional irreducible representations of a group G and φ is a linear map from M to N that commutes with the action of the group, then either φ is invertible, or φ = 0. An important special case occurs when M = N, i.e. φ is a self-map; in particular, any element of the center of a group must act as a scalar operator on M. The lemma is named after Issai Schur who used it to prove the Schur orthogonality relations and develop the basics of the representation theory of finite groups. Schur's lemma admits generalisations to Lie groups and Lie algebras, the most common of which are due to Jacques Dixmier and Daniel Quillen.

In mathematics, more specifically in group theory, the character of a group representation is a function on the group that associates to each group element the trace of the corresponding matrix. The character carries the essential information about the representation in a more condensed form. Georg Frobenius initially developed representation theory of finite groups entirely based on the characters, and without any explicit matrix realization of representations themselves. This is possible because a complex representation of a finite group is determined by its character. The situation with representations over a field of positive characteristic, so-called "modular representations", is more delicate, but Richard Brauer developed a powerful theory of characters in this case as well. Many deep theorems on the structure of finite groups use characters of modular representations.

In mathematics and in theoretical physics, the Stone–von Neumann theorem refers to any one of a number of different formulations of the uniqueness of the canonical commutation relations between position and momentum operators. It is named after Marshall Stone and John von Neumann.

The representation theory of groups is a part of mathematics which examines how groups act on given structures.

In mathematics, the representation theory of the symmetric group is a particular case of the representation theory of finite groups, for which a concrete and detailed theory can be obtained. This has a large area of potential applications, from symmetric function theory to quantum chemistry studies of atoms, molecules and solids.

<span class="mw-page-title-main">Burnside's theorem</span> Mathematics, group theory

In mathematics, Burnside's theorem in group theory states that if G is a finite group of order where p and q are prime numbers, and a and b are non-negative integers, then G is solvable. Hence each non-Abelian finite simple group has order divisible by at least three distinct primes.

<span class="mw-page-title-main">Representation theory of the Lorentz group</span> Representation of the symmetry group of spacetime in special relativity

The Lorentz group is a Lie group of symmetries of the spacetime of special relativity. This group can be realized as a collection of matrices, linear transformations, or unitary operators on some Hilbert space; it has a variety of representations. This group is significant because special relativity together with quantum mechanics are the two physical theories that are most thoroughly established, and the conjunction of these two theories is the study of the infinite-dimensional unitary representations of the Lorentz group. These have both historical importance in mainstream physics, as well as connections to more speculative present-day theories.

In physics and particularly in particle physics, a multiplet is the state space for 'internal' degrees of freedom of a particle, that is, degrees of freedom associated to a particle itself, as opposed to 'external' degrees of freedom such as the particle's position in space. Examples of such degrees of freedom are the spin state of a particle in quantum mechanics, or the color, isospin and hypercharge state of particles in the Standard model of particle physics. Formally, we describe this state space by a vector space which carries the action of a group of continuous symmetries.

In mathematics, especially in the area of algebra known as representation theory, the representation ring of a group is a ring formed from all the finite-dimensional linear representations of the group. Elements of the representation ring are sometimes called virtual representations. For a given group, the ring will depend on the base field of the representations. The case of complex coefficients is the most developed, but the case of algebraically closed fields of characteristic p where the Sylow p-subgroups are cyclic is also theoretically approachable.

In mathematics, Maschke's theorem, named after Heinrich Maschke, is a theorem in group representation theory that concerns the decomposition of representations of a finite group into irreducible pieces. Maschke's theorem allows one to make general conclusions about representations of a finite group G without actually computing them. It reduces the task of classifying all representations to a more manageable task of classifying irreducible representations, since when the theorem applies, any representation is a direct sum of irreducible pieces (constituents). Moreover, it follows from the Jordan–Hölder theorem that, while the decomposition into a direct sum of irreducible subrepresentations may not be unique, the irreducible pieces have well-defined multiplicities. In particular, a representation of a finite group over a field of characteristic zero is determined up to isomorphism by its character.

<span class="mw-page-title-main">Symmetry in quantum mechanics</span> Properties underlying modern physics

Symmetries in quantum mechanics describe features of spacetime and particles which are unchanged under some transformation, in the context of quantum mechanics, relativistic quantum mechanics and quantum field theory, and with applications in the mathematical formulation of the standard model and condensed matter physics. In general, symmetry in physics, invariance, and conservation laws, are fundamentally important constraints for formulating physical theories and models. In practice, they are powerful methods for solving problems and predicting what can happen. While conservation laws do not always give the answer to the problem directly, they form the correct constraints and the first steps to solving a multitude of problems. In application, understanding symmetries can also provide insights on the eigenstates that can be expected. For example, the existence of degenerate states can be inferred by the presence of non commuting symmetry operators or that the non degenerate states are also eigenvectors of symmetry operators.

In mathematics, specifically in representation theory, a semisimple representation is a linear representation of a group or an algebra that is a direct sum of simple representations. It is an example of the general mathematical notion of semisimplicity.

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