23.9 Finite Abelian Groups and the Fourier Transform

Everything in this chapter has been building a machine, and for one family of groups the machine produces an object the book already owns. When $G$ is abelian and the field is $\mathbb{C}$ , Section 4 forces every irreducible representation down to a single dimension, Section 8 makes the resulting characters orthonormal, and what is left is one unitary matrix. For the cyclic group that matrix is the Fourier matrix of Chapter 12 Section 9, entry for entry. This section proves that, and two companion statements: the convolution theorem is the group algebra splitting into a product of copies of $\mathbb{C}$ , and a circulant is an element of that group algebra multiplying.

Throughout, $G$ is a finite abelian group, with identity written $e$ , and the field is $\mathbb{C}$ unless a statement says otherwise. When $G = \mathbb{Z}/n\mathbb{Z}$ we follow Chapter 12 Section 9 and run every index from $0$ to $n-1$ , reading subscripts modulo $n$ . We write $\delta_g$ for the basis vector of the group algebra $\mathbb{C}[G]$ attached to $g \in G$ (Definition 23.1.5), so that $\delta_g\delta_h = \delta_{gh}$ and $\delta_e$ is the identity of the algebra; the Kronecker delta of Chapter 11 always carries two numerical subscripts, as in $\delta_{jk}$ , and no group element is ever written as a pair of numbers.

23.9.1. One dimension is all there is

Section 4 proved that over an algebraically closed field the irreducible representations of a commutative algebra are lines, and Section 7 turned representations of $G$ into representations of $\mathbb{C}[G]$ . Since $G$ is abelian, $\mathbb{C}[G]$ is commutative, so the two results together leave no room: an irreducible complex representation of $G$ is one-dimensional, and an operator on a line is a number. A character is then not merely a function on $G$ ; it is a homomorphism out of $G$ .

Before that we recall the one fact about finite groups that Chapter 0 did not record: every $g$ in a finite group has a least $m \ge 1$ with $g^m = e$ , its order, and $\langle g\rangle = \{e, g, \dots, g^{m-1}\}$ is then a subgroup with exactly $m$ elements. Section 8 proved it, as Lemma 23.8.1, writing the identity $1$ where this section writes $e$ ; we use it constantly below.

A group of the form $\langle g\rangle$ gets a name, since it is the only shape of group we can handle in full.

Definition 23.9.1 (Cyclic group)

A group $G$ is cyclic if $G = \langle g\rangle$ for some $g \in G$ ; such a $g$ is called a generator of $G$ . A cyclic group is abelian, since $g^kg^l = g^{k+l} = g^lg^k$ .

One construction of groups from groups is needed before the examples, and Chapter 0 did not record it either.

Definition 23.9.2 (Direct product of groups)

Let $G$ and $H$ be groups. Their direct product $G \times H$ is the set of ordered pairs $(g, h)$ with the componentwise operation $(g,h)(g',h') \mathrel{:=} (gg', hh')$ . It is a group, with identity $(e_G, e_H)$ and $(g,h)^{-1} = (g^{-1}, h^{-1})$ ; the three axioms are checked one component at a time. It is abelian when $G$ and $H$ are, and $\lvert G\times H\rvert = \lvert G\rvert\,\lvert H\rvert$ .

By Lemma 23.8.1, a finite cyclic group $G = \langle g\rangle$ has $\lvert G\rvert$ equal to the order of $g$ . The standard example is $\mathbb{Z}/n\mathbb{Z}$ under addition, generated by $[1]$ , with $[1]$ of order $n$ . The group $\mathbb{Z}$ is cyclic and infinite. The Klein four-group $\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$ is abelian but not cyclic: every element satisfies $x + x = 0$ , so no element has order $4$ .

Now the theorem that starts the section.

Theorem 23.9.1 (Characters of an Abelian Group Are Homomorphisms)

Let $G$ be a finite abelian group and let the field be $\mathbb{C}$ . Then:

(a) every irreducible representation of $G$ is one-dimensional;
(b) a one-dimensional representation of $G$ is the same thing as a group homomorphism $\chi \colon G \to \mathbb{C}^{\times}$ , and the character of that representation is $\chi$ itself;
(c) every one-dimensional representation is irreducible, and two of them are equivalent if and only if they are equal;
(d) for every such $\chi$ and every $g \in G$ , the number $\chi(g)$ is an $m$ -th root of unity, where $m$ is the order of $g$ (Lemma 23.8.1); in particular $\lvert\chi(g)\rvert = 1$ and $\chi(g)^{-1} = \overline{\chi(g)} = \chi(g^{-1})$ .

Idea. Only (a) is deep, and Section 4 did it: in a commutative algebra every element commutes with the whole algebra, so Schur’s lemma (Theorem 23.4.1) makes every element act as a scalar, and then every line is invariant, so an irreducible representation can only be a line. The rest is bookkeeping about $1 \times 1$ matrices, together with the observation that a finite group makes every value a root of unity.

Proof.

(a) A representation of $G$ over $\mathbb{C}$ is a representation of the algebra $\mathbb{C}[G]$ (Theorem 23.7.1), and $\mathbb{C}[G]$ is commutative because $G$ is abelian: the products $\delta_g\delta_h = \delta_{gh}$ and $\delta_h\delta_g = \delta_{hg}$ agree on basis vectors, and the general case follows by bilinearity. Since $\mathbb{C}$ is algebraically closed, Corollary 23.4.4 applies and every irreducible representation is one-dimensional.
(b) Let $\rho \colon G \to \operatorname{GL}(V)$ with $\dim V = 1$ . For each $g$ the operator $\rho(g)$ maps the line $V$ to itself, so $\rho(g) = \chi(g)\,\operatorname{id}_V$ for a unique scalar $\chi(g)$ , and $\chi(g) \ne 0$ because $\rho(g)$ is invertible. From $\rho(gh) = \rho(g)\rho(h)$ we get $\chi(gh) = \chi(g)\chi(h)$ , so $\chi \colon G \to \mathbb{C}^{\times}$ is a homomorphism (Definition 0.10.3). In any basis of $V$ the matrix of $\rho(g)$ is the $1\times1$ matrix with entry $\chi(g)$ , so its trace, which is the character (Definition 23.8.2), is $\chi(g)$ . Conversely a homomorphism $\chi \colon G \to \mathbb{C}^{\times}$ defines a representation on $V = \mathbb{C}$ by $\rho(g)z = \chi(g)z$ .
(c) A one-dimensional $V$ has no subspaces but $\{0\}$ and $V$ , and $V \ne \{0\}$ , so there is no proper nonzero subrepresentation and $\rho$ is irreducible (Definition 23.7.4). Suppose $\rho, \rho'$ are one-dimensional with scalars $\chi, \chi'$ and $T \colon V \to V'$ is an isomorphism with $T\rho(g) = \rho'(g)T$ for all $g$ . Applying both sides to a nonzero $v \in V$ gives $\chi(g)\,Tv = \chi'(g)\,Tv$ , and $Tv \ne 0$ , so $\chi = \chi'$ . The converse is immediate with $T = \operatorname{id}$ .
(d) By Lemma 23.8.1 there is $m \ge 1$ with $g^m = e$ . Then $\chi(g)^m = \chi(g^m) = \chi(e) = 1$ by Theorem 0.10.3, so $\chi(g)$ is an $m$ -th root of unity (Example (Roots of Unity)). Taking absolute values, $\lvert\chi(g)\rvert^m = 1$ with $\lvert\chi(g)\rvert$ a positive real, so $\lvert\chi(g)\rvert = 1$ and therefore $\overline{\chi(g)} = \chi(g)^{-1}$ . Finally $\chi(g)^{-1} = \chi(g^{-1})$ , again by Theorem 0.10.3; this last identity is Proposition 23.8.2 (e) in the one-dimensional case.

