Group of Permutations

Definition and Notation

A \(\,\) permutation \(\,\) of a finite set \(\,X=\{1,2,\dots,n\}\,\) is a (bijective) mapping from \(\,X\,\) onto itself.

The set of all permutations of the set \(\,\{1,2,\dots,n\}\,\) is denoted by \(\,S_n\,.\)

A convenient way of representing a permutation is the two-line notation:

\[\begin{split}\sigma\ =\ \left(\begin{array}{cccc} 1 & 2 & \dots & n \\ \sigma(1) & \sigma(2) & \dots & \sigma(n) \end{array}\right)\,,\end{split}\]

where in the upper row are listed arguments, and in the lower row the corresponding images.

Arguments may appear in any order, provided that the respective images are attached to them. For example, the following permutation can be written down in 24 equivalent forms:

\[\begin{split}\left(\begin{array}{cccc} 1 & 2 & 3 & 4 \\ 3 & 1 & 2 & 4 \end{array}\right)\ =\ \left(\begin{array}{cccc} 2 & 3 & 4 & 1 \\ 1 & 2 & 4 & 3 \end{array}\right)\ =\ \left(\begin{array}{cccc} 4 & 1 & 2 & 3 \\ 4 & 3 & 1 & 2 \end{array}\right)\ =\ \dots\end{split}\]

Permutations can be composed as mappings: \(\\\) if \(\,\rho,\sigma\in S_n,\ \,\) then the composition \(\,\rho\circ\sigma\,\) is determined by

(1)\[(\rho\circ\sigma)(k)\ =\ \rho\,[\,\sigma(k)\,]\,, \qquad k\in\{1,2,\dots,n\}\,.\]

In the two-line notation the rule reads:

\[ \begin{align}\begin{aligned}\begin{split}\rho\circ\sigma\ =\ \left(\begin{array}{cccc} 1 & 2 & \dots & n \\ \rho(1) & \rho(2) & \dots & \rho(n) \end{array}\right)\ \circ\ \left(\begin{array}{cccc} 1 & 2 & \dots & n \\ \sigma(1) & \sigma(2) & \dots & \sigma(n) \end{array}\right)\ =\end{split}\\\begin{split}=\ \left(\begin{array}{cccc} 1 & 2 & \dots & n \\ \rho\,[\sigma(1)] & \rho\,[\sigma(2)] & \dots & \rho\,[\sigma(n)] \end{array}\right)\,.\end{split}\end{aligned}\end{align} \]

It’s worth pointing out the order of operations: \(\\\) for each number \(\,k\in\{1,2,\dots,n\}\,\) we first determine the image of \(\,k\,\) under permutation \(\,\sigma,\ \) \(\\\) and then the image of the obtained result under permutation \(\,\rho.\ \) For example,

\[ \begin{align}\begin{aligned}\begin{split}\left(\begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 4 & 1 & 3 & 5 & 2 \end{array}\right)\ \circ\ \left(\begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 1 & 3 & 4 \end{array}\right)\ =\ \left(\begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 4 & 3 & 5 \end{array}\right)\,.\end{split}\\\;\end{aligned}\end{align} \]

Theorem 1. \(\,\) The structure \(\ \left(\,S_n,\,\circ\,\right)\ \) is a group \(\ (n\in N).\)

Proof. \(\,\) We shall check the consecutive axioms in the definition of a group.

0. \(\,\) A composition of two permutations in \(\,S_n\,\) is also a permutation belonging to \(\,S_n.\,\)

   \(\,\) Therefore, the composition \(\ \circ\ \) is an internal operation in the set \(\,S_n.\)
1. \(\,\) The composition of permutations, as composition of mappings, is associative.

   \(\,\) Indeed, \(\,\) if \(\,\rho,\sigma,\tau\in S_n,\ \) then for each \(\,k\in\{1,2,\dots,n\}:\)
   \[ \begin{align}\begin{aligned}\left[\,\rho\circ (\sigma\circ\tau )\,\right]\,(k) \ =\ \rho\,\left[\, (\sigma\circ\tau )(k)\,\right] \ =\ \rho\,\{\,\sigma\,\left[\,\tau(k)\,\right]\,\}\,,\\\left[\, (\rho\circ\sigma )\circ\tau\,\right]\,(k) \ =\ (\rho\circ\sigma )\,\left[\,\tau(k)\,\right] \ =\ \rho\,\{\,\sigma\,\left[\,\tau(k)\,\right]\,\}\,.\end{aligned}\end{align} \]

   \(\,\) Consequently, \(\qquad\quad\rho\circ (\sigma\circ\tau )\ =\ ( \rho\circ\sigma )\circ\tau\,,\qquad\forall\ \ \rho,\sigma,\tau\in S_n\,.\)

