Permutation of a set

2020 Mathematics Subject Classification: Primary: 20-XX [MSN][ZBL]

A permutation is a one-to-one mapping of a set onto itself. The term permutation is used mainly for a finite set $X$. In that case it is convenient to assume that $X=\{1,\dots,n\}$ and to write the permutation in the form

$$\def\g{\gamma}\g = \begin{pmatrix}1&\dots&n\\i_1&\dots&i_n\end{pmatrix},\tag{$*$}$$ where $i_1,\dots,i_n$ is a certain permutation of the numbers $1,\dots,n$. The notation (*) means that $\g$ transforms the number $k$ into $i_k$, i.e. $\g(k) = i_k$ (one writes also $k^\g = i_k$) for $i=1,\dots,n$. The number of different permutations of a set $X$ with $|X|=n$ is equal to $n!$. The product of the permutations $\def\a{\alpha}\a$ and $\def\b{\beta}\b$ of a set $X$ is defined as the successive application of the mappings $\a$ and $\b$, and is given by the formula $\a\b(x) = \a(\b(x))$ for all $x\in X$. (In the notation $x^\g$, the expression $x^{\a\b}$ is to be read as $(x^\a)^\b$, i.e. first $\a$, then $\b$.)

The set of all permutations of $X$ forms a group with respect to this multiplication, called the symmetric group. Any subgroup of a symmetric group is called a permutation group.

The symmetric group of permutations of a set $X$ is denoted by $S(X)$, and it contains as a subgroup $SF(X)$, the group consisting of those permutations $\g$ which displace only a finite subset of elements (i.e. $\g(x)\ne x$ only for a finite set of elements $x\in X$). If $X$ is finite and consists of $n$ elements, the symmetric group is denoted by $S_n$.

A transposition is a permutation of $X$ that displaces only two elements $i$ and $j$; it is denoted by $(i,j)$. In $S_n$ there are precisely $n(n-1)/2$ transpositions. Any permutation $\g\in SF(X)$ in $S_n$ can be written as a product of transpositions. In particular, each permutation in $S_n$ is a product of transpositions. A permutation can be written as a product of transpositions in many ways. However, for a given $\g$ the parity of the number of factors in a decomposition of $\g$ into transpositions is independent of the method of decomposing it. A permutation representable as a product of an even number of transpositions is called even, while one that decomposes as a product of an odd number of transpositions is called odd. In $S_n$ there are $n!/2$ even permutations and the same number of odd ones. If a permutation $\g\in S_n$ is written in the form (*), its parity coincides with the parity of the number of inversions in the permutation $i_1,\dots,i_n$, i.e. it is equal to the number of pairs $\{i_k,i_j\}$ such that $k<j$, $i_k>i_j$. A transposition is clearly an odd permutation. Composing a permutation with a single transposition alters the parity of the number of inversions. The product of two even permutations, and also of two odd ones, is an even permutation, while the product of an even and an odd permutation (in either order) is odd. The even permutations constitute a normal subgroup $A(X)$ in the group $SF(X)$, called the alternating group. For $|X|=n$, the subgroup $A(X)$ is denoted by $A_n$.

A cycle of length $l$ is a permutation $\def\s{\sigma}\s$ of a finite set $Y=\{y_1,\dots,y_l\}$ such that

$$\s(y_1) = y_2,\dots,\s(y_{l-1}) = y_l,\s(y_l) = y_1.$$ A finite cycle is denoted by $(y_1,\dots,y_l)$. An infinite cycle is a permutation of a countable set, of the form

$$Y=\{\dots,y_{-2},y_{-1},y_0,y_1,y_2,\dots\}$$ where for any integer $i$, $\s(y_i) = y_{i+1}$. The symbol for an infinite cycle is:

$$(\dots,y_{-2},y_{-1},y_0,y_1,y_2,\dots).$$ A cycle of length 2 is a transposition. The group $S_n$ contains $(n-1)!$ cycles of length $n$. For any permutation $\g$ from $S(X)$ there exists a decomposition of $X$ into non-intersecting subsets such that on each of them $\g$ acts as a cycle. The finite subsets in this decomposition take the form

$$\{x,\g(x),\dots,\g^{l-1}(x)\},$$ where $\g^l(x) = x$, while the infinite ones take the form

$$\{\dots,\g^{-2},\g^{-1},x,\g(x),\g^2(x),\dots\},$$ where $\g^k(x) \ne x$ for $k\ne 0$. The cycles induced by $\g$ on the subsets of the decomposition are called disjoint cycles of the permutation $\g$. For example, $(1,3,4)$ and $(2,5)$ are disjoint cycles of the permutation

$$\g = \begin{pmatrix}1&2&3&4&5\\3&5&4&1&2\end{pmatrix};$$ and $\g$ is written in the form

$$(1,3,4)(2,5)$$ as the product of its disjoint cycles. In general, if $\g$ is not the identity permutation and has only a finite number of cycles of length greater than one, then $\g$ is the product of such cycles. In particular, each non-identity permutation from $SF(X)$ is the product of its disjoint cycles of length greater than one. The order of a permutation $\g$ from $SF(X)$, i.e. the order of the cyclic group $\langle \g\rangle$, is equal to the lowest common multiple of the lengths of its disjoint cycles.

From the disjoint cycles of a given permutation one can obtain the disjoint cycles of any permutation conjugate with it (cf. Conjugate elements). For example, if

$$\g = (a_1,\dots,a_l)\dots(a_j,\dots,a_n)$$ is the product of the disjoint cycles of the permutation $\g$ from $S_n$, if $\def\d{\delta}\d\in S_n$ and if $\d(a_i)=b_i$, $i=1,\dots,n$, then

$$\d\g\d^{-1} = (b_1,\dots,b_l)\dots(b_j,\dots,b_n)$$ is the decomposition of the permutation $\d\g\d^{-1}$ as a product of disjoint cycles. Two permutations of the group $S_n$ are conjugate in $S_n$ if and only if they have the same number of disjoint cycles of each length.

Let $s\in S_n$ and let $k$ be the number of independent cycles of $s$, including cycles of length 1. Then the difference $n-k$ is called the decrement of the permutation $s$. The least number of factors in a decomposition of the permutation $s$ as a product of transpositions coincides with its decrement. The parity of a permutation coincides with the parity of its decrement.

Permutations arose originally in combinatorics in the 18th century. At the end of the 18th century, J.L. Lagrange applied them in his research on the solvability of algebraic equations by radicals. A.L. Cauchy gave much attention to this topic, and was responsible, in particular, for the idea of expressing a permutation as a product of cycles. Research on the group properties of permutations has been carried out by N.H. Abel and, particularly, by E. Galois. See Galois theory and Permutation group.

References

[Ha]	M. Hall, "The theory of groups", Macmillan (1959) MR0103215 Zbl 0084.02202
[Jo]	C. Jordan, "Traité des substitutions et des équations algébriques", Paris (1957) MR0091260 Zbl 0078.01204
[Ko]	A.I. Kostrikin, "Introduction to algebra", Springer (1982) (Translated from Russian) MR0661256 Zbl 0482.00001
[Ku]	A.G. Kurosh, "Higher algebra", MIR (1972) (Translated from Russian) Zbl 0237.13001
[Su]	M. Suzuki, "Group theory", 1–2, Springer (1986) MR0815926 Zbl 0586.20001