Math 202C: Lecture 7

Let the symmetric group \mathrm{S}(n) on \{1,\dots,n\} be identified with its right Cayley graph as generated by the conjugacy class of transpositions: two permutations \rho,\sigma \in \mathrm{S}(n) are joined by a single edge if and only if \sigma = \rho\tau for some transposition \tau \in \mathrm{S}(n). We equip \mathrm{S}(n) with the corresponding word norm, so that |\pi| is the minimal length of a factorization of \pi into transpositions, or equivalently the length of a geodesic path from the identity permutation to \pi in the Cayley graph.

Our current two-part goal is to compute the number of walks of given length between two specified vertices in \mathrm{S}(n), and to estimate the total variation distance between the distribution of simple random walk on \mathrm{S}(n) and its stationary distribution, which is the uniform measure U(\pi)=\frac{1}{n!} on \mathrm{S}(n).

We will start by asking these same questions about certain simple subgroups of \mathrm{S}(n). Let k be a positive integer such that 2k \leq n, and let \mathrm{B}(k) be the subgroup of \mathrm{S}(n) generated by k disjoint transpositions, say

\tau_1=(1\ 2),\ \tau_2=(3\ 4),\ \dots, \tau_k = (2k-1\ 2k).

Thus \mathrm{B}(k) is an abelian group of order 2^k, whose elements are all permutations of the form

\pi =\tau_1^{e_1} \dots \tau_k^{e_k}, \quad e_i \in \{0,1\}.

For example,

\mathrm{B}(2) = \{(1)(2)(3)(4), (1\ 2), (3\ 4),(1\ 2)(3\ 4)\}.

We identify \mathrm{B}(k) with its Cayley graph, which is an induced subgraph of the Cayley graph of \mathrm{S}(n) often referred to as the k-dimensional hypercube graph.

Problem 7.1: Prove that \mathrm{B}(k) is isomorphic to the group \mathbb{Z}_2^k of bitstrings of length k, and that under this isomorphism the word norm |\pi| 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 \mathrm{B}(k). The first employs the Hilbert space

\mathbb{C}\mathrm{B}(k) = \left\{\sum\limits_{\pi \in \mathrm{B}(k)} a_\pi \pi \colon a_\pi \in \mathbb{C}\right\}

of formal \mathbb{C}-linear combinations of permutations \pi \in \mathrm{B}(k), with the scalar product defined by declaring the permutation basis

\{\pi \colon \pi \in \mathrm{B}(k)\}

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

\mathbb{C}^{\mathrm{B}(k)} = \left\{ f \colon \mathrm{B}(k) \to \mathbb{C} \right\}

of \mathbb{C}-valued functions of permutations \pi \in \mathrm{B}(k)\}, with the scalar product defined by declaring the indicator function basis

\{ \delta_\pi(\sigma) := [\pi=\sigma] \colon \pi \in \mathrm{B}(k)\}

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

\mathbb{C}^{\mathrm{B}(k)} \longrightarrow \mathbb{C}\mathrm{B}(k)

given by

f \mapsto \sum\limits_{\pi \in \mathrm{B}(k)} f(\pi) \pi.

Because \mathrm{B}(k) is not just a set, but a group, the corresponding Hilbert spaces \mathbb{C}\mathrm{B}(k) and \mathbb{C}^{\mathrm{B}(k)} are algebras. The multiplication in \mathbb{C}\mathrm{B}(k) is defined by

\left( \sum\limits_{\rho \in \mathrm{B}(k)} a_\rho \rho \right)\left( \sum\limits_{\sigma \in \mathrm{B}(k)} b_\sigma \sigma \right) = \sum\limits_{(\rho,\sigma) \in \mathrm{B}(k)^2} a_\rho b_\sigma \rho\sigma = \sum\limits_{\pi \in \mathrm{B}(k)} \left( \sum\limits_{\sigma \in \mathrm{B}(k)} a_{\pi\sigma^{-1}} b_\sigma\right)\pi.

The multiplication in \mathbb{C}^{\mathrm{B}(k)} is defined by

\left( f*g \right)(\pi) = \sum\limits_{\sigma \in \mathrm{B}(k)} f(\pi\sigma^{-1}) g(\sigma).

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

(f*g)(x) = \int_{-\infty}^{\infty} f(x-t)g(t)\mathrm{d}t,

and indeed this similarity is part of a meaningful analogy which we are just starting to discuss. It is clear that the isomorphism \mathbb{C}^{\mathrm{B}(k)} \to \mathbb{C}\mathrm{B}(k) discussed above is an algebra isomorphism, i.e. it intertwines the two product operations.

In the algebraic formulation, the adjacency operator A \in \mathbb{C}\mathrm{B}(k) is defined by its action on the permutation basis,

A\pi = \sum\limits_{i=1}^k \pi\tau_i.

In the functional implementation, the adjacency operator A \in \mathbb{C}^{\mathrm{B}(k)} is defined by its action on the indicator function basis,

A\delta_{\pi} = \sum\limits_{i=1}^k \delta_{\pi\tau_i}.

Both implementations of the linearization of \mathrm{B}(k) — 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 A must somehow come from the group structure of \mathrm{B}(k) — not just from linear algebra, but from the interaction of linear algebra and group theory. Indeed, inside the linearization \mathbb{C}^{\mathrm{B}(k)} as a function space, there is a natural family of functions linked to the lingering group structure.