2. \(\,\) The neutral element for composition is the identity permutation id,

   \(\,\) which maps every element of the set to itself:
   \[\begin{split}\text{id}\ =\ \left(\begin{array}{cccccc} 1 & 2 & 3 & \dots & n \\ 1 & 2 & 3 & \dots & n \end{array}\right)\,.\end{split}\]

   \(\,\) Indeed, it’s easy to verify that \(\quad\sigma\circ\text{id}\ =\ \text{id}\circ\sigma\ =\ \sigma\,,\quad\forall\ \sigma\in S_n.\)

3. Every permutation \(\ \sigma\in S_n\ \) has an inverse \(\ \sigma^{-1}\in S_n\ \) \(\\\) such that \(\ \ \sigma\circ\sigma^{-1}\ =\ \,\sigma^{-1}\circ\,\sigma\ =\ \text{id}\,.\ \) Expressly,

   \[\begin{split}\text{if}\quad \sigma\ =\ \left(\begin{array}{cccccc} 1 & 2 & 3 & \dots & n \\ s_1 & s_2 & s_3 & \dots & s_n \end{array}\right)\,, \quad\text{then}\quad\ \sigma^{-1}\ =\ \left(\begin{array}{cccccc} s_1 & s_2 & s_3 & \dots & s_n \\ 1 & 2 & 3 & \dots & n \end{array}\right)\,. \quad\bullet\end{split}\]

The group \(\ S_n\ \) of permutations is called the symmetric group. \(\\\) It has \(\,n!\,\) elements, \(\,\) and for \(\,n>2\,\) is non-abelian.

In the following we shall omit the symbol \(\ \circ:\) \(\ \ \rho\circ\sigma\ \rightarrow\ \rho\,\sigma\,,\ \) \(\\\) and a composition of permutations shall be called a product of them.

Cyclic Permutations and Parity

A permutation \(\ \sigma\in S_n\ \) is \(\,\) a \(\,\) cycle of length \(\,k\ \) (shortly: a \(\,k\)-cycle) \(\,\) when \(\\\) there exists a subset \(\ Y=\{a_1,a_2,\dots,a_k\}\ \) of the set \(\,X=\{1,2,\dots,n\},\ \) such that

\[ \begin{align}\begin{aligned}\sigma(a_1)=a_2,\quad\sigma(a_2)=a_3,\quad\dots,\quad \sigma(a_{k-1})=a_k,\quad\sigma(a_k)=a_1,\\\text{and}\qquad\sigma(i)=i\qquad\text{for}\qquad i\notin Y\,.\end{aligned}\end{align} \]

The aforementioned subset \(\,Y\,\) is called \(\,\) the \(\,\) orbit \(\,\) of the cycle.

Elements mapped to themselves being omitted, a \(\,k\)-cycle is written in the one-line fashion as \(\ \sigma=(a_1,a_2,\dots,a_k).\ \) Thus, using the two-line notation, a \(\,k\)-cycle reads

\[\begin{split}S_n\,\ni\,(a_1,a_2,\dots,a_k)\ =\ \left(\begin{array}{ccccccccc} a_1 & a_2 & \dots & a_{k-1} & a_k & a_{k+1} & \dots & a_{n-1} & a_n \\ a_2 & a_3 & \dots & a_k & a_1 & a_{k+1} & \dots & a_{n-1} & a_n \end{array}\right)\,.\end{split}\]

Example: \(\quad \left(\begin{array}{cccccc} 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 6 & 4 & 2 & 5 & 3 \end{array}\right)\ =\ \left(\begin{array}{cccccc} 2 & 6 & 3 & 4 & 1 & 5 \\ 6 & 3 & 4 & 2 & 1 & 5 \end{array}\right)\ =\ (2,6,3,4)\,.\)

Instead, the permutation \(\quad \left(\begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 3 & 1 & 2 & 5 & 4 \end{array}\right)\ =\ \left(\begin{array}{ccccc} 1 & 3 & 2 & 4 & 5 \\ 3 & 2 & 1 & 5 & 4 \end{array}\right)\quad\) is not a cycle.

The one-line cycle notation is not unique. A \(\,k\)-cycle may be written in \(\,k\,\) different ways, depending on the choice of the initial element \(\,a_1\,:\)

\[(2,6,3,4)\ =\ (6,3,4,2)\ =\ (3,4,2,6)\ =\ (4,2,6,3)\,.\]

A cycle of length 1 is the identity permutation:

