The Symmetric Group, Permutations and Cycles
Consider the set X = {1, 2, . . . n}. Let Fn be the set of all bijections from
X to X. A bijection from a
set X to itself is also called a permutation of X.
Composition of permutations works like the standard
composition of functions. For 
When there is no danger of confusion, the
ration s-2.html">operator may be dropped, making 
equivalent to 
Often, composition is referred
to as a "product".
Consider the group 
of
all permutations with the composition operation-this is called the
symmetric group on X . Here are some properties of this group .
•Permutations can be ex pressed in a two -row matrix style,
where the first row is the input and the
second row is the output. For example,
means 
etc.
•Consider a permutation 
which only changes the positions of some elements
as fol lows . 
for every
Such a permutation is
called a cycle, and is represented as 
For
instance, 
contains
We say that a cycle
fixes any element in the set 
that is not in
the cycle. Finally, we call
a cycle of length r an r-cycle, and it fixes the remaining n-r elements
•A 1-cycle is the same as the identity permutation. A
2-cycle t is called a transposition. 
swaps the two elements i and j and fixes the rest. Note that
•Useful fact. Every permutation can be uniquely expressed
as the product of disjoint cycles. For
example,
can be written as
•Furthermore, every permutation can be expressed as a
product (i.e., composition) of transpositions,
but this decomposition is not unique. For example,
However, the parity of the decomposition is the same in
each of these represntations. I.e. any
permutation which can be written as a product of an even number of
transpositions can never
be written as another product of an odd number of transpositions, and vice
versa. We define
permutations which can be written as an even number of transpositions as even,
and the others
as odd.
Two More Definitions
•For any group 
, given
, the conjugate of b by a is the element
.
For the special case of the symmetric group, if
replaces every element
in 
It is functionally equivalent
to 
•Let 
be groups. A
function 
is a homomorphism if for
A function 
is an
isomorphism if is both a homorphism and a
bijection. Finally, a function
is an automorphism if is an isomorphism from
a group G to itself.
