The set of all
permutations of $S$
is the same as the invertible mappings in $M(S).$
The set of all permutations of a nonempty set $S$
with composition is a group.
This group is called
the symmetric group on $S$
denoted by $\Sym(S).$
Theorem 6.1
[Theorem 4.1(b)]
and
$\Sym(S)\subsetneq M(S).$
Contrast
symmetry group
on page 46.
A group of permutations with composition is a
permutation group.
If $S$ is the underlying set
of a permutation group then
it is
a permutation group on $S.$
$\Sym(S)$ is a permutation group on $S.$
$G\subsetneq\Sym(S)$ for some
permutation groups $G.$
That is, $G$ need not contain all
permutations of $S.$
For examples, see the
If $G$ is a permutation group on $S$
then $\iota_S$ is the identity of $G.$
The groups of
A set of permutations on $S$
need not be a permutation group on $S.$
The elements of a permutation group
are mappings, whereas the
elements of $S$ can be anything,
such as numbers.
Remember that, like $M(S),$
a set of permutations of $S$
is a set of mappings,
whereas the
elements of $S$ can be something else,
such as numbers.
For instance, the elements of a
permutation group, such as $\Sym(S),$
are mappings.
If $S=\{1,2,\ldots,n\},$
the first $n$ positive integers,
then we write
$S_n$$=\Sym(n)$$=\Sym(S).$
This group is called
the symmetric group of degree $n,$
or simply
"Sym n."
Members of $S_n$
may be represented in
two-row form.
For example,
\[
\left(
\begin{matrix}
1 &2 &3 &4\\
2 &4 &3 &1\\
\end{matrix}
\right)
\]
is the permutation in $S_4$
defined by
$1\mapsto2,$
$2\mapsto4,$
$3\mapsto3,$
and
$4\mapsto1.$
How to write two-row form of a permutation in $S_n.$
-
Write $1,2,\ldots,n$
in the first row.
-
Below each number $k$
write its image
$\alpha(k).$
-
Wrap in parentheses.
The identity element of $S_n$
is
\[
\left(
\begin{matrix}
1 &2 &\cdots &n\\
1 &2 &\cdots &n\\
\end{matrix}
\right)
\]
The inverse of an element in $S_n$
is obtained by reading from the bottom
entry to the top entry
rather than from top to bottom.
For instance, if $1$ appears beneath
$4$ in $\alpha$ then $4$ will appear
beneath $1$ in $\alpha^{-1}.$
The inverse of an element in $S_4$
\[
\left(
\begin{matrix}
1 &2 &3 &4\\
2 &4 &3 &1\\
\end{matrix}
\right)^{-1}
=
\left(
\begin{matrix}
1 &2 &3 &4\\
4 &1 &3 &2\\
\end{matrix}
\right)
\]
Composition of permutations in $S_n$
follows the same convention as for
other mappings: read from right to left.
(Some authors compose permutations left to
right, one must check in each case what
convention is followed.)
Composition of permutations in $S_n$
\[
\left(
\begin{matrix}
1 &2 &3 &4\\
2 &4 &1 &3\\
\end{matrix}
\right)
\circ
\left(
\begin{matrix}
1 &2 &3 &4\\
3 &4 &1 &2\\
\end{matrix}
\right)
=
\left(
\begin{matrix}
1 &2 &3 &4\\
1 &3 &2 &4\\
\end{matrix}
\right)
\]
but
\[
\left(
\begin{matrix}
1 &2 &3 &4\\
3 &4 &1 &2\\
\end{matrix}
\right)
\circ
\left(
\begin{matrix}
1 &2 &3 &4\\
2 &4 &1 &3\\
\end{matrix}
\right)
=
\left(
\begin{matrix}
1 &2 &3 &4\\
4 &2 &3 &1\\
\end{matrix}
\right)
\]
The elements of $S_3$ are
\[
\left(
\begin{matrix}
1 &2 &3\\
1 &2 &3\\
\end{matrix}
\right)
\]
\[
\left(
\begin{matrix}
1 &2 &3\\
2 &3 &1\\
\end{matrix}
\right)
\]
\[
\left(
\begin{matrix}
1 &2 &3\\
3 &1 &2\\
\end{matrix}
\right)
\]
\[
\left(
\begin{matrix}
1 &2 &3\\
2 &1 &3\\
\end{matrix}
\right)
\]
\[
\left(
\begin{matrix}
1 &2 &3\\
3 &2 &1\\
\end{matrix}
\right)
\]
\[
\left(
\begin{matrix}
1 &2 &3\\
1 &3 &2\\
\end{matrix}
\right)
\]
The order of $S_n$ is $n!.$
An
abelian group
is a group whose operation
is commutative.
A non-abelian
group is not Abelian.
If $n\ge3$ then $S_n$ is non-Abelian.
$S_1$ and $S_2$ are Abelian.
More generally,
for any $S,$
if
$\abs{S}=1$ or $\abs{S}=2$
then $\Sym(S)$ is Abelian.
If $\abs{S}\gt2$
then $\Sym(S)$
is non-Abelian.
Elements of $S_n$ are frequently written
using
cycle notation.
If $S$ is a set and $a_1,\ldots,a_k\in S$
then $(a_1\cdots a_k)$
denotes the permutation of $S$ for which
\[
\begin{align*}
a_1 &\mapsto a_2\\
a_2 &\mapsto a_3\\
&\cdots\\
a_{k-1} &\mapsto a_k\\
a_{k} &\mapsto a_1
\end{align*}
\]
and
\[
x\mapsto x
\]
for all other $x\in S.$
Such a permutation is called a
cycle
or
$k$-cycle.
For clarity,
$(a_1,\ldots,a_k)$
may be written instead of
$(a_1\cdots a_k).$
Not all permutations are cycles.
For instance, only some,
not all, elements of $S_3,$
can be written as a
$3$-cycle
$(a_1 a_2 a_3).$
For example, the permutation
\[
\left(
\begin{matrix}
1 &2 &3 &4\\
3 &4 &1 &2\\
\end{matrix}
\right)
\]
is not a cycle.
However, see
If $a$ is any element of $S$
then the
$1$-cycle
$(a)$
is
the identity permutation of $S.$
Therefore, $(a)=(b)$
for any two elements $a,b\in S.$
Cycles are composed just as
any other permutations
except that $\circ$ is usually omitted.
Following common practice, we may refer
to a composition of cycles or of other
permutations as a
product.
Although elements of $S_n$
are typically written using
cycle notation,
the definition of
$k$-cycle
does not require that
$S={1,\ldots,n}.$
Therefore, permutations of any $S,$
that is, elements of $\Sym(S)$
may be written using cycle notation
as per the
Cycles $(a_1\cdots a_m)$
and $(b_1\cdots b_n)$
are
disjoint
if $a_i\ne b_j$
for all $i,j.$
Cycles
$(1\ 2\ 4)$
and
$(3\ 5\ 6)$
are disjoint
but
$(1\ 2\ 4)$
and
$(3\ 4\ 6)$
are not.
Disjoint cycles commute.
That is, if $\alpha$ and $\beta$
are disjoint cycles then
\[
\alpha\beta=\beta\alpha.
\]
Prime Factorization Theorem for Permutations.
Any permutation of a finite set is either
a cycle or can be written as a product
of pairwise disjoint cycles; and except
for the order in which the cycles are
written, and the inclusion or omission
of 1-cycles, this can be done in only
one way.
How to prime factor a permutation.
-
Start the first cycle with $1.$
-
Continue until we get back to $1.$
-
Close the first cycle.
-
Start the second cycle with the
smallest number not in the first
cycle.
-
Continue until we get to that number.
-
Close the second cycle.
-
Repeat, never repeating a number
that has already appeared.
Two-cycles are called
transpositions.
Alex Notes