Permutations - Permutations in Group Theory - Notation

Notation

There are three main notations for permutations of a finite set S. In Cauchy's two-line notation, one lists the elements of S in the first row, and for each one its image under the permutation below it in the second row. For instance, a particular permutation of the set {1,2,3,4,5} can be written as:

this means that σ satisfies σ(1)=2, σ(2)=5, σ(3)=4, σ(4)=3, and σ(5)=1.

In one-line notation, one gives only the second row of this array, so the one-line notation for the permutation above is 25431. (It is typical to use commas to separate these entries only if some have two or more digits.)

Cycle notation, the third method of notation, focuses on the effect of successively applying the permutation. It expresses the permutation as a product of cycles corresponding to the orbits (with at least two elements) of the permutation; since distinct orbits are disjoint, this is loosely referred to as "the decomposition into disjoint cycles" of the permutation. It works as follows: starting from some element x of S with σ(x) ≠ x, one writes the sequence (x σ(x) σ(σ(x)) ...) of successive images under σ, until the image would be x, at which point one instead closes the parenthesis. The set of values written down forms the orbit (under σ) of x, and the parenthesized expression gives the corresponding cycle of σ. One then continues choosing an element y of S that is not in the orbit already written down, and such that σ(y) ≠ y, and writes down the corresponding cycle, and so on until all elements of S either belong to a cycle written down or are fixed points of σ. Since for every new cycle the starting point can be chosen in different ways, there are in general many different cycle notations for the same permutation; for the example above one has for instance

Each cycle (x₁ x₂ ... x_l) of σ denotes a permutation in its own right, namely the one that takes the same values as σ on this orbit (so it maps x_i to x_i+1 for i < l, and x_l to x₁), while mapping all other elements of S to themselves. The size l of the orbit is called the length of the cycle. Distinct orbits of σ are by definition disjoint, so the corresponding cycles are easily seen to commute, and σ is the product of its cycles (taken in any order). Therefore the concatenation of cycles in the cycle notation can be interpreted as denoting composition of permutations, whence the name "decomposition" of the permutation. This decomposition is essentially unique: apart from the reordering the cycles in the product, there are no other ways to write σ as a product of cycles (possibly unrelated to the cycles of σ) that have disjoint orbits. The cycle notation is less unique, since each individual cycle can be written in different ways, as in the example above where (5 1 2) denotes the same cycle as (1 2 5) (but (5 2 1) would denote a different permutation).

An orbit of size 1 (a fixed point x in S) has no corresponding cycle, since that permutation would fix x as well as every other element of S, in other words it would be the identity, independently of x. It is possible to include (x) in the cycle notation for σ to stress that σ fixes x (and this is even standard in combinatorics, as described in cycles and fixed points), but this does not correspond to a factor in the (group theoretic) decomposition of σ. If the notion of "cycle" were taken to include the identity permutation, then this would spoil the uniqueness (up to order) of the decomposition of a permutation into disjoint cycles. The decomposition into disjoint cycles of the identity permutation is an empty product; its cycle notation would be empty, so some other notation like e is usually used instead.

Cycles of length two are called transpositions; such permutations merely exchange the place of two elements.