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. The Fourier transform of a function at a representation of is For each representation of , is a matrix, where is the degree of . The inverse Fourier transform at an element of is given by The convolution of two functions is defined as The Fourier transform of a convolution at any representation of is given by For functions , the Plancherel formula states where are the irreducible representations of . If the group G is a finite abelian group, the situation simplifies considerably: all irreducible representations 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 of group homomorphisms from G to . This group is known as the Pontryagin dual of G. 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. 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, .