Math 202: Convolution algebras

We have so far reviewed abstract algebras, function algebras, and endomorphism algebras. We now come to the convolution algebra \mathcal{C}(G) of a finite group G. As a vector space, this is not just isomorphic but literally equal to \mathcal{F}(G). However, the two are quite different as algebras, and to emphasize this we will write |g\rangle for the elementary function corresponding to g \in G rather than E_g. Then, the convolution product of two elementary functions in \mathcal{C}(G) is

|g\rangle|h\rangle = |gh\rangle,

where gh is the group product. This is not at all the same as the point wise product rule E_gE_h=\delta_{gh}E_g. Extending the above bilinearly, we get that the convolution of any two functions

A = \sum\limits_{g \in G} A(g)|g\rangle \quad\text{and}\quad B=\sum\limits_{g \in G} B(g)|g\rangle

in \mathcal{C}(G) is

|A\rangle|B\rangle = \sum\limits_{g\in G}\sum\limits_{h \in G} A(g)B(h)|gh\rangle,

or equivalently

|A\rangle|B\rangle = \sum\limits_{g \in G} \left(\sum\limits_{\substack{h,k \in G\\ g=hk}} A(h)B(k)\right)|g\rangle.

In particular, the multiplicative identity in \mathcal{C}(G) is |e\rangle, where e \in G is the group identity.

Conjugation is also defined differently in \mathcal{C}(G) then in \mathcal{F}(G): it is defined by anti linearly extending the rule |g\rangle^*=|g^{-1}\rangle, so that

|A\rangle^*=\sum\limits_{g \in G} \overline{A(g)} |g^{-1}\rangle = \sum\limits_{g \in G}\overline{A(g^{-1})}|g\rangle.

In particular, the elementary basis \{|g\rangle \colon g \in G\} of \mathcal{C}(G) consists of unitary elements, so it is definitely not a Fourier basis. Nevertheless, we have the following important result.

Theorem C1. If G is abelian, then \mathcal{C}(G) and \mathcal{F}(G) are isomorphic algebras.

The converse of Theorem C1 is also true, since any algebra isomorphic to a function algebra must be commutative and it is easy to show that \mathcal{C}(G) is commutative precisely when G is abelian.

Theorem C1 means that the convolution algebra \mathcal{C}(G) contains a “hidden” Fourier basis. The construction of this hidden Fourier basis and the corresponding Fourier transform is a sacred part of applied algebra, the theory of the Discrete Fourier Transform (DFT), and you must be DTF with the DFT.

The construction of the hidden Fourier basis in \mathcal{C}(G) leverages the structure of the underlying abelian group G. Namely, a multiplicative character of G is a group homomorphism

\chi \colon G \longrightarrow \mathbb{U}_1,

where \mathbb{U}_1 is the unit circle in the complex plane. The set of all multiplicative characters is denoted \widehat{G} and called the dual group of G when equipped with point wise multiplication.

Theorem C2. The dual group \widehat{G} is indeed a group, and it is isomorphic to G.

This result can be proved directly, but to use it efficiently my preference is to consider a third group \Lambda isomorphic to both G and \widehat{G} which may be thought of as simultaneously parameterizing both of them. To construct \Lambda, first recall that every finite abelian group is isomorphic to a product of cyclic groups, so we may without loss in generality assume that

G=G_1 \times \dots \times G_r

where G_i is a cyclic group of order n_i with generator g_i. Let \Lambda = \mathbb{Z}_{n_1} \times \dots \times \mathbb{Z}_{n_r}, so that explicitly

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

and parameterize G by \Lambda as

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

At the same time, points of \Lambda parameterize \widehat{G}.

Theorem C3. The set \widehat{G} of multiplicative characters of G is given explicitly by the functions

\chi^\lambda(g_\alpha)=\omega_1^{\alpha_1\lambda_1} \dots \omega_r^{\alpha_r\lambda_r}, \quad \lambda \in \Lambda,

where \omega_k is the principal n_kth root of unity.

Now introduce the scalar product on \mathcal{C}(G) in which \{|g\rangle \colon g \in G\} is an orthonormal basis. Explicitly, we have

\langle A | B\rangle = \sum\limits_{g \in G} \overline{A(g)}B(g).

Consider the functions in \mathcal{C}(G) defined by

|C^\lambda\rangle = \sum\limits_{\alpha \in \Lambda} \chi^\lambda_\alpha |g_\alpha\rangle, \quad \lambda \in \Lambda,

where \chi^\lambda_\alpha:=\chi^\lambda(g_\alpha).

Theorem C4. The functions |C^\lambda\rangle satisfy the scalar product orthogonality relation

\langle C^\lambda | C^\mu \rangle = \delta_{\lambda\mu}|G|.

Since \{|C^\lambda\rangle \colon \lambda \in \Lambda\} is an orthogonal set in \mathcal{C}(G), it is linearly independent, and since it has cardinality |\Lambda|=|G| it is a basis of \mathcal{C}(G), called the character basis of \mathcal{C}(G). Up to normalization, the character basis of \mathcal{C}(G) is a Fourier basis. More precisely, define

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

We then have the following

Theorem C5. The functions \{|F^\lambda\rangle \colon \lambda \in \Lambda\} are a Fourier basis of \mathcal{C}(G).

We can now take an arbitrary function |A\rangle \in \mathcal{C}(G), expand it in the Fourier basis,

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

and from the general theory of abstract algebras we immediately have that the map |A\rangle \mapsto \widehat{A} is an algebra isomorphism \mathcal{C}(G) \to \mathcal{F}(\Lambda). Since \mathcal{F}(\Lambda) is isomorphic to \mathcal{F}(G), simply because |\Lambda|=|G| and the function algebras of any two finite sets of the same cardinality are isomorphic, Theorem C1 is proved.

The Fourier transform on the convolution algebra \mathcal{C}(G) of a finite abelian group has been studied extensively and is widely used. The following dual formulas frequently appear.

Theorem C6. Formula for the Fourier transform of A \in \mathcal{C}(G),

\widehat{A}(\lambda) = \sum\limits_{g \in G} \overline{\chi^\lambda(g)}A(g).

Recovery of a function A \in \mathcal{C}(G) from its Fourier transform,

A(g) = \frac{1}{|\Lambda|}\sum\limits_{\lambda \in \Lambda} \widehat{A}(\lambda)\chi^\lambda(g).

There is also an important reciprocal relationship between A and \widehat{A} which says that if one is highly concentrated, the other cannot be.

Theorem C7. For any nonzero function A \in \mathcal{C}(G), we have

|\mathrm{Supp}(A)||\mathrm{Supp}(\widehat{A})|\geq |G|.

Also important and useful is the simultaneous implementation of the Fourier and Wedderburn transforms on the convolution algebra \mathcal{C}(G) of a finite abelian group G. The Wedderburn transform takes an arbitrary function |A\rangle \in \mathcal{C}(G) and maps it to the linear operator A \in \mathrm{End}\mathcal{C}(G) defined by

A|B\rangle=|A\rangle|B\rangle=\sum\limits_{g \in G} \left(\sum\limits_{g=hk} A(h)B(k)\right)|g\rangle, \quad |B\rangle \in \mathcal{C}(G).

Writing F=\{F^\lambda \colon \lambda \in \Lambda\} for the Fourier basis of \mathcal{C}(G), the general relationship between the Fourier transform and the Wedderburn transform says that the operator A belongs to the diagonal subalgebra \mathcal{D}(F) of \mathrm{End}\mathcal{C}(G), and moreover that

A|F^\lambda\rangle = \widehat{A}(\lambda)|F^\lambda\rangle, \quad \lambda \in \Lambda.

What is important here is that we have explicit formulas both for the eigenfunctions |F^\lambda\rangle and the eigenvalues \widehat{A}(\lambda) in terms of the multiplicative characters \chi^\lambda of the underlying groups G, which are in turn explicitly describable in terms of roots of unity corresponding to the decomposition of G into a product of cyclic groups. You should be able to implement this architecture for various groups, e.g. the discrete circle G=\mathbb{Z}_n or the discrete hypercube G=\mathbb{Z}_2^n.

Published by Jonathan Novak

Mathematician at UC San Diego.

Leave a Reply