Let the symmetric group on be identified with its right Cayley graph as generated by the conjugacy class of transpositions: two permutations are joined by a single edge if and only if for some transposition We equip with the corresponding word norm, so that is the minimal length of a factorization of into transpositions, or equivalently the length of a geodesic path from the identity permutation to in the Cayley graph.

Our current two-part goal is to compute the number of walks of given length between two specified vertices in , and to estimate the total variation distance between the distribution of simple random walk on and its stationary distribution, which is the uniform measure on

We will start by asking these same questions about certain simple subgroups of . Let be a positive integer such that and let be the subgroup of generated by disjoint transpositions, say

Thus is an abelian group of order whose elements are all permutations of the form

For example,

We identify with its Cayley graph, which is an induced subgraph of the Cayley graph of often referred to as the -dimensional hypercube graph.

**Problem 7.1:** Prove that is isomorphic to the group of bitstrings of length and that under this isomorphism the word norm is given by the number of nonzero bits.

There are two ways to implement the linear algebraic approach to the study of (random) walks on the hypercube The first employs the Hilbert space

of formal -linear combinations of permutations with the scalar product defined by declaring the permutation basis

to be orthonormal. This is the space favored by algebraists. Analysts prefer to use the space

of -valued functions of permutations with the scalar product defined by declaring the indicator function basis

to be orthonormal (the square bracket above is the Iverson bracket). These two spaces are isomorphic, with a Hilbert space isomorphism

given by

Because is not just a set, but a group, the corresponding Hilbert spaces and are algebras. The multiplication in is defined by

The multiplication in is defined by

This latter multiplication is typically referred to as *convolution* because of its formal similarity to convolution of functions on the real line,

and indeed this similarity is part of a meaningful analogy which we are just starting to discuss. It is clear that the isomorphism discussed above is an algebra isomorphism, i.e. it intertwines the two product operations.

In the algebraic formulation, the adjacency operator is defined by its action on the permutation basis,

In the functional implementation, the adjacency operator is defined by its action on the indicator function basis,

Both implementations of the linearization of — meaning ways of embedding this group into a vector space — are useful, and it is advisable to keep both in mind. In what follows, the functional implementation is somewhat more natural, but we will move back and forth between the two freely.

Intuition leads us to believe that the keys to the spectrum of must somehow come from the group structure of — not just from linear algebra, but from the interaction of linear algebra and group theory. Indeed, inside the linearization as a function space, there is a natural family of functions linked to the lingering group structure.

**Definition 1:** The **characters** of are the elements of which are group homomorphisms

from the hypercube to the multiplicative group of nonzero complex numbers. The set of characters of is called the **dual** of and denoted

Much more generally, for any finite abelian group , one defines its Pontryagin dual to be the set of all group homomorphisms

these being referred to as the characters of . The Pontryagin dual can be defined for much more general abelian groups, but in this course we will almost exclusively deal with finite groups.

Returning to the case at hand, let us note that Definition 1 is actually even simpler and more natural than it appears, since all elements of are permutations of order i.e. involutions. This means that we have the constraint

so that in fact the values of any character of must be a square root of i.e. either or From this it follows that the number of characters of must be the order of since each character is determined by the values

and we have choices, , for each of these values. This suggests that we can in fact parameterize the characters of by the elements of which offers the beginnings of an explanation as to why is called the dual of

**Theorem 1:** The characters of are precisely the functions defined by

*Proof*: Clearly, the number of these putative characters is which we know to be the total number of characters, so that it is sufficient to check that they are in fact group homomorphisms. But this is clear:

— Q.E.D.

**Problem 7.2:** Show that the multiplication defined by

gives the structure of a group, and that this *dual group* is isomorphic to

**Theorem 2:** The set is an orthogonal basis of

*Proof:* Since the cardinality of equals the cardinality of which is in turn the dimension of it is sufficient to prove orthogonality. Let be arbitrary. Then

where we have used Problem 7.1 and denotes the identity permutation. So it is sufficient to consider scalar products of the form In the case we have

If then there exists such that We then have

whence

— Q.E.D.

**Problem 7.3:** Prove the dual orthogonality relation

In Lecture 8, we will link the characters of to the adjacency operator of its Cayley graph.