Here is an overview of Fourier analysis applied to finite abelian groups. It shows how to generalize a priori different computations such as the discrete Fourier transform or the Hadamard-Walsh transform.
Let be a finite abelian group with additive notation. A character of is a group homomorphism that is to say for all
It is straightforward to check that the characters of form a group called the dual group, which is denoted by .
- Group law :
- Neutral element : is called the principal character
- Inversion :
We consider, up to an isomorphism, that a cyclic group of order is the additive group of integers modulo denoted by . Then, to each we can associate a mapping
This mapping is independent of the choice of the representatives since is n-periodic in both and . In order to improve the readability we remove the squares around the representatives and write instead of .
It is easy to check that are characters of
For similar reasons we have
which gives the group law of . This implies that the dual group is a cyclic group of order . Hence the following lemma
This result can be generalized to finite abelian groups
Theorem : Let G be a finite abelian group. Then
It is well known from abstract algebra that a finite abelian group can be decomposed as a direct sum of cyclic groups, namely
The trick consists of proving an isomorphism with the group direct product
Let be characters of respectively. We define the function
Clearly, is a character of and the construction of from is injective.
Now, consider . The restriction is a character of . It follows .
Let be a finite abelian group. The functions form the Hilbert space . In particular, the characters are elements of and satisfy the following lemma
Lemma : Suppose . Then
The first case is easy. If then
Note that we have used the property meaning that each value is a root of unity. Indeed, the dual group being finite, all characters have finite order.
The second case is not really more difficult. Put . Since the character is different from . Thus there exists such that . The inner product can be rewritten using and the property (since is a root of unity as explained before).
We can permute the elements of by adding
Finally we deduce since by definition.
We are now ready to define the Fourier transform on finite abelian groups.
Fourier transform : Let be a finite abelian group and . Then the Fourier transform of is by definition
This definition is really similar to the well known discrete Fourier transform. We can illustrate on two examples.
We have seen that characters of are given by . Thus, the Fourier transform as defined on finite abelian groups is
We recover the definition of the usual discrete Fourier transform.
Example : ( times)
Clearly, the characters are m-products of the characters of (if you do not see why then recall the proof of above).
The characters of are easy to determine :
As a consequence the characters of are given by m-products
where and . We use the standard inner product of vectors to simplify the writing
The Fourier transform as defined on finite abelian groups is
We recover the definition of the usual Hadamard-Walsh transform.