
8.1: Permutations

Permutations appear in many different mathematical concepts, and so we give a general introduction to them in this section.

Definition of Permutations.

Given a positive integer $$n \in \mathbb{Z}_{+}$$, a  permutation of an (ordered) list of $$n$$ distinct objects is any reordering of this list.  When describing  the reorderings themselves, though, the nature of the objects involved is more or less irrelevant.  E.g., we can imagine interchanging the second and third items in a list of five distinct objects --- no matter what those items are --- and this defines a particular permutation that can be applied to any list of five objects.

Since the nature of the objects being rearranged (i.e., permuted) is immaterial, it is common to use the integers $$1,2,\ldots,n$$ as the standard list of $$n$$ objects. Alternatively, one can also think of these integers as labels for the items in any list of $$n$$ distinct elements. This gives rise to the following definition.

Definition 8.1.1. A permutation $$\pi$$ of $$n$$ elements is a one-to-one and onto function having the set $$\{1,2,\ldots, n\}$$ as both its domain and codomain.

In other words, a permutation is a function $$\pi:\{1, 2, \ldots, n\} \longrightarrow \{1, 2, \ldots, n\}$$ such that, for every integer $$i \in \{1, \ldots, n\}$$, there exists exactly one integer $$j \in \{1, \ldots, n\}$$ for which $$\pi(j) = i$$.  We will usually denote permutations by Greek letters such as $$\pi$$(pi), $$\sigma$$(sigma), and $$\tau$$(tau). The set of all permutations of  $$n$$ elements is denoted by $$\mathcal{S}_{n}$$ and is typically referred to as the symmetric group of degree $$n$$.  (In particular, the set $$\mathcal{S}_{n}$$ forms a group under function composition as discussed in  Section 8.1.2).

Given a permutation $$\pi \in \mathcal{S}_{n}$$, there are several common notations used for specifying how $$\pi$$ permutes the integers $$1, 2, \ldots, n$$.  The important thing to keep in mind when working with these different notations is that $$\pi$$ is a function defined on the finite set $$\{1, 2, \ldots, n\}$$, with notation being used as a convenient short-hand for keeping track of how $$\pi$$ permutes the elements in this set.

Definition 8.1.2. Given a permutation $$\pi \in \mathcal{S}_{n}$$, denote $$\pi_{i} = \pi(i)$$ for each $$i \in \{1, \ldots, n\}$$. Then the two-line notation for $$\pi$$ is given by the $$2 \times n$$ matrix
$\pi = \begin{pmatrix} 1 & 2 & \cdots & n \\ \pi_{1} & \pi_{2} & \cdots & \pi_{n} \end{pmatrix}.$

In other words, given a permutation $$\pi \in \mathcal{S}_{n}$$ and an integer $$i \in \{1, \ldots, n\}$$, we are denoting the image of $$i$$ under $$\pi$$ by $$\pi_{i}$$ instead of using the more conventional function notation $$\pi(i)$$. Then, in order to specify the image of each integer $$i \in \{1, \ldots, n\}$$ under $$\pi$$, we list these images in a two-line array as shown above. (One can also use so-called one-line notation for $$\pi$$, which is given by simply ignoring the top row and writing $$\pi = \pi_{1}\pi_{2}\cdots\pi_{n}$$.)

It is important to note that, although we represent permutations as $$2 \times n$$ matrices, you should not think of permutations as linear transformations from an $$n$$-dimensional vector space into a two-dimensional vector space.  Moreover, the composition operation on permutation that we describe in Section 8.1.2 below does not correspond to matrix multiplication. The use of matrix notation in denoting permutations is merely a matter of convenience.

Example 8.1.3.  Suppose that we have a set of five distinct objects and that we wish to describe the permutation that places the first item into the second position, the second item into the fifth position, the third item into the first position, the fourth item into the third position, and the fifth item into the fourth position.  Then, using the notation developed above, we have the permutation $$\pi \in \mathcal{S}_{5}$$ such that
$\pi_{1} = \pi(1) = 3, \quad \pi_{2} = \pi(2) = 1, \quad \pi_{3} = \pi(3) = 4, \quad \pi_{4} = \pi(4) = 5, \quad \pi_{5} = \pi(5) = 2.$

In two-line notation, we would write $$\pi$$ as
$\pi = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 1 & 4 & 5 & 2 \end{pmatrix}.$