Part (a) is where the field matters, and it matters twice over. It uses algebraic closure, and Section 4 exhibited what goes wrong without it: the rotation representation of a cyclic group on $\mathbb{R}^2$ is irreducible of dimension $2$ . Nothing in (a) needs a hypothesis on the characteristic; that hypothesis enters when we want representations to decompose, which is Maschke’s theorem (Theorem 23.7.3), and again through Section 8, whose orthogonality relations are proved by averaging over the group and need it too.

Example (The characters of a cyclic group)

Let $G = \mathbb{Z}/n\mathbb{Z}$ , written additively, and let $\omega \mathrel{:=} e^{2\pi i/n}$ . Find all homomorphisms $G \to \mathbb{C}^{\times}$ .

Solution. Section 7 did this, in Example (The irreducible complex representations of a cyclic group): such a $\chi$ is determined by $z \mathrel{:=} \chi([1])$ , which satisfies $z^n = \chi([n]) = \chi([0]) = 1$ and so equals $\omega^j$ for exactly one $j \in \{0, \dots, n-1\}$ (Example (Roots of Unity)); and each $j$ does give a homomorphism. So there are exactly $n$ characters, $\chi_j([m]) = \omega^{jm} \qquad (j, m = 0, 1, \dots, n-1) ,$ with $\chi_0$ the constant function $1$ . What Section 7 obtained as a list of irreducible representations is, by Theorem 23.9.1 (b), the same list read as homomorphisms.

Example (The Klein four-group)

Let $G = \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$ , with elements written $(x, y)$ for $x, y \in \{0, 1\}$ . Find all characters and write down the resulting table.

Solution. Every element satisfies $2(x,y) = (0,0)$ , so $\chi(x,y)^2 = \chi\bigl(2(x,y)\bigr) = \chi(0,0) = 1$ by Theorem 23.9.1 (b), and each value $\chi(x,y)$ is $\pm1$ . A homomorphism is determined by $\chi(1,0)$ and $\chi(0,1)$ , and any choice of signs for those two works: setting $\chi_{a,b}(x,y) \mathrel{:=} (-1)^{ax+by}$ for $a, b \in \{0,1\}$ gives a homomorphism, because $(-1)^{a(x+x')+b(y+y')}$ factors and the exponent only matters modulo $2$ . So there are exactly four characters, and the table of values, with rows the characters and columns the elements in the order $(0,0), (1,0), (0,1), (1,1)$ , is $\begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{pmatrix} ,$ the rows being $\chi_{0,0}, \chi_{1,0}, \chi_{0,1}, \chi_{1,1}$ . Any two distinct rows agree in two places and disagree in two, so their entrywise product sums to $0$ : the rows are orthogonal, as Theorem 23.8.7 says they must be.

Warning. The word “character” is doing double duty, and only for abelian groups do the two jobs coincide. For a general finite group the character $\chi_\rho = \operatorname{tr}\rho$ of Definition 23.8.2 is not a homomorphism: $\chi_\rho(e) = \dim V$ , which is $1$ only when $\rho$ is one-dimensional. The group $S_3$ has an irreducible complex representation of dimension $2$ (Section 7), whose character takes the value $2$ at the identity and is therefore not a homomorphism into $\mathbb{C}^{\times}$ . Reserve “the characters of $G$ ” for the homomorphisms $G \to \mathbb{C}^{\times}$ only when $G$ is abelian, which is what we do from here on.

Quick check. The group $\mathbb{Z}/3\mathbb{Z}$ has exactly one homomorphism into $\mathbb{R}^{\times}$ . Which, and why does this not contradict Theorem 23.9.1?

Solution. If $\chi \colon \mathbb{Z}/3\mathbb{Z} \to \mathbb{R}^{\times}$ is a homomorphism, then $\chi([1])^3 = 1$ with $\chi([1])$ real, and the only real cube root of $1$ is $1$ . So $\chi$ is trivial. There is no contradiction: Theorem 23.9.1 is a statement over $\mathbb{C}$ , and its part (a) rests on algebraic closure. Over $\mathbb{R}$ the group $\mathbb{Z}/3\mathbb{Z}$ has an irreducible two-dimensional representation, by rotation through $2\pi/3$ , and that representation has no one-dimensional pieces to contribute a character.

23.9.2. The dual group

The characters of $G$ are now a set of functions on $G$ , and that set has structure of its own: the pointwise product of two homomorphisms into an abelian group is again a homomorphism. So the characters form a group, and the rest of the section is about how that group compares with $G$ .

The dual group of $G$ is the group of ways to measure $G$ by complex numbers of modulus one.

Definition 23.9.3 (Dual group)

Let $G$ be a finite abelian group. The dual group of $G$ is $\widehat G \mathrel{:=} \{\, \chi \colon G \to \mathbb{C}^{\times} : \chi \text{ is a group homomorphism} \,\},$ with the pointwise operation $(\chi\psi)(g) \mathrel{:=} \chi(g)\psi(g)$ . Its elements are the characters of $G$ .

In words: an element of $\widehat G$ is one homomorphism out of $G$ , and two of them are multiplied by multiplying their values at each point separately. Nothing here refers to a representation any more; by Theorem 23.9.1 this is exactly the set of irreducible characters of $G$ , repackaged so that it carries a product.

Proposition 23.9.2 (The Dual Group Is a Group)

For a finite abelian group $G$ , the set $\widehat G$ with the pointwise operation is a finite abelian group. Its identity is the trivial character $\chi_0$ , with $\chi_0(g) = 1$ for every $g$ , and the inverse of $\chi$ is $\overline{\chi}$ , the function $g \mapsto \overline{\chi(g)}$ .

Proof. First, the operation lands in $\widehat G$ : if $\chi, \psi \in \widehat G$ then $(\chi\psi)(gh) = \chi(g)\chi(h)\psi(g)\psi(h) = (\chi\psi)(g)\,(\chi\psi)(h) ,$ where the first equality is that $\chi$ and $\psi$ are homomorphisms and the second reorders the four factors, using that $\mathbb{C}^{\times}$ is commutative; so $\chi\psi \in \widehat G$ . Associativity and commutativity hold pointwise because they hold in $\mathbb{C}^{\times}$ . The constant function $\chi_0 = 1$ is a homomorphism and satisfies $\chi_0\chi = \chi$ . For inverses, $\overline{\chi}$ is a homomorphism because conjugation is multiplicative, and $\chi(g)\overline{\chi(g)} = \lvert\chi(g)\rvert^2 = 1$ by Theorem 23.9.1 (d), so $\chi\overline{\chi} = \chi_0$ . Finally $\widehat G$ is finite: a character is determined by its values on the $\lvert G\rvert$ elements of $G$ , and each value $\chi(g)$ is an $m$ -th root of unity, where $m$ is the order of $g$ and $m \le \lvert G\rvert$ (Lemma 23.8.1); there are only finitely many such numbers. This proves the proposition.

How big is $\widehat G$ ? Section 8 already answered this, and the answer costs one observation about abelian groups.

Proposition 23.9.3 (The Dual Group Has the Same Size)

For every finite abelian group $G$ , $\lvert\widehat G\rvert = \lvert G\rvert$ .

Proof. Two elements $g, h \in G$ are conjugate when $h = xgx^{-1}$ for some $x \in G$ (Definition 23.8.1). In an abelian group $xgx^{-1} = gxx^{-1} = g$ , so each conjugacy class is a single element and $G$ has exactly $\lvert G\rvert$ conjugacy classes. By Theorem 23.8.9 the number of irreducible complex characters of $G$ equals the number of conjugacy classes, hence it is $\lvert G\rvert$ . By Theorem 23.9.1 (b) and (c), the irreducible characters are precisely the elements of $\widehat G$ , each arising from one equivalence class of irreducible representations. So $\lvert\widehat G\rvert = \lvert G\rvert$ .

That is a statement about cardinality. The stronger statement is that $\widehat G$ and $G$ are isomorphic as groups, and here the book runs into a limit it should name rather than hide. We can prove it for cyclic groups, and we can prove that it survives taking products; and that is as far as Chapter 0’s group theory reaches.

