Our first topic introduces a special kind of function; recall from differential calculus that a function is a rule \(f\) which assigns to each value in a set \(A\) exactly one value in a set \(B\text{.}\) We denote this by \(f:A\to B\) and name the sets \(A\) and \(B\) respectively the domain and codomain of \(f\text{.}\) Moreover, if \(a\in A\) is assigned by \(f\) to the value \(b\in B\text{,}\) we write \(b=f(a)\text{.}\)
Definition2.1.1.Permutation.
Suppose \(A\) is a set. Then a function \(\sigma:A\to A\) is a permutation of \(A\) if and only if \(\sigma\) satisfies the following two criteria:
(Surjective/Onto) For each element \(a\in A\text{,}\) there is an element \(a'\in A\) such that \({\sigma(a') = a}\text{.}\)
(Injective/One-to-one) For any elements \(a,b\in A\text{,}\) if \(f(a)=f(b)\) then \(a=b\text{.}\)
Functions which are both one-to-one and onto are also called bijections, so an easier definition of a permutation \(\sigma\) of \(A\) is that \(\sigma\) is a bijection from \(A\) to itself. It is important to note that the definition of a permutation of \(A\) does not require that the set \(A\) be finite. However, we will be considering only finite sets as a rule.
Convention2.1.2.
There are certain sets we will use frequently in our study of permutations, namely the set of letters of the English alphabet and subsets of the natural numbers. For convenience sake, we denote them as follows:
\(\mathcal{E}\) is the set of letters in the English alphabet.
For a finite set \(A\) which is not a subset of \([n]\) for any \(n\text{,}\) we denote the set of all permutations of \(A\) by \(\sym{A}\text{.}\)
Subsection2.1.1One-line and two-line notations
There are several distinct ways of representing permutations which are useful in different situations. The first two are one-line notation and two-line notation.
Definition2.1.3.Two-line notation.
Let \(\sigma\in\sym{A}\) be a permutation of a set \(A=\set{a_1,a_2,\dotsc,a_n}\text{.}\) Then the two-line notation for \(\sigma\) is
There is considerable disagreement in the literature as to whether the symbols in one-line notation should be separated by a comma, a space, or nothing at all. We adopt the convention that permutations listed in one-line notation will have no spaces between symbols for permutations of just a few symbols, but with a space between symbols for longer permutations. For instance,
will be represented by \(\gamma = 10~3~2~9~4~8~7~5~1~6\text{.}\)
Two line notation is especially useful when there is no natural order for the symbols in the set being permuted. For example, if \(A=\set{\clubsuit, \diamondsuit, \heartsuit, \spadesuit, \nabla, \surd, \infty}\text{,}\) then the following is a valid permutation of \(A\text{:}\)
Since the set \(A=\set{\clubsuit, \diamondsuit, \heartsuit, \spadesuit, \nabla, \sqrt{x}, \infty}\) defined above has no clear order, we should not impose one in order to use one-line notation to represent \(\phi\text{.}\)
Checkpoint2.1.5.Permutations of \(\set{1,2,3,4}\).
List all permutations of the set \(\set{1,2,3,4}\) in one-line notation.
Since permutations of a set \(A\) are bijections from \(A\) to \(A\text{,}\) each element of \(\sym{A}\) has the same domain and codomain; thus they can be composed.
Definition2.1.6.Permutation composition.
Suppose \(\sigma,\tau\in S_A\) for some set \(A\text{.}\) Then the composition of \(\tau\) after \(\sigma\) is the function \(\tau\circ\sigma:A\to A\) defined by
for each \(a\in A\text{.}\) Moreover, the composition symbol \(\circ\) will be suppressed, and we will write \(\tau\sigma\) as a product rather than a composition.
Remark2.1.7.Composition order.
We must be careful to always consider permutation multiplication in the correct order. An easy way to remember this is to think of the composition symbol as being pronounced “after”. Then \(\tau\sigma = \tau\after\sigma\) is the permutation which performs \(\tau\) after performing \(\sigma\text{.}\)
We need not prove that the composition of permutations exists and is a function, but we do need to be careful to show that it is a permutation: that is, we must show that if \(\sigma,\tau\in \sym{A}\) for a set \(A\text{,}\) then both \(\tau\sigma,\sigma\tau\in\sym{A}\text{.}\) When an operator (like \(\circ\)) on a set satisfies the property that its output remains in the set, it is a closed operator.
Theorem2.1.8.\(\sym{A}\) is closed under composition.
Let \(A\) be a set and \(\sym{A}\) the set of permutations of \(A\text{,}\) and suppose \(\sigma,\tau\in\sym{A}\text{.}\) Then \(\sigma\after\tau\in\sym{A}\) and \(\tau\after\sigma\in\sym{A}\text{.}\)
Proof.
Let \(\sigma,\tau\in\sym{A}\) for a set \(A\text{.}\) It suffices to show that \(\tau\sigma\in\sym{A}\text{,}\) for then the case \(\sigma\tau\in\sym{A}\) holds by a symmetric argument exchanging the roles of \(\sigma\) and \(\tau\text{.}\)
In order to show that \(\tau\sigma\) is injective, suppose that \(a_1,a_2\in A\) such that \((\tau\sigma)(a_1) = (\tau\sigma)(a_2).\) Then by definition, \(\tau(\sigma(a_1)) = \tau(\sigma(a_2))\text{;}\) but since \(\tau\) is injective, this necessitates that \(\sigma(a_1) = \sigma(a_2)\text{.}\) In turn, since \(\sigma\) is injective, we have that \(a_1 = a_2\text{,}\) and thus have shown that \(a_1=a_2\) whenever \((\tau\sigma)(a_1) = (\tau\sigma)(a_2)\text{.}\) Therefore \(\tau\sigma\) is injective.
In order to show that \(\tau\sigma\) is surjective, let \(a_3\in A\text{.}\) Since \(\tau\) is surjective, there is some \(a_2\in A\) such that \(\tau(a_2) = a_3\text{;}\) likewise, since \(\sigma\) is surjective, there is some \(a_1\in A\) such that \(\sigma(a_1)=a_2\text{.}\) But then
and hence \(a_3\in (\tau\sigma)(A)\text{.}\) Since our selection of \(a_3\) was arbitrary, we have that \(\tau\sigma\) is surjective.
As we have shown \(\tau\sigma\) to be both injective and surjective on \(A\text{,}\) we have establised \(\tau\sigma\in\sym{A}\) as desired.
Closure is only one of the many important properties of the multiplication operator. The next most common property we expect operators to have is the associative property.
Definition2.1.9.Associative multiplication.
Multiplication is associative if and only if \((ab)c = a(bc).\)
Theorem2.1.10.Composition in \(\sym{A}\) is associative.
Let \(A\) be a set, and suppose \(\rho,\sigma,\tau\in\sym{A}\text{.}\) Then
with all equalities justified by the definition of composition.
Since multiplication is associative, we can safely write \(\rho\sigma\tau\) rather than \(\rho(\sigma\tau)\text{,}\) since the product is unique as long as the relative order of the terms is preserved: \(\rho\) must be applied after \(\sigma\text{,}\) which must be applied after \(\tau\text{.}\)
Calculating products of permutations can be a frustrating exercise. Thankfully, there is a simple algorithm to determine the product.
Algorithm2.1.11.Left-multiplication of permutations.
Suppose \(\sigma_1,\sigma_2,\dotsc,\sigma_k\) are permutations of the set \(A=\set{a_1,a_2,\dotsc,a_n}\text{,}\) and further suppose the product \(\sigma_k\circ\sigma_{k-1}\circ\cdots\circ\sigma_2\circ\sigma_1\) is desired.
and suppose we want to determine the product \(\sigma_5\sigma_4\sigma_3\sigma_2\sigma_1\text{.}\) Now write the two-line notation for each permutation in a single column, where the top of the column is the rightmost permutation in the product; in this case, \(\sigma_1\text{.}\) To find the value of \(\sigma_5\sigma_4\sigma_3\sigma_2\sigma_1(1)\text{,}\) for instance, you can trace the output of a permutation into the input of the next permutation, and so on.
This idea will be extended when we talk about cryptography later in Chapter 3.
Subsubsection2.1.2.2Properties of permutation multiplication
Having defined multiplication of permutations, it is natural to consider whether there is a multiplicative identity.
Definition2.1.14.Identity permutation.
Suppose \(A\) is a set, and let \(e_A:A\to A\) be the function such that \(e_A(a)=a\) for each \(a\in A\text{.}\) Then \(e_A\) is the identity permutation on \(A\). When the set \(A\) being permuted is clear by context, the identity permutation will simply be denoted \(e\text{.}\)
Particularly, if \(A=\set{a_1,a_2,\dotsc,a_n}\) is a finite set, then
Having a good algorithm for permutation products inspires us to want to apply the same permutation repeatedly, and so we can define the power of a permutation.
Definition2.1.15.Natural powers of a permutation.
Let \(A\) be a set and \(\sigma\in\sym{A}\text{.}\) Define \(\sigma^0 = e_A\text{,}\) and for each \(k\in\Zp\) define recursively \(\sigma^k = \sigma(\sigma^{k-1})\) to be the kth power of \(\sigma\text{.}\)
Definition2.1.16.Inverse of a permutation.
Suppose \(\sigma,\tau\in\sym{A}\) for some set \(A\text{.}\) Then \(\tau\) is an inverse of \(\sigma\) if and only if \(\sigma\tau = e_A = \tau\sigma\text{.}\)
Theorem2.1.17.Unique inverses.
Suppose \(\rho,\sigma,\tau\in S_A\) such that \(\rho\sigma=e_A=\sigma\rho\) and \(\tau\sigma=e_A=\sigma\tau\text{.}\) Then \(\rho=\tau\text{.}\)
Proof.
If \(\rho\text{,}\)\(\sigma\text{,}\) and \(\tau\) are as hypothesized, then
Having inverses we can extend the definition of powers of permutations to all integer powers: if \(\sigma\in\sym{A}\) for some set \(A\text{,}\) then
\begin{equation*}
\sigma^k = \begin{cases}
e_A, \amp \text{ if }k=0 \\
\sigma\left(\sigma^{k-1}\right), \amp \text{ if }k \gt 0 \\
\left(\sigma^{-1}\right)^{-k}, \amp \text{ if }k \lt 0.
\end{cases}
\end{equation*}
Note that this is exactly analogous to the definition of integer powers of a nonzero real number.
Example2.1.18.Composition is not commutative.
We need to note that composition is not commutative. Generally speaking for \(\sigma,\tau\in\sym{A}\text{,}\)\(\sigma\tau\neq\tau\sigma\text{.}\) To demonstrate, consider the simple permutations \(\tau_1 = 23451\) and \(\tau_2 = 54213\) on the set \([5]\text{.}\)
Figure2.1.19.Permutation products (as a composition) are not commutative.
The color pattern indicates the output of each permutation, so we see \(\tau_2\tau_1 = 42135\text{,}\) but \(\tau_1\tau_2 = 15324\text{.}\)
Subsubsection2.1.2.3Abstract algebra and permutation groups
Definition2.1.20.Groups.
A group \((G,*)\) is a set \(G\) along with a closed associative operation \(*\) which has an identity element \(e_G\) and for which each element \(g\in G\) has a unique inverse \(g^{-1}\in G\text{.}\)
Definition2.1.21.Symmetric Group.
If \(A\) is a set, then \(\sym{A}\) is the symmetric group over \(A\text{,}\) and \(\sym{n}\) is the symmetric group over \(n\) symbols.
The study of group theory was inspired by the work of Lagrange on generalizations of permutation groups. This and many other topics are introduced to undergraduate math majors in their first course in Abstract Algebra, which is almost totally focused on group theory. An important result in group theory is Cayley’s Theorem, which is especially important for those working with groups in an applied setting.
Definition2.1.22.Group isomorphism.
Suppose \((G,*)\) and \((H,\cdot)\) are groups, and suppose there is a bijection \(\phi:G\to H\) such that \(\phi(g_1*g_2) = \phi(g_1)\cdot\phi(g_2)\) for every \(g_1,g_2\in G\text{.}\) Then \(G\) is isomorphic to \(H\) and the bijection \(\phi\) is a group isomorphism.
Theorem2.1.23.Cayley’s Theorem.
Every abstract group is isomorphic to a subgroup of a symmetric group.
Technically, a subgroup hasn’t yet been defined, but it is simply a subset of a group which satisfies the definition of a group under the same operation as its parent group.
Subsection2.1.3Cycles and disjoint cycle decomposition
Having now built all the definitions and theory necessary for an algebraic study of groups, we introduce the preferred notation for writing permutations used by group theorists. Called the disjoint cycle notation, it allows several important characteristics of permutations to be made very visible.
Definition2.1.24.Fixed points and supports of permutations.
Suppose \(a\in A\) and \(\sigma\in S_A\text{.}\) Then \(\sigma\) fixes \(a\), or equivalently \(a\) is a fixed point of \(\sigma\), if and only if \(\sigma(a)=a\text{.}\) These elements are collected into a set
There is an interesting type of permutation whose behavior on its support behaves in a predictable fashion.
Definition2.1.25.Cyclic permutations.
Let \(i_1, i_2, \ldots, i_r\) be distinct integers in \([n]\text{,}\) where \(n\geq r\text{.}\) Suppose \(\alpha\in S_n\) has \(\supp{\alpha} = \set{i_1,i_2,\dotsc,i_r}\) and also that
An interesting result of the definition of cycles is that every \(1\)-cycle is equivalent to the identity: if \(a\in[n]\) and \(\alpha=(a)\text{,}\) then \(\supp{\alpha} = \emptyset\text{,}\) so \(\fix{\alpha}=[n]\) and \(\alpha=e\text{.}\) For this reason it is common to write the identity in \(\sym{n}\) as \((1)\text{.}\)
Checkpoint2.1.26.Behavior of permutation supports.
Suppose \(\alpha\in\sym{N}\) and suppose \(x\in \supp{\alpha}\text{.}\) Prove that \(\alpha(x)\in\supp{\alpha}.\)
Solution.
If \(\alpha\in\sym{N}\) and \(x\in \supp{\alpha}\text{,}\) but we assume towards a contradiction that \(\alpha(x)\in\fix{\alpha}\text{,}\) then we have \(\alpha(x) = \alpha(\alpha(x))\text{,}\) but \(x\neq\alpha(x)\text{;}\) this contradicts that \(\alpha\) is injective! Hence it must be that \(\alpha(x)\in\supp{\alpha}\text{.}\)
Definition2.1.27.Disjoint cycles.
Two cycles \(\alpha\) and \(\beta\) are disjoint if and only if \(\supp{\alpha}\cap\supp{\beta} = \emptyset.\)
While it is not true in the general case, one of the important reasons we consider cyclic permutations is that disjoint cycles commute.
Lemma2.1.28.Disjoint cyclic permutations commute.
Let \(n\in\Zp\text{.}\) If \(\alpha\) and \(\beta\) are disjoint cycles in \(S_n\text{,}\) then \(\alpha\beta=\beta\alpha\text{.}\)
Proof.
Suppose \(\alpha,\beta\in\sym{n}\) are disjoint cycles and \(x\in[n]\text{.}\) First assume \(x\in\supp{\alpha}\text{.}\) Since \(\supp{\alpha}\cap\supp{\beta}=\emptyset\text{,}\) it must be that \(x\in\fix{\beta}\text{.}\) However by Checkpoint 2.1.26 we know \(\alpha(x)\in\supp{\alpha}\text{,}\) so likewise \(\alpha(x)\in\\fix{\beta}\text{.}\) But then
By an analogous argument, if we instead assume \(x\in\supp{\beta}\) then \((\alpha\beta)(x)=(\beta\alpha)(x)\text{.}\)
Since \(\alpha\) and \(\beta\) are disjoint, there is no \(x\in\supp{\alpha}\cap\supp{\beta}\text{.}\) So finally, we assume \(x\in\fix{\alpha}\cap\fix{\beta}\text{;}\) but then obviously
Every permutation in \(\sym{n}\) is either a cycle or a product of disjoint cycles.
Proof.
If \(\sigma\) is the identity, we write \(\sigma=(1)\) and the proof is trivial. Therefore let us suppose \(\sigma\in\sym{n}\) is not the identity, so that \(\supp{\sigma}\neq\emptyset\text{.}\) Then let \(a_1 = \min\supp{\sigma}\text{.}\) Since \([n]\) is finite, the set \(\set{k\in\Zp:\sigma^k(a_1)\neq a_1}\) must be finite; let
But then \(\sigma^{k_1}(a_1) = a_1\text{,}\) or \(\sigma\) is not a permutation! Therefore we can define \(\alpha_1 = (\sigma^{0}(a_1), \sigma^1(a_1), \dotsc, \sigma^{k_1-1}(a_1))\text{,}\) and we have constructed \(\alpha_1\) to be a cyclic permutation.
Proceeding in the same manner, define \(a_j\) to be the mimimal element of \(\supp{\sigma}\) which is not an element of \(\supp{\alpha_i}\) for any \(i\lt j\text{.}\) Then define \(k_j = 1+\max\set{k\in\Zp:\sigma^{k}(a_j)\neq a_j}\) so that \(\alpha_j = (\sigma^{0}(a_j), \sigma^1(a_j), \dotsc, \sigma^{k_j-1}(a_j))\) is a cyclic permutation. Let the set of indices be \(J\text{.}\) By our construction, \(\supp{\alpha_i}\cap\supp{\alpha_j}=\emptyset\) whenever \(i\lt j\text{.}\)
By the finiteness of \([n]\) and the preceding construction, we have \(\sigma=\prod_{j\in J}\alpha_j\) as desired.
Moreover, this decomposition into disjoint cycles can be written uniquely up to the order in which the cycles appear, and the proof of the preceding theorem gives us exactly the method we use to obtain the decomposition.
Example2.1.30.Writing a permutation in disjoint cycle notation.
Consider the permutation \(\sigma\) written in one-line notation as
While cycle notation is useful for many purposes, some find it difficult to multiply permutations written in their cycle decompositions. Remember Remark 2.1.7! Multiplication of permutations is always left composition using “after”. All permutations are applied in right-to-left order.
Example2.1.31.Products of cycles.
Consider the following permutations in \(\sym{8}\text{:}\)
We can compute \(\rho\sigma\tau\) from right to left!
Table2.1.32.Calculating a product of cycles
\(x\)
\(\tau(x)\)
\(\sigma(\tau(x))\)
\(\rho(\sigma(\tau(x)))\)
1
\((2~4~3)(1) = 1\)
\((1~3~5~8~2~4)(1) = 3\)
\((1~2~7~4)(3~5~6~8)(3) = 5\)
2
\((2~4~3)(2) = 4\)
\((1~3~5~8~2~4)(4) = 1\)
\((1~2~7~4)(3~5~6~8)(1) = 2\)
3
\((2~4~3)(1) = 2\)
\((1~3~5~8~2~4)(2) = 4\)
\((1~2~7~4)(3~5~6~8)(3) = 1\)
4
\((2~4~3)(1) = 3\)
\((1~3~5~8~2~4)(3) = 5\)
\((1~2~7~4)(3~5~6~8)(3) = 6\)
5
\((2~4~3)(5) = 5\)
\((1~3~5~8~2~4)(5) = 8\)
\((1~2~7~4)(3~5~6~8)(3) = 3\)
6
\((2~4~3)(6) = 6\)
\((1~3~5~8~2~4)(6) = 6\)
\((1~2~7~4)(3~5~6~8)(6) = 8\)
7
\((2~4~3)(7) = 7\)
\((1~3~5~8~2~4)(7) = 7\)
\((1~2~7~4)(3~5~6~8)(7) = 4\)
8
\((2~4~3)(8) = 8\)
\((1~3~5~8~2~4)(8) = 2\)
\((1~2~7~4)(3~5~6~8)(2) = 7\)
So we write \(\rho\sigma\tau = (1~5~3)(2)(4~6~8~7) = (1~5~3)(4~6~8~7).\)
Checkpoint2.1.33.Calculating products in cycle notation.
From Products of cycles there are six ways to arrange a product of \(\rho\text{,}\)\(\sigma\text{,}\) and \(\tau\text{;}\) find the other five and write them in cycle notation.
Checkpoint2.1.34.Calculating powers using cycle notation.