It is relatively straightforward to find the number of permutations of $$n$$ elements, i.e., to determine cardinality of the set $$\mathcal{S}_{n}$$.  To construct an arbitrary permutation of $$n$$ elements, we can proceed as follows: First, choose an integer $$i \in \{1, \ldots, n\}$$ to put into the first position.  Clearly, we have exactly $$n$$ possible choices.  Next, choose the element to go in the second position.  Since we have already chosen one element from the set $$\{1, \ldots, n\}$$, there are now exactly $$n - 1$$ remaining choices.  Proceeding in this way, we have $$n - 2$$ choices when choosing the third element from the set $$\{1, \ldots, n\}$$, then $$n - 3$$ choices when choosing the fourth element, and so on until we are left with exactly one choice for the $$n^{\rm th}$$ element.  This proves the following theorem.

Theorem 8.1.4.  The number of elements in the symmetric group $$\mathcal{S}_{n}$$ is given by
$|\mathcal{S}_{n}| = n\cdot(n-1)\cdot(n-2)\cdot\,\cdots\,\cdot 3\cdot 2\cdot 1 = n!$

We conclude this section with several examples, including a complete description of the one permutation in $$\mathcal{S}_{1}$$, the two permutations in $$\mathcal{S}_{2}$$, and the six permutations in $$\mathcal{S}_{3}$$. For your own practice, you should (patiently) attempt to list the $$4! = 24$$ permutations in $$\mathcal{S}_{4}$$.

Example 8.1.5.

1. Given any positive integer $$n \in \mathbb{Z}_{+}$$, the identity function $$\mbox{id}:\{1, \ldots, n\} \longrightarrow \{1, \ldots, n\}$$ given by $$\mbox{id}(i) = i$$, $$\forall \ i \in \{1, \ldots, n\}$$, is a permutation in $$\mathcal{S}_{n}$$.  This function can be thought of as the trivial reordering that does not change the order at all, and so we call it the trivial or identity permutation.
2. If $$n = 1$$, then, by Theorem 8.1.4,  $$|\mathcal{S}_{n}| =1! = 1$$.  Thus, $$\mathcal{S}_{1}$$ contains only the identity permutation.
3. If $$n = 2$$, then, by Theorem 8.1.4, $$|\mathcal{S}_{n}| = 2! = 2 \cdot 1 = 2$$.  Thus, there is only one non-trivial permutation $$\pi$$ in $$\mathcal{S}_{2}$$, namely the transformation interchanging the first and the second elements in a list.  As a function, $$\pi(1) = 2$$ and $$\pi(2) = 1$$, and, in two-line notation,

$\pi = \begin{pmatrix} 1 & 2 \\ \pi_{1} & \pi_{2} \end{pmatrix} = \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix}.$

4. If $$n = 3$$, then, by Theorem 8.1.4, $$|\mathcal{S}_{n}| = 3! = 3 \cdot 2 \cdot 1 = 6$$.  Thus, there are five non-trivial permutation in $$\mathcal{S}_{3}$$.

Using two-line notation, we have that
$\mathcal{S}_{3} = \left\{ \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix} \right\}$

Keep in mind the fact that each element in $$\mathcal{S}_{3}$$ is simultaneously both a function and a reordering operation.  E.g., the permutation

$\pi = \begin{pmatrix} 1 & 2 & 3 \\ \pi_{1} & \pi_{2} & \pi_{3} \end{pmatrix} = \begin{pmatrix}1 & 2 & 3\\ 2 & 3 & 1\end{pmatrix}$

can be read as defining the reordering that, with respect to the original list, places the second element in the first position, the third element in the second position, and the first element in the third position. This permutation could equally well have been identified by describing its action on the (ordered) list of letters $$a,b,c$$.  In other words,

$\begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} = \begin{pmatrix} a & b & c \\ b & c & a \end{pmatrix},$

regardless of what the letters $$a, b, c$$ might happen to represent.

Composition of Permutations

Let $$n \in \mathbb{Z}_{+}$$ be a positive integer and $$\pi,\sigma \in \mathcal{S}_{n}$$ be permutations. Then, since $$\pi$$ and $$\sigma$$ are both functions from the set $$\{1,\ldots, n\}$$ to itself, we can compose them to obtain a new function $$\pi \circ \sigma$$ (read as pi after sigma'') that takes on the values

$(\pi \circ \sigma)(1) = \pi(\sigma(1)), \quad (\pi \circ \sigma)(2) = \pi(\sigma(2)), \quad \ldots \quad (\pi \circ \sigma)(n) = \pi(\sigma(n)).$

In two-line notation, we can write $$\pi \circ \sigma$$ as

