Symmetric group: Difference between revisions
imported>David Lee Harden (created "Symmetric group" article and wrote about cycles and parity) |
imported>David Lee Harden (→Deeper Notes: Orbits and Blocks: added an introduction to (im)primitivity and blocks) |
||
(11 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
{{subpages}} | |||
In [[mathematics]], the '''symmetric group''' is the [[group (mathematics)|group]] of all [[permutation]]s of a set, that is, of all [[invertible function]]s from a set to itself. It is a central object of study in [[group theory]]. | |||
== Definition == | == Definition == | ||
If <math>n</math> is a positive integer, the symmetric group on <math>n</math> "letters" (often denoted <math>S_{n}</math>) is the group formed by all [[bijection]]s from a set <math>S</math> to itself (under the operation of [[function composition]]), where <math>S</math> is an <math>n</math>-element set. It is customary to take <math>S</math> to be the set of integers from <math>1</math> to <math>n</math>, but this is not strictly necessary. The bijections which are elements of the symmetric group are called ''permutations''. | |||
Note that this means the [[identity element]] of the group is the [[identity map]] on <math>S</math>, which is the map sending each element of <math>S</math> to itself. | |||
Note that this means the identity of the group is the identity map on <math>S</math>, which is the map sending each element of <math>S</math> to itself. | |||
The order of <math>S_{n}</math> is <math>n!</math>. | The [[order (group theory)|order]] of <math>S_{n}</math> is given by the [[factorial]] function <math>n!</math>. | ||
== Cycle Decomposition == | == Cycle Decomposition == | ||
Line 11: | Line 13: | ||
Any permutation of a finite set can be written as a product of permutations called ''cycles''. A cycle <math>\rho</math> acting on <math>S</math> fixes all the elements of S outside a nonempty subset <math>C</math> of <math>S</math>. On <math>C</math>, the action of <math>\rho</math> is as follows: for some indexing <math> C = \{ c_{1}, \ldots, c_{k} \} </math> of the elements of <math>C</math>, <math>\rho</math> sends <math>c_{i}</math> to <math>c_{i+1}</math> for all <math>1 \leq i \leq k-1</math> and sends <math>c_{k}</math> to <math>c_{1}</math>. Then one writes | Any permutation of a finite set can be written as a product of permutations called ''cycles''. A cycle <math>\rho</math> acting on <math>S</math> fixes all the elements of S outside a nonempty subset <math>C</math> of <math>S</math>. On <math>C</math>, the action of <math>\rho</math> is as follows: for some indexing <math> C = \{ c_{1}, \ldots, c_{k} \} </math> of the elements of <math>C</math>, <math>\rho</math> sends <math>c_{i}</math> to <math>c_{i+1}</math> for all <math>1 \leq i \leq k-1</math> and sends <math>c_{k}</math> to <math>c_{1}</math>. Then one writes | ||
:<math> \rho = (c_{1}, \ldots, c_{k})</math> | :<math> \rho = \left(c_{1}, \ldots, c_{k}\right)</math> | ||
(Sometimes the commas are omitted.) If k > 1, such a <math>\rho</math> is called a ''k-cycle''. | (Sometimes the commas are omitted.) If k > 1, such a <math>\rho</math> is called a ''k-cycle''. | ||
Line 17: | Line 19: | ||
If <math>C</math> is a one-element set, then its element is a ''fixed point'' of the permutation. Fixed points are often omitted from permutations written in cycle notation, since any <math>\rho</math> cycling the elements of <math>C</math> as discussed above would be the identity permutation. | If <math>C</math> is a one-element set, then its element is a ''fixed point'' of the permutation. Fixed points are often omitted from permutations written in cycle notation, since any <math>\rho</math> cycling the elements of <math>C</math> as discussed above would be the identity permutation. | ||
The ''cycle shape'' of an element is the list of cycle lengths written in decreasing order. | |||
The [[order (group theory)|order]] of a permutation is the [[least common multiple]] of the cycle lengths in the cycle decomposition. | |||
==Conjugacy== | |||
We recall that the ''[[Conjugation (group theory)|conjugate]]'' of a group element <math>\alpha</math> by an element <math>\beta</math> is <math>\alpha^\beta = \beta^{-1} \alpha \beta</math>. Conjugation of a permutation is particularly simple to express in terms of cycle decomposition. If | |||
:<math>\alpha = \left(a_{1} \ldots a_{k} \right) \left(b_{1} \ldots b_{l} \right) \cdots \, </math> | |||
then the conjugate | |||
:<math>\alpha^\beta = \left(\beta(a_{1}) \ldots \beta(a_{k}) \right) \left(\beta(b_{1}) \ldots \beta(b_{l}) \right) \cdots . \, </math> | |||
Two elements are conjugate if and only if they have the same cycle shape. The number of [[conjugacy class]]es of ''S''<sub>''n''</sub> is thus equal to <math>p(n)</math>, the number of [[Partition (mathematics)|partition]]s of ''n''. | |||
== Permutational Parity == | == Permutational Parity == | ||
A 2-cycle is called a ''transposition''. | A 2-cycle is called a ''transposition''. | ||
A permutation | A cycle can be written as a product of transpositions, | ||
<math>(a~b~c~\ldots~z) = (a~b)(a~c)\cdots(a~z)</math>, and hence every permutation in <math>S_{n}</math>, for n > 1, can be written as a product of transpositions. | |||
A permutation of ''n'' points is then called ''even'' if it can be written as the product of an even number of transpositions and ''odd'' if it can be written as the product of an odd number of transpositions. | |||
The nontrivial fact about this terminology is that it is well-defined; that is, no permutation is both even and odd. | The nontrivial fact about this terminology is that it is well-defined; that is, no permutation is both even and odd. | ||
The even permutations in <math>S_{n}</math> form a subgroup of <math>S_{n}</math>. This subgroup is called the ''alternating group on n letters'' and denoted <math>A_{n}</math>. | The even permutations in <math>S_{n}</math> form a subgroup of <math>S_{n}</math>. This subgroup is called the ''alternating group on n letters'' and denoted <math>A_{n}</math>. In fact, <math>A_{n}</math> is always a normal subgroup of <math>S_{n}</math>. | ||
The order of <math>A_{n}</math> is <math>\frac{n!}{2}</math>. | The order of <math>A_{n}</math> is <math>\frac{n!}{2}</math>. | ||
[[ | == Notes on the Structure of the Symmetric Group == | ||
[[ | |||
[[ | <math>S_{n}</math> has proper [[normal subgroup]]s if and only if n >= 3. Then the only proper normal subgroup of <math>S_{n}</math> is <math>A_{n}</math>, unless n=4. When n=4, there is an additional proper normal subgroup, often denoted V, consisting of the identity permutation and the permutations (1,2)(3,4), (1,3)(2,4), and (1,4)(2,3). | ||
The [[conjugacy class]]es of <math>S_{n}</math> are in [[one-to-one correspondence]] with the [[partition]]s of the integer n. Two permutations in <math>S_{n}</math> are [[conjugate]] in <math>S_{n}</math> if and only the have the same lengths of cycles. These cycle lengths, including fixed points as cycles of length 1, add up to n and so form a partition of n. | |||
== Deeper Notes: Orbits and Blocks == | |||
Let <math>G</math> be a subgroup of <math>S_{n}</math>. One may define an equivalence <math>~</math> relation on {1,...,n}, where <math>i</math>~<math>j</math> means that some element of <math>G</math> maps <math>i</math> to <math>j</math>. The resulting equivalence classes are called ''orbits''. <math>G</math> is called ''transitive'' if {1,...,n} forms one single orbit. | |||
Let the orbits of <math>G</math> be <math> O_{1}, \ldots, O_{k}</math>. The action of <math>G</math> on <math> O_{i}</math> gives a homomorphism <math> \phi_{i} : G \to S_{|O_{i}|} </math>. While <math>G</math> is isomorphic to a subgroup of the product of the <math> \phi_{i}(G) </math>, this product is not, in general, isomorphic to <math>G</math>. For example, any <math>G</math> can be made to act on <math>2n</math> points by using two copies of its action on <math>n</math> points. Yet no finite <math>G</math>, aside from the trivial group, is isomorphic to <math> G \times G </math>. | |||
While an intransitive permutation group may be broken up into orbits, a transitive permutation group has to be analyzed with greater subtlety: it could be ''primitive'', or its action will be 'condensable' into an action on a set of ''blocks''. | |||
A ''primitive'' permutation group on the points {1,...,n} (note: we implicitly assume that <math> n > 1 </math> here) is, with only one exception, a group which leaves invariant no proper partition of {1,...,n}: | |||
A partition of {1,...,n} is an expression of {1,...,n} as a union of pairwise disjoint subsets. | |||
Any partition is proper, except for {1,...,n} = {1,...,n} and the expression of {1,...,n} as the union of its one-element subsets. | |||
Permutations of indices naturally induce permutations of partitions: for example, the permutation (1,2,3,4) sends the partition <math> \lbrace 1,2,3,4 \rbrace = \lbrace 1,2 \rbrace \cup \lbrace 3,4 \rbrace </math> to <math> \lbrace 1,2,3,4 \rbrace = \lbrace 2,3 \rbrace \cup \lbrace 4,1 \rbrace = \lbrace 1,4 \rbrace \cup \lbrace 2,3 \rbrace </math>, sends the partition <math> \lbrace 1,2,3,4 \rbrace = \lbrace 2,3 \rbrace \cup \lbrace 1,4 \rbrace </math> to the partition <math> \lbrace 1,2,3,4 \rbrace = \lbrace 3,4 \rbrace \cup \lbrace 1,2 \rbrace = \lbrace 1,2 \rbrace \cup \lbrace 3,4 \rbrace </math>, and sends the partition <math> \lbrace 1,2,3,4 \rbrace = \lbrace 1,3 \rbrace \cup \lbrace 2,4 \rbrace </math> to <math> \lbrace 1,2,3,4 \rbrace = \lbrace 2,4 \rbrace \cup \lbrace 1,3 \rbrace = \lbrace 1,3 \rbrace \cup \lbrace 2,4 \rbrace </math> (i.e., to itself). So the cycle (1,2,3,4) induces the permutation (12 34, 14 23)(13 24) on the partitions of \lbrace 1,2,3,4 \rbrace into 2 disjoint 2-element sets. | |||
Since <math> \lbrace 1,2 \rbrace </math> has no proper partitions, the trivial subgroup of <math> S_{2} </math> would be considered primitive by the preceding, but it is not considered primitive: this is the sole exception referred to above. This is done for consistency: If <math> n \geq 3 </math>, then {1,...,n} has proper partitions. | |||
If G is trivial, then G fixes every partition of {1,...,n}, including the proper ones. | |||
If G is nontrivial but intransitive, the partition of {1,...,n} into orbits for the action of G will be proper (the nontriviality of G excludes the partition into singletons, while the intransitivity of G excludes the one-block partition), and it is a G-invariant partition of {1,...,n}. Thus primitive permutation groups are transitive, including the case when n=2. |
Latest revision as of 20:52, 25 June 2009
![](http://s9.addthis.com/button1-share.gif)
In mathematics, the symmetric group is the group of all permutations of a set, that is, of all invertible functions from a set to itself. It is a central object of study in group theory.
Definition
If is a positive integer, the symmetric group on "letters" (often denoted ) is the group formed by all bijections from a set to itself (under the operation of function composition), where is an -element set. It is customary to take to be the set of integers from to , but this is not strictly necessary. The bijections which are elements of the symmetric group are called permutations.
Note that this means the identity element of the group is the identity map on , which is the map sending each element of to itself.
The order of is given by the factorial function .
Cycle Decomposition
Any permutation of a finite set can be written as a product of permutations called cycles. A cycle acting on fixes all the elements of S outside a nonempty subset of . On , the action of is as follows: for some indexing of the elements of , sends to for all and sends to . Then one writes
(Sometimes the commas are omitted.) If k > 1, such a is called a k-cycle.
For example, the permutation of the integers from 1 to 4 sending to for all can be denoted .
If is a one-element set, then its element is a fixed point of the permutation. Fixed points are often omitted from permutations written in cycle notation, since any cycling the elements of as discussed above would be the identity permutation.
The cycle shape of an element is the list of cycle lengths written in decreasing order.
The order of a permutation is the least common multiple of the cycle lengths in the cycle decomposition.
Conjugacy
We recall that the conjugate of a group element by an element is . Conjugation of a permutation is particularly simple to express in terms of cycle decomposition. If
then the conjugate
Two elements are conjugate if and only if they have the same cycle shape. The number of conjugacy classes of Sn is thus equal to , the number of partitions of n.
Permutational Parity
A 2-cycle is called a transposition. A cycle can be written as a product of transpositions, , and hence every permutation in , for n > 1, can be written as a product of transpositions. A permutation of n points is then called even if it can be written as the product of an even number of transpositions and odd if it can be written as the product of an odd number of transpositions. The nontrivial fact about this terminology is that it is well-defined; that is, no permutation is both even and odd.
The even permutations in form a subgroup of . This subgroup is called the alternating group on n letters and denoted . In fact, is always a normal subgroup of .
The order of is .
Notes on the Structure of the Symmetric Group
has proper normal subgroups if and only if n >= 3. Then the only proper normal subgroup of is , unless n=4. When n=4, there is an additional proper normal subgroup, often denoted V, consisting of the identity permutation and the permutations (1,2)(3,4), (1,3)(2,4), and (1,4)(2,3).
The conjugacy classes of are in one-to-one correspondence with the partitions of the integer n. Two permutations in are conjugate in if and only the have the same lengths of cycles. These cycle lengths, including fixed points as cycles of length 1, add up to n and so form a partition of n.
Deeper Notes: Orbits and Blocks
Let be a subgroup of . One may define an equivalence relation on {1,...,n}, where ~ means that some element of maps to . The resulting equivalence classes are called orbits. is called transitive if {1,...,n} forms one single orbit. Let the orbits of be . The action of on gives a homomorphism . While is isomorphic to a subgroup of the product of the , this product is not, in general, isomorphic to . For example, any can be made to act on points by using two copies of its action on points. Yet no finite , aside from the trivial group, is isomorphic to .
While an intransitive permutation group may be broken up into orbits, a transitive permutation group has to be analyzed with greater subtlety: it could be primitive, or its action will be 'condensable' into an action on a set of blocks.
A primitive permutation group on the points {1,...,n} (note: we implicitly assume that here) is, with only one exception, a group which leaves invariant no proper partition of {1,...,n}: A partition of {1,...,n} is an expression of {1,...,n} as a union of pairwise disjoint subsets. Any partition is proper, except for {1,...,n} = {1,...,n} and the expression of {1,...,n} as the union of its one-element subsets. Permutations of indices naturally induce permutations of partitions: for example, the permutation (1,2,3,4) sends the partition to , sends the partition to the partition , and sends the partition to (i.e., to itself). So the cycle (1,2,3,4) induces the permutation (12 34, 14 23)(13 24) on the partitions of \lbrace 1,2,3,4 \rbrace into 2 disjoint 2-element sets.
Since has no proper partitions, the trivial subgroup of would be considered primitive by the preceding, but it is not considered primitive: this is the sole exception referred to above. This is done for consistency: If , then {1,...,n} has proper partitions. If G is trivial, then G fixes every partition of {1,...,n}, including the proper ones. If G is nontrivial but intransitive, the partition of {1,...,n} into orbits for the action of G will be proper (the nontriviality of G excludes the partition into singletons, while the intransitivity of G excludes the one-block partition), and it is a G-invariant partition of {1,...,n}. Thus primitive permutation groups are transitive, including the case when n=2.