Discrete Fourier Transform on Abelian Group

From ProofWiki
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$