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 = x1, f(x) = x2 and so on. Under the permutation f, x1 becomes x2, x2 becomes x3, ..., and let xk+1 happen to be x1 again for the first time. The permutation that scrolls x1, ..., xk this way while keeping all the remaining numbers fixed, is called a cycle and is denoted (x1 x2 ... xk). If f = (x1 x2 ... xk) then k = n and there is nothing we can add to describe f. However, if there exists y1 that does not belong to the orbit of x, it has an orbit of its own with which we associate another cycle: (y1 y2 ... ym). Eventually all the elements will be associated with one cycle or another - each with one cycle only. We can then write f = (x1 x2 ... xk)(y1 y2 ... ym)..., 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 (xi xj) 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 = g1g2 ... Let g1 = (x1 x2 ... xk). Then it's easy to see that

(1) (x1 x2 ... xk) = (x1 xk)(x1 xk-1) ... (x1 x2)

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 = g1g2 ... gk = h1h2...hm where all gi's and hi'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.

The parity of a permutation is often referred to as its sign or signatue.

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


References

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

Permutations

  • Transpositions
  • Groups of Permutations
  • Sliders
  • Puzzles on graphs
  • Equation in Permutations

    |Contact| |Front page| |Contents| |Algebra|

    Copyright © 1996-2017 Alexander Bogomolny

  •  62684681

    Search by google: