nLab
symmetric group

Contents

Contents

Idea

The permutations of a set XX form a group, S XS_X, under composition. This is especially clear if one thinks of the permutation as a bijection on XX, where the multiplication / composition is just composition of functions. This group is called the symmetric group of XX and often denoted S XS_X, Σ X\Sigma_X, Sym(X)Sym(X) or similar.

The subgroups of symmetric groups are the permutation groups.

When XX is the finite set (n)={1,,n}(n) = \{1,\dots,n\}, then its symmetric group is a finite group of cardinality n!n! = “nn factorial”, and one typically writes S nS_n or Σ n\Sigma_n.

(We will make frequent use of the entry permutation for some key notation and concepts.)

Examples

The symmetric group S 3S_3

S 3S_3 is the group of permutations of (3)={1,2,3}(3)=\{1,2,3\}.

One simple way to represent an element of S 3S_3 is by listing the (3)(3) on the top row of an array with a second row denoting the image of each element under the permutation. For instance, the element sigma=(12,21,33)sigma= (1\mapsto 2, 2\mapsto 1, 3\mapsto 3) can be written more compactly as

σ=(1 2 3 2 1 3).\sigma= \left(\array{1&2&3\\2&1&3}\right).

We can also use, even more compactly, ‘cycle notation’, as explained in more detail at permutation, in which successive images under the permutation, σ\sigma, are listed until you get back to where you started. Elements of (3), or more generally of (n), are usually not listed as cycles of length 1, exept that (1) may be used too indicate the identity element. For the above permutation, this gives

σ=(12)\sigma = (1\,2)

the transposition exchanging the elements 1 and 2 and leaving 3 ‘unmoved’. Whilst the 3-cycle, (123)(1\,2\,3), shifts every element to the right one position and then maps 3 to 1.

In general, an element of S nS_n can be represented by a two row array

σ=(1 2 n σ(1) σ(2) σ(n)).\sigma= \left(\array{1&2&\ldots &n\\\sigma(1)&\sigma(2)&\ldots&\sigma(n)}\right).

It can also be given in cycle notation. We repeat the example from the entry on permutations. This is from S 6S_6:

Let σ\sigma be the permutation on (6)(6) defined by

σ=(11 24 35 46 53 62)=(1 2 3 4 5 6 1 4 5 6 3 2)\sigma = (\array{1 \mapsto 1 & 2\mapsto 4 & 3 \mapsto 5 & 4 \mapsto 6 & 5 \mapsto 3 & 6 \mapsto 2})= \left(\array{1&2&3&4&5&6\\1&4&5&6&3&2}\right)

The domain of the permutation is partitioned into three σ\langle\sigma\rangle-orbits

(6)={1}{2,4,6}{3,5}(6) = \{1\} \cup \{2,4,6\} \cup \{3,5\}

corresponding to the three cycles

1σ12σ4σ6σ23σ5σ31 \underset{\sigma}{\to} 1 \qquad 2 \underset{\sigma}{\to} 4 \underset{\sigma}{\to} 6 \underset{\sigma}{\to} 2 \qquad 3 \underset{\sigma}{\to} 5 \underset{\sigma}{\to} 3

We express this more compactly by writing σ\sigma as the composition σ=(1)(246)(35)\sigma = (1)(2\,4\,6)(3\,5), or σ=(246)(35)\sigma = (2\,4\,6)(3\,5) leaving implicit the action of the identity (1).

We can also write σ\sigma as a product of transpositions

(24)(26)(35)(2\,4)(2\,6)(3\,5)

The symmetric group S 4S_4

The symmetric group on 4 elements is isomorphic to the full tetrahedral group as well as to the orientation-preserving octahedral group.

Properties

Cycle decomposition

As an element of the symmetric group S XS_X, every permutation σ:XX\sigma : X \to X generates a cyclic subgroup σ\langle \sigma \rangle, 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 σ\sigma.

For example, let σ\sigma be the permutation on (6)(6) defined by

σ=(11 24 35 46 53 62)\sigma = (\array{1 \mapsto 1 & 2 \mapsto 4 & 3 \mapsto 5 & 4 \mapsto 6 & 5 \mapsto 3 & 6 \mapsto 2})

The domain of the permutation is partitioned into three σ\langle\sigma\rangle-orbits