Theorem 23.9.4 (The Dual of a Product of Cyclic Groups)

Let $G$ and $H$ be finite abelian groups. Then:

(a) if $G$ is cyclic, then $\widehat G \cong G$ ;
(b) $\widehat{G \times H} \cong \widehat G \times \widehat H$ ;
(c) consequently, if $G$ is a direct product of finitely many finite cyclic groups, then $\widehat G \cong G$ .

Idea. For (a), a homomorphism out of $\langle g\rangle$ is decided by one value, and that value may be any $n$ -th root of unity; so the dual is listed by the same $n$ exponents that list $G$ , and matching exponent to exponent is the isomorphism. For (b), a character of a product splits into its two restrictions, and multiplying the restrictions back together recovers it. Part (c) is then induction on the number of factors.

Proof.

(a) Let $G = \langle g\rangle$ with $\lvert G\rvert = n$ , so $g$ has order $n$ (Lemma 23.8.1), and put $\omega = e^{2\pi i/n}$ . For $j \in \mathbb{Z}$ define $\chi_j(g^k) \mathrel{:=} \omega^{jk}$ . This is well defined: if $g^k = g^l$ then $n \mid k - l$ , so $\omega^{jk} = \omega^{jl}$ . It is a homomorphism, since $\omega^{j(k+l)} = \omega^{jk}\omega^{jl}$ , so $\chi_j \in \widehat G$ .
Now define $\Theta \colon G \to \widehat G$ by $\Theta(g^j) \mathrel{:=} \chi_j$ . It is well defined by the same divisibility: $n \mid j - j'$ gives $\omega^{jk} = \omega^{j'k}$ for every $k$ , so $\chi_j = \chi_{j'}$ . It is a homomorphism, because $\chi_j\chi_{j'}$ sends $g^k$ to $\omega^{jk}\omega^{j'k} = \omega^{(j+j')k}$ , which is $\chi_{j+j'}(g^k)$ . It is injective: if $\Theta(g^j) = \chi_0$ then $\omega^{j} = \chi_j(g) = 1$ , so $n \mid j$ and $g^j = e$ ; and a homomorphism with trivial kernel is injective, since $\Theta(x) = \Theta(y)$ gives $\Theta(xy^{-1}) = \chi_0$ by Theorem 0.10.3. It is surjective: given $\chi\in\widehat G$ , we have $\chi(g)^n = \chi(g^n) = \chi(e) = 1$ , so $\chi(g) = \omega^{j}$ for some $j$ (Example (Roots of Unity)), and then $\chi(g^k) = \omega^{jk} = \chi_j(g^k)$ for every $k$ , so $\chi = \chi_j = \Theta(g^j)$ . Hence $\Theta$ is an isomorphism.
(b) Define $\Xi \colon \widehat G\times\widehat H \to \widehat{G\times H}$ by letting $\Xi(\chi,\psi)$ be the function $(g,h)\mapsto \chi(g)\psi(h)$ . That function is a homomorphism, since $\chi(gg')\psi(hh') = \bigl(\chi(g)\psi(h)\bigr)\bigl(\chi(g')\psi(h')\bigr) ,$ using commutativity of $\mathbb{C}^{\times}$ . The map $\Xi$ is a homomorphism of groups because both sides are computed pointwise. It is injective: if $\chi(g)\psi(h) = 1$ for all $g, h$ , then taking $h = e_H$ gives $\chi(g) = 1$ for all $g$ , whence also $\psi = \chi_0$ ; so the kernel is trivial and $\Xi$ is injective, for the reason given in (a). It is surjective: given $\theta \in \widehat{G\times H}$ , set $\chi(g) \mathrel{:=} \theta(g, e_H)$ and $\psi(h) \mathrel{:=} \theta(e_G, h)$ , both homomorphisms; then $\theta(g,h) = \theta\bigl((g,e_H)(e_G,h)\bigr) = \chi(g)\psi(h) ,$ so $\theta = \Xi(\chi,\psi)$ . Hence $\Xi$ is an isomorphism.
(c) Induct on the number $r$ of factors. For $r = 1$ this is (a). If $G = G_1\times\dots\times G_r$ with each $G_i$ cyclic, write $G = G_1 \times K$ with $K = G_2\times\dots\times G_r$ . By (b), $\widehat G \cong \widehat{G_1}\times\widehat K$ , which by (a) and the inductive hypothesis is isomorphic to $G_1\times K = G$ .

Remark. The chapter can go no further here, and it should say so. It is true that every finite abelian group is a direct product of cyclic groups, so that $\widehat G\cong G$ for every finite abelian $G$ . That structure theorem is not proved in this book, and nothing below depends on it: every later statement of this section is either about a cyclic group or uses only Proposition 23.9.3, which is proved. The linear-algebra shadow of the structure theorem is in Chapter 10 Section 7: Theorem 10.7.3 diagonalizes a matrix over $F[x]$ with a divisibility chain, and the identical argument over $\mathbb{Z}$ turns a matrix of relations between generators of a finite abelian group into a list of cyclic factors. Chapter 10 sets that out as Exercise (C1: The same algorithm over the integers), and an exercise is not a proof; the input it assumes, that a finite abelian group is presentable by an integer relation matrix at all, is also not proved there.

Warning. The isomorphism $\widehat G\cong G$ of Theorem 23.9.4 is not canonical: the map $\Theta$ in the proof depends on choosing a generator $g$ of $G$ and a primitive root of unity $\omega$ , and different choices give different isomorphisms. There is no way to remove the choice. What is canonical is the isomorphism from $G$ to its double dual, $g \mapsto (\chi\mapsto\chi(g))$ , which mentions no choices at all; Exercise (C2: The double dual needs no choices) asks you to prove it. This is the same phenomenon as Chapter 5’s $V \cong V^{*}$ against $V\cong V^{**}$ , and it is not a coincidence.

Quick check. Why does Proposition 23.9.3 fail for $S_3$ if “character” is read as “homomorphism into $\mathbb{C}^{\times}$ ”?

Solution. Because Proposition 23.9.3 used that every conjugacy class of an abelian group is a single element. In $S_3$ there are three classes, not six, so there are three irreducible characters; and of those only two are one-dimensional, so the set of homomorphisms $S_3\to\mathbb{C}^{\times}$ has two elements, not six. The proof breaks at the first line, not the last.

23.9.3. The character matrix, the transform, and inversion

With $\lvert\widehat G\rvert = \lvert G\rvert = n$ we may line the two sets up and form a square matrix of values. Everything the section is heading towards is a statement about that one matrix.

Definition 23.9.4 (Character matrix)

Let $G$ be a finite abelian group of order $n$ . Fix an ordering $g_0, \dots, g_{n-1}$ of $G$ and an ordering $\chi_0, \dots, \chi_{n-1}$ of $\widehat G$ , which has $n$ elements too (Proposition 23.9.3). The character matrix of $G$ for those orderings is $\mathbf{U} \in M_n(\mathbb{C})$ with $(\mathbf{U})_{mj} \mathrel{:=} \frac{\chi_j(g_m)}{\sqrt n} \qquad (0 \le m, j \le n-1) .$ Its $j$ -th column lists the values of $\chi_j$ , scaled by $n^{-1/2}$ .

Section 8 rescaled the same table the other way up: the matrix in the proof of Corollary 23.8.11 has the characters along its rows, and is the transpose of this $\mathbf{U}$ once every class size $c_j$ is $1$ , which for an abelian $G$ it is.

The scaling is there for one reason, and the next theorem is that reason. Alongside it we name the transform.

Definition 23.9.5 (Fourier transform on a finite abelian group)

Let $G$ be a finite abelian group of order $n$ and let $f \colon G\to\mathbb{C}$ . The Fourier transform of $f$ is the function $\widehat f \colon \widehat G\to\mathbb{C}$ given by $\widehat f(\chi) \mathrel{:=} \sum_{g\in G} f(g)\,\chi(g) .$

Theorem 23.9.5 (Fourier Inversion on a Finite Abelian Group)

Let $G$ be a finite abelian group of order $n$ , with orderings fixed as in Definition 23.9.4 and character matrix $\mathbf{U}$ . Then:

(a) $\mathbf{U}$ is unitary, and the $n$ functions $n^{-1/2}\chi_j$ form an orthonormal basis of the space $\mathbb{C}^{G}$ of all functions $G\to\mathbb{C}$ ;
(b) (Inversion) every $f\colon G\to\mathbb{C}$ satisfies $f(g) = \frac1n\sum_{\chi\in\widehat G}\widehat f(\chi)\,\overline{\chi(g)} \qquad (g \in G) ;$
(c) (Plancherel) $\displaystyle\sum_{g\in G}\lvert f(g)\rvert^2 = \frac1n\sum_{\chi\in\widehat G}\bigl\lvert\widehat f(\chi)\bigr\rvert^2$ .

Idea. Identify a function on $G$ with its column of values, so that $\mathbb{C}^{G}$ becomes $\mathbb{C}^n$ with the standard inner product. Orthonormality of the characters, which Section 8 proved by averaging and Schur’s lemma (Theorem 23.4.1), then says exactly that the columns of $\mathbf{U}$ are an orthonormal basis. Inversion and Plancherel are what a unitary matrix always gives: expand in the new basis, and lengths do not change.

Proof.

(a) Identify $f \in \mathbb{C}^{G}$ with the column $\mathbf{x}\in\mathbb{C}^n$ , $x_m = f(g_m)$ . Under this identification the standard inner product on $\mathbb{C}^n$ is $\langle f, f' \rangle = \sum_g f(g)\overline{f'(g)}$ . The $j$ -th column of $\mathbf{U}$ is the function $n^{-1/2}\chi_j$ , and for any $j, k$ , $\langle \tfrac{\chi_j}{\sqrt n}, \tfrac{\chi_k}{\sqrt n} \rangle = \frac1n\sum_{g\in G}\chi_j(g)\overline{\chi_k(g)} ,$ which is the inner product of class functions of Definition 23.8.4 applied to $\chi_j$ and $\chi_k$ . By Theorem 23.9.1 (b) and (c) these are irreducible characters, of inequivalent representations when $j \ne k$ , so the value is $\delta_{jk}$ by Theorem 23.8.7. Hence the columns of $\mathbf{U}$ are orthonormal; there are $n$ of them in $\mathbb{C}^n$ , so they form an orthonormal basis (Theorem 11.1.4, Theorem 1.6.4), and $\mathbf{U}$ is unitary (Theorem 11.7.3).
(b) Write $\mathbf{y} \in \mathbb{C}^n$ for the column with $y_j = n^{-1/2}\widehat f(\chi_j)$ . By Definition 23.9.5, $y_j = \frac{1}{\sqrt n}\sum_{m} f(g_m)\chi_j(g_m) = \sum_m (\mathbf{U})_{mj}\,x_m ,$ that is $\mathbf{y} = \mathbf{U}^{\top}\mathbf{x}$ . Now $\mathbf{U}^{\top}$ is unitary as well, since $(\mathbf{U}^{\top})^{*}\mathbf{U}^{\top} = \overline{\mathbf{U}}\,\mathbf{U}^{\top} = \overline{\mathbf{U}\,\mathbf{U}^{*}} = \mathbf{I}$ , so $\mathbf{x} = (\mathbf{U}^{\top})^{*}\mathbf{y} = \overline{\mathbf{U}}\,\mathbf{y}$ . Reading off entry $m$ , $f(g_m) = \sum_j \overline{(\mathbf{U})_{mj}}\,y_j = \frac1n\sum_j \widehat f(\chi_j)\,\overline{\chi_j(g_m)} ,$ which is the stated formula.
(c) A unitary matrix preserves the norm (Theorem 11.7.3), so $\left\| \mathbf{y} \right\|^2 = \left\| \mathbf{x} \right\|^2$ . Here $\left\| \mathbf{x} \right\|^2 = \sum_g\lvert f(g)\rvert^2$ and $\left\| \mathbf{y} \right\|^2 = \tfrac1n\sum_j\lvert\widehat f(\chi_j)\rvert^2$ . This proves the theorem.

