permutation notation

There are at least three methods of denoting permutations.

The first method of denoting a permutation that acts on a finite set is to simply list where it sends each element. For example, the function $f$ defined as follows is a permutation on $\{1,2,3,4,5,6\}$:

$$f(1)=3$$

$$f(2)=1$$

$$f(3)=2$$

$$f(4)=6$$

$$f(5)=5$$

$$f(6)=4$$

Another method of denoting a permutation that acts on a finite set is to give the information in a matrix. This matrix will have $2$ rows and $n$ columns, where $n$ is the cardinality of the set on which the permutation is acting. The first row is each of the elements of the set on which the permutation is acting, and the second row is created so that, whenever a column is read, the bottom element is where the permutation sends the top element. If the set on which the permutation is acting has an order on it, then the elements usually occur in the first row according to that order. For example, the function $f$ as described above would be denoted as:

final method of denoting a permutation is as follows:

1. Write a left parenthesis and an element that is not sent to itself by the permutation. (If the permutation fixes every element of the set, then it is the identity. In that case, if the set is of the form $\{1,\mathrm{\dots },n\}$, then this permutation is typically denoted $(1)$.) If the set on which the permutation is acting has an order (http://planetmath.org/PartialOrder) on it, then the elements are considered according to that order.

2. Immediately to the right of the previous element, write the element to which the permutation sends it.

3. Repeat the previous step until repetition would occur. Instead of repeating the element, put a right parenthesis.

4. Repeat this procedure for the remainder of the set on which the permutation is acting.

This procedure yields a permutation written in cycle notation.

The procedure will be demonstrated for the function $f$.

Since the function $f$ acts on $\{1,2,3,4,5,6\}$, $1$ is the first element of this set, and $f(1)\ne 1$, we start by writing:

$$(1$$

Since $f(1)=3$, we put $3$ after $1$:

$$(13$$

Since $f(3)=2$, we put $2$ after $3$:

$$(132$$

Since $f(2)=1$, we put a right parenthesis:

$$(132)$$

In the remainder of the set, $4$ is the the first element. Since $f(4)\ne 4$, $(4$ is added:

$$(132)(4$$

Since $f(4)=6$, we put $6$ after $4$:

$$(132(46$$

Since $f(6)=4$, we put a right parenthesis:

$$(132)(46)$$

The element $5$ is the only one remaining. Since it is fixed (http://planetmath.org/Fixed) by the permutation, it need not be written. Thus, the permutation is $(132)(46)$.

Note that, with this method of denoting permutations, only elements that are not fixed by the permutation are written. Thus, this procedure can be used to denote permutations that act on any set, so long as the number of elements that are not fixed by the permutation is finite. Also, this method of denoting permutations is more concise than the other methods. For these two reasons, this last method is the one that is most often used. The permutation has then been written as a “product” of cycles.

Title	permutation notation
Canonical name	PermutationNotation
Date of creation	2013-03-22 17:27:34
Last modified on	2013-03-22 17:27:34
Owner	Wkbj79 (1863)
Last modified by	Wkbj79 (1863)
Numerical id	8
Author	Wkbj79 (1863)
Entry type	Topic
Classification	msc 05A05
Classification	msc 03-00
Classification	msc 20B99
Related topic	Cycle2
Related topic	CycleNotation