nLab Cayley graph of Sym(3)

Idea

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

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

$$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)$, 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)$ as

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

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

(1)$$[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)$$\big[ e^{- \lambda \cdot d_C} \big] \;\in\; Mat_{6 \times 6}(\mathbb{R})$$

for the Cayley distance kernel on $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)

$$\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\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 $\mathbb{R}[Sym(3)]$ is:

(3)$$\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 $\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:

• geometric group theory

• Cayley graph

• Cayley distance

• Cayley distance kernel