The Representation Theory of the Discrete Fourier Transform

Functions on Groups

Given a finite group $G$, I want to consider the algebra of complex-valued functions on $G$ (i.e. $\{f:G \to \C\}$).

Why? There are several reasons to study this algebra of functions. From a purely group-theoretic perspective, it is interesting because it can help you understand groups better. Today, however, I'll mostly focus on applications to CS.

What algebra structure are we using?

There are multiple choices of algebra structure on the set of functions $\{f:G \to \C\}$. Addition and scalar multiplication are pretty straightforward; clearly they should be done pointwise. You might also want to multiply the functions pointwise. This defines a perfectly fine algebra, but then nothing in our algebra actually depends on the group structure. We want to take advantage of the group structure to study these functions. So we won't define multiplication this way. Instead, we take the slightly stranger definition that $f_1 * f_2 (g) := \sum_{g_1 g_2 = g} f_1(g_1)\cdot f_2(g_2)$ We call this product convolution.

The group algebra $\C[G]$ is the algebra of complex-valued functions on $G$ with pointwise addition and scalar multiplication, and convolution as the product.

Miscellaneous facts about $\C[G]$

For $h \in G$, we define the $\delta$-function $\delta_h(g) := \begin{cases} 1 & g = h\\0 & \text{otherwise}\end{cases}$ With the convolution product, the multiplicative identity is the function $\delta_e$.

You can check that $f \star \delta_e(g) = \sum_{g_1g_2 = g} f(g_1) \delta_e(g_2) = f(g)\delta_e(e) = f(g)$ One useful basis for $\C[G]$ is given by $\{\delta_h\;|\;h \in G\}$.

We can define a hermitian product on $\C[G]$ by $\inrp {f_1} {f_2} := \frac 1 {|G|} \sum_{g \in G} f_1(g) \cdot \overline{f_2(g)}$

Example: $\C[\Z/n\Z]$

Suggestively, I'll denote $\delta_k$ by $x^k$. Then, elements of $\C[\Z/n\Z]$ are sums $a = \sum_{i=0}^{n-1} a_i x^i$. The product is given by $a\cdot b = \sum_{i = 0}^{n-1} \left[\sum_{j + k = i} a_j b_k \right]x^i$ So we see that $\C[\Z/n\Z] = \C[x]/(x^n-1)$. This is an important example for CS applications.

One useful tool for studying rings is studying modules over that ring. This trick will be very helpful to us.

Modules over $\C[G]$

Let $M$ be a module over $\C[G]$. First, we note that we can use our action of $\C[G]$ on $M$ to define an action of $\C$ on $M$. Simply define $\lambda \cdot m := (\lambda \delta_e) \cdot m$ for all $m \in M$. You can check that this makes $M$ into a complex vector space. Since $\delta_e$ is the multiplicative identity, it commutes with every element of $\C[G]$. So the action of every other element of $\C[G]$ on $M$ is linear with respect to this $\C$-action.

Furthermore, given a $\C$-vector space structure on $M$, the $\C[G]$ module structure is entirely determined by how each $\delta_g$ acts on $M$. So we can describe $M$ as a complex vector space along with a map $\rho:G \to \Aut(M)$.

Representations

A representation of $G$ is a vector space $V$ along with a homomorphism $\rho:G \to \Aut(M)$. We will denote this representation $(V, \rho)$, or just $V$.

Given a representation $(V, \rho)$, a subrepresentation is a linear subspace $W \subseteq V$ such that $g\cdot w \in W$ for all $w \in W$. Note that this makes $W$ into a representation of $G$.

A representation is called irreducible if its only subrepresentations are $\{0\}$ and itself. I'll call irreducible $G$-representations irreps.

