nLab
permutation

Contents

Idea

A permutation is an automorphism in Set. More explicitly, a permutation of a set XX is an invertible function from XX to itself.

Definition

The group of permutations of XX (that is the automorphism group of XX in SetSet) is the symmetric group (or permutation group) on XX. This group may be denoted S XS_X, Σ X\Sigma_X, or X!X!. When XX is the finite set [n][n] with nn elements, then its symmetric group is a finite group, and one typically writes S nS_n or Σ n\Sigma_n; note that this group has n!n! elements.

In combinatorics, one often wants a slight generalisation. Given a natural number rr, an rr-permutation of XX is an injective function from [r][r] to XX, that is a list of rr distinct elements of XX. Note that the number of rr-permutations of [n][n] is counted by the falling factorial n(n1)(nr+1)n(n-1)\dots(n-r+1). Then an nn-permutation of [n][n] is the same as a permutation of [n][n], and the total number of such permutations is of course counted by the ordinary factorial n!n!. (That an injective function from XX to itself must be invertible characterises XX as a Dedekind-finite set.)

Concrete representations

Via string diagrams

Via cycle decompositions

Every permutation π:XX\pi : X \to X generates a cyclic subgroup π\langle \pi \rangle of the symmetric group S XS_X, and hence inherits a group action on XX. The orbits of this action partition the set XX into a disjoint union of cycles, called the cyclic decomposition of the permutation π\pi.

For example, let π\pi be the permutation on [6]={0,,5}[6] = \{0,\dots,5\} defined by

π=00 13 24 35 42 51\pi = \array{0 \mapsto 0 \\ 1 \mapsto 3 \\ 2 \mapsto 4 \\ 3 \mapsto 5 \\ 4 \mapsto 2 \\ 5 \mapsto 1}

The domain of the permutation is partitioned into three π\langle\pi\rangle-orbits

[6]={0}{1,3,5}{2,4}[6] = \{0\} \cup \{1,3,5\} \cup \{2,4\}

corresponding to the three cycles

0π01π3π5π12π4π20 \underset{\pi}{\to} 0 \qquad 1 \underset{\pi}{\to} 3 \underset{\pi}{\to} 5 \underset{\pi}{\to} 1 \qquad 2 \underset{\pi}{\to} 4 \underset{\pi}{\to} 2

Finally, we can express this more compactly by writing π\pi in cycle form, as the product π=(0)(135)(24)\pi = (0)(1\,3\,5)(2\,4).

Properties

Relation to the field with one element

One may regard the symmetric group S nS_n as the general linear group in dimension nn on the field with one element GL(n,𝔽 1)GL(n,\mathbb{F}_1).

Whitehead tower and relation to supersymmetry

The symmetric groups and alternating groups are the first stages in a restriction of the Whitehead tower of the orthogonal group to “finite discrete ∞-groups” in the sense of homotopy type with finite homotopy groups. The homotopy fibers of the stages of the “finite Whitehead tower” are the stable homotopy groups of spheres (Epa-Ganter 16). (See also at super algebra – Abstract idea.)

BFivebrane(n) B 2π 3𝕊 B𝒜 n BString(n) Bπ 2𝕊 BA˜ n BSpin(n) π 1𝕊 BA n BSO(n) BS n BO(n) \array{ && && \vdots \\ && && \downarrow \\ && && \mathbf{B}Fivebrane(n) \\ && \downarrow && \downarrow \\ \mathbf{B}^2 \pi_3 \mathbb{S} &\stackrel{}{\longrightarrow} & \mathbf{B}\mathcal{A}_n &\hookrightarrow& \mathbf{B} String(n) \\ && \downarrow && \downarrow \\ \mathbf{B} \pi_2 \mathbb{S} &\longrightarrow & \mathbf{B} \tilde A_n &\hookrightarrow& \mathbf{B} Spin(n) \\ && \downarrow && \downarrow \\ \pi_1 \mathbb{S} &\longrightarrow& \mathbf{B} A_n &\hookrightarrow& \mathbf{B} SO(n) \\ && \downarrow && \downarrow \\ && \mathbf{B} S_n &\hookrightarrow& \mathbf{B} O(n) }

Notice that the squares on the right are not homotopy pullback squares. (The homotopy pullback of the string 2-group along A˜Spin(n)\tilde A \hookrightarrow Spin(n) is a BU(1)\mathbf{B}U(1)-extension of A˜\tilde A, but here we get the universal finite 2-group extension, by /24\mathbb{Z}/24 instead.

Examples

References

Revised on June 25, 2016 23:44:58 by Mike Shulman (76.167.222.204)