Two remarks on conventions, both harmless. Some authors put a conjugate into the transform, defining $\widehat f(\chi) = \sum_g f(g)\overline{\chi(g)}$ ; since $\overline{\chi} = \chi^{-1} \in\widehat G$ (Proposition 23.9.2), this only relabels $\widehat G$ by inversion, and the inversion formula swaps its conjugate accordingly. We use the version without the conjugate because it is the one Chapter 12 already wrote down. Second, the $n^{-1/2}$ sits in $\mathbf{U}$ and not in $\widehat f$ , which is again Chapter 12’s choice.

23.9.4. The cyclic group is Chapter 12

Now take $G = \mathbb{Z}/n\mathbb{Z}$ , ordered by $g_m = [m]$ , with the characters $\chi_j([m]) = \omega^{jm}$ of Example (The characters of a cyclic group) in that order, and $\omega = e^{2\pi i/n}$ . Three theorems follow, and together they say that the discrete Fourier transform of Chapter 12 was representation theory all along.

Theorem 23.9.6 (The Character Matrix Is the Fourier Matrix)

For $G = \mathbb{Z}/n\mathbb{Z}$ with the orderings above, the character matrix of Definition 23.9.4 is exactly the Fourier matrix $\mathbf{F}$ of Theorem 12.9.3: $(\mathbf{U})_{mj} = \frac{\omega^{jm}}{\sqrt n} = (\mathbf{F})_{mj} \qquad (0 \le m, j \le n-1) .$ In particular the unitarity of $\mathbf{F}$ and the orthonormality of the characters of $\mathbb{Z}/n\mathbb{Z}$ are the same statement.

Proof. By Definition 23.9.4 and Example (The characters of a cyclic group), $(\mathbf{U})_{mj} = \chi_j(g_m)/\sqrt n = \omega^{jm}/\sqrt n$ . By Theorem 12.9.3, $(\mathbf{F})_{mj} = \omega^{mj}/\sqrt n$ . The two agree because $jm = mj$ . The final sentence is Theorem 23.9.5 (a) read for this $\mathbf{U}$ .

That last sentence deserves to be dwelt on, because the book has now proved the same fact twice by genuinely different routes. Chapter 12 proved $\mathbf{F}^{*}\mathbf{F} = \mathbf{I}$ by summing a geometric series: for $z^n = 1$ and $z\ne1$ , $1 + z + \dots + z^{n-1} = 0$ . Section 8 proved orthonormality of irreducible characters by averaging an arbitrary linear map over the group and applying Schur’s lemma. The first argument is a computation that happens to come out; the second says why it had to. Neither is redundant, and the second does not make the first obsolete, since the first is what you use to compute.

Theorem 23.9.7 (The Group Algebra of an Abelian Group Splits)

Let $G$ be a finite abelian group of order $n$ , and let $\mathbb{C}^{\widehat G}$ denote the algebra of all functions $\widehat G\to\mathbb{C}$ with pointwise operations, which is a product of $n$ copies of $\mathbb{C}$ . Then $\Phi \colon \mathbb{C}[G] \to \mathbb{C}^{\widehat G}, \qquad \Phi\Bigl(\sum_{g} c_g\delta_g\Bigr)(\chi) \mathrel{:=} \sum_{g} c_g\,\chi(g),$ is an isomorphism of algebras. For $G = \mathbb{Z}/n\mathbb{Z}$ it is the discrete Fourier transform $\mathbf{c}\mapsto\widehat{\mathbf{c}} = \sqrt n\,\mathbf{F}\mathbf{c}$ of Chapter 12 Section 9, and its multiplicativity is Theorem 12.9.6 (b).

