Definitions
Nearby Words

# Fourier transform on finite groups

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 rightarrow mathbb\left\{C\right\},$ at a representation $rho,$ of $G,$ is


widehat{f}(rho) = sum_{a in G} f(a) rho(a).

So for each representation $rho,$ of $G,$, $widehat\left\{f\right\}\left(rho\right),$ is a $d_rho times d_rho,$ matrix, where $d_rho,$ is the degree of $rho,$.

Let $rho_i,$ be the irreducible representations of $G$. Then the inverse Fourier transform at an element $a,$ of $G,$ is given by


f(a) = frac{1}
sum_i d_i text{Tr}left(rho_i(a^{-1})widehat{f}(rho_i)right),>

where $d_i,$ is the degree of the representation $rho_i.,$

## Properties

### Transform of a convolution

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


(f ast g)(a) = sum_{b in G} f(ab^{-1}) g(b).

The Fourier transform of a convolution at any representation $rho,$ of $G,$ is given by


widehat{f ast g}(rho) = widehat{f}(rho)widehat{g}(rho).

### Plancherel formula

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


sum_{a in G} f(a^{-1}) g(a) = frac{1}
sum_i d_i text{Tr}left(widehat{f}(rho_i)widehat{g}(rho_i)right),>

where $rho_i,$ are the irreducible representations of $G.,$

## Fourier transform on finite abelian groups

Since the irreducible representations of finite abelian groups are all of degree 1 and hence equal to the irreducible characters of the group, Fourier analysis on finite abelian groups is significantly simplified. For instance, the Fourier transform yields a scalar- and not matrix-valued function.

Furthermore, the irreducible characters of a group may be put in one-to-one correspondence with the elements of the group.

Therefore, we may define the Fourier transform for finite abelian groups as


widehat{f}(s) = sum_{a in G} f(a) bar{chi_s}(a).

Note that the right-hand side is simply $langle f, chi_srangle$ for the inner product on the vector space of functions from $G,$ to $mathbb\left\{C\right\},$ defined by


langle f, g rangle = sum_{a in G} f(a) bar{g}(a).

The inverse Fourier transform is then given by


f(a) = frac{1}
> sum_{s in G} widehat{f}(s) chi_s(a).

A property that is often useful in probability is that the Fourier transform of the uniform distribution is simply $delta_\left\{a,0\right\},,$ where 0 is the group identity and $delta_\left\{i,j\right\},$ is the Kronecker delta.

## 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 . These algorithms can be used for the construction of numerical methods for solving partial differential equations that preserve the symmetries of the equations .