(Fourier Analysis on Finite Abelian Groups I) Characters of finite abelian groups

Fourier analysis on finite abelian groups are one of the most important topics in theory and applications: physics, computer science,... We will start the series notes about Fourier transform for the discrete case before going to its applications. The origin content is taken from the book "Fourier Analysis Over Finite Abelian Groups" of Bao Luong.

In this note, we present several properties of the character of finite abelian groups $G$.

1. The character of a group

Definition 1. A character of a group is a homomorphism from $G$ to $\mathbb{C}^\times$. The set of all characters of $G$ is denoted by $\hat{G}$, or $\rm{Hom}(G,\mathbb{C}^\times)$. 

Theorem 2.  $\hat{G}$ is an abelian group, with respect to the pointwise product $\chi \chi^{'}(x)= \chi(x)\chi^{'}(x)$ for all $\chi,\chi'\in \hat{G}$.

Proof.

• The pointwise product of two homomorphism $\chi, \psi \in \hat{G}$ is again a homomorphism in $\hat{G}$. Let $a,b$ be elements of $G$, we have $\chi \psi (ab) = \chi (ab) \psi (ab) = \chi (a) \chi (b) \psi (a) \psi (b) = \chi \psi (a) \chi \psi (b)$. 
• The identity of $\hat{G}$ is $1_\hat{G}$.
• An element $\chi (x) \in \hat{G}$ has an inverse element $\chi^{-1}(x) = \chi(x^{-1})$.
• The commutative and associative properties of $\hat{g}$ are inherited by $\mathbb{C}^\times$.

(Q.E.D)

The group $\hat{G}$ is called the dual group of $G$, and in the case of finite abelian group we can prove that $G \cong \hat{G}$. 

Lemma 3. A cyclic group $\mathbb{Z}_n$ is isomorphic with its dual group $\hat{\mathbb{Z}_n}$.

Proof.
Let $\chi: \mathbb{Z}_n \to \mathbb{C^{\times}}$ be a homomorphism. We have $\chi(0)=\chi(na)= \chi(a)^n = 1$. Hence, $\chi(a) \in \mu_n$ with $\mu_n$ is the group of $n^\text{th}$-root of unity.  Since $\mathbb{Z}_n = <1>$ is a cyclic group, we only care about the mapping $\chi(1)$ to $\mu_n$, and others can be constructed as $\chi(a) = a\chi(1)$.
So how is the structure of $\hat{\mathbb{Z}_n}$? We will see it by defined a mapping $\chi_x$ as follows:

$\chi_x: \mathbb{Z}_n \to \mathbb{C}^{\times}$       $a \mapsto \chi_x(a)$ 

with $x \in \mathbb{Z}_n, \omega \in \mu_n$ and $\chi_x(a) = \omega^{xa}$.

1. The mapping $\chi_x \in \hat{\mathbb{Z}_n}$ is a homomorphism: for $\forall a,b \in \mathbb{Z}_n$, $\chi_x(a+b) = \chi_x(a) \chi_x(b) = \omega^{x(a+b)}$.
2.  $\forall a \in \mathbb{Z}_n \text{, } \chi_x(a) = \chi_y(a) \Leftrightarrow x = y \mod n  $.

$\Rightarrow \hat{\mathbb{Z}_n} = \{ \chi_x \text{, with } x \in \mathbb{Z}_n \} $.
Let $\phi: \mathbb{Z}_n \to \hat{\mathbb{Z}_n}$ with $x \mapsto \chi_x$. The mapping $\phi$ is a homomorphism since $\phi (x+y) (a)= \chi_{x+y} (a)= \omega ^{(x+y)a} = \chi_x (a) \chi_y(a)= \phi(x) \phi(y) $. Moreover, $\phi$ is bijective by the construction and (2).

We conclude that $\mathbb{Z}_n \cong \hat{\mathbb{Z}_n}$.

(Q.E.D)

Lemma 4: Let $G_1 \cong G_2$ be finite abelian groups.  Prove that $\hat{G_2} \cong \hat{G_1}$.
Proof.
Let $f$ be an isomorphism from $G_1$ to $G_2$ and $\chi_1 \in \hat{G_1}, \chi_2 \in \hat{G_2} $. We have $\chi_1 = \chi_2 \circ f$.

 

There is a one to one mapping from $\chi_1$ to $\chi_2$. The mapping $h : \hat{G_2} \to \hat{G_1}$ ($ \chi_2 \mapsto \chi_2 \circ f $) is a homomorphism. Hence, $\hat{G_1} \cong \hat {G_2}$.

(Q.E.D)

