# Discrete Fourier Transform on Abelian Group

Jump to navigation Jump to search

## 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$:

$\ds \map \eta x = \frac 1 {\map \phi q} \sum_{\chi \mathop \in G^*} \innerprod \eta \chi_G \map \chi x$

where:

$\ds \innerprod \eta \chi_G = \sum_{x \mathop \in G} \map \eta x \map {\overline \chi} x$

## Proof

 $\ds \frac 1 {\map \phi q} \sum_{\chi \mathop \in G^*} \innerprod \eta \chi_G \map \chi y$ $=$ $\ds \frac 1 {\map \phi q} \sum_{\chi \mathop \in G^*} \sum_{x \mathop \in G} \map \eta x \map {\overline \chi} x \map \chi y$ $\ds$ $=$ $\ds \frac 1 {\map \phi q} \sum_{x \mathop \in G} \map \eta x \sum_{\chi \mathop \in G^*} \map {\overline \chi} x \map \chi y$ $\ds$ $=$ $\ds \frac 1 {\map \phi q} \map \eta y \map \phi y$ Orthogonality Relations for Characters $\ds$ $=$ $\ds \map \eta y$

$\blacksquare$