Definition 1: The characters of \mathrm{B}(k) are the elements \chi of \mathbb{C}^{\mathrm{B}(k)} which are group homomorphisms

\chi \colon \mathrm{B}(k) \longrightarrow \mathbb{C}^\times

from the hypercube to the multiplicative group of nonzero complex numbers. The set of characters of \mathrm{B}(k) is called the dual of \mathrm{B}(k), and denoted \widehat{\mathrm{B}(k)}.

Much more generally, for any finite abelian group \mathrm{G}, one defines its Pontryagin dual \widehat{\mathrm{G}} to be the set of all group homomorphisms

\chi \colon \mathrm{G} \longrightarrow \mathbb{C}^\times,

these being referred to as the characters of \mathrm{G}. 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 \mathrm{G}=\mathrm{B}(k) at hand, let us note that Definition 1 is actually even simpler and more natural than it appears, since all elements of \mathrm{B}(k) are permutations of order 2, i.e. involutions. This means that we have the constraint

\chi(\pi^2) = \chi(\pi)^2= 1,

so that in fact the values of any character \chi of \mathrm{B}(k) must be a square root of 1, i.e. either 1 or -1. From this it follows that the number of characters of \mathrm{B}(k) must be 2^k, the order of \mathrm{B}(k), since each character \chi is determined by the values

\chi(\tau_i), \quad 1 \leq i \leq k,

and we have 2 choices, \pm 1, for each of these values. This suggests that we can in fact parameterize the characters of \mathrm{B}(k) by the elements of \mathrm{B}(k), which offers the beginnings of an explanation as to why \widehat{\mathrm{B}(k)} is called the dual of \mathrm{B}(k).

Theorem 1: The characters of \mathrm{B}(k) are precisely the functions defined by

\chi_{\tau_1^{x_1} \dots \tau_k^{x_k}}(\tau_1^{y_1} \dots \tau_k^{y_k}) = (-1)^{x_1y_1+\dots+x_ky_k}.

Proof: Clearly, the number of these putative characters is 2^k, 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:

\chi_{\tau_1^{x_1} \dots \tau_k^{x_k}}(\tau_1^{y_1} \dots \tau_k^{y_k}) = (-1)^{x_1y_1+\dots+x_ky_k} = (-1)^{x_1y_1} \dots (-1)^{x_ky_k} = \chi_{\tau_1^{x_1} \dots \tau_k^{x_k}}(\tau_1^{y_1}) \dots \chi_{\tau_1^{x_1} \dots \tau_k^{x_k}}(\tau_k^{y_k}).

— Q.E.D.

Problem 7.2: Show that the multiplication defined by

\chi_{\rho}\chi_\sigma := \chi_{\rho\sigma}

gives \widehat{\mathrm{B}(k)} the structure of a group, and that this dual group is isomorphic to \mathrm{B}(k).

Theorem 2: The set \widehat{\mathrm{B}(k)} is an orthogonal basis of \mathbb{C}^{\mathrm{B}(k)}.

Proof: Since the cardinality of \widehat{\mathrm{B}(k)} equals the cardinality of \mathrm{B}(k), which is in turn the dimension of \mathbb{C}^{\mathrm{B}(k)}, it is sufficient to prove orthogonality. Let \rho,\sigma \in \mathrm{B}(k) be arbitrary. Then

\langle \chi_\rho,\chi_\sigma \rangle = \sum\limits_{\pi \in \mathrm{B}(k)} \chi_\rho(\pi)\chi_\sigma(\pi) = \sum\limits_{\pi \in \mathrm{B}(k)} \chi_{\rho\sigma}(\pi) = \langle \chi_{\rho\sigma},\chi_\iota\rangle,

where we have used Problem 7.1 and \iota \in \mathrm{B}(k) denotes the identity permutation. So it is sufficient to consider scalar products of the form \langle \chi_\rho,\chi_\iota\rangle. In the case \rho=\iota, we have

\langle \chi_\iota,\chi_\iota \rangle = \sum\limits_{\pi \in \mathrm{B}(k)} \chi_\iota(\pi)\chi_\iota(\pi) = \sum\limits_{\pi \in \mathrm{B}(k)} 1 = 2^k.

If \rho \neq \iota, then there exists \sigma \in \mathrm{B}(k) such that \chi_\rho(\sigma)=-1. We then have

- \langle \chi_\rho,\chi_\iota \rangle = \chi_\rho(\sigma) \sum\limits_{\pi \in \mathrm{B}(k)} \chi_\rho(\pi) = \sum\limits_{\pi \in \mathrm{B}(k)} \chi_\rho(\sigma\pi) = \langle \chi_\rho,\chi_\iota \rangle,

whence \langle \chi_\rho,\chi_\iota \rangle=0.

— Q.E.D.

Problem 7.3: Prove the dual orthogonality relation

\sum\limits_{\pi \in \mathrm{B}(k)} \chi_\pi(\rho)\chi_\pi(\sigma)= 2^k[\rho=\sigma].

In Lecture 8, we will link the characters of \mathrm{B}(k) to the adjacency operator of its Cayley graph.

Leave a Reply