nLab
Cayley distance

Contents

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 nn \in \mathbb{N} consider the symmetric group Sym(n)Sym(n) with its structure as a finitely generated group exhibited by the finite set of generators given by all transposition permutations

Gen{σ i,j|1i,j<n}Sym(n). 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)Sym(n) which is the graph distance of the corresponding Cayley graph, hence the function

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

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

σ 2=σ i d,j dσ i 2,j 2σ i 1,j 1σ 1. \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 σSym(n)\sigma \in Sym(n) we have

σ *d C(,)d C(()σ,()σ)=d C(,). \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 σ 1,σ 2Sym(n)\sigma_1, \sigma_2 \,\in\, Sym(n) equals nn minus the number of permutation cycles in σ 1σ 2 1\sigma_1 \circ \sigma_2^{-1}:

d C(σ 1,σ 2)=n|Cycles(σ 1σ 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 σ 2=e\sigma_2 = e is the neutral element of Sym(n)Sym(n), hence the identity permutation.

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

Now observe that:

  1. a cyclic permutation of kk elements is the composite of no less than k1k-1 transpositions:

    (1)(1 2 3 k k 1 2 k1)=σ k1,k2σ 3,2σ 2,1σ 1,kk1factors \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 k1k-1 transposition factors in (1) for cycles of kk 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)iSym(n+1)Sym(n+2) Sym(n) \overset{ i }{ \hookrightarrow } Sym(n+1) \hookrightarrow Sym(n+2) \hookrightarrow \cdots

in that

d C(σ 1,σ 2)=d C(i(σ 1),i(σ 2)). 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)Sym(n) with their Cayley distance function between them

Proof

Observing that

|Cycles(i(σ 1)i(σ 2) 1)|=|Cycles(σ 1σ 2 1)|+1 \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)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

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

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

[d C](d C(σ i,σ j)) i,jMat 6×6() [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]=[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] [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:

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.