nLab Cayley distance

Contents

Context

Group Theory

Idea
Definition
Properties
Examples
Related concepts
References

Idea

The Cayley distance between two permutations is the minimum number of transpositions of elements needed to turn one into the other.

(This is in contrast to the Kendall distance which counts the minimum number of transpositions of adjacent pairs of elements.)

Definition

(Cayley distance) For $n \in \mathbb{N}$ consider the symmetric group $Sym(n)$ with its structure as a finitely generated group exhibited by the finite set of generators given by all transposition permutations

Gen \;\coloneqq\; \big\{ \sigma_{i,j} \,\vert\, 1 \leq i, j \lt n \big\} \;\subset\; Sym(n) \,.

Then the Cayley distance (e.g Diaconis 88, p. 112) is the distance on $Sym(n)$ which is the graph distance of the corresponding Cayley graph, hence the function

d_C(-,-) \;\colon\; Sym(n) \times Sym(n) \longrightarrow \mathbb{N} \hookrightarrow \mathbb{R}

which sends any pair of permutations $\sigma_1, \sigma_2 \in Sym(n)$ to the minimum number $d(\sigma_1, \sigma_2) \in \mathbb{N}$ of transpositions $\sigma_{i_1, j_1}, \sigma_{i_2, j_2}, \cdots, \sigma_{i_d, j_d}$ such that

\sigma_2 \;=\; \sigma_{i_d, j_d} \circ \cdots \circ \sigma_{i_2, j_2} \circ \sigma_{i_1, j_1} \circ \sigma_1 \,.

Properties

Proposition

(Cayley metric is right invariant) The Cayley metric is an right invariant metric in that for all $\sigma \in Sym(n)$ we have

\sigma^\ast d_C(-,-) \;\coloneqq\; d_C \big( (-) \circ \sigma ,\, (-) \circ \sigma \big) \;=\; d_C \big( - ,\, - \big) \,.

Proof

This is immediate from the definition.

Proposition

(Cayley’s formula) The Cayley distance (Def. ) between $\sigma_1, \sigma_2 \,\in\, Sym(n)$ equals $n$ minus the number of permutation cycles in $\sigma_1 \circ \sigma_2^{-1}$ :

d_C(\sigma_1, \sigma_2) \;=\; n - \left\vert Cycles \big( \sigma_1 \circ \sigma_2^{-1} \big) \right\vert \,.

(e.g. Diaconis 88, p. 118)

Proof

By right invariance (Prop. ) it is sufficient to see the statement for the case that $\sigma_2 = e$ is the neutral element of $Sym(n)$ , hence the identity permutation.

Here we need to see that for $\sigma = \sigma_1$ any permutation, the minimum number of transpositions whose product yields $\sigma$ equals $n$ minus the number of cycles in $\sigma$ .

Now observe that:

a cyclic permutation of $k$ elements is the composite of no less than $k-1$ transpositions:

(1) $\left( \array{ 1 & 2 & 3 & \cdots & k \\ k & 1 & 2 & \cdots & k-1 } \right) \;=\; \underset{ k-1 \; factors }{ \underbrace{ \sigma_{k-1,k-2} \circ \cdots \circ \sigma_{3,2} \circ \sigma_{2,1} \circ \sigma_{1,k} } }$
Any $\sigma$ is the product of elements of the form (1), one for each of its permutation cycles.

Since it is $k-1$ transposition factors in (1) for cycles of $k$ elements, each cycle reduces the number of transposition needed by one.

Proposition

Cayley distance is preserved under the canonical inclusions of symmetric groups

(2)

Sym(n) \overset{ i }{ \hookrightarrow } Sym(n+1) \hookrightarrow Sym(n+2) \hookrightarrow \cdots

in that

d_C( \sigma_1, \sigma_2 ) \; = \; d_C\big( i(\sigma_1), i(\sigma_2) \big) \,.

In other words, when regarding the metric space given by the set of permutations in $Sym(n)$ with their Cayley distance function between them

as an $(\mathbb{R}_{\geq 0}, \geq)$ 0-enriched category (see here), then the functors induced by the inclusions (2) are fully faithful and hence are full subcategory inclusions.
as a matrix, then the inclusions (2) correspond to principal submatrices.

Proof

Observing that

\left\vert Cycles \big( i(\sigma_1) \circ i(\sigma_2)^{-1} \big) \right\vert \;=\; \left\vert Cycles \big( \sigma_1 \circ \sigma_2^{-1} \big) \right\vert \;+\; 1

the claim follows by Cayley’s formula (Prop. ).

Examples

Example

(Cayley distance on Sym(3))

The Cayley graph of the symmetric groups on 3 elements, $Sym(3)$ , with edges corresponding to any transposition (not necessarily adjacent) looks like this:

from which one readily reads off the Cayley distance: Ordering the 6 permutations as

\vec \sigma \;\coloneqq\; \left[ \array{ 123 \\ 213 \\ 132 \\ 321 \\ 312 \\ 231 } \right]

the Cayley distance on $Sym(3)$ , regarded as a $6 \times 6$ matrix

[d_C] \;\coloneqq\; \big( d_C \big( \sigma_i, \sigma_j \big) \big)_{i,j} \;\in\; Mat_{6 \times 6}(\mathbb{N})

is this:

[d_C] \;=\; \left[ \array{ 0 & 1 & 1 & 1 & 2 & 2 \\ 1 & 0 & 2 & 2 & 1 & 1 \\ 1 & 2 & 0 & 2 & 1 & 1 \\ 1 & 2 & 2 & 0 & 1 & 1 \\ 2 & 1 & 1 & 1 & 0 & 2 \\ 2 & 1 & 1 & 1 & 2 & 0 } \right]

Related concepts

References

Textbook accounts:

Persi Diaconis, Chapter 6B of: Group Representations in Probability and Statistics, IMS Lecture Notes Monogr. Ser., 11: 198pp. (1988) (jstor:i397389, ISBN: 0940600145, pdf)