Math 202B: Lecture 17

In this lecture and the next, we will develop the Discrete Fourier Transform (DFT), which is probably the most widely used algebra isomorphism. Abstractly, we already know about this isomorphism from our first characterization of function algebras long ago: a given algebra \mathcal{A} is isomorphic to a function algebra if and only if it admits a basis \{F^\lambda \colon \lambda \in \Lambda\} of selfadjoint and pairwise orthogonal idempotents – a “Fourier basis.” Whenever we have such a basis, we can expand each A \in \mathcal{A} as

A=\sum\limits_{\lambda \in \Lambda} \widehat{A}(\lambda)F^\lambda,

and in doing so we associate a function \widehat{A}(\lambda) \in \mathcal{F}(\Lambda) to each A \in \mathcal{A}. This association is an algebra isomorphism which we call the Fourier transform on \mathcal{A}.

Thus, returning to the setting of convolution algebras, the basic question is how to concretely construct a Fourier basis in \mathcal{C}(G). It is clear that this construction must somehow leverage the group structure of G, and the basic ingredient is the following.

Definition 17.1. Given a finite group G, a group homomorphism \chi \colon G \to \mathbb{U} from G to the unit circle \mathbb{U} = \{u \in \mathbb{C} \colon |u|=1\} is called a multiplicative character of G.

Every group G has at least one multiplicative character, namely the “trivial character” which sends every group element to the number 1. In last week’s homework you constructed an example of a group for which the trivial character is the the only multiplicative character. For abelian groups, the opposite extreme holds: there are as many multiplicative characters as there are group elements. This fact is the key to constructing a Fourier basis of the convolution algebra of a finite abelian group.

To begin, recall that every finite abelian group is isomorphic to a product of cyclic groups. We thus fix a positive integer r \in \mathbb{N}, and r positive integers n_1,\dots,n_r \in \mathbb{N}, and consider the group

G = G_1 \times \dots \times G_r,

where G_i is a cyclic group of order n_i with generator g_i. Define the dual group of G to be

\Lambda = \{\alpha=(\alpha_1,\dots,\alpha_r) \colon \alpha_k \in \{0,1,\dots,n_k-1\},\ 1 \leq k \leq r\}.

That is,

\Lambda = \mathbb{Z}_{n_1} \times \dots \times \mathbb{Z}_{n_r},

where \mathbb{Z}_n= is the additive group of integers modulo n. We can parameterize G by the points of \Lambda, writing

g_\alpha=(g_1^{\alpha_1},\dots,g_r^{\alpha_r}), \quad \alpha \in \Lambda.

Problem 17.1. Prove that the parameterization \alpha \mapsto g_\alpha is a group isomorphism \Lambda \to G (Note that because |\Lambda|=|G| it is sufficient to show the parameterization is an injective group homomorphism).

Theorem 17.1. For every \lambda \in \Lambda, the function \chi^\lambda \colon G \to U(\mathbb{C}) defined by

\chi^\lambda(g_\alpha) = \omega_1^{\alpha_1\lambda_1} \dots \omega_r^{\alpha_r\lambda^r},

where \omega_k=\exp\left(\frac{2\pi i}{n_k}\right) is a principal n_kth root of unity, is a multiplicative character of G.

Proof: For any \lambda \in \Lambda, it is clear that \chi^\lambda(e)=1, because the identity element e \in G has parameters \alpha=(0,0,\dots,0). Moreover, for any \alpha,\beta \in \Lambda we have

\chi^\lambda(g_\alpha g_\beta) = \chi^\lambda(g_{\alpha+\beta})=(\omega_1)^{(\alpha_1+\beta_1)\lambda_1} \dots (\omega_r)^{(\alpha_r+\beta_r)\lambda_r)} = (\omega_1)^{\alpha_1\lambda_1} \dots (\omega_r)^{\alpha_r\lambda_r}(\omega_1)^{\beta_1\lambda_1} \dots (\omega_r)^{\beta_r\lambda_r}=\chi^\lambda(g_\alpha)\chi^\lambda(g_\beta),

so \chi^\lambda is indeed a group homomorphism G \to U(\mathbb{C}).

-QED

Problem 17.2. Enhance Theorem 17.1 by proving that there are no other multiplicative characters of G.

