Hi everyone!

Consider the following problem. You're given two arrays $$$a_1, a_2, \dots, a_{n!}$$$ and $$$b_1, b_2, \dots, b_{n!}$$$.

You need to compute the array $$$c_1, c_2, \dots, c_{n!}$$$, such that

where $$$i \circ j$$$ denotes the composition of the $$$i$$$-th and the $$$j$$$-th lexicographically smallest permutations of $$$n$$$ elements.

Generally, typical approach to such things would be to escape into space in which the convolution corresponds to the component-wise product of two vectors, and then to transform back into initial space. For example, with the summation rule being $$$i + j \equiv k \pmod n$$$, it is well known that the corresponding transform is exactly the discrete Fourier transform of vectors $$$a_i$$$ and $$$b_j$$$.

But with more generic groups, things may be much more complicated. This is the second blog in a series of blog posts explaining it.

• Fourier transform on groups. Part 1: Irreducible representations
• Fourier transform on groups. Part 2: Characters

Great thanks to Endagorion and Golovanov399 for helping to understand the theory for this part!

In this blog, we will learn the basics of character theory which will allow us to define the inverse Fourier transform on finite groups.

Prerequisites

Difficulty: ★★★★★

One is expected to have some reasonable intuition with group theory and be well-familiar with linear algebra, and be familiar with some tangent definitions (e.g. what is a ring, what is a field, what is a linear span, what is a vector space, dot product, hermite product etc). Familiarity with discrete Fourier transform, and similar transforms used to compute convolutions is also essential.

$$$\operatorname{Hom}(V, W)$$$ as a representation

As this section is particularly dense on the mathematical notation, I decided to hide it under spoiler tag. It is highly recommended to familiarize with it, as it provides a whole lot of necessary intuition and motivation as to why exactly we're introducing the characters the way we do in the next section. However, if you're more interested in concrete results, and are fine with skipping less relevant details, you can proceed to the next section directly.

Characters

The result above allows us to introduce the key concept of the representation theory, the characters of the representation.

Def. 3. Let $$$x$$$ be the representation of a group $$$G$$$ in a vector space $$$V$$$. The character of a group element $$$g \in G$$$ is defined as

Let $$$\chi$$$ and $$$\theta$$$ be the characters of irreducible representations $$$x$$$ and $$$y$$$. Then, using the results above, we get

The expression above can be treated as an inner product $$$\langle \theta, \chi \rangle$$$ on the vector space $$$\mathbb C^{|G|}$$$.

Orthonormality of the characters

One particularly nice property of characters is that if $$$x \sim x_1 + x_2$$$, and the representations $$$x_1$$$ and $$$x_2$$$ have characters $$$\chi_1$$$ and $$$\chi_2$$$, then the characters $$$\chi$$$ of $$$x$$$ can be obtained as the sum of characters of $$$x_1$$$ and $$$x_2$$$, that is

Let $$$x_1, x_2, \dots$$$ be the set of pairwise non-isomorphic, irreducible representations, and let $$$\chi_1, \chi_2, \dots \in \mathbb C^{|G|}$$$ be their character vectors. Then, as was already noted above, $$$\langle \chi_i, \chi_j\rangle = \delta_{ij}$$$, that is, the inner product is equal to $$$1$$$ when $$$i = j$$$ and $$$0$$$ otherwise. In particular, it means that irreducible characters are linearly independent, so there may be at most $$$|G|$$$ irreducible representations.

Another corollary here is that every representation $$$x$$$ is uniquely determined by its characters (up to isomorphism). Indeed, let

where $$$v_1, v_2, \dots$$$ are non-negative integers and $$$v_i x_i \sim x_i + x_i + \dots$$$, repeated $$$v_i$$$ times. Then

and the numbers $$$v_1, v_2, \dots$$$ are uniquely determined as $$$v_i = \langle \chi, \chi_i \rangle$$$ due to orthonormality of $$$\chi_1, \chi_2, \dots$$$. From this also follows that

Then, since any representation of a finite group can be decomposed into a direct sum of irreducible representations, we can deduce that the representation $$$x$$$ of a finite group $$$G$$$ is irreducible if and only if for its characters holds

Regular representation

Def. 4. The regular representation of $$$G$$$ is a representation $$$x$$$ in the space $$$\mathbb C^{|G|}$$$, such that $$$x^g(e_h) = e_{gh}$$$ for a basis $$$e_1, e_2, \dots, e_{|G|}$$$.

This representation, while being very simple and straight-forward in its definition, has a bunch of very interesting properties in terms of its characters. First of all, we may notice that in this representation, the characters are expressed as

This is due to the fact that $$$x^1 = I$$$ is the identity matrix, as $$$x^1 e_h = e_{1h} = e_h$$$, while any other $$$x^g$$$ has only zero elements on the diagonal, if it is represented as a matrix, hence it has a zero trace. This fact allows to express the coefficients in the decomposition of the regular representation character $$$r$$$ into irreducible characters as

where $$$V_i$$$ is the space of the irreducible representation $$$x_i$$$. Here we used the fact that $$$\chi(1)$$$ always equates to the dimension of $$$V$$$, as $$$x^1$$$ is always the unit matrix. That being said, each unique irreducible representation $$$x_i$$$ is included in the regular representation $$$x$$$ with multiplicity that is equal to the degree of $$$x_i$$$. From this also follows that