$\begin{pmatrix} 1 & 2 & \cdots & n \\ \pi(\sigma(1)) & \pi(\sigma(2)) & \cdots & \pi(\sigma(n)) \end{pmatrix} \mbox{ or } \begin{pmatrix} 1 & 2 & \cdots & n \\ \pi_{\sigma(1)} & \pi_{\sigma(2)} & \cdots & \pi_{\sigma(n)} \end{pmatrix} \mbox{ or } \begin{pmatrix} 1 & 2 & \cdots & n \\ \pi_{\sigma_{1}} & \pi_{\sigma_{2}} & \cdots & \pi_{\sigma_{n}} \end{pmatrix}.$

Example 8.1.6.   From $$\mathcal{S}_{3}$$, suppose that we have the permutations $$\pi$$ and $$\sigma$$ given by

$\pi(1) = 2, \ \pi(2) = 3, \ \pi(3) = 1 \sigma(1) = 1, \ \sigma(2) = 3, \ \sigma(3) = 2.$

Then note that

$(\pi \circ \sigma)(1) = \pi(\sigma(1)) = \pi(1) = 2,$
$(\pi \circ \sigma)(2) = \pi(\sigma(2)) = \pi(3) = 1,$
$(\pi \circ \sigma)(3) = \pi(\sigma(3)) = \pi(2) = 3.$

In other words,

$\begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ \pi(1) & \pi(3) & \pi(2) \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}.$

Similar computations (which you should check for your own practice) yield compositions such as

$\begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ \sigma(2) & \sigma(3) & \sigma(1) \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix},$

$\begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ \sigma(1) & \sigma(2) & \sigma(3) \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix},$

and

$\begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ \mbox{id}(2) & \mbox{id}(3) & \mbox{id}(1) \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}.$

In particular, note that the result of each composition above is a permutation, that composition is not a commutative operation, and that composition with $$\mbox{id}$$ leaves a permutation unchanged. Moreover, since each permutation $$\pi$$ is a bijection, one can always construct an inverse permutation $$\pi^{-1}$$ such that $$\pi \circ \pi^{-1} = \mbox{id}$$.  E.g.,

$\begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ \pi(3) & \pi(1) & \pi(2) \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix}.$

We summarize the basic properties of composition on the symmetric group in the following theorem.

Theorem 8.1.7  Let $$n \in \mathbb{Z}_{+}$$ be a positive integer.  Then the set $$\mathcal{S}_{n}$$ has the following properties:

1. Given any two permutations $$\pi, \sigma \in \mathcal{S}_{n}$$, the composition $$\pi \circ \sigma \in \mathcal{S}_{n}$$.
2. (Associativity of Composition) Given any three  permutations $$\pi, \sigma, \tau \in \mathcal{S}_{n}$$, $(\pi \circ \sigma) \circ \tau = \pi \circ (\sigma \circ \tau).$
3. (Identity Element for Composition) Given any permutation $$\pi \in \mathcal{S}_{n}$$, $\pi \circ \mbox{id} = \mbox{id} \circ \pi = \pi.$
4. (Inverse Elements for Composition) Given any permutation $$\pi \in \mathcal{S}_{n}$$, there exists a unique permutation $$\pi^{-1} \in \mathcal{S}_{n}$$ such that $\pi \circ \pi^{-1} = \pi^{-1} \circ \pi = \mbox{id}.$

In other words, the set $$\mathcal{S}_{n}$$ forms a group under composition.

Note that the composition of permutations is not commutative in general. In particular, for $$n \geq 3$$, it is easy to find permutations $$\pi$$ and $$\sigma$$ such that $$\pi\circ\sigma\neq \sigma\circ\pi$$.

Inversions and the sign of a permutation

Let $$n \in \mathbb{Z}_{+}$$ be a positive integer. Then, given a permutation $$\pi \in \mathcal{S}_{n}$$, it is natural to ask how out of order'' $$\pi$$ is in comparison to the identity permutation. One method for quantifying this is to count the number of so-called inversion pairs in $$\pi$$ as these describe pairs of objects that are out of order relative to each other.

Definition 8.1.8. Let $$\pi \in \mathcal{S}_{n}$$ be a permutation. Then an inversion pair $$(i, j)$$ of $$\pi$$ is a pair of positive integers $$i, j \in \{1, \ldots, n\}$$ for which $$i < j$$ but $$\pi(i) > \pi(j)$$. Note, in particular, that the components of an inversion pair are the positions where the two out of order'' elements occur.

Example 8.1.9.  We classify all inversion pairs for elements in $$\mathcal{S}_{3}$$:

