Difference between revisions of "Symmetric group"
(Created page with "{{Stub page|grade=A*|msg=Demote to grade D once fleshed out and referenced}} __TOC__ : '''Note: ''' the ''symmetric group'' is a ''permutation group'' on finitely many sym...") |
m (Adding example) |
||
(One intermediate revision by the same user not shown) | |||
Line 8: | Line 8: | ||
** {{M|\sigma\tau:\eq \sigma\circ\tau}} with: {{M|\sigma\tau:\{1,\ldots,k\}\rightarrow\{1,\ldots,k\} }} by {{M|\sigma\tau:i\mapsto\sigma(\tau(i))}} | ** {{M|\sigma\tau:\eq \sigma\circ\tau}} with: {{M|\sigma\tau:\{1,\ldots,k\}\rightarrow\{1,\ldots,k\} }} by {{M|\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 {{M|i\sigma}} for what we'd use {{M|\sigma(i)}} or {{M|\sigma i}} at a push for. Then {{M|\sigma\tau}} would be {{M|\tau\circ\sigma}} in our notation}} | *** {{Caveat|Be careful, a lot of authors (Allenby, McCoy to name 2) go left-to-right and write {{M|i\sigma}} for what we'd use {{M|\sigma(i)}} or {{M|\sigma i}} at a push for. Then {{M|\sigma\tau}} would be {{M|\tau\circ\sigma}} in our notation}} | ||
+ | ==Permutation notation== | ||
+ | The "base" way to write a permutation, {{M|\sigma\in S_k}}, is as a table: | ||
+ | * {{MM|1=\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 {{M|\sigma}} considered as a [[function]] and thing below it is the image of that element under {{M|\sigma}} | ||
+ | |||
+ | |||
+ | This notation quickly becomes heavy so we switch to {{link|cycle notation|group theory}}, 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:Permutation (group theory) of S5|Example]]=== | ||
+ | {{:Example:Permutation (group theory) of S5/Body}} | ||
+ | See [[Cycle notation (group theory)]] for more information. | ||
==See also== | ==See also== | ||
− | * {{Cycle notation|(group theory)}} | + | * {{link|Cycle notation|(group theory)}} |
− | ** [[Every element of the symmetric group can be | + | ** [[Every element of the symmetric group, if not a cycle itself, can be expressed as a product of disjoint cycles]] |
** {{link|Transposition|group theory}} - a {{M|2}}-cycle. | ** {{link|Transposition|group theory}} - a {{M|2}}-cycle. | ||
*** [[Every element of the symmetric group can be written as an even or odd number of transpositions, but not both]] | *** [[Every element of the symmetric group can be written as an even or odd number of transpositions, but not both]] | ||
+ | |||
==References== | ==References== | ||
<references/> | <references/> | ||
{{Group theory navbox|plain}} | {{Group theory navbox|plain}} | ||
{{Definition|Group Theory|Abstract Algebra}} | {{Definition|Group Theory|Abstract Algebra}} |
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 [ilmath]k\in\mathbb{N} [/ilmath] be given. The symmetric group on [ilmath]k[/ilmath] symbols, denoted [ilmath]S_k[/ilmath], is the permutation group on [ilmath]\{1,2,\ldots,k-1,k\}\subset\mathbb{N} [/ilmath]. The set of the group is the set of all permutations on [ilmath]\{1,2,\ldots,k-1,k\} [/ilmath]. See proof that the symmetric group is actually a group for details.
- Identity element: [ilmath]e:\{1,\ldots,k\}\rightarrow\{1,\ldots,k\} [/ilmath] which acts as so: [ilmath]e:i\mapsto i[/ilmath] - this is the identity permutation, it does nothing.
- The group operation is ordinary function composition, for [ilmath]\sigma,\tau\in S_k[/ilmath] we define:
- [ilmath]\sigma\tau:\eq \sigma\circ\tau[/ilmath] with: [ilmath]\sigma\tau:\{1,\ldots,k\}\rightarrow\{1,\ldots,k\} [/ilmath] by [ilmath]\sigma\tau:i\mapsto\sigma(\tau(i))[/ilmath]
- Caveat:Be careful, a lot of authors (Allenby, McCoy to name 2) go left-to-right and write [ilmath]i\sigma[/ilmath] for what we'd use [ilmath]\sigma(i)[/ilmath] or [ilmath]\sigma i[/ilmath] at a push for. Then [ilmath]\sigma\tau[/ilmath] would be [ilmath]\tau\circ\sigma[/ilmath] in our notation
- [ilmath]\sigma\tau:\eq \sigma\circ\tau[/ilmath] with: [ilmath]\sigma\tau:\{1,\ldots,k\}\rightarrow\{1,\ldots,k\} [/ilmath] by [ilmath]\sigma\tau:i\mapsto\sigma(\tau(i))[/ilmath]
Permutation notation
The "base" way to write a permutation, [ilmath]\sigma\in S_k[/ilmath], is as a table:
- [math]\left(\begin{array}{ccccc}1 & 2 & \cdots & k-1 & k\\ \sigma(1) & \sigma(2) & \cdots & \sigma(k-1) & \sigma(k)\end{array}\right)[/math]
The top row is an element of the domain of [ilmath]\sigma[/ilmath] considered as a function and thing below it is the image of that element under [ilmath]\sigma[/ilmath]
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:
Example
Let us consider [ilmath]S_5[/ilmath] as an example.
- Let [ilmath]\sigma\in S_5[/ilmath] be the permutation given as follows:
- [ilmath]\sigma:1\mapsto 3[/ilmath], [ilmath]\sigma:2\mapsto 2[/ilmath], [ilmath]\sigma:3\mapsto 5[/ilmath], [ilmath]\sigma:4\mapsto 1[/ilmath], [ilmath]\sigma:5\mapsto 4[/ilmath]
- This can be written more neatly as:
- [math]\left(\begin{array}{ccccc}1 & 2 & 3 & 4 & 5 \\ 3 & 2 & 5 & 1 & 4\end{array}\right)[/math], the thing in the top row is sent to the thing below it.
- This can be written as the product of disjoint cycles too:
- [math](1\ 3\ 5\ 4)[/math] or [ilmath](1\ 3\ 5\ 4)(2)[/ilmath] if you do not take the "implicit identity" part. That is any element not in a cycle stays the same
- Or as transpositions
- [math](1\ 4)(1\ 5)(1\ 3)[/math] - recall we read right-to-left, so this is read:
- [ilmath]1\mapsto 3\mapsto 3\mapsto 3[/ilmath]
- [ilmath]3\mapsto 1\mapsto 5\mapsto 5[/ilmath]
- [ilmath]5\mapsto 5\mapsto 1\mapsto 4[/ilmath]
- [ilmath]4\mapsto 4\mapsto 4\mapsto 1[/ilmath] - the cycle [ilmath](1\ 3\ 5\ 4)[/ilmath]
- And of course [ilmath]2\mapsto 2\mapsto 2\mapsto 2[/ilmath]
- [math](1\ 4)(1\ 5)(1\ 3)[/math] - recall we read right-to-left, so this is read:
- This can be written as the product of disjoint cycles too:
See Cycle notation (group theory) for more information.
See also
References
|