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.

**CHARACTER**

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 :

**ISOMORPHISM**

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

**Lemma :**

This result can be generalized to finite abelian groups

**Theorem :** Let G be a finite abelian group. Then

*Proof*

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 .

**ORTHOGONALITY**

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

*Proof*

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

Therefore

Finally we deduce since by definition.

**FOURIER TRANSFORM**

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.

**Example :**

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.