• $$\mbox{id} = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix}$$ has no inversion pairs since no elements are out of order''.
• $$\pi = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix}$$ has the single inversion pair $$(2, 3)$$ since $$\pi(2) = 3 > 2 = \pi(3)$$.
• $$\pi = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}$$ has the single inversion pair $$(1, 2)$$ since $$\pi(1) = 2 > 1 = \pi(2)$$.
• $$\pi = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}$$ has the two inversion pairs $$(1, 3)$$ and $$(2, 3)$$ since we have that both $$\pi(1) = 2 > 1 = \pi(3)$$ and $$\pi(2) = 3 > 1 = \pi(3)$$.
• $$\pi = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix}$$ has the two inversion pairs $$(1, 2)$$ and $$(1, 3)$$ since we have that both $$\pi(1) = 3 > 1 = \pi(2)$$ and $$\pi(1) = 3 > 2 = \pi(3)$$.
• $$\pi = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix}$$ has the three inversion pairs $$(1, 2)$$, $$(1, 3)$$, and $$(2, 3)$$, as you can check.

Example 8.1.10. As another example, for each $$i, j \in \{1, \ldots, n\}$$ with $$i < j$$, we define the transposition $$t_{i j} \in \mathcal{S}_{n}$$ by
$t_{i j} = \begin{pmatrix} 1 & 2 & \cdots & i & \cdots & j & \cdots & n \\ 1 & 2 & \cdots & j & \cdots & i & \cdots & n \\ \end{pmatrix}.$

In other words, $$t_{i j}$$ is the permutation that interchanges $$i$$ and $$j$$ while leaving all other integers fixed in place. One can check that the number of inversions pairs in $$t_{i j}$$ is exactly $$2(j - i) - 1$$. Thus, the number of inversions in a transposition is always odd.  E.g.,

$t_{1 3}=\begin{pmatrix}1 & 2 & 3 & 4 \\ 3 & 2 & 1 & 4\end{pmatrix}$

has inversion pairs $$(1, 2)$$, $$(1, 3)$$, and $$(2, 3)$$.

For the purposes of using permutations in Linear Algebra, the significance of inversion pairs is mainly due to the following fundamental definition.

Definition 8.1.11.  Let $$\pi \in \mathcal{S}_{n}$$ be a permutation. Then the sign of $$\pi$$, denoted by $$\mbox{sign}(\pi)$$, is defined by

$\mbox{sign}(\pi) = (-1)^{\# \; {\rm of} \; {\rm inversion} \; {\rm pairs} \; {\rm in} \; \pi} = \begin{cases} +1, & \mbox{if the number of inversions in } \pi \mbox{ is even} \\ -1, & \mbox{if the number of inversions in } \pi \mbox{ is odd} \\ \end{cases}.$

We call $$\pi$$ an even permutation if $$\mbox{sign}(\pi) = +1$$, whereas $$\pi$$ is called an odd permutation if $$\mbox{sign}(\pi) = -1$$.

Example 8.1.12.  Based upon the computations in Example 8.1.9 above, we have that

$\mbox{sign} \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix} = \mbox{sign} \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} = \mbox{sign} \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} = +1$

and that

$\mbox{sign} \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix} = \mbox{sign} \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix} = \mbox{sign} \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix} = -1.$

Similarly, from Example 8.1.10, it follows that any transposition is an odd permutation.

We summarize some of the most basic properties of the sign operation on the symmetric group in the following theorem.

Theorem 8.1.13.

Let $$n \in \mathbb{Z}_{+}$$ be a positive integer. Then,

1. for $$\mbox{id} \in \mathcal{S}_{n}$$ the identity permutation,  $\mbox{sign}(\mbox{id}) = +1.$
2. for $$t_{i j} \in \mathcal{S}_{n}$$ a  transposition with $$i, j \in \{1, \ldots, n\}$$ and $$i < j$$,

\mbox{sign}(t_{i j}) = -1.
\label{eqn:sign_transposition} \tag{8.1.1}

3. given any two permutations $$\pi, \sigma \in \mathcal{S}_{n}$$,

\begin{eqnarray}
\mbox{sign}(\pi\circ\sigma) & = & \mbox{sign}(\pi)\,\mbox{sign}(\sigma)
\label{eqn:sign_product}, \tag{8.1.2}\\
\mbox{sign}(\pi^{-1})       & = & \mbox{sign}(\pi).
\label{eqn:sign_inverse} \tag{8.1.3}
\end{eqnarray}

4. the number of even permutations in $$\mathcal{S}_{n}$$, when $$n \geq 2$$, is exactly $$\frac{1}{2}n!$$.

5. the set $$A_{n}$$ of even permutations in $$\mathcal{S}_{n}$$ forms a group under composition.

Contributors

Both hardbound and softbound versions of this textbook are available online at WorldScientific.com.