Difference between revisions of "Symmetric group"
(added material on notation, generating systems, and parity of permutations) |
(every group is a permutation group) |
||
Line 1: | Line 1: | ||
The '''symmetric group''' <math>S_{n}</math> is defined to be the [[group]] of all [[permutation]]s of <math>n</math> objects. More generally, the symmetric group of a [[set]] <math>M</math>, denoted <math>S_M</math>, <math>\mathfrak{S}_M</math>, or <math>\text{Sym}(M)</math>, is the group of permutations on <math>M</math>. A [[subgroup]] of the symmetric group on <math>M</math> is sometimes called a '''permutation group''' on <math>M</math>. In this context, a permutation is to be thought of as a [[bijective]] [[function]] from a [[set]] of size <math>n</math> to itself, and the group operation is [[composition]] of functions. | The '''symmetric group''' <math>S_{n}</math> is defined to be the [[group]] of all [[permutation]]s of <math>n</math> objects. More generally, the symmetric group of a [[set]] <math>M</math>, denoted <math>S_M</math>, <math>\mathfrak{S}_M</math>, or <math>\text{Sym}(M)</math>, is the group of permutations on <math>M</math>. A [[subgroup]] of the symmetric group on <math>M</math> is sometimes called a '''permutation group''' on <math>M</math>. In this context, a permutation is to be thought of as a [[bijective]] [[function]] from a [[set]] of size <math>n</math> to itself, and the group operation is [[composition]] of functions. | ||
− | The symmetric group is of interest in many different branches of mathematics, especially [[combinatorics]]. (This is in part due to the various different representations of permutations: as functions, as products of [[cycle]]s, as [[sequence]]s or [[word]]s, etc.) Knowledge of the symmetric group <math>S_{n}</math> can also be crucial in such areas as [[Galois theory]]. For example, an important theorem in [[Galois theory]] is that the [[Galois group]] of the general polynomial equation of degree <math>n</math> is <math>S_{n}</math>, and this can be used to prove that [[polynomial]] [[equation]]s of degree five and higher are unsolvable through the use of elementary arithmetic and root extractions. | + | The symmetric group is of interest in many different branches of mathematics, especially [[combinatorics]]. (This is in part due to the various different representations of permutations: as functions, as products of [[cycle]]s, as [[sequence]]s or [[word]]s, etc.) Knowledge of the symmetric group <math>S_{n}</math> can also be crucial in such areas as [[Galois theory]]. For example, an important theorem in [[Galois theory]] is that the [[Galois group]] of the general polynomial equation of degree <math>n</math> is <math>S_{n}</math>, and this can be used to prove that [[polynomial]] [[equation]]s of degree five and higher are unsolvable through the use of elementary arithmetic and root extractions. |
+ | |||
+ | The study of symmetric groups is also interesting because every group is isomorphic to a permutation group, i.e., a subgroup of a symmetric group. Indeed, if <math>G</math> is a group, then for <math>a \in G</math>, the mapping <math>x \mapsto ax</math> is a permutation of <math>G</math>. Thus symmetric groups can be considered universal with respect to subgroups, just as [[free group]]s can be considered universal with respect to [[quotient group]]s. | ||
== Representations of Finite Permutations == | == Representations of Finite Permutations == |
Latest revision as of 15:33, 25 May 2008
The symmetric group is defined to be the group of all permutations of
objects. More generally, the symmetric group of a set
, denoted
,
, or
, is the group of permutations on
. A subgroup of the symmetric group on
is sometimes called a permutation group on
. In this context, a permutation is to be thought of as a bijective function from a set of size
to itself, and the group operation is composition of functions.
The symmetric group is of interest in many different branches of mathematics, especially combinatorics. (This is in part due to the various different representations of permutations: as functions, as products of cycles, as sequences or words, etc.) Knowledge of the symmetric group can also be crucial in such areas as Galois theory. For example, an important theorem in Galois theory is that the Galois group of the general polynomial equation of degree
is
, and this can be used to prove that polynomial equations of degree five and higher are unsolvable through the use of elementary arithmetic and root extractions.
The study of symmetric groups is also interesting because every group is isomorphic to a permutation group, i.e., a subgroup of a symmetric group. Indeed, if is a group, then for
, the mapping
is a permutation of
. Thus symmetric groups can be considered universal with respect to subgroups, just as free groups can be considered universal with respect to quotient groups.
Contents
Representations of Finite Permutations
Let be an element of
. One way to denote
is as
So for instance, with
, we might have
In the more concise cycle notation, we represent a cycle
of order
as
for some arbitrary
in the support of
; and we write an arbitrary permutation as a composition of cycles. Thus we may have
This notation is concise; it lends itself to easy computation of products and inverses.
Finally, we may represent a permutation as a permutation matrix, i.e., the matrix that maps to
. An
matrix is a permutation matrix if and only if all its entries are zeros and ones, each column has exactly one 1, and each row has exactly one 1. In this instance, we have
In the next two sections, will represent a finite set.
Transpositions and Generators
A transposition is a cycle whose support has two elements. A transposition whose support is may be denoted
. Evidently, every transposition is its own inverse.
In this section and the next one, will represent a finite set.
Theorem 1. The symmetric group is generated by its transpositions.
Proof. We induct on . For our base case,
, the theorem is trivial. Now, suppose that
is an element of
. Let
be an arbitrary element of
. Let
be the subgroup of elements of
for which
is a fixed point. Evidently,
is isomorphic to
by restrictions of mappings, so by inductive hypothesis, it is generated by its transpositions. Then
, for some permutation
. Since
can be expressed as a product of transpositions, it follows that
can be expressed as a product of transpositions.
Note that in general this theorem is not true on infinite sets without permitting infinite compositions of functions.
Theorem 2. The symmetric group is generated by the transpositions
.
Proof. By theorem 1, it is enough to prove that any transposition is generated by
. Without loss of generality, suppose
. We induct on
. Our base case,
, is trivial. For the inductive step, we note that
Since
is in the subgroup generated by
, it follows that
is, as well.
Theorem 3. Let be a cycle whose orbit is
, let
be an element of
, and let
be a transposition on
. Then
and
generate
.
Proof. Let be an arbitrary element of
. Then we may denote every element of
as
, where
is an integer. Suppose
. By Theorem 2, it is enough to show that
lies in the subgroup generated by
and
, for each integer
. But this follows from the observation
Thus
and
generate
, as desired.
Even and Odd Permutations; Alternating Groups
For an element , an inversion is an ordered pair of integers
such that
and
. We will let
denote the number of inversions of
. A permutation is called odd if it has an odd number of inversions, and even if it contains an even number of inversions. We wish to show that the mapping
is a homomorphism; this would imply that even permutations form a normal subgroup of
.
Let be a mapping from
to
, and suppose
. Let
be the mapping so that
Then evidently
.
Let be the mapping
Lemma. The function is not the zero function, and
.
Proof. If are distinct, then
. Let
denote 1 if
is a
-inversion, and 0, otherwise. Then by rearranging terms,
as desired.
Theorem 4. There exists a unique homomorphism from
to the multiplicative group
such that
, for any transposition
.
Proof. To show the existance of , it suffices to show its existance for
. We will show that
is such a homomorphism. Indeed, if
are elements of
, then by the lemma,
On the other hand,
Since
(from the lemma), it follows that
i.e.,
is a homomorphism, as desired, and evidently
for every transposition
.
Since is generated by its transpositions (Theorem 1), it follows that
is unique.
This is what we wanted to prove. The kernel of is the set of even permutations on
, called the alternating group of
. It is usually denoted as
,
, or
.