Introductory texts that discuss permutations don’t seem to stress the notion of length of a permutation. In my book I tried to stress this useful notion, but the treatment in my book is confusing at points, so let me try here to give a very short and hopefully clearer account.
Fix an integer and let be the set of all bijections of the set . Since the composition of bijections is a bijection, and the inverse of a bijection is also a bijection, is a group under composition. The elements of are called permutations of . Sometimes it is convenient to display a permutation by listing the elements in a row and the images below:
For any and , the orbit of is the set
For example, the orbits of
denote the set of all orbits of . The length of is
Thus, in our example above,
Notice that the length does not change if we view a permutation in as a permutation of , keeping and fixed.
means a permutation that takes to , to , and so on, with being taken to , and all other elements are held fixed. Such a permutation is called a cycle. (Whether you view the identity permutation as a cycle or not is up to you; one could make it less ambiguous by using the term cycle only for those permutations that have exactly one orbit.) Thus,
is a cycle. The notation does not require we specify which set this permutation acts on (of course, the set must contain .) If as above is in then
Notice that dropped out of this calculation. The length of a cycle is just the number of elements in the orbit of this cycle minus . (“The orbit” having the obvious interpretation.)
Every permutation is a product of the cycles that correspond to its orbits, the distinct orbits being disjoint.
A transposition is a permutation that exchanges two elements, and holds all others fixed. For example,
is a transposition. Clearly, a permutation is a transposition if and only if its length is . Moreover, every transposition is equal to its own inverse.
If we multiply a permutation by a transposition to form then there are exactly two possibilities:
(1) if and are both in the same orbit of then that orbit is split into two orbits for ;
(2) if and are in different orbits of then these orbits are combined into one orbit for .
All other orbits of remain orbits of .
and, multiplying on the left by , we have
A consequence of this very nice fact is the effect on the length of a permutation under multiplication by a transposition:
where the first case occurs when transposes elements in different orbits of , and the second case occurs when transposes elements within one orbit of .
Thus for any permutation we can systematically break down each of its cycles (orbits) by hitting them with transpositions: there is a sequence of transpositions such that the length of is , which means that
the identity. Note that this is equivalent to
because each is a transposition (hence equal to its inverse).
Thus, every permutation is a product of transpositions, and the smallest such number of transpositions is the length of .
for all permutations and .
The orbits of are exactly the orbits of , and so both and have the same number of orbits. Hence they have the same length:
Next for any permutations and , the orbits of are exactly of the form where runs over the orbits of . Hence