maths.free › Abstract Algebra › 5. Permutation Groups › Definitions and Notation

Definitions and Notation

In general, the permutations of a set X form a group S_X. If X is a finite set, we can assume X=\{ 1, 2, \ldots, n\}. In this case we write S_n instead of S_X. S_n the symmetric group on n letters The follow

Definitions and Notation

In general, the permutations of a set \(X\) form a group \(S_X\). If \(X\) is a finite set, we can assume \(X=\{ 1, 2, \ldots, n\}\). In this case we write \(S_n\) instead of \(S_X\). \(S_n\) the symmetric group on \(n\) letters The following theorem says that \(S_n\) is a group. We call this group the symmetric group on \(n\) letters.

A subgroup of \(S_n\) is called a permutation group.

Example

Consider the subgroup \(G\) of \(S_5\) consisting of the identity permutation \(\identity\) and the permutations \[\begin{aligned}\sigma & = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 5 & 4 \end{pmatrix} \\ \tau & = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 2 & 1 & 4 & 5 \end{pmatrix} \\ \mu & = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 2 & 1 & 5 & 4 \end{pmatrix}\end{aligned}\]. The following table tells us how to multiply elements in the permutation group \(G\).

\[\begin{aligned}\end{aligned}\]

Remark

Though it is natural to multiply elements in a group from left to right, functions are composed from right to left. Let \(\sigma\) and \(\tau\) be permutations on a set \(X\). To compose \(\sigma\) and \(\tau\) as functions, we calculate \((\sigma \circ \tau)(x) = \sigma( \tau(x))\). That is, we do \(\tau\) first, then \(\sigma\). There are several ways to approach this inconsistency. We will adopt the convention of multiplying permutations right to left. To compute \(\sigma \tau\), do \(\tau\) first and then \(\sigma\). That is, by \(\sigma \tau (x)\) we mean \(\sigma( \tau( x))\). (Another way of solving this problem would be to write functions on the right; that is, instead of writing \(\sigma(x)\), we could write \((x)\sigma\). We could also multiply permutations left to right to agree with the usual way of multiplying elements in a group. Certainly all of these methods have been used.

Example

Permutation multiplication is not usually commutative. Let \[\begin{aligned}\sigma & = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 1 & 2 & 3 \end{pmatrix} \\ \tau & = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \end{pmatrix}\end{aligned}\]. Then \[\begin{aligned}\end{aligned}\], but \[\begin{aligned}\end{aligned}\].

Cycle Notation

The notation that we have used to represent permutations up to this point is cumbersome, to say the least. To work effectively with permutation groups, we need a more streamlined method of writing down and manipulating permutations.

A permutation \(\sigma \in S_X\) is a cycle of length \(k\) if there exist elements \(a_1, a_2, \ldots, a_k \in X\) such that \[\begin{aligned}\sigma( a_1 ) & = a_2 \\ \sigma( a_2 ) & = a_3 \\ & \aatavdots{=} \\ \sigma( a_k ) & = a_1\end{aligned}\] and \(\sigma( x) = x\) for all other elements \(x \in X\). We will write \((a_1, a_2, \ldots, a_k )\) to denote the cycle \(\sigma\). \((a_1, a_2, \ldots, a_k )\) cycle of length \(k\) Cycles are the building blocks of all permutations.

Example

The permutation \[\begin{aligned}\end{aligned}\] is a cycle of length \(6\), whereas \[\begin{aligned}\end{aligned}\] is a cycle of length \(3\).

Not every permutation is a cycle. Consider the permutation \[\begin{aligned}\end{aligned}\]. This permutation actually contains a cycle of length \(2\) and a cycle of length \(4\).

Example

It is very easy to compute products of cycles. Suppose that \[\begin{aligned}\end{aligned}\]. If we think of \(\sigma\) as \[\begin{aligned}\end{aligned}\], and \(\tau\) as \[\begin{aligned}\end{aligned}\], then for \(\sigma \tau\) remembering that we apply \(\tau\) first and then \(\sigma\), it must be the case that \[\begin{aligned}\end{aligned}\], or \(\sigma \tau = (1 \, 3 \, 5 \, 6 )\). If \(\mu = (1 \, 6 \, 3 \, 4)\), then \(\sigma \mu = (1\, 6\, 5\, 2)(3\, 4)\).

Two cycles in \(S_X\), \(\sigma = (a_1, a_2, \ldots, a_k )\) and \(\tau = (b_1, b_2, \ldots, b_l )\), are disjoint if \(a_i \neq b_j\) for all \(i\) and \(j\).

Example

The cycles \((1\, 3\, 5)\) and \((2\, 7 )\) are disjoint; however, the cycles \((1\, 3\, 5)\) and \((3\, 4\, 7 )\) are not. Calculating their products, we find that \[\begin{aligned}(1\, 3\, 5)(2\, 7 ) & = (1\, 3\, 5)(2\, 7 ) \\ (1\, 3\, 5)(3\, 4\, 7 ) & = (1\, 3\, 4\, 7\, 5)\end{aligned}\]. The product of two cycles that are not disjoint may reduce to something less complicated; the product of disjoint cycles cannot be simplified.

Condensed — the full section is in Judson, Abstract Algebra: Theory and Applications.

Transpositions

The simplest permutation is a cycle of length \(2\). Such cycles are called transpositions. Since \[\begin{aligned}\end{aligned}\], any cycle can be written as the product of transpositions, leading to the following proposition.

Example

Consider the permutation \[\begin{aligned}\end{aligned}\]. As we can see, there is no unique way to represent permutation as the product of transpositions. For instance, we can write the identity permutation as \((1 \, 2 )(1 \, 2 )\), as \((1 \, 3 )(2 \, 4 )(1 \, 3 )( 2 \, 4 )\), and in many other ways. However, as it turns out, no permutation can be written as the product of both an even number of transpositions and an odd number of transpositions. For instance, we could represent the permutation \((1 \, 6)\) by \[\begin{aligned}\end{aligned}\] or by \[\begin{aligned}\end{aligned}\], but \((1 \, 6)\) will always be the product of an odd number of transpositions.

Theorem

If a permutation \(\sigma\) can be expressed as the product of an even number of transpositions, then any other product of transpositions equaling \(\sigma\) must also contain an even number of transpositions. Similarly, if \(\sigma\) can be expressed as the product of an odd number of transpositions, then any other product of transpositions equaling \(\sigma\) must also contain an odd number of transpositions.

Proof

Suppose that \[\begin{aligned}\end{aligned}\], where \(m\) is even. We must show that \(n\) is also an even number. The inverse of \(\sigma\) is \(\sigma_m \cdots \sigma_1\). Since \[\begin{aligned}\end{aligned}\], \(n\) must be even by . The proof for the case in which \(\sigma\) can be expressed as an odd number of transpositions is left as an exercise.

In light of , we define a permutation to be even if it can be expressed as an even number of transpositions and odd if it can be expressed as an odd number of transpositions.

Condensed — the full section is in Judson, Abstract Algebra: Theory and Applications.

The Alternating Groups

One of the most important subgroups of \(S_n\) is the set of all even permutations, \(A_n\). \(A_n\) the alternating group on \(n\) letters The group \(A_n\) is called the alternating group on \(n\) letters.

Proposition

The number of even permutations in \(S_n\), \(n \geq 2\), is equal to the number of odd permutations; hence, the order of \(A_n\) is \(n!/2\).

Proof

Let \(A_n\) be the set of even permutations in \(S_n\) and \(B_n\) be the set of odd permutations. If we can show that there is a bijection between these sets, they must contain the same number of elements. Fix a transposition \(\sigma\) in \(S_n\). Since \(n \geq 2\), such a \(\sigma\) exists. Define \[\begin{aligned}\end{aligned}\] by \[\begin{aligned}\end{aligned}\]. Suppose that \(\lambda_{\sigma} ( \tau ) = \lambda_{\sigma} ( \mu )\). Then \(\sigma \tau = \sigma \mu\) and so \[\begin{aligned}\end{aligned}\]. Therefore, \(\lambda_{\sigma}\) is one-to-one. We will leave the proof that \(\lambda_{\sigma}\) is surjective to the reader.

Example

The group \(A_4\) is the subgroup of \(S_4\) consisting of even permutations. There are twelve elements in \(A_4\): \[\begin{aligned}& (1) && (1 \, 2)(3 \, 4) && (1 \, 3)(2 \, 4) && (1 \, 4)(2 \, 3) \\ & (1 \, 2 \, 3) && (1 \, 3 \, 2) && (1 \, 2 \, 4) && (1 \, 4 \, 2) \\ & (1 \, 3 \, 4) && (1 \, 4 \, 3) && (2 \, 3 \, 4) && (2 \, 4 \, 3)\end{aligned}\]. One of the end-of-chapter exercises will be to write down all the subgroups of \(A_4\). You will find that there is no subgroup of order 6. Does this surprise you?

Historical Note

Lagrange first thought of permutations as functions from a set to itself, but it was Cauchy who developed the basic theorems and notation for permutations. He was the first to use cycle notation. Augustin-Louis Cauchy (17891857) was born in Paris at the height of the French Revolution. His family soon left Paris for the village of Arcueil to escape the Reign of Terror. One of the family's neighbors there was Pierre-Simon Laplace (17491827), who encouraged him to seek a career in mathematics. Cauchy began his career as a mathematician by solving a problem in geometry given to him by Lagrange. Cauchy wrote over 800 papers on such diverse topics as differential equations, finite groups, applied mathematics, and complex analysis. He was one of the mathematicians responsible for making calculus rigorous. Perhaps more theorems and concepts in mathematics have the name Cauchy attached to them than that of any other mathematician.

Symbols used here

\lambda

lambda (eigenvalue)
The factor by which an eigenvector is stretched: Av = λv.

A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}