We now have a special subset \{\chi^\lambda \colon \lambda \in \Lambda\} of the convolution algebra \mathcal{C}(G) of the finite abelian group G, the set of all its multiplicative characters. We now claim that this set forms a basis of \mathcal{C}(G). Since the number of characters is |\Lambda|=|G|, which is the dimension of \mathcal{C}(G), it is sufficient to show that \{\chi^\lambda \colon \lambda \in \Lambda\} is a linearly independent set in \mathcal{C}(G).

Theorem 17.2. The set \{\chi^\lambda \colon \lambda \in \Lambda\} is orthogonal with respect to the \ell^2-scalar product on G – we have

\langle \chi^\lambda,\chi^\mu\rangle = \sum\limits_{g \in G} \overline{\chi^\lambda(g)} \chi^\mu(g) = \delta_{\lambda\mu}|G|.

Proof: For any \lambda,\mu \in \Lambda, we have

\langle \chi^\lambda,\chi^\mu \rangle = \sum\limits_{\alpha \in \Lambda} \overline{\chi^\lambda(g_\alpha)}\chi^\mu(g_\alpha) = \sum\limits_{\alpha \in \Lambda}(\omega_1)^{\alpha_1(\mu_1-\lambda_1)} \dots (\omega_r)^{\alpha_r(\mu_r-\lambda_r)}=\left(\sum\limits_{\alpha_1=0}^{n_1-1} \zeta_1^{\alpha_1}\right) \dots \left(\sum\limits_{\alpha_r=0}^{n_r-1} \zeta_r^{\alpha_r}\right),

where

\zeta_1 = \omega_1^{\mu_1-\lambda_1},\ \dots,\ \zeta_r=\omega_r^{\mu_r-\lambda_r}.

Thus if \lambda=\mu we have

\langle \chi^\lambda,\chi^\mu \rangle = n_1 \dots n_r = |\Lambda|=|G|,

and if \lambda \neq \mu we have

\langle \chi^\lambda,\chi^\mu \rangle =\frac{1-\zeta_1^{n_1}}{1-\zeta_1} \dots \frac{1-\zeta_r^{n_r}}{1-\zeta_r},

where the denominator of each factor is nonzero and the numerator of some factor is zero, because \zeta_k=\omega_k^{\mu_k-\lambda_k} is an n_kth root of unity and \mu_k \neq \lambda_k for some k .

-QED

The orthogonal basis \{\chi^\lambda \colon \lambda \in \Lambda\} of \mathcal{C}(G) is called its character basis. In fact, the rescaled character basis

F^\lambda = \frac{1}{|G|}F^\lambda, \quad \lambda \in \Lambda,

is even better, for the following reason.

Theorem 17.3. The set \{F^\lambda \colon \lambda \in \Lambda\} is a Fourier basis of \mathcal{C}(G).

Proof: For any \lambda \in \Lambda, we have

(F^\lambda)^* = \left( \frac{1}{|G|}\sum\limits_{g \in G} \chi^\lambda(g) E_g\right)^*=\frac{1}{|G|}\sum\limits_{g \in G} \overline{\chi^\lambda(g)} E_g^* =\frac{1}{|G|} \sum\limits_{g \in G} \chi^\lambda(g^{-1}) E_{g^{-1}} = F^\lambda.

For any \lambda,\mu \in \Lambda, we have

F^\lambda F^\mu = \left( \frac{1}{|G|}\sum\limits_{g \in G} \chi^\lambda(g) E_g\right)\left( \frac{1}{|G|}\sum\limits_{g \in G} \chi^\mu(g) E_g\right)=\frac{1}{|G|^2}\sum\limits_{g \in G} \left( \sum\limits_{h \in G}\chi^\lambda(gh^{-1})\chi^\mu(h)\right)E_g = \frac{1}{|G|^2}\sum\limits_{g \in G} \chi^\lambda(g)\left( \sum\limits_{h \in G}\chi^\lambda(h^{-1})\chi^\mu(h)\right)E_g.

The internal sum is

\sum\limits_{h \in G}\chi^\lambda({h^{-1}})\chi^\mu(h)=\sum\limits_{h \in G}\overline{\chi^\lambda(h)}\chi^\mu(h)=\delta_{\lambda\mu}|G|,

where the final equality is Theorem 8.3. Thus

F^\lambda F^\mu = \frac{1}{|G|^2}\delta_{\lambda\mu}|G|\sum\limits_{g \in G} \chi^\lambda(g)E_g=\delta_{\lambda\mu}F^\lambda.

-QED

Published by Jonathan Novak

Mathematician at UC San Diego.

Leave a Reply