Discrete Fourier Transform on Abelian Group
In particular: Links to definitions of what $\chi$, $\C^\times$, $\phi \left({q}\right)$, $\overline \chi$ all mean.
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links.
To discuss this in more detail, feel free to use the talk page.
Once you have done so, you can remove this instance of {{MissingLinks}} from the code.
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)\) | |||||||||||
| \(\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)\) | |||||||||||
| \(\displaystyle \) | \(=\) | \(\displaystyle \frac 1 {\phi \left({q}\right)} \eta \left({y}\right) \phi \left({y}\right)\) | Orthogonality Relations for Characters | ||||||||||
| \(\displaystyle \) | \(=\) | \(\displaystyle \eta \left({y}\right)\) |
$\blacksquare$
