Contents

group theory

# Contents

## 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

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

1. 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} } }$
2. 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

###### 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

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]$

## References

Textbook accounts:

See also:

• Richard G.E. Pinch, The distance of a permutation from a subgroup of $S_n$ (arXiv:math/0511501)

• Thaynara Arielly de Lima; Mauricio Ayala-Rincón, Complexity of Cayley distance and other general metrics on permutation groups (doi:10.1109/ColombianCC.2012.6398020, pdf)

Discussion of characters for the symmetric group that depend only on Cayley distance from the neutral element (“block character”):

Discussion of the Cayley distance kernel:

Last revised on May 8, 2021 at 08:34:17. See the history of this page for a list of all contributions to it.