Idea. The map is multiplicative for one reason only: $\chi(gh) = \chi(g)\chi(h)$ , so evaluating a character on a product of group algebra elements factors. Bijectivity is not a separate argument either; the matrix of $\Phi$ in the obvious bases is the character matrix up to transposing and scaling, and that matrix is unitary.

Proof. Write $a = \sum_g c_g\delta_g$ and $b = \sum_h d_h\delta_h$ in $\mathbb{C}[G]$ (Definition 23.1.5), so that $ab = \sum_{g,h}c_gd_h\,\delta_{gh}$ . The map $\Phi$ is linear in $a$ by construction. For multiplicativity, evaluate at $\chi\in\widehat G$ : $\begin{aligned} \Phi(ab)(\chi) &= \sum_{g,h}c_gd_h\,\chi(gh) = \sum_{g,h}c_gd_h\,\chi(g)\chi(h) \\ &= \Bigl(\sum_g c_g\chi(g)\Bigr)\Bigl(\sum_h d_h\chi(h)\Bigr) = \Phi(a)(\chi)\,\Phi(b)(\chi) , \end{aligned}$ the second equality because $\chi$ is a homomorphism. The identity of $\mathbb{C}[G]$ is $\delta_e$ , and $\Phi(\delta_e)(\chi) = \chi(e) = 1$ for every $\chi$ , which is the identity of $\mathbb{C}^{\widehat G}$ . So $\Phi$ is a homomorphism of algebras (Definition 23.1.2).

For bijectivity, order $G$ and $\widehat G$ as in Definition 23.9.4. In the basis $(\delta_{g_0},\dots,\delta_{g_{n-1}})$ of $\mathbb{C}[G]$ and the basis of point masses on $\widehat G$ , the matrix of $\Phi$ has $(j,m)$ -entry $\chi_j(g_m) = \sqrt n\,(\mathbf{U})_{mj}$ ; that is, the matrix is $\sqrt n\,\mathbf{U}^{\top}$ . By Theorem 23.9.5 (a), $\mathbf{U}$ is unitary, hence invertible, hence so is $\sqrt n\,\mathbf{U}^{\top}$ . A linear bijection that is a homomorphism of algebras is an isomorphism of algebras.

For $G = \mathbb{Z}/n\mathbb{Z}$ , write $a = \sum_m c_m\delta_{[m]}$ . Then $\Phi(a)(\chi_j) = \sum_m c_m\omega^{jm} = p_{\mathbf{c}}(\omega^j)$ , the $j$ -th entry of the vector $\widehat{\mathbf{c}} = \sqrt n\,\mathbf{F}\mathbf{c}$ of Chapter 12 Section 9, with $p_{\mathbf{c}}$ the symbol of Definition 12.9.1. Multiplicativity of $\Phi$ then reads $p_{\mathbf{c}\ast\mathbf{d}}(\omega^j) = p_{\mathbf{c}}(\omega^j)p_{\mathbf{d}}(\omega^j)$ , which is Theorem 12.9.6 (b).

So the convolution theorem is a splitting theorem. Convolution is hard to look at because it is multiplication in $\mathbb{C}[G]$ written in the basis of point masses; in the basis of characters the same multiplication is diagonal, because there the algebra has fallen apart into $n$ independent copies of $\mathbb{C}$ . Seen from Section 6 this is no surprise: $\mathbb{C}[G]$ is semisimple by Theorem 23.7.3 applied to the regular representation, and a commutative semisimple algebra over $\mathbb{C}$ is a product of matrix algebras by Theorem 23.6.1, all of whose blocks must be $1\times1$ because $M_k(\mathbb{C})$ is commutative only for $k = 1$ . Then $\dim\mathbb{C}[G] = \lvert G\rvert$ and Corollary 23.6.2 force the number of blocks to be $\lvert G\rvert$ . The content of Theorem 23.9.7 over and above that is the explicit isomorphism.

The third identification puts Chapter 12’s matrices back into the picture.

Theorem 23.9.8 (Circulants Are the Group Algebra of the Cyclic Group)

Let $n \ge 1$ and let $\mathcal{C}_n\subseteq M_n(\mathbb{C})$ be the algebra of circulants (Corollary 12.9.5). Let $\Psi\colon\mathbb{C}[\mathbb{Z}/n\mathbb{Z}]\to M_n(\mathbb{C})$ be the linear map with $\Psi(\delta_{[m]}) \mathrel{:=} \mathbf{S}^{m} \qquad (m = 0, 1, \dots, n-1),$ where $\mathbf{S}$ is the cyclic shift. Then:

(a) $\Psi$ is an isomorphism of algebras onto $\mathcal{C}_n$ , and $\Psi\bigl(\sum_m c_m\delta_{[m]}\bigr)$ is the circulant $\mathbf{C}$ with first row $\mathbf{c}$ ;
(b) $\Psi(a)$ is the matrix of the map “multiply by $a$ ” on $\mathbb{C}[\mathbb{Z}/n\mathbb{Z}]$ , in the ordered basis $\mathcal{B} = \bigl(\delta_{[0]},\ \delta_{[-1]},\ \delta_{[-2]},\ \dots,\ \delta_{[-(n-1)]}\bigr) ;$
(c) $\mathbf{F}^{*}\Psi(a)\mathbf{F}$ is the diagonal matrix whose $j$ -th entry is $\Phi(a)(\chi_j)$ ; that is, $\Phi$ is $\Psi$ followed by conjugating with $\mathbf{F}$ and reading off the diagonal.

Idea. Part (a) is almost a tautology once the right map is chosen: $\Psi$ sends the basis element $\delta_{[m]}$ to $\mathbf{S}^m$ , and the only relation in the group, $[m] + [k] = [m+k]$ read modulo $n$ , matches the only relation among the powers, $\mathbf{S}^n = \mathbf{I}$ . Part (b) is an index computation, and the reversal of the basis in it is forced by Chapter 12’s convention $(\mathbf{C})_{jk} = c_{k-j}$ . Part (c) is Theorem 12.9.4 restated.

Proof.

(a) By Theorem 12.9.1 (a), $\sum_m c_m\mathbf{S}^m = p_{\mathbf{c}}(\mathbf{S})$ is the circulant with first row $\mathbf{c}$ , so $\Psi$ has the stated values and its image is $\mathcal{C}_n$ , which by Corollary 12.9.5 (a) has $\mathbf{I},\mathbf{S},\dots,\mathbf{S}^{n-1}$ as a basis. Hence $\Psi$ carries a basis to a basis and is a linear bijection onto $\mathcal{C}_n$ . For multiplicativity it suffices, by bilinearity of both products, to check it on basis vectors: $\Psi\bigl(\delta_{[m]}\delta_{[k]}\bigr) = \Psi\bigl(\delta_{[m+k]}\bigr) = \mathbf{S}^{(m+k)\bmod n} = \mathbf{S}^{m}\mathbf{S}^{k},$ the last equality because $\mathbf{S}^n = \mathbf{I}$ . Finally $\Psi(\delta_{[0]}) = \mathbf{I}$ , so $\Psi$ is an isomorphism of algebras onto $\mathcal{C}_n$ .
(b) Write $\mathcal{B} = (u_0,\dots,u_{n-1})$ with $u_k = \delta_{[-k]}$ ; this is a reordering of the basis of point masses, hence a basis. For $a = \sum_m c_m\delta_{[m]}$ , $a\,u_k = \sum_m c_m\,\delta_{[m-k]} = \sum_m c_m\,u_{k-m} = \sum_j c_{k-j}\,u_j ,$ substituting $j = k-m$ and reading all subscripts modulo $n$ . So the $(j,k)$ -entry of the matrix of multiplication by $a$ in $\mathcal{B}$ is $c_{k-j}$ , which is $(\mathbf{C})_{jk}$ by Definition 12.9.1. Hence that matrix is $\mathbf{C} = \Psi(a)$ .
(c) By (a) and Theorem 12.9.4, $\mathbf{F}^{*}\Psi(a)\mathbf{F} = \operatorname{diag}(p_{\mathbf{c}}(1),\dots,p_{\mathbf{c}}(\omega^{n-1}))$ , and $p_{\mathbf{c}}(\omega^j) = \Phi(a)(\chi_j)$ was computed at the end of the proof of Theorem 23.9.7.

