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
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
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:
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
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.