Let $G_1, G_2$ be finite abelian groups. The mapping $\chi_1 \otimes \chi_2: G_1 \times G_2 \to \mathbb{C}^{\times}$ is called the tensor product of two characters if $\chi_1 \otimes \chi_2(a,b) = \chi_1(a) \chi_2(b)$ with $\chi_1 \in \hat{G_1}, \chi_2 \in \hat{G_2}$. This product is unique, and we denoted $\chi_{xy}=\chi_x \otimes \chi_y$.
The definition of the tensor product of two characters yields to an interesting relation between $\widehat{G_1 \times G_2}$ and $\hat{G_1}, \hat{G_2}$.

Lemma 5: $\hat{G_1} \times \hat{G_2} \cong \widehat{G_1 \times G_2}$, where $G_1$ and $G_2$ are finite abelian group.
Proof.
To make it clear we write the statement above by

$Hom(G_1 , \mathbb{C}^\times) \times Hom(G_2, \mathbb{C}^\times) \cong Hom(G_1 \times G_2, \mathbb{C}^\times) $

Consider the injections $i_1 : G_1 \to G_1 \times G_2$ with $a \mapsto (a,1)$ and $i_2 : G_2 \to G_1 \times G_2$ with $b \mapsto (1, b)$. Let $\chi \in Hom(G_1 \times G_2, \mathbb{C}^{\times})$, the composition $\chi \circ i_i$ is a character of $Hom( G_i, \mathbb{C}^{\times})$ where $i \in \{ 1, 2 \}$. Furthermore, $\chi_{12}(a,b)=\chi(i_1(a)) \chi(i_1(b)) = \chi (a,b)$. It can be seen that an arbitrary character $\chi$ of $\widehat{G_1 \times G_2}$ can be express by a tensor product of two character $\chi_1 \in \hat{G_1}$ and $\chi_2 \in \hat{G_2}$: $\chi = \chi_1 \otimes \chi_2$.

$f: Hom(G_1 , \mathbb{C}^\times) \times Hom(G_2, \mathbb{C}^\times) \cong Hom(G_1 \times G_2, \mathbb{C}^\times) $
$(\chi_1, \chi_2) \mapsto \chi_{12}$

We have $f((\chi_1,\chi_2)(\chi_{1'},\chi_{2'})) (a,b) = f(\chi_{11'}, \chi_{22'}) (a,b) = \chi_1 (a) \chi_{1'}(a)\chi_2 (b) \chi_{2'}(b) $
$= \chi_{12}(a,b) \chi_{1'2'}(a,b) = f(\chi_1,\chi_2)f(\chi_{1'},\chi_{2'})$. The mapping $f$ is homomorphism.

(Q.E.D)

Theorem 6. There is an isomorphism from a finite abelian group $G$ to its dual group $\hat{G}$.

Proof.

• We know that a finite abelian group is isomorphism with the direct product of cyclic groups (The Fundamental theorem of finite Abelian group). Hence, we can express $G \cong \mathbb{Z}_{n_1} \times \mathbb{Z}_{n_2} \times \ldots \times \mathbb{Z}_{nm}$. 
• Apply Lemma 5 and Lemma 4, we have $\hat{G} \cong \widehat{\mathbb{Z}_{n_1} \times \mathbb{Z}_{n_2} \times \ldots \times \mathbb{Z}_{nm}} \cong \hat{\mathbb{Z}_{n_1}} \times \hat{\mathbb{Z}_{n_2}} \times \ldots \times \hat{\mathbb{Z}_{nm}} \cong G$. 

(Q.E.D)

2. The orthogonal relation

Let $f: G \to C$, we see that $V^G = \{ f \}$ is a vector space over the $\mathbb{C}$.

• The addition of two functions in $V^G$ is defined as: $(fg)(x) = f(x) g(x) \Rightarrow fg \in V^G$ .
• The scalar product of $f \in V^G$ and $a \in \mathbb{C}$ is $(af)(x) = a(f(x)) \Rightarrow af \in V^G$.
• $(a+b)f = af +bf$.
• $a(f+g) =af + bg $
• The identity mapping in $V^G$ is $1_{V^G}(x) = 1$.
• The inverse element of $f \in V^G$ is $f^{-1}(x) = \frac{1}{f(x)}$. 

It is natural to ask about dimensions of the vector space $V^G$. We need to construct a set of linearly independent vector $\{\delta_i\}$ that spans $V^G$. The cardinality of $\{\delta_s\}$ is $dim(V^G)$. Let's try to build the mapping $\delta_i$ (it is also called the Kronecker delta) as follows:

$\delta_i: G \to C$ 

with $G = \{ a_1, \ldots, a_n\}$ and $\delta_i(a_j) = 1$ if $i=j$  and $\delta_i(a_j) = 0$ if $i \ne j$.

