nLab Cayley graph of Sym(3)

Contents

Context

Group Theory

group theory

Classical groups

Finite groups

Group schemes

Topological groups

Lie groups

Super-Lie groups

Higher groups

Cohomology and Extensions

Related concepts

Contents

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:

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