Permutations

The set of all permutations of \(n\) objects forms a group \(S_n\) of order \(n!\). It is called the \(n\)th symmetric group.

A permutation that interchanges \(m\) objects cyclically is called circular permutation or a cycle of degree \(m\). Denote the object by the positive integers. Then the cycle that moves 1 to 2, 2 to 3, \(..., m-1\) to \(m\) and \(m\) to \(1\) is written \((1 2 ... m)\).

Every permutation can be unique represented into cycles operating on disjoint sets.

Example: \((1 2 3 4 5 6)^2 = (1 3 5)(2 4 6)\)

So we may write a given permutation \(P = C_1 ... C_r\) where the \(C_i\) are cycles. Since cycles on disjoint sets commute, we have \(P^m = C_1^m ... C_r^m\), and we see that the order of a permutation is the lowest common multiple of the orders of its component cycles. A permutation is regular if all of its cycle are of the same degree.

Two permutations \(a, b \in S_n\) are conjugate or similar if there exists \(t\in S_n\) with \(b = t^{-1} a t\). Let \(a = C_1 ... C_r\) where the \(C_i\) are cycles. Then the cycle decomposition of \(b\) is obtained by applying \(t\) to the elements inside the brackets of the strings representing each cycle, that is, if \(C_i = (a_1 a_2 ... a_m)\) then \(t^{-1} C_i t = (t(a_1) t(a_2) ... t(a_m))\) where \(t(a_i)\) represents the element \(t\) maps \(a_i\) to.

Let \(a\in S_n\), and write \(a = C_1 ... C_r\) such that the cycles are arranged in non-decreasing order, that is, if we write \(\mu_i\) for the cycle length of \(C_i\), then \(1 \le \mu_1 \le ... \le \mu_r\), and \(\mu_1 +...+\mu_r = n\). Thus every permutation is associated with a partition of \(n\) into positive integers. Two permutations that belong to the same partition are said to belong to the same class of \(S_n\).

It is clear that two permuations of \(S_n\) are conjugate if and only if they belong to the same class.

Now let us count how many partitions belong to a given class. Say a permutation has \(\alpha_i\) cycles of degree \(i\), so that \(\alpha_1 + 2 \alpha_2 + ... + n\alpha_n = n\). Then a set of nonnegative integers \(\{\alpha_1 ,..., \alpha_n\}\) determines a class which we shall denote \(\alpha\). When writing down the cycles, we need to use up \(n\) numbers, and there are \(n!\) ways to do this. But since for any \(i\), we may permute the \(i\)-cycles amongst themselves, we must divide by \(\alpha_1 ! ... \alpha_n !\) times. Lastly, a cycle of length \(i\) can be written in \(i\) different ways, so if \(h_\alpha\) denotes the number of permutations in the class \(\alpha\), we have

[Cauchy].

A 2-cycle is called a transposition.

Let \(x_1,...,x_n\) be indeterminates and consider the product of differences

Then applying a permutation \(\pi \in S_n\) to the variables will either preserve this value or negate it. We write

A permutation \(\pi\) is said to be even if \(\zeta(\pi) = 1\), and odd otherwise, that is, if \(\zeta(\pi) = {-1}\). The function \(\zeta\) is called the alternating character of \(S_n\).

Theorem: Let \(a,b \in S_n\). Then \(\zeta(a b) = \zeta(a)\zeta(b)\).

Proof: Write \(\Delta_\pi\) for \(\Delta(\pi(x_1,...,x_n))\).

Note all permutations of the same class have the same alternating character: by the theorem we have \(\zeta(b) \zeta(b^{-1}) = \zeta(1) = 1\), and \(\zeta(b^{-1}a b) = \zeta(a)\) after applying the theorem again.

Theorem: All transpositions are odd permutations.

Proof: The permutation \((1 2)\) negates the factor \((x_1 - x_2)\) in \(\Delta\) but leaves the other factors unchanged, thus we have \(\zeta((1 2)) = {-1}\). Then the results follows after using the identities

Every permutation \(\pi\) can be written as a product of transpositions, because a cycle \((a_1 ... a_m)\) can be written as \((a_1 a_2)(a_1 a_3) ... (a_1 a_m)\). By the above theorem, the number of transpositions in such a representation is odd or even depending on whether \(\pi\) is odd or even.

Note \(S_n\) can be generated by the \(n-1\) transpositions \((1 2), (1 3),..., (1 n)\).

Theorem: In any group of permutations \(G\), either all or exactly half the elements are even. The even permutations of \(G\) form a subgroup.

Proof: It is clear that the even permutations form a subgroup.