\[S_n\,\ni\,\text{id}\ =\ (1)\ =\ (2)\ =\ \dots\ =\ (n)\,.\]

A cycle of length 2 (i.e. with a 2-element orbit) is called \(\,\) a \(\,\) transposition. \(\,\) An example is

\[\begin{split}S_6\,\ni\,\tau_{25}\ =\ (2,5)\ =\ \left(\begin{array}{cccccc} 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 5 & 3 & 4 & 2 & 6 \end{array}\right)\,.\end{split}\]

Two cycles, \(\ \rho=(a_1,a_2,\dots,a_k),\ \sigma=(b_1,b_2,\dots,b_l)\in S_n\,,\ \) are disjoint when their orbits \(\ Y_{\rho}=\{a_1,a_2,\dots,a_k\},\) \(\ Y_{\sigma}=\{b_1,b_2,\dots,b_l\}\ \) are disjoint sets: \(\ Y_{\rho}\cap Y_{\sigma}=\emptyset\,.\ \,\)

For example, the cycles \(\ (3,6,2)\ \) and \(\ (1,7,4,5)\ \) in the group \(\ S_7\ \) are disjoint, whereas \(\ (4,2,5,1)\ \) and \(\ (3,1,6,2)\ \) are not. It’s worth to notice that a product of two disjoint cycles is commutative: \(\ \rho\,\sigma=\sigma\,\rho\,.\)

Theorem 2. \(\\\) Every permutation can be expressed as a product of disjoint cycles. \(\\\) The expression is unique up to the order of (commuting) factors. 3

