Difference between revisions of "Symmetric group"

Latest revision as of 12:21, 30 November 2016

Note: the symmetric group is a permutation group on finitely many symbols, see permutation group (which uses the same notation) for the more general case.

Definition

Let $k\in\mathbb{N}$ be given. The symmetric group on $k$ symbols, denoted $S_k$, is the permutation group on $\{1,2,\ldots,k-1,k\}\subset\mathbb{N}$. The set of the group is the set of all permutations on $\{1,2,\ldots,k-1,k\}$. See proof that the symmetric group is actually a group for details.

• Identity element: $e:\{1,\ldots,k\}\rightarrow\{1,\ldots,k\}$ which acts as so: $e:i\mapsto i$ - this is the identity permutation, it does nothing.
• The group operation is ordinary function composition, for $\sigma,\tau\in S_k$ we define:
  • $\sigma\tau:\eq \sigma\circ\tau$ with: $\sigma\tau:\{1,\ldots,k\}\rightarrow\{1,\ldots,k\}$ by $\sigma\tau:i\mapsto\sigma(\tau(i))$
    • Caveat:Be careful, a lot of authors (Allenby, McCoy to name 2) go left-to-right and write $i\sigma$ for what we'd use $\sigma(i)$ or $\sigma i$ at a push for. Then $\sigma\tau$ would be $\tau\circ\sigma$ in our notation

Permutation notation

The "base" way to write a permutation, $\sigma\in S_k$, is as a table:

• $$\left(\begin{array}{ccccc}1 & 2 & \cdots & k-1 & k\\ \sigma(1) & \sigma(2) & \cdots & \sigma(k-1) & \sigma(k)\end{array}\right)$$

The top row is an element of the domain of $\sigma$ considered as a function and thing below it is the image of that element under $\sigma$

This notation quickly becomes heavy so we switch to cycle notation, which we demonstrate below.

Note, however, that in order to use cycle notation we require the following:

• Every element of the symmetric group, if not a cycle itself, can be expressed as a product of disjoint cycles

Example

Let us consider $S_5$ as an example.

• Let $\sigma\in S_5$ be the permutation given as follows:
  • $\sigma:1\mapsto 3$, $\sigma:2\mapsto 2$, $\sigma:3\mapsto 5$, $\sigma:4\mapsto 1$, $\sigma:5\mapsto 4$

  This can be written more neatly as:

  • $$\left(\begin{array}{ccccc}1 & 2 & 3 & 4 & 5 \\ 3 & 2 & 5 & 1 & 4\end{array}\right)$$ , the thing in the top row is sent to the thing below it.
    • This can be written as the product of disjoint cycles too:
      • $$(1\ 3\ 5\ 4)$$ or $(1\ 3\ 5\ 4)(2)$ if you do not take the "implicit identity" part. That is any element not in a cycle stays the same
    • Or as transpositions
      • $$(1\ 4)(1\ 5)(1\ 3)$$ - recall we read right-to-left, so this is read:
        • $1\mapsto 3\mapsto 3\mapsto 3$
        • $3\mapsto 1\mapsto 5\mapsto 5$
        • $5\mapsto 5\mapsto 1\mapsto 4$
        • $4\mapsto 4\mapsto 4\mapsto 1$ - the cycle $(1\ 3\ 5\ 4)$
        • And of course $2\mapsto 2\mapsto 2\mapsto 2$

See Cycle notation (group theory) for more information.

See also

• Cycle notation
  • Every element of the symmetric group, if not a cycle itself, can be expressed as a product of disjoint cycles
  • Transposition - a $2$-cycle.
    • Every element of the symmetric group can be written as an even or odd number of transpositions, but not both

References