Linear representation of additive groups and the Fourier Transform: Part 1
In this article I will show that the cyclic group of order n, that is the set
To begin I want to consider linear representations of the cyclic group of order n: that is I want to assign to each element of the group a linear operator on an inner product space in a way consistent with the group structure [or if you prefer, to find a homomorphism from the cyclic group to the group of automorphisms of an inner product space (an orthogonal group)]. There are lots of ways to do this, for lots of different vector spaces – the simplest is to map every group element to the identity (the trivial (linear) representation).
It would be nice to have some sort of canonical linear representation. Given a set we can form a vector space by taking all formal linear combinations of its elements (that is we consider the elements of the set to be linearly independent vectors, and the vector space is their span). If a group acts on that set we can extend it to a linear representation of the induced vector space by extending the group linearly; this is called the permutation representation.
For example if the set is
Now the group G acts on the set G by left multiplication, and so we can construct a permutation representation. This is called the regular representation of G.
What does this look like for a cyclic group of order n? The vector space has a basis of
There is also a natural inner product
Now since S is unitary it is normal and hence by the spectral theorem unitarily diagonalisable. So let’s look for it’s eigenvectors and eigenvalues: since
The diagonalising matrix is then
So
F is precisely the discrete Fourier transform (up to a choice of normalisation): if
Many of the properties of the discrete Fourier transform follow immediately; we know it is unitary by the spectral theorem which is precisely the Plancherel theorem. In particular it is invertible, which gives completeness. One half of the shift theorem is also immediate
What about convolutions? Given that each basis vector corresponds to a group element, there is a natural algebraic structure on the vector space, namely
What is the exact structure on V? There’s an inner product, but there’s also a relative ordering of the basis elements; it doesn’t matter where we start numbering the basis elements (except in the definition of convolutions) but S defines an order for them relative to each other. So to say the Fourier transform is defined by a complex inner product space is lying a little, because there is this extra structure. [Also, considering the Fourier transform is only defined up to a phase it could be more natural to think of two vectors being equivalent if they differ only by a phase.] Actually there is a much more natural way to introduce this structure.
There is another way to think of a permutation representation. We form the vector space associated to a set as the vector space of all linear functions from the set to the complex numbers. The basis vector corresponding to the element s is the characteristic function of s,
Now let’s look back at the regular representation of the cyclic group through this lens. We consider functions
A convolution is then
So what have we got? We started looking at regular linear representations of the cyclic group, and to change to a basis in which the group operations were diagonal we invented the discrete Fourier transform.
The power in this idea is there are many generalisations. We could have a look at more complicated groups or even more general algebraic structures. The representation theory of cyclic groups is very simple since they are abelian, there’s a lot more involved in trying to diagonalize the representations of non-abelian groups. We could then have other notions of convolutions and Fourier-type transforms. We could also look at mapping to other vector spaces or even to different geometric structures. If instead of constructing vector spaces over the complex numbers we constructed it over finite fields we would get (for the right combination of dimension of the vector space and characteristic of the field) the finite Fourier transform which is important in coding theory. One could also look at what happens to direct sums, tensor products and the like of the regular representations.