nLab Cayley graph of Sym(3)

Redirected from "Cayley distance on Sym(3)".
Contents

Contents

Idea

This page shows the Cayley graph of the symmetric group on 33 elements, Sym(3)Sym(3) and makes explicit some of its properties.

In all of the following we abbreviate permutations of 3 elements as

ijk(1 2 3 i j k). i j k \;\coloneqq\; \left( \array{ 1 & 2 & 3 \\ i & j & k } \right) \,.

Definition

The following shows the Cayley graph of the symmetric groups on 3 elements, Sym(3)Sym(3), with edges corresponding to any transposition (not necessarily adjacent), hence whose graph distance is the Cayley distance:

Properties

Cayley distance

If we order the 6 elements of Sym(3)Sym(3) as

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

then the Cayley distance, 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

(1)[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]

Cayley distance kernel

For λ +\lambda \in \mathbb{R}_+, write

(2)[e λd C]Mat 6×6() \big[ e^{- \lambda \cdot d_C} \big] \;\in\; Mat_{6 \times 6}(\mathbb{R})

for the Cayley distance kernel on Sym(3)Sym(3), hence the matrix which is the exponential of the Cayley distance-matrix (1) multiplied by λ- \lambda.

The eigenvalues of this matrix are (from here)

e 2λ1e 2λ,e 2λ±3e λ+2e 2λ, \frac { e^ {2\lambda} -1 } {e^ {2\lambda}} \,,\;\;\; \frac { e^{2\lambda} \pm 3 e^{\lambda} + 2 } {e^{2\lambda}} \,,

where the first one appears with multiplicity 4 and is positive since λ\lambda is positive. The only eigenvalue that can become non-positive for λ +\lambda \in \mathbb{R}_+ is:

e 2λ3e λ+2is{<0 | λ<ln(2) =0 | λ=ln(2) >0 | λ>ln(2) e^{2\lambda} - 3 e^\lambda + 2 \;\;is\;\; \left\{ \array{ \lt 0 &\vert& \lambda \lt ln(2) \\ = 0 &\vert& \lambda = ln(2) \\ \gt 0 &\vert& \lambda \gt ln(2) } \right.

In conclusion:

The Cayley distance kernel (2), regarded as a bilinear form on the linear span [Sym(3)]\mathbb{R}[Sym(3)] is:

(3)indefinite for λ<ln(2) positive semi-definite for λ=ln(2) positive definite for λ>ln(2) \array{ \text{indefinite} & \text{for} & \lambda \lt ln(2) \\ \text{positive semi-definite} &\text{for}& \lambda = ln(2) \\ \text{positive definite} &\text{for}& \lambda \gt ln(2) }

Remark

(relation to weight systems on horizontal chord diagrams)
Incidentally, the critical value λ=ln(2)\lambda = ln(2) in (3) is that corresponding to the fundamental sl(2,C)-Lie algebra weight systems on horizontal chord diagrams (under the canonical identification of the latter with permutations and using Cayley’s observation to express Cayley distance in terms of numbers of permutation cycles), see CSS21.

References

See the references at:

Last revised on April 21, 2021 at 08:57:13. See the history of this page for a list of all contributions to it.