Example: \(\quad\left(\begin{array}{cccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 6 & 2 & 4 & 3 & 5 & 9 & 8 & 10 & 1 & 7 \end{array}\right)\ =\ (1,6,9)(3,4)(7,8,10)\,.\)

Proposition 1. \(\\\) A \(\,k\)-cycle can be decomposed into the product of \(\ k-1\ \) transpositions \(\ (k\geq 2):\)

\[(a_1,a_2,a_3,\dots,a_{k-1},a_k)\ \,=\ \, (a_1,a_k)(a_1,a_{k-1})\ \dots\ (a_1,a_3)(a_1,a_2)\,.\]

Note: \(\,\) The order of factors on the right-hand side is relevant!

Corollary 1. \(\\\) Every permutation \(\ \sigma\in S_n,\ n\geq 2,\ \) can be represented as a product of transpositions \(\\\) (such representation is not unique). \(\ \) For example,

\[ \begin{align}\begin{aligned}\begin{split}\left(\begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 4 & 3 & 1 \end{array}\right)\ =\ (1,2,5)(3,4)\ =\end{split}\\=\ (1,5)(1,2)(3,4)\ =\ (1,3)(3,4)(4,5)(2,4)(1,4)\,.\end{aligned}\end{align} \]

Proposition 2. \(\,\) Every transposition \(\,\tau\in S_n,\ n\geq 2,\ \) may be written as a product of an odd number of adjacent transpositions. Namely, for \(\,i<j\,\) we get:

\[\begin{split}\begin{array}{ccc} (i,j) & = & (i,i+1)\,(i+1,i+2)\,\dots\,(j-2,j-1)\,\circ \\ & & \circ\,(j-1,j)\,\circ \\ & & \circ\,(j-1,j-2)\,\dots\,\,(i+2,i+1)\,(i+1,i)\,, \end{array}\end{split}\]

Example. \(\quad (1,4)\ =\ (1,2)\,(2,3)\,(3,4)\,(3,2)\,(2,1)\ =\ (1,2)\,(2,3)\,(3,4)\,(2,3)\,(1,2)\,.\)

Corollary 2. \(\\\) Every permutation \(\,\sigma\in S_n\,,\ n\geq 2,\ \) may be represented as a product of adjacent transpositions (this representation is also not unique).

Proposition 1. and Proposition 2. can be validated by a direct comparison of images of each \(\,k\in\{\,1,\,2,\,\ldots,\,n\}\,\) under permutations in left- and right-hand side of the equation.

As we have pointed out, a decomposition of a given permutation into a product of transpositions is not unique. Nevertheless, the number of factors in every such decomposition is either always even or always odd. In Appendix A5. we prove the following

Theorem 3. \(\\\) Suppose a permutation \(\,\sigma\in S_n\,\) has two different representations as a product of transpositions: \(\ \sigma\ =\ \tau_1\,\tau_2\,\dots\,\tau_r\ =\ \tau'_1\,\tau'_2\,\dots\,\tau'_s\,.\ \) Then both expressions yield the same parity of the number of factors: \(\quad (-1)^r\,=\ (-1)^s\,.\)

Corollary 3. \(\\\) The above theorem makes it possible to define a sign of a permutation as follows:

\[\text{sgn}:\qquad S_n\,\ni\,\sigma\quad\rightarrow \quad\text{sgn}\,\sigma\ :\,=\ (-1)^r\,\in\,\{-1,1\}\,,\]

where \(\,r\,\) is the number of factors in an arbitrary decomposition of the permutation \(\,\sigma\,\) into a product of transpositions. Additionally, we assume that if \(\ \sigma\in S_1\ \) (then \(\,\sigma=\text{id}\)), \(\,\) then by convention \(\,\text{sgn}\,\sigma = +1.\)

A permutation \(\ \sigma\in S_n\ \,\) is \(\,\) even \(\,\) when \(\,\text{sgn}\,\sigma = +1\,,\ \,\) and is \(\,\) odd \(\,\) when \(\,\text{sgn}\,\sigma = -1\,.\)

Permutations in Sage

The Sage command Permutations(n) returns the class of permutations of \(\,n\,\) numbers, written in a one-line notation: \(\\\)

\[\begin{split}\left(\begin{array}{cccccc} 1 & 2 & 3 & \dots & n \\ s_1 & s_2 & s_3 & \dots & s_n \end{array}\right)\quad\sim\quad [\,s_1,\ s_2,\ s_3,\ \ldots,\ s_n\,]\,.\end{split}\]

sage: P3 = Permutations(3)
sage: print P3; P3.list()

Standard permutations of 3
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

In general, the command \(\,\) Permutations() yields the class of permutations of any set:

sage: P = Permutations(['a', 'b', 'c'])
sage: print P; P.list()

Permutations of the set ['a', 'b', 'c']
[['a', 'b', 'c'],
 ['a', 'c', 'b'],
 ['b', 'a', 'c'],
 ['b', 'c', 'a'],
 ['c', 'a', 'b'],
 ['c', 'b', 'a']]

A particular permutation can be extracted by a direct indication or by indexing:

sage: P3 = Permutations(3)
sage: L = P3.list()
sage: p0 = P3([1, 2, 3])
sage: p1 = P3[1]
sage: p2 = L[2]
sage: print L; p0, p1, p2

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
([1, 2, 3], [1, 3, 2], [2, 1, 3])

Given a permutation \(\,p\,\) written in one of the following ways:

• list of integers, viewed as one-line permutation notation,

• string of tuples of integers, expressing the permutation in cycle notation \(\\\) (a 1-cycle may be used to set the size of permutation),

• list of tuples, representing the cycles in cycle notation \(\\\) (a 1-cycle with a comma may be used to set the size of permutation),

the function Permutation() returns \(\,p\,\) as an object of the class of permutations.

sage: p1 = Permutation([4,1,3,5,2])
sage: p2 = Permutation('(1,3)(5)')
sage: p3 = Permutation([(1,4),(5,)])
sage: p4 = Permutation(((1,3,4),(2,5)))

sage: print p1.parent()
sage: print p1
sage: print p2
sage: print p3
sage: print p4

Standard permutations
[4, 1, 3, 5, 2]
[3, 2, 1, 4, 5]
[4, 2, 3, 1, 5]
[3, 5, 4, 1, 2]

There are two conventions, \(\,\) right-to-left \(\,\) and \(\,\) left-to-right, \(\,\) of composing (multiplying) \(\,\) permutations.

A composition may be effectuated by means of the methods left_action_product(), right_action_product() \(\,\) or \(\,\) by the binary multiplication operator \(\,"\ast":\)

• p1.left_action_product(p2) returns the product of \(\,p1\,\) and \(\,p2,\ \) in which \(\,p2\ \) is applied first; this right-to-left convention reflects the principle (1) of composing permutations as mappings;

• p1.right_action_product(p2) returns the product of \(\,p1\,\) and \(\,p2,\ \) in which \(\,p1\ \) is applied first; this left-to-right convention becomes natural if the image of a number \(\,i\,\) under a permutation \(\,p\,\) is written as \(\,i^p\,;\) \(\,\) then \(\ i^{(pq)}=\left(i^p\right)^q\,.\)

• p1*p2 \(\,\) by default yields a product of \(\,p1\,\) and \(\,p2\ \) calculated according to the latter (left-to-right) rule.

The above regulations are illustrated by the following Sage code:

The class of permutations contains several other useful methods 4, of which we shall mention here only a few.

3

See http://math.mit.edu/~mckernan/Teaching/12-13/Spring/18.703/l_5.pdf for a proof.

4

http://doc.sagemath.org/html/en/reference/combinat/sage/combinat/permutation.html