If \(G\) contains no odd permutations, there is nothing to prove. Otherwise let \(q\in G\) be an odd permutation, so that \(\zeta{q} ={-1}\). Then as \(q G = G\), we have

Since \(\zeta\) is multiplicative we have

hence \(\sum \zeta(g) = 0\), proving the result.

The set of all even permutation of degree \(n\) forms a group \(A_n\) of order \(\frac{1}{2} n!\), called the alternating group of degree \(n\).

Since \((1 i)(1 j) = (1 i j)\) for distinct \(1, i, j\), and since \((1 i j) = (1 2 j)(1 2 i)(1 2 j)\) we see that \(A_n\) may be generated from the \(n-2\) 3-cycles

Cayley’s Theorem: Let \(G = \{g_1,...,g_{|G|}\}\) be any group. Each \(g_i \in G\) can be associated with the permutation of \(S_n\) that takes \(g_j\) to \(g_j g_i\). The set of these permutations forms a subgroup \(G'\) of \(S_n\), and \(G' \cong G\).

The permutation group \(G'\) associated with a group \(G\) is called the regular representation of \(G\). In general, if an abstract group \(G\) is isomorphic to some concrete mathematical group (e.g. permutations, matrices) then we say we have a faithful representation of \(G\).

A group of permutations \(G \subset S_n\) is said to be transitive if for every \(\alpha,\beta \in \{1,...,n\}\) there exists \(g\in G\) with \(g(\alpha) = \beta\), that is, for any two objects, there exists a permutation that maps one to the other. Otherwise the group is intransitive.

Example: \(\{(1), (1 2), (3 4), (1 2)(3 4)\}\) is intransitive because no permutations takes 1 to 3. It is isomorphic to the transitive group \(\{ (1), (1 2)(3 4), (1 3)(2 4), (1 4)(2 3) \}\).

Write \(G_\alpha\) for the subgroup of permutations of \(G\) that fix \(\alpha\).

Theorem: A group of permutations \(G \subset S_n\) is transitive if and only if the subgroup \(G_1\) is of index \(n\) relative to \(G\).

Proof: If \(G\) is transitive, then there exists element

that map \(1\) to \(2,3,...,n\) respectively. Consider the sets

The sets are disjoint because each acts differently on the element 1. Futhermore, any \(q \in G\) transforms \(1\) to \(k\), say, hence \(q \in G_1 g_{1 k}\) because \(q g_{1 k}\) leaves 1 unchanged so must lie in \(G_1\). So these disjoint cosets partition \(G\), showing that \(G_1\) has index \(n\) in \(G\).

Conversely, if \(G_1\) has index \(n\), decompose \(G\) into cosets \(G_1 g_1,...,G_1 g_n\). Then if \(g_i , g_j\) transform 1 to the same object \(\alpha\), we have that \(g_i g_j^{-1} \in G_1\), implying that \(G_1 g_i = G_1 g_j\) and hence \(i = j\). Thus we may label the \(g_i\) such that \(g_i(1) = i\).

Lastly, if \(\alpha,\beta \in \{1,...,n\}\) then \(g_\alpha^{-1} g_\beta\) transforms \(\alpha\) into \(\beta\).

Corollary: The order of a transitive groups of permuations of degree \(n\) is divisible by \(n\).

A group of permutations \(G\) is said to be \(k\)-ply transitive if for any sets of size \(k\) \(\{\alpha_1,...,\alpha_k\}, \{\beta_1,...,\beta_k\} \subset \{1,...,n\}\) there exists \(g\in G\) with \(g(\alpha_i) = \beta_i\) for all \(i\).

The number of distinct subsets of size \(k\) in a set of size \(n\) is given by \(n(n-1)...(n-k+1)\). Thus we have:

Theorem: The order of a \(k\)-ply transitive group of degree \(n\) is divisible by \(n(n-1)...(n-k+1)\).

Theorem: The group \(G\) is \(k\)-ply transitive if \(G\) is simply transitive and \(G_1\) is \((k-1)\)-ply transitive with respect to \(\{2,3,...,n\}\).

Let \(G\) be a transitive group in \(S_n\). Suppose it is possible to place \(1,...,n\) in an \(r \times s\) matrix where \(r s = n, r,s> 1\) such that the permutations of \(G\) either permute the objects of any one row amongst themselves or else interchange objects of one row with another. In other words, two objects that start in the same row are never transformed to objects in different rows, and vice versa. Then \(G\) is said to be imprimitive, and the rows are called imprimitive systems. Otherwise \(G\) is said to be primitive. Note all doubly-transitive groups are primitive, and in particular, \(S_n\) is primitive.