matrix
A rectangular array of numbers; a linear map.

x \in A,\ A \subseteq B

element of, subset
x belongs to A; every element of A is in B.

\sigma,\ s,\ \sigma^2

standard deviation, sample s.d., variance
Typical distance from the mean; its square.

\bar{x},\ \mu

sample mean, population mean
Average of the data; average of the whole population.

y',\ y''

first and second derivative of y
Prime notation for derivatives with respect to x (or t).

imaginary unit
i² = −1.

\leq,\ \geq

less/greater than or equal
Inequalities that allow equality; < and > exclude it.

\neq

not equal
The two sides are different.

\mathbb{N},\ \mathbb{Z},\ \mathbb{Q},\ \mathbb{R},\ \mathbb{C}

number sets
Naturals, integers, rationals, reals, complex numbers.

\blacksquare\ \text{or}\ \square

end of proof (halmos)
Marks the point where the statement has been established.

a \equiv b \pmod n

congruent modulo n
n divides a − b; a and b have the same remainder.

a \mid b,\ \gcd(a,b)

divides, greatest common divisor
b is a multiple of a; the largest number dividing both.

(G, \cdot),\ e,\ g^{-1}

group, identity, inverse
A set with an operation; the do-nothing element; the element that undoes g.

G \cong H,\ G / N

isomorphic, quotient group
Same structure; the group of cosets of a normal subgroup N.

\mathbb{Z}/n\mathbb{Z},\ \mathbb{Z}_n

integers modulo n
The remainders 0…n−1 with clock arithmetic.

Questions people ask

What is a group, in plain words?

A set with one operation that is associative, has an identity, and lets every element be undone. Symmetries of any object form a group — that is where the idea came from.

What is the difference between a ring and a field?

A ring has addition and multiplication that behave like the integers (you cannot always divide); a field is a ring where every non-zero element has a reciprocal, like the rationals or the reals.

የራስዎን ይሞክሩ

Parts of this page are adapted from Judson, Abstract Algebra: Theory and Applications (GFDL 1.3). Condensed and re-explained here; errors are ours.

በ Abstract Algebra

Groups Subgroups, cosets and Lagrange's theorem Cyclic groups and permutation groups Homomorphisms, normal subgroups and quotient groups Rings and fields Galois theory: why the quintic has no formula