(6)={1}{2,4,6}{3,5}(6) = \{1\} \cup \{2,4,6\} \cup \{3,5\}

corresponding to the three cycles

1σ12σ4σ6σ23σ5σ31 \underset{\sigma}{\to} 1 \qquad 2 \underset{\sigma}{\to} 4 \underset{\sigma}{\to} 6 \underset{\sigma}{\to} 2 \qquad 3 \underset{\sigma}{\to} 5 \underset{\sigma}{\to} 3

We can express this more compactly by writing σ\sigma in “cycle notation”, as the composition σ=(1)(246)(35)\sigma = (1)(2\,4\,6)(3\,5), or σ=(246)(35)\sigma = (2\,4\,6)(3\,5) leaving implicit the action of the identity (1).

Even in the simple example of S 3S_3 one can see some patterns.

  • (12)(12) clearly has order 2, whilst (123)(123) has square (132)(132), which is also the inverse of (123)(123), and has order 3.

  • (123)=(12)(13)(123) = (12)(13), so transpositions generate the whole group.

This gives a listing of the elements of S 3S_3 as

{1,(12),(13),(23),(123),(132)}.\{ 1, (12),(13),(23),(123),(132)\}.
a,b|a 3,b 2,(ab) 2.\langle a,b | a^3, b^2,(a b)^2 \rangle.

where aa corresponds to the 3-cycle, (123)(123), whilst bb corresponds to any transposition. It also has a presentation in which the generators correspond to the transpositions:

σ 1,σ 2|σ 1 2,σ 2 2,(σ 1σ 2) 3\langle \sigma_1,\sigma_2 | \sigma_1^2,\sigma_2^2, (\sigma_1\sigma_2)^3\rangle

It is easy to see that these relations imply that

σ 1σ 2σ 1=σ 2σ 1σ 2\sigma_1\sigma_2\sigma_1= \sigma_2\sigma_1\sigma_2

which relates this symmetric group to the braid group, Br 3, and to the trefoil group. It is clear that there is an epimorphism S 3Br 3S_3\to Br_3 obtained by making the two braid generators become the transpositions.

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).

See there.

Conjugacy classes

Proposition

Let nn \in \mathbb{N} and Σ(n)\Sigma(n) the symmetric group on nn elements. Then the conjugacy classes of elements of Σ(n)\Sigma(n), hence of permutations of nn elements, correspond to the cycle structures: two elements are conjugate to each other precisely if they have the same number of distinct cycles of the same length, or in other words if they define the same underlying partition of nn.

Example

For the symmetric group on three elements there are three such classes:

(1 2 3) ~ (1 3 2)
(1 2)(3) ~ (1 3)(2) ~ (1)(2 3)
(1)(2)(3)
Young diagram (3) Layer 1
Young diagram (2,1) Layer 1
Young diagram (1,1,1) Layer 1

\,

\,

\,

\,

\,

\,

\,

Classifying space and universal Thom space

The classifying space BΣ(n)B \Sigma(n) of the symmetric group on nn elements may be presented by Emb({1,,n}, )/Σ(n)Emb(\{1,\cdots, n\}, \mathbb{R}^\infty)/\Sigma(n), the Fadell's configuration space on nn unordered points in \mathbb{R}^\infty.

(e.g. Bödigheimer 87, Example 10)

Write τ n\tau_n for the rank nn vector bundle over this which exhibits the canonical action of Σ(n)\Sigma(n) on n\mathbb{R}^n, by permutation of coordinates.

The Thom space BΣ(n) τ nB \Sigma(n)^{\tau_n} of this bundle appears as the cofficients of the spectral symmetric algebra of the “absolute spectral superpointSym 𝕊Σ𝕊Sym_{\mathbb{S}} \Sigma \mathbb{S} (see Rezk 10, slide 4).

See also (Hopkins-Mahowald-Sadofsky 94, around def. 2.8)

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 and at Platonic 2-group.)

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.

References

Textbook accounts include

Discussion of the classifying spaces of symetric groups includes

See also

For the operadic structure of permutations, see Volume 1, Chapter 1 of:

For more on permutation patterns, see:

Last revised on December 31, 2018 at 06:03:22. See the history of this page for a list of all contributions to it.