Fourier Transform over Finite Abelian Groups

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 G be a finite abelian group with additive notation. A character of G is a group homomorphism \chi : G \rightarrow \mathbb{C} - \{ 0 \} that is to say for all a , b \in G

\displaystyle \chi ( a + b ) = \chi ( a ) \chi ( b )

\displaystyle \chi ( 0 ) = 1

It is straightforward to check that the characters of G form a group called the dual group, which is denoted by \widehat{G}.

  • Group law : ( \chi_1 \chi_2 ) ( a ) = \chi_1 ( a ) \chi_2 ( a )
  • Neutral element : \chi_0 = 1 is called the principal character
  • Inversion : \chi^{-1} ( a ) = \chi ( a )^{-1}

ISOMORPHISM

We consider, up to an isomorphism, that a cyclic group of order n is the additive group of integers modulo n denoted by \mathbb{Z}_n. Then, to each [p] \in \mathbb{Z}_n we can associate a mapping

\displaystyle \chi_{[p]} : \mathbb{Z}_n \rightarrow \mathbb{C} \textrm{ such that } \chi_{[p]} ( [q] ) = e^{i 2 \pi p q / n}

This mapping is independent of the choice of the representatives since e^{i 2 \pi p q / n} is n-periodic in both p and q. In order to improve the readability we remove the squares around the representatives and write p instead of [p].

It is easy to check that \chi_{p} are characters of \mathbb{Z}_n

\displaystyle \chi_{p} ( q + q' ) = \chi_{p} ( q ) \chi_{p} ( q' )

For similar reasons we have

\displaystyle \chi_{p + p'} ( q ) = \chi_{p} ( q ) \chi_{p'} ( q )

which gives the group law of \widehat{\mathbb{Z}_n}. This implies that the dual group is a cyclic group of order n. Hence the following lemma

Lemma : \mathbb{Z}_n \simeq \widehat{\mathbb{Z}_n}

This result can be generalized to finite abelian groups

Theorem : Let G be a finite abelian group. Then G \simeq \widehat{G}

Proof

It is well known from abstract algebra that a finite abelian group can be decomposed as a direct sum of cyclic groups, namely

\displaystyle G = G_1 \oplus \cdots \oplus G_m

The trick consists of proving an isomorphism with the group direct product

\displaystyle \widehat{G} \simeq \widehat{G_1} \oplus \cdots \oplus \widehat{G_m}.

Let \chi_1 , \cdots , \chi_m be characters of G_1 , \cdots , G_m respectively. We define the function

\displaystyle \chi ( g_1 , \cdots , g_m ) = \chi_1 ( g_1 ) \cdots \chi_m( g_m )

Clearly, \chi is a character of G and the construction of \chi from \chi_1 , \cdots , \chi_m is injective.

Now, consider \chi \in \widehat{G}. The restriction \chi_i = \chi | G_i is a character of G_i. It follows \chi = \chi_1 \oplus \cdots \oplus \chi_m.

ORTHOGONALITY

Let G be a finite abelian group. The functions f : G \rightarrow \mathbb{C} form the Hilbert space \ell^2(G). In particular, the characters are elements of \ell^2(G) and satisfy the following lemma

Lemma : Suppose \chi , \eta \in \widehat{G}. Then

\displaystyle \left\langle \chi , \eta \right\rangle = \begin{cases} |G| \textrm{ if } \chi = \eta \\ 0 \textrm{ otherwise} \end{cases}

Proof

The first case is easy. If \chi = \eta then

\displaystyle \left\langle \chi , \eta \right\rangle = \sum_{g \in G} \chi(g) \overline{\eta(g)} = \sum_{g \in G} | \chi(g) |^2 = \sum_{g \in G} 1 = |G|

Note that we have used the property | \chi(g) | = 1 meaning that each value \chi(g) 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 \sigma = \chi \eta^{-1} . Since \chi \neq \eta the character \sigma is different from 1. Thus there exists h such that \sigma(h) \neq 1. The inner product can be rewritten using \sigma and the property \overline{\eta} = \eta^{-1} (since \eta(g) is a root of unity as explained before).

\displaystyle \left\langle \chi , \eta \right\rangle = \sum_{g \in G} \sigma(g)

We can permute the elements of G by adding h

\displaystyle \left\langle \chi , \eta \right\rangle = \sum_{g \in G} \sigma(h + g) = \sigma(h) \sum_{g \in G} \sigma(g) = \sigma(h) \left\langle \chi , \eta \right\rangle

Therefore

\displaystyle (1 - \sigma(h)) \left\langle \chi , \eta \right\rangle = 0

Finally we deduce \left\langle \chi , \eta \right\rangle = 0 since \sigma(h) \neq 1 by definition.

FOURIER TRANSFORM

We are now ready to define the Fourier transform on finite abelian groups.

Fourier transform : Let G be a finite abelian group and f : G \rightarrow \mathbb{C}. Then the Fourier transform of f is by definition

\displaystyle \widehat{f} : \widehat{G} \rightarrow \mathbb{C} \textrm{ with } \widehat{f} ( \chi ) = \frac{1}{\sqrt{|G|}} \left\langle f , \chi \right\rangle

This definition is really similar to the well known discrete Fourier transform. We can illustrate on two examples.

Example : G = \mathbb{Z}_n

We have seen that characters of \mathbb{Z}_n are given by \chi_p ( q) = e^{i 2 \pi p q / n}. Thus, the Fourier transform as defined on finite abelian groups is

\displaystyle \widehat{f} ( \chi_p ) = \frac{1}{\sqrt{n}} \sum_{q \in \mathbb{Z}_n} e^{- i 2 \pi p q / n} f ( q )

We recover the definition of the usual discrete Fourier transform.

Example : G = \mathbb{F}_{2}^{m} = \mathbb{Z}_2 \oplus \cdots \oplus \mathbb{Z}_2 (m times)

Clearly, the characters are m-products of the characters of \mathbb{Z}_2 (if you do not see why then recall the proof of G \simeq \widehat{G} above).

The characters of \mathbb{Z}_2 are easy to determine :

\displaystyle \chi_p ( q ) = e^{i 2 \pi p q / 2} = ( - 1 )^{p q}

As a consequence the characters of \mathbb{F}_{2}^{m} are given by m-products

\displaystyle \chi_p ( q ) = ( - 1 )^{p_1 q_1} \cdots ( - 1 )^{p_m q_m}

where p = (p_1 , \cdots , p_m) and q = (q_1 , \cdots , q_m). We use the standard inner product of vectors to simplify the writing

\displaystyle \chi_p ( q ) = ( - 1 )^{p \cdot q}

The Fourier transform as defined on finite abelian groups is

\displaystyle \widehat{f} ( \chi_p ) = \frac{1}{\sqrt{2^m}} \sum_{q \in \mathbb{F}_{2}^{m}} ( - 1 )^{p \cdot q} f ( q )

We recover the definition of the usual Hadamard-Walsh transform.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s