where $$$\deg x_i = \dim V_i$$$. Another important result here is that $$$r$$$ is expressed as

which allows us to reformulate initial formula for $$$r(g)$$$ as

Note: Rings a bell yet? Recall the identity

where $$$\omega_n$$$ is the $$$n$$$-th root of unity s. t. $$$\omega_n^n = 1$$$. And, indeed, $$$\chi_j(k) = \omega_n^{kj}$$$ are the $$$1$$$-dimensional irreducible characters of the cyclic group, which gives the connection of the standard discrete Fourier transform with the formula above.

Inverse Fourier transform

Now, assume once again that

and that we know $$$F(x_1), F(x_2), \dots$$$ for all irreducible representations $$$x_1, x_2, \dots$$$ of $$$G$$$. How do we recover $$$f_1, f_2, \dots, f_{|G|}$$$?

First of all, let's think for a moment why it is possible at all. Above, while analyzing the regular representation, we found out that

It is a very reassuring fact for us, because $$$|G|$$$ is the dimension of the $$$f_1, f_2, \dots, f_{|G|}$$$, if we treat it as a vector. On the other hand, each $$$F(x_i)$$$ can be represented as a square matrix of degree $$$\deg x_i$$$, meaning that overall the space of all possible $$$F(x_1), F(x_2), \dots$$$ has a dimension which is equal to the sum of the squared $$$\deg x_i$$$. So, at the very least we clearly see that the dimensions match up, heavily hinting that the inverse transform should exist. How should such transform look like?

Let's once again consider the regular representation $$$x$$$. As we found out above,

So, if we compute $$$F(x)$$$ in the regular representation $$$x$$$ (assuming the basis corresponds to the decomposition), what we get is a block-diagonal matrix, where the diagonal has $$$\deg x_1$$$ blocks that are equal to $$$F(x_1)$$$, then $$$\deg x_2$$$ blocks that are equal to $$$F(x_2)$$$, and so on. We can introduce a natural inner product on the linear space of all possible values of $$$F(x)$$$, defined in the coordinate form as

What is even more important is that the same inner product can be rewritten in a coordinate-agnostic form as

Note that for $$$F(x) = x^g$$$ and $$$G(x) = x^h$$$, by definition of the regular representation, it holds that

as $$$(x^h)^* = (x^h)^{-1} = x^{h^{-1}}$$$ for unitary matrices, and $$$x^g x^{h^{-1}} = x^{gh^{-1}}$$$. Hence, if we redefine the inner product to be divided by $$$|G|$$$, the family of transforms $$$x^g$$$ for all $$$g \in G$$$ would form an orthonormal basis in the space of all possible $$$F(x)$$$. On the other hand, since $$$F(x)$$$ and $$$G(x)$$$ are block-diagonal with same sizes of blocks, we can further rewrite it as

Using this formula, which is also known as the Plancherel formula, the decomposition in this basis is expressed through the inner product as

where $$$y_i = F(x_i)$$$, $$$d_i = \deg x_i$$$, and $$$x_1, x_2, \dots$$$ are all pairwise non-isomorphic irreducible representations of $$$G$$$. The formula above is known as the inverse Fourier transform on finite groups.

Extra: Conjugacy classes

Let's recall the following definition from a group theory:

Def. 5. The elements $$$a, b \in G$$$ are conjugate if there is an element $$$g \in G$$$ such that $$$a = g^{-1} b g$$$.

Conjugacy is an equivalence relation, meaning that we can define the conjugacy classes:

Def. 6. A conjugacy class is an equivalence class in $$$G$$$ under the conjugacy relation.

If $$$a$$$ and $$$b$$$ are conjugate, for the representation $$$x$$$ it means that $$$x^a = (x^g)^{-1} x^b x^g$$$, so the linear maps $$$x^a$$$ and $$$x^b$$$ must be similar. In particular, it means that $$$x^a$$$ and $$$x^b$$$ have the same characteristic polynomial. Thus, $$$\operatorname{tr} x^a = \operatorname{tr} x^b$$$, hence $$$\chi(a) = \chi(b)$$$.

In other words, for any conjugacy class $$$K$$$, the character is the same for all elements of the conjugacy class. Let $$$\chi(K)$$$ be the value of the character on the conjugacy class $$$K$$$, then the inner product of characters rewrites as

and we may treat the characters as vectors over $$$\mathbb C^k$$$ instead of $$$\mathbb C^{|G|}$$$, where $$$k$$$ is the number of conjugacy classes in $$$G$$$. This allows us to provide a more strict upper bound for the maximum possible number of the irreducible representations of $$$G$$$. Since the characters of irreducible representations are also orthonormal over $$$\mathbb C^k$$$, it means that there may be no more than $$$k$$$ pairwise non-isomorphic irreducible representations of $$$G$$$. And this bound is, in fact, always achieved!

It means that the number of non-isomorphic irreducible representations over the field $$$\mathbb C$$$ is exactly the number of conjugacy classes in the group $$$G$$$. Then, to find specific representations, it is often possible (in particular, in the case of permutation group $$$S_n$$$) to find a bijection between conjugacy classes and irreducible pairwise non-isomorphic representations. Finding irreducible representations for the symmetric group $$$S_n$$$ will be the main topic of the next blog in the series, so stay tuned!