# Discrete Fourier Transform on Abelian Group

## Theorem

Let $G$ be a finite abelian group.

Let $G^*$ be the dual group of characters $G \to \C^\times$.

Let $\eta: G \to \C$ be a mapping from $G$ to the set of complex numbers.

Then for all $x \in G$:

$\displaystyle \eta \left({x}\right) = \frac 1 {\phi \left({q}\right)} \sum_{\chi \mathop \in G^*} \langle \eta, \chi \rangle_G \chi(x)$

where:

$\displaystyle \langle \eta, \chi \rangle_G = \sum_{x \mathop \in G} \eta \left({x}\right) \overline{\chi} \left({x}\right)$

## Proof

 $\displaystyle \frac 1 {\phi \left({q}\right)} \sum_{\chi \mathop \in G^*} \langle \eta, \chi \rangle_G \chi \left({y}\right)$ $=$ $\displaystyle \frac 1 {\phi \left({q}\right)} \sum_{\chi \mathop \in G^*} \sum_{x \mathop \in G} \eta \left({x}\right) \overline \chi \left({x}\right) \chi \left({y}\right)$ $\quad$ $\quad$ $\displaystyle$ $=$ $\displaystyle \frac 1 {\phi \left({q}\right)} \sum_{x \mathop \in G} \eta(x) \sum_{\chi \mathop \in G^*} \overline \chi \left({x}\right) \chi \left({y}\right)$ $\quad$ $\quad$ $\displaystyle$ $=$ $\displaystyle \frac 1 {\phi \left({q}\right)} \eta \left({y}\right) \phi \left({y}\right)$ $\quad$ Orthogonality Relations for Characters $\quad$ $\displaystyle$ $=$ $\displaystyle \eta \left({y}\right)$ $\quad$ $\quad$

$\blacksquare$