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 .

## References

• .
• Diaconis, P. (1988). Group Representations in Probability and Statistics. Lecture Notes — Monograph Series, Vol. 11. Hayward, California: Institute of Mathematical Statistics.
• Diaconis, P. (1991). "Finite Fourier Methods: Access to Tools." In Probabilistic Combinatorics and its Applications, Proceedings of Symposia in Applied Mathematics, Vol. 44. Bollobás, B., and Chung, F. R. K. (ed.).
• .
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 34, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.7955083847045898, "perplexity_flag": "head"}