A $G$-linear map (or morphism) between representations $(V, \rho)$, $(W, \pi)$ is a linear map $\phi: V \to W$ such that $\phi \circ \rho(g) = \pi(g) \circ \phi$ for all $g \in G$. We denote the set of all such morphisms between representations $V$ and $W$ by $\Hom_G(V, W)$ (Note that the particular action of $G$ on $V$ and $W$ is important, but we don't write $\rho$ and $\pi$ explicitly because the notation is already kind of long).

1. Any nonzero morphism between two irreps is an isomorphism.
2. Any nonzero morphism from an irrep to itself is an isomorphism.

1. Let $E, F$ be irreps. Suppose $\phi : E \to F$. $\ker \phi$ is a linear subspace of $E$. And if $\phi(v) = 0$, then $\phi(gv) = g \phi(v) = 0$. So $\ker \phi$ is $G$-invariant. Similarly, $\im \phi$ is a linear subspace of $F$. And if $w = \phi(v)$, then $gw = \phi(gv)$. So $\im \phi$ is also $G$-invariant. Since $E$ and $F$ are irreducible, this means that $\ker \phi$ and $\im \phi$ are either 0 or the whole vector space. If $\phi$ is nonzero, we must have $\ker \phi \neq E$, $\im \phi \neq 0$. So $\phi$ must be an isomorphism.
2. Let $\phi:E \to E$ be a nonzero morphism. Since we are working over $\C$, it must have a nonzero eigenvalue $\lambda$. Thus, $\phi - \lambda \I$ is not an isomorphism. By (a), it must be 0. So $\phi = \lambda \I$.

Characters

Given a representation $(V, \rho)$, we define an associated character $\chi_V:G \to \C$ given by $\chi_V(g) = \Tr[\rho(g)]$.

Now we've gone full circle and come back to $\C[G]$.

Note: $\chi_V$ is constant on conjugacy classes of $G$.

$\chi_V(hgh^{-1}) = \Tr[\rho(hgh^{-1})] = \Tr[\rho(h)\rho(g)\rho(h^{-1})] = \Tr[\rho(g)\rho(h^{-1})\rho(h)] = \Tr[\rho(g)] = \chi_V(g)$

A class function is a function on $G$ that is constant on conjugacy classes.

So we can also think the characters are complex-valued class functions.

There's a very nice theorem about the inner products of characters.

$\inrp {\chi_V} {\chi_W} = \dim \Hom_G(V, W)$

I don't have time to prove this at the moment. It's not too hard, though.

For irreps $E, F$, we have $\inrp {\chi_E} {\chi_F} = \begin{cases} 1 & E \cong F\\0 & \text{otherwise}\end{cases}$

Therefore, the characters of irreps are an orthonormal subset of the group algebra.

Fact: the number of irreducible representations of $G$ is the same as the number of conjugacy classes of $G$. Therefore, characters of irreps form a basis for the space of class functions on $G$.

If $G$ is abelian, the characters of irreps form an orthonormal basis for $\C[G]$.

Example: $\C[\Z/n\Z]$

Recall that $\C[\Z/n\Z] = \C[x]/(x^n-1)$, the ring of polynomials modulo $(x^n-1)$. What do these look like in the irreducible character basis?

What are the irreps of $\Z/n\Z$?

Irreducible representations of abelian groups are 1-dimensional.

Let $(E, \rho)$ be an irrep of an abelian group $G$. Fix $g \in G$. For every $h \in G$, $\rho(g)\rho(h) = \rho(gh) = \rho(hg) = \rho(h)\rho(g)$. Thus, $\rho(g)$ is a $G$-morphism from $E$ to $E$. By Schur's lemma, it must be a scalar multiple of the identity. This is true for every element of $g$. Therefore, every subspace of $E$ is a subrepresentation. Since $E$ is irreducible, this means that $E$ must have no nontrivial subspaces. So $E$ must be one-dimensional.

Thus, to find the irreps of $\Z/n\Z$, we only have to consider homomorphisms $\phi : \Z/n\Z \to \Aut[\C] = \C \setminus \{0\}$. Since $\Z/n\Z$ is cyclic, these homomorphisms are determined by $\phi(1)$. Since 1 has order $n$ in $\Z/n\Z$, $\phi(1)$ must be an $n$th root of unity. Let $\omega$ be a primitive $n$th root of unity. Then for all $k = 0, \ldots, n-1$ we get a homomorphism $\phi_k : \Z/n\Z \to \C$ given by $\phi_k(1) = \omega^k$. Since we have found $n$ irreducible representations, we have them all. Since the representations are all 1-dimensional, these are also the irreducible characters.

We can express a function on $\Z/n\Z$ in the character basis by taking its inner products with the irreducible characters. $\inrp {\phi_k} f = \sum_{\ell=0}^{n-1} \phi_k(\ell) \overline{f(\ell)} = \sum_{\ell=0}^{n-1} \overline{f(\ell)} \omega^{\ell k}$ Recall, we expressed these functions $f$ as $f = \sum_{\ell = 0}^{n-1} f(\ell) x^{\ell}$. So this is essentially evaluating the polynomial on $\omega^k$. This also looks a lot like the Fourier transform. In fact, it is the Discrete Fourier Transform.

If we write the function as a column vector, we can express this operation by the matrix $\begin{pmatrix} 1 & 1 & 1 & 1 & \cdots & 1\\ 1 & \omega & \omega^2 & \omega^3 & \cdots & \omega^{n-1}\\ 1 & \omega^2 & \omega^4 & \omega^6 & \cdots & \omega^{2(n-1)}\\ 1 & \omega^3 & \omega^6 & \omega^9 & \cdots & \omega^{3(n-1)}\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & \omega^{n-1} & \omega^{2(n-1)} & \omega^{3(n-1)} & \cdots & \omega^{(n-1)(n-1)} \end{pmatrix} \begin{pmatrix} \overline{f(0)}\\ \overline{f(1)}\\ \overline{f(2)}\\ \overline{f(3)}\\ \vdots\\ \overline{f(n-1)} \end{pmatrix}$ It turns out that because this matrix is so regularly-structured, we can compute this matrix-vector product really quickly. The Fast Fourier Transform lets us compute this in $O(n \log n)$ time, which is must faster than the naive $O(n^2)$ time for regular matrix-vector products. The Fast Fourier Transform has applications all over CS. It's used in signal processing, data compression (e.g. image processing), solving PDEs, multiplying polynomials, multiplying integers, and convolution, among other things.