Transpositions

With our earlier conventions, a permutation is a 1-1 correspondence f: {1, 2, ..., n} → {1, 2, ..., n}. Pick an x ∈ {1, 2, ..., n} and consider its orbit x, f(x), f(f(x)), ... Since we only have a finite number of elements, sooner or later we'll necessarily get f(f(...f(x))) = x. Let x = x₁, f(x) = x₂ and so on. Under the permutation f, x₁ becomes x₂, x₂ becomes x₃, ..., and let x_k+1 happen to be x₁ again for the first time. The permutation that scrolls x₁, ..., x_k this way while keeping all the remaining numbers fixed, is called a cycle and is denoted (x₁ x₂ ... x_k). If f = (x₁ x₂ ... x_k) then k = n and there is nothing we can add to describe f. However, if there exists y₁ that does not belong to the orbit of x, it has an orbit of its own with which we associate another cycle: (y₁ y₂ ... y_m). Eventually all the elements will be associated with one cycle or another - each with one cycle only. We can then write f = (x₁ x₂ ... x_k)(y₁ y₂ ... y_m)..., meaning by this scrolling consecutively the elements along their corresponding orbits. Two cycles associated with the orbits of two different elements either coincide or have empty intersection. In the latter case the cycles are called disjoint. Two disjoint f and g cycles commute: fg = gf. It can be shown that the representation of a permutation as a product of disjoint cycles is unique up to the order of the cycles.

A fixed point forms a one-element (or trivial) cycle. A 2-element cycle (x_i x_j) is called a transposition.

Theorem 1

Any permutation is a product of transpositions. (The representation as a product of transpositions is not unique.)

Remark

As before, this means that f produces the same effect as consecutive application of a series of transpositions.

Proof of Theorem 1

Given a permutation f, first factor it into a product of cycles: f = g₁g₂ ... Let g₁ = (x₁ x₂ ... x_k). Then it's easy to see that

(1)	(x₁ x₂ ... x_k) = (x₁ x_k)(x₁ x_k-1) ... (x₁ x₂)

The product is not symmetric and the transpositions are performed from right to left. We can apply this argument to all the cycles g and then execute all thus obtained transpositions sequentially.

Representation of a permutation as a product of (disjoint) cycles is unique. Its representation as a product of transpositions is not. However, one quantity related to a permutation is invariant under its various representations as a product of transpositions. This is the parity of the number of transpositions in the representation.

Theorem 2

Assume that for a permutation f, f = g₁g₂ ... g_k = h₁h₂...h_m where all g_i's and h_i's are transpositions. Then k and m have the same parity, i.e. they are either both even or both odd.

Thus there are even and odd permutations. The former are obtained as a product of an even number of transpositions; the latter are formed by an odd number of terms. Multiplying a permutation by a transposition obviously changes its parity. As a consequence, parity of the product (consecutive execution) of two or, for that matter, any number of permutations obeys the laws of the arithmetic modulo 2. In other words, the product of two permutations (which is definitely another permutation) will be even iff the component permutations are either both even or both odd.

Pemutations have an additional visualization in a circular fashion. Quite a convenience.

References

J. Landin, An Introduction to Algebraic Structures, Dover, NY, 1969.

Permutations

Transpositions

Groups of Permutations

Sliders

Puzzles on graphs

40608031