Warning. Part (b) reverses the basis, and the reversal is not cosmetic. With Chapter 12’s convention $(\mathbf{C})_{jk} = c_{k-j}$ , applying a circulant to a vector is not convolution: $(\mathbf{C}\mathbf{x})_j = \sum_t c_t x_{j+t}$ , with a plus sign, whereas $(\mathbf{c}\ast\mathbf{x})_j = \sum_t c_tx_{j-t}$ . What is true is that $\mathbf{C}\mathbf{x} = \mathbf{c}^{-}\ast\mathbf{x}$ , where $\mathbf{c}^{-}$ is the vector with $(\mathbf{c}^{-})_t = c_{-t}$ , and that the product of two circulants is the circulant of the convolution of their first rows (Theorem 12.9.6 (a)). The group algebra sees the product, which is why Theorem 23.9.8 (a) needs no reversal while (b) does. If you keep only one of these, keep the product statement.

Example (The case

n = 4

, checked against Chapter 12)

For $G = \mathbb{Z}/4\mathbb{Z}$ , write down the character table, the character matrix, and the image under $\Phi$ of the element $a = \delta_{[0]} + 2\delta_{[1]} + 3\delta_{[2]} + 4\delta_{[3]}$ . Compare with Chapter 12 Section 9.

Solution. Here $\omega = e^{2\pi i/4} = i$ and $\chi_j([m]) = i^{jm}$ . The table of values, rows $\chi_0,\chi_1,\chi_2,\chi_3$ and columns $[0],[1],[2],[3]$ , is $\begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{pmatrix} .$ The array is symmetric, since $i^{jm} = i^{mj}$ , so reading it with rows indexed by $m$ and columns by $j$ and dividing by $\sqrt4 = 2$ gives the character matrix $\mathbf{U} = \frac12\begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{pmatrix} .$ This is exactly the matrix $\mathbf{F}$ of Example (The Fourier matrix of size four).

By Theorem 23.9.8 (a), $\Psi(a)$ is the circulant with first row $(1,2,3,4)$ , the running example of Chapter 12 Section 9. By Theorem 23.9.7, $\begin{aligned} \Phi(a)(\chi_0) &= 1 + 2 + 3 + 4 = 10, \\ \Phi(a)(\chi_1) &= 1 + 2i - 3 - 4i = -2 - 2i, \\ \Phi(a)(\chi_2) &= 1 - 2 + 3 - 4 = -2, \\ \Phi(a)(\chi_3) &= 1 - 2i - 3 + 4i = -2 + 2i, \end{aligned}$ using $i^2 = -1$ and $i^3 = -i$ . These are the four eigenvalues found in Example (The running example, diagonalized), in the same order, and Theorem 23.9.8 (c) says that $\mathbf{F}^{*}\Psi(a)\mathbf{F} = \operatorname{diag}(10, -2-2i, -2, -2+2i)$ , which is what that example computed. As a check on the first value, $\chi_0$ is the trivial character, so $\Phi(a)(\chi_0)$ is the sum of the coefficients, which is the common row sum $10$ of the circulant.

What has been bought? Chapter 12 said that a circulant is a polynomial in the shift, and proved it with an induction on the entries of $\mathbf{S}^m$ . That statement is now structural: $\mathbb{C}[\mathbb{Z}/n\mathbb{Z}]$ is generated as an algebra by one element $\delta_{[1]}$ , whose image is $\mathbf{S}$ , so every element of the algebra is a polynomial in $\mathbf{S}$ . What the structural reading does not hand over free is that those polynomials are exactly the circulants; that is still Chapter 12’s entry computation (Theorem 12.9.1 (a)), quoted in the proof of Theorem 23.9.8 (a). The one matrix $\mathbf{F}$ that diagonalizes every circulant simultaneously is the character matrix, which exists before any circulant is named because the characters of $G$ exist before any element of $\mathbb{C}[G]$ is named. And the reason the eigenvalues came out as $n$ evaluations of one polynomial is that they are the $n$ coordinates of $a$ in the product decomposition $\mathbb{C}[G]\cong\mathbb{C}^{\widehat G}$ .

23.9.5. Exercises

A. Check your understanding

Exercise (A1)

(a) Define the dual group $\widehat G$ of a finite abelian group $G$ , and say what its identity and inverses are.
(b) State why $\lvert\widehat G\rvert = \lvert G\rvert$ , naming the two results used.
(c) Write down the character matrix of $G$ and state what its unitarity says about the characters.
(d) Determine whether the following are true, with a reason. (i) Every irreducible complex representation of a finite abelian group is one-dimensional. (ii) The book has proved $\widehat G\cong G$ for every finite abelian $G$ . (iii) The Fourier matrix of Chapter 12 Section 9 is the character matrix of $\mathbb{Z}/n\mathbb{Z}$ . (iv) For $\mathbf{A} \in \mathcal{C}_n$ and $\mathbf{x}\in\mathbb{C}^n$ , $\mathbf{A}\mathbf{x}$ is the convolution of the first row of $\mathbf{A}$ with $\mathbf{x}$ .
(e) Explain in one sentence why the values of a character of a finite abelian group are roots of unity.

Solution.

(a) $\widehat G$ is the set of group homomorphisms $G\to\mathbb{C}^{\times}$ with the pointwise product (Definition 23.9.3). Its identity is the trivial character $\chi_0 \equiv 1$ , and the inverse of $\chi$ is $\conj\chi$ (Proposition 23.9.2).
(b) Because $G$ is abelian, each conjugacy class is a single element, so there are $\lvert G\rvert$ classes; Theorem 23.8.9 makes the number of irreducible characters equal to that, and Theorem 23.9.1 identifies the irreducible characters with the elements of $\widehat G$ (Proposition 23.9.3).
(c) $(\mathbf{U})_{mj} = \chi_j(g_m)/\sqrt n$ for fixed orderings of $G$ and $\widehat G$ (Definition 23.9.4). Unitarity says the columns are orthonormal, that is, $\tfrac1n\sum_g\chi_j(g)\overline{\chi_k(g)} = \delta_{jk}$ : the characters are an orthonormal basis of the functions on $G$ (Theorem 23.9.5).
(d)
- (i) True over $\mathbb{C}$ , by Theorem 23.9.1 (a); it is false over $\mathbb{R}$ . (ii) False. It is proved here only for direct products of cyclic groups (Theorem 23.9.4), and the book does not prove that every finite abelian group is such a product. (iii) True, entry for entry (Theorem 23.9.6). (iv) False: $(\mathbf{A}\mathbf{x})_j = \sum_t c_tx_{j+t}$ , while convolution has $x_{j-t}$ . The product of two circulants, however, is the circulant of the convolution.
(e) Each $g$ has finite order $m$ (Lemma 23.8.1), and applying $\chi$ to $g^m = e$ gives $\chi(g)^m = 1$ .

B. Practice

Exercise (B1: The character table of the group of order three)

Let $G = \mathbb{Z}/3\mathbb{Z}$ and $\omega = e^{2\pi i/3}$ .

(a) Write down the three characters and the character matrix.
(b) Verify one off-diagonal orthogonality relation by hand.
(c) Let $a = 2\delta_{[0]} - \delta_{[1]} - \delta_{[2]} \in\mathbb{C}[G]$ . Compute $\Phi(a)$ , write down the circulant $\Psi(a)$ , and state its eigenvalues.

Solution.