• $\{\delta_i\}^n_{i=1}$ is linearly independent since if there is existed a collection of coefficients $c_i \in \mathbb{C}$ satisfied: $\forall a \in G, \sum^{n}_{i=1}c_i \delta_i (a) = 0$. Then, $a = a_i$ leads to $c_i = 0$. Hence, we only obtain a trivial solution $\{c_i=0 \}^{n}_{i=1}$.
• Every function $f \in V^G$ can be expressed as $f(a) = \sum^{n}_{i=1}{f(a) \delta_i(a)}$.

The set $\{ \delta_i \}^n_{i=1}$ forms the standard basis of $V^G$. Moreover,  $dim(V^G) = |\{\delta_i\}^n_{i=1}| = |G|$.

Lemma 7: The dimensions of $V^G$ is |G|.

(Q.E.D)

 Endowing the vector space $V^G$ with a suitable inner product $<,>$ , we can see a beautiful result about the orthogonal basis of $V^G$. More precisely, this basis is the dual goup of $G$.

Now, we define the inner product of two functions $f,g \in V^G$

$<f,g> = \sum_{a \in G}{f(a) \overline{g(a)}} $

with $\bar{g(a)}$ is the complex conjugate.

The inner product $<f,g>$ is satisfied the following axioms:

• Conjugate symmetry: $<f,g> = \overline{<g,f>}$:  $\overline{<g,f>}=\overline{\sum_{a \in G}{g(a) \overline{f(a)}}} = \sum_{a \in G}{f(a) \overline{g(a)}} = <f,g>$. 
• Linearity: 
• $\forall \alpha \in \mathbb{C}, <\alpha f, g> = \alpha<f, g> = \alpha\sum_{a \in G}{f(a) \overline{g(a)}}$. 
• $<f_1 + f_2,g> = <f_1,g> +  <f_2,f> $ .

Lemma 8. $\forall \chi \in \hat{G},\sum_{a}{\chi(a)} = 0$. Note that, $\chi$ is not the trivial character $\chi_0$ with $\forall a \in G, \chi_0(a) = 1$.
Proof.
We can always choose $b \ne 1$ such that $\chi(b) \ne 0$  (the proof is found in the previous post, Exercise 3).
$\Rightarrow \sum_{a}{\chi(b)\chi(a)} = \sum_{a}{\chi(ab)} = 0 \Rightarrow \sum_{a}{\chi(a)} = 0$.

(Q.E.D)

So, what is the inner product of two characters $\chi_1, \chi_2 \in \hat{G}$? Let's try to compute it step by step to see 

$<\chi, \psi> = \begin{cases}
0   &  \chi \ne \psi \\
|G| &  \chi = \psi
\end{cases}
$.

More precisely, $\forall \chi, \psi \in \hat{G}, <\chi, \psi> = \sum_{a \in G}{\chi(a) \overline{\psi (a)}} = \sum_{a \in G}{\chi(a) \psi^-1 (a)}$. If $\chi \ne \psi $, then by Lemma 7, $<\chi, \psi> = 0$, otherwise $<\chi, \psi> = |G|$. 

Theorem 9: The group $\hat{G}$ forms the orthogonal basis of the vector space $V^G$.

Proof.

The set $\hat{G}$ is orthogonal, then $\hat{G}$ is linearly independent. In Lemma 7, we proved that $dim(V^G) = |G| = |\hat{G}|$ $\Rightarrow $ $\hat{G}$ is an orthogonal basis of $V^G$.

(Q.E.D)

Remark 10: In a inner product vector space $V$, an arbitrary vector $v \in V$ is represented by the following equation

$v = \sum^n_{i=1}{c_i u_i}$ (*) 

, where $U = \{ v_1, \ldots, v_n\}$ is a orthogonal basis of $V$. By the bilinear properties of inner product, we obtain $<v,u_j> = <\sum^n_{i=1}{c_i u_i}, u_j > =\sum^n_{i=1}{c_i<u_i,u_j>} = c_j <u_j, u_j> $.

Rewrite (*):

$v = \sum^n_{i=1}{\frac{<v,u_i>}{<u_i,u_i>} u_i}$

Back to this section, $\hat{G}$ is an orthogonal basis of $V^G$, then 

                                  $ f = \frac{1}{|G|} \sum_{\chi \in \hat{G}}{<f,\chi>{\chi}}$.

Simplify a character $\chi$ by $B_{\chi} = \frac{1}{|G|} \chi $, the orthonormal basis of $V^G$ is $B = \{ B_{\chi} \text{ with } \chi \in \hat {G} \}$. Hence, every function $f \in V^G$ can be represented as:

$f = \sum_{B_{\chi} \in B}{<f,B_{\chi}>B_{\chi}}$.

The result obtained by the Fourier transform of $f$ is $\hat{f} = <f,B_{\chi}>$. In the next post, several ideas about Fourier Transform will be yields. And we hope it can make you happy.