(a) By Example (The characters of a cyclic group), $\chi_j([m]) = \omega^{jm}$ for $j = 0, 1, 2$ , and $\mathbf{U} = \frac{1}{\sqrt3}\begin{pmatrix} 1 & 1 & 1 \\ 1 & \omega & \omega^2 \\ 1 & \omega^2 & \omega^4 \end{pmatrix} = \frac{1}{\sqrt3}\begin{pmatrix} 1 & 1 & 1 \\ 1 & \omega & \omega^2 \\ 1 & \omega^2 & \omega \end{pmatrix},$ using $\omega^4 = \omega^3\omega = \omega$ .
(b) Take $j = 1$ , $k = 0$ . Then $\tfrac13\sum_{m=0}^{2}\chi_1([m])\overline{\chi_0([m])} = \tfrac13(1 + \omega + \omega^2) = 0,$ since $\omega \ne 1$ and $(\omega-1)(1+\omega+\omega^2) = \omega^3-1 = 0$ .
(c) Here $\mathbf{c} = (2,-1,-1)$ , so $\Phi(a)(\chi_j) = 2 - \omega^{j} - \omega^{2j}$ . For $j = 0$ this is $2 - 1 - 1 = 0$ . For $j = 1$ and $j = 2$ the two subtracted terms are $\omega$ and $\omega^2$ in one order or the other, and $\omega + \omega^2 = -1$ by (b), so the value is $2 + 1 = 3$ both times. By Theorem 23.9.8 (a), $\Psi(a) = \begin{pmatrix} 2 & -1 & -1 \\ -1 & 2 & -1 \\ -1 & -1 & 2\end{pmatrix},$ with eigenvalues $0, 3, 3$ . The eigenvalue $0$ is visible directly: every row sums to $0$ , so the all-ones vector is in the kernel.

Exercise (B2: A product of two cyclic groups)

Let $G = \mathbb{Z}/2\mathbb{Z}\times\mathbb{Z}/3\mathbb{Z}$ and $\omega = e^{2\pi i/3}$ .

(a) Use Theorem 23.9.4 (b) to list the six characters of $G$ explicitly.
(b) Show that $G$ is cyclic by exhibiting a generator, and say which character of $G$ corresponds to which character of $\mathbb{Z}/6\mathbb{Z}$ under your isomorphism.

Solution.

(a) By Theorem 23.9.4 (b) every character of $G$ is $(x,y)\mapsto\chi(x)\psi(y)$ with $\chi\in\widehat{\mathbb{Z}/2\mathbb{Z}}$ and $\psi\in\widehat{\mathbb{Z}/3\mathbb{Z}}$ . By Example (The characters of a cyclic group) these are $\chi_a(x) = (-1)^{ax}$ for $a \in\{0,1\}$ and $\psi_b(y) = \omega^{by}$ for $b\in\{0,1,2\}$ . So the six characters are $\theta_{a,b}(x,y) = (-1)^{ax}\omega^{by} \qquad (a\in\{0,1\},\ b\in\{0,1,2\}),$ and there are $2\cdot3 = 6 = \lvert G\rvert$ of them, as Proposition 23.9.3 requires.
(b) Let $g = ([1],[1])$ . Its multiples are $([1],[1]), ([0],[2]), ([1],[0]), ([0],[1]), ([1],[2]), ([0],[0])$ for $k = 1,\dots,6$ , all six distinct, so $g$ has order $6$ and $G = \langle g\rangle$ is cyclic. Send $[k]\in\mathbb{Z}/6\mathbb{Z}$ to $kg$ ; this is the isomorphism. Under it the character $\chi_j$ of $\mathbb{Z}/6\mathbb{Z}$ with $\chi_j([k]) = \zeta^{jk}$ , $\zeta = e^{2\pi i/6}$ , pulls back to $\theta_{a,b}$ with $\theta_{a,b}(g) = (-1)^{a}\omega^{b} = \zeta^{3a+2b}$ , so $j \equiv 3a + 2b \pmod 6$ . As $(a,b)$ runs over the six pairs, $3a+2b$ runs over $0, 2, 4, 3, 5, 1$ modulo $6$ , hitting each residue once.

Exercise (B3: A transform and its inversion)

Let $G = \mathbb{Z}/4\mathbb{Z}$ and let $f$ be the function with values $f([0]), f([1]), f([2]), f([3]) = 1, 1, -1, -1$ .

(a) Compute $\widehat f(\chi_j)$ for $j = 0, 1, 2, 3$ .
(b) Recover $f([1])$ from Theorem 23.9.5 (b).
(c) Check Plancherel’s identity for $f$ .

Solution.

(a) With $\chi_j([m]) = i^{jm}$ and Definition 23.9.5, $\begin{aligned} \widehat f(\chi_0) &= 1 + 1 - 1 - 1 = 0, \\ \widehat f(\chi_1) &= 1 + i - (-1) - (-i) = 2 + 2i, \\ \widehat f(\chi_2) &= 1 - 1 - 1 + 1 = 0, \\ \widehat f(\chi_3) &= 1 - i + 1 - i = 2 - 2i . \end{aligned}$ For $j = 3$ the powers are $i^0, i^3, i^6, i^9 = 1, -i, -1, i$ , so the sum is $1 - i + 1 - i$ .
(b) Only $j = 1, 3$ contribute, and $\overline{\chi_1([1])} = \conj i = -i$ , $\overline{\chi_3([1])} = \overline{-i} = i$ . So $\tfrac14\bigl((2+2i)(-i) + (2-2i)(i)\bigr) = \tfrac14\bigl((2 - 2i) + (2 + 2i)\bigr) = 1 ,$ using $(2+2i)(-i) = -2i - 2i^2 = 2 - 2i$ and $(2-2i)(i) = 2i - 2i^2 = 2 + 2i$ . This is $f([1])$ , as it should be.
(c) The left side is $1 + 1 + 1 + 1 = 4$ . The right side is $\tfrac14(0 + \lvert2+2i\rvert^2 + 0 + \lvert2-2i\rvert^2) = \tfrac14(8 + 8) = 4$ . They agree.

C. Going deeper

Exercise (C1: The idempotents that do the splitting)

Let $G$ be a finite abelian group of order $n$ . For $\chi\in\widehat G$ put $\varepsilon_\chi \mathrel{:=} \frac1n\sum_{g\in G}\overline{\chi(g)}\,\delta_g \in \mathbb{C}[G].$

(a) Prove that $\Phi(\varepsilon_\chi)(\psi)$ equals $1$ when $\psi = \chi$ and $0$ otherwise.
(b) Deduce that $\varepsilon_\chi\varepsilon_\psi = 0$ for $\chi\ne\psi$ , that $\varepsilon_\chi^2 = \varepsilon_\chi$ , and that $\sum_\chi\varepsilon_\chi = \delta_e$ .
(c) For $G = \mathbb{Z}/4\mathbb{Z}$ write $\varepsilon_{\chi_1}$ out, and identify the matrix $\Psi(\varepsilon_{\chi_1})$ in terms of the Fourier vector $\mathbf{f}_1$ of Chapter 12 Section 9.

Hint for (a): the sum is an inner product of two characters.

Solution.

(a) By Definition 23.9.5 and the definition of $\Phi$ , $\Phi(\varepsilon_\chi)(\psi) = \frac1n\sum_{g}\overline{\chi(g)}\,\psi(g) = \frac1n\sum_g \psi(g)\overline{\chi(g)} ,$ which is the inner product of the irreducible characters $\psi$ and $\chi$ (Definition 23.8.4). By Theorem 23.8.7 it is $1$ if $\psi = \chi$ and $0$ otherwise.
(b) $\Phi$ is an isomorphism of algebras (Theorem 23.9.7), and in $\mathbb{C}^{\widehat G}$ the functions $\Phi(\varepsilon_\chi)$ are the point masses at the various $\chi$ . Point masses satisfy exactly the three relations claimed: the pointwise product of two distinct ones is $0$ , each is its own square, and their sum is the constant function $1$ , which is $\Phi(\delta_e)$ . Applying $\Phi^{-1}$ transfers the relations to $\mathbb{C}[G]$ .
(c) With $\chi_1([m]) = i^m$ , $\overline{\chi_1([m])} = (-i)^m$ , so $\varepsilon_{\chi_1} = \tfrac14\bigl(\delta_{[0]} - i\,\delta_{[1]} - \delta_{[2]} + i\,\delta_{[3]}\bigr).$ By Theorem 23.9.8 (a), $\Psi(\varepsilon_{\chi_1})$ is the circulant with first row $\tfrac14(1,-i,-1,i)$ , whose $(j,k)$ -entry is $\tfrac14(-i)^{k-j} = \tfrac14 i^{\,j-k}$ . With $\mathbf{f}_1 = \tfrac12(1,i,-1,-i)$ , the matrix $\mathbf{f}_1\mathbf{f}_1^{*}$ has $(j,k)$ -entry $\tfrac14 i^{j}\overline{i^{k}} = \tfrac14 i^{\,j-k}$ . This $\varepsilon_{\chi_1}$ is the idempotent called $e_2$ in Example (The group algebra of a cyclic group of order four), whose list runs from $1$ and is written in the generator $g = [1]$ . So $\Psi(\varepsilon_{\chi_1}) = \mathbf{f}_1\mathbf{f}_1^{*}$ , the orthogonal projection onto the line spanned by $\mathbf{f}_1$ . The idempotents of the group algebra are the spectral projections of Chapter 12.

Exercise (C2: The double dual needs no choices)

Let $G$ be a finite abelian group. For $g\in G$ define $\operatorname{ev}_g \colon \widehat G\to\mathbb{C}^{\times}$ by $\operatorname{ev}_g(\chi) \mathrel{:=} \chi(g)$ .

(a) Prove that $\operatorname{ev}_g \in \widehat{\widehat G}$ and that $g\mapsto\operatorname{ev}_g$ is a group homomorphism $G\to\widehat{\widehat G}$ .
(b) Prove that it is injective. Hint: the rows of the character matrix are indexed by the elements of $G$ .
(c) Deduce that it is an isomorphism, and explain why this is not a second proof of Theorem 23.9.4.

Solution.

(a) For $\chi,\psi\in\widehat G$ , $\operatorname{ev}_g(\chi\psi) = (\chi\psi)(g) = \chi(g)\psi(g) = \operatorname{ev}_g(\chi)\operatorname{ev}_g(\psi)$ , so $\operatorname{ev}_g$ is a homomorphism $\widehat G\to\mathbb{C}^{\times}$ , that is an element of $\widehat{\widehat G}$ . And $\operatorname{ev}_{gh}(\chi) = \chi(gh) = \chi(g)\chi(h) = (\operatorname{ev}_g\operatorname{ev}_h)(\chi)$ , so $g\mapsto\operatorname{ev}_g$ is a homomorphism.
(b) Suppose $\operatorname{ev}_g$ is the trivial character of $\widehat G$ , that is $\chi(g) = 1 = \chi(e)$ for every $\chi\in\widehat G$ . Then the rows of the character matrix indexed by $g$ and by $e$ are equal, so $\mathbf{U}$ has two equal rows and is singular, contradicting Theorem 23.9.5 (a) unless $g = e$ . Hence the kernel is trivial and the map is injective (Theorem 0.10.3 gives that the kernel is a subgroup, and a homomorphism with trivial kernel is injective by cancellation).
(c) By Proposition 23.9.3 applied twice, $\lvert\widehat{\widehat G}\rvert = \lvert\widehat G\rvert = \lvert G\rvert$ , so an injective homomorphism between them is a bijection, hence an isomorphism. It is not a proof that $\widehat G\cong G$ : it compares $G$ with the dual of its dual, and gives no map between $G$ and $\widehat G$ at all. The difference is exactly the one Chapter 5 drew between $V\cong V^{*}$ , which needs a choice of basis, and $V\cong V^{**}$ , which does not.

Exercise (C3: The same theory over a finite field)

Two properties of $\mathbb{C}$ were in use throughout this section: it contains $n$ distinct $n$ -th roots of unity, and $n$ is invertible in it. They are not everything $\mathbb{C}$ contributed: algebraic closure was spent in Theorem 23.9.1 (a), and Section 8’s orthogonality relations were proved for complex representations only. But for one group and one field the conclusions can be checked directly with nothing more than those two properties. Take $F = \mathbb{F}_5$ , $G = \mathbb{Z}/4\mathbb{Z}$ , and $\omega = 2 \in\mathbb{F}_5$ .

(a) Verify that $\omega$ has order $4$ in $\mathbb{F}_5^{\times}$ , and that $4$ is invertible in $\mathbb{F}_5$ .
(b) Write down the $4\times4$ matrix $\mathbf{M}$ with $(\mathbf{M})_{mj} = \omega^{jm}$ over $\mathbb{F}_5$ and check that $4^{-1}\sum_m\omega^{jm}\omega^{-km} = \delta_{jk}$ for $j = 1$ and $k = 0, 1$ .
(c) Let $\mathbf{C}$ be the circulant over $\mathbb{F}_5$ with first row $(1,2,3,4)$ . Compute $\mathbf{M}^{-1}\mathbf{C}\mathbf{M}$ without inverting $\mathbf{M}$ , by evaluating the symbol at the powers of $\omega$ .

Hint for (c): the proof of Theorem 12.9.4 used only $\mathbf{S}^n = \mathbf{I}$ and the geometric-series identity, both of which hold over $\mathbb{F}_5$ .

Solution.

(a) $2^1 = 2$ , $2^2 = 4$ , $2^3 = 3$ , $2^4 = 1$ in $\mathbb{F}_5$ , so $\omega = 2$ has order $4$ and $1, 2, 4, 3$ are four distinct fourth roots of $1$ . Also $4\cdot4 = 16 = 1$ , so $4$ is invertible with $4^{-1} = 4$ . Note $\operatorname{char}\mathbb{F}_5 = 5$ does not divide $\lvert G\rvert = 4$ , which is Maschke’s hypothesis.
(b) Reading rows $m = 0,1,2,3$ and columns $j = 0,1,2,3$ , $\mathbf{M} = \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & 2 & 4 & 3 \\ 1 & 4 & 1 & 4 \\ 1 & 3 & 4 & 2 \end{pmatrix} .$ For $j = k = 1$ every term is $\omega^{m}\omega^{-m} = 1$ , so the sum is $4^{-1}\cdot4 = 1$ . For $j = 1$ , $k = 0$ it is $4^{-1}(1 + 2 + 4 + 3) = 4\cdot 10 = 4\cdot 0 = 0$ in $\mathbb{F}_5$ .
(c) The symbol is $p_{\mathbf{c}}(x) = 1 + 2x + 3x^2 + 4x^3$ . Evaluating over $\mathbb{F}_5$ : $\begin{aligned} p_{\mathbf{c}}(1) &= 1+2+3+4 = 10 = 0, \\ p_{\mathbf{c}}(2) &= 1+4+12+32 = 49 = 4, \\ p_{\mathbf{c}}(4) &= 1+8+48+256 = 313 = 3, \\ p_{\mathbf{c}}(3) &= 1+6+27+108 = 142 = 2 . \end{aligned}$ The columns of $\mathbf{M}$ are the eigenvectors, so $\mathbf{M}^{-1}\mathbf{C}\mathbf{M} = \operatorname{diag}(0, 4, 3, 2)$ . The matrix $\mathbf{C}$ is singular over $\mathbb{F}_5$ , as it must be: its row sums are $10 = 0$ . Every conclusion checked here holds over $\mathbb{F}_5$ for this $G$ , except that “unitary” has no meaning and $\mathbf{M}$ is merely invertible; the orthogonality relations survive with $\overline{\,\cdot\,}$ replaced by inversion in $\mathbb{F}_5^{\times}$ .