2 Sets and functions 2.11 Permutations 2.13 Cycles

2.12 Inverses and composition

2.12.1 Inverse of a permutation

Permutations are bijections, so by Theorem 2.10.1 they have inverse functions. The inverse function to a permutation $\sigma$ undoes what $\sigma$ did, in the sense that if $\sigma(x)=y$ then $\sigma^{-1}(y)=x$ . In two row notation you write $\sigma(x)$ beneath $x$ , so you can get the two row notation for $\sigma^{-1}$ by swapping the rows (and reordering).

Example 2.12.1.

	$\displaystyle\sigma$	$\displaystyle=\begin{pmatrix}1&2&3&4\\ 2&3&4&1\end{pmatrix}$
	$\displaystyle\sigma^{-1}$	$\displaystyle=\begin{pmatrix}2&3&4&1\\ 1&2&3&4\end{pmatrix}=\begin{pmatrix}1&2&3&4\\ 4&1&2&3\end{pmatrix}$

2.12.2 Composition of permutations

We know by Theorem 2.10.2 that the composition of two bijections is a bijection, so the composition of two permutations of a set $X$ is again a permutation of $X$ .

Example 2.12.2.

Let

	$\displaystyle\sigma$	$\displaystyle=\begin{pmatrix}1&2&3\\ 2&1&3\end{pmatrix}$
	$\displaystyle\tau$	$\displaystyle=\begin{pmatrix}1&2&3\\ 1&3&2\end{pmatrix}$

Then $\sigma\circ\tau$ is the function $\{1,2,3\}\to\{1,2,3\}$ whose rule is “do $\tau$ , then do $\sigma$ .” Thus

	$\displaystyle(\sigma\circ\tau)(1)$	$\displaystyle=\sigma(\tau(1))=\sigma(1)=2$
	$\displaystyle(\sigma\circ\tau)(2)$	$\displaystyle=\sigma(\tau(2))=\sigma(3)=3$
	$\displaystyle(\sigma\circ\tau)(3)$	$\displaystyle=\sigma(\tau(3))=\sigma(2)=1$

In two row notation,

\sigma\circ\tau=\begin{pmatrix}1&2&3\\ 2&3&1\end{pmatrix}.

There are several similarities between composing permutations and multiplying nonzero numbers. For example, if $a$ , $b$ , and $c$ are nonzero real number then $a(bc)=(ab)c$ . Furthermore the identity permutation behaves for composition just like the number 1 behaves for multiplication. For each nonzero real number $a$ we have $a\times 1=1\times a=a$ , and for each permutation $s$ we have $s\circ\operatorname{id}=\operatorname{id}\circ s=s$ . Equally, for each nonzero real number $a$ there is another nonzero real number $a^{-1}$ such that $a\times a^{-1}=1=a^{-1}\times a$ , and for each permutation $s$ there is an inverse permutation $s^{-1}$ such that $s\circ s^{-1}=\operatorname{id}=s^{-1}\circ s$ . Because of these similarities we often talk about multiplying two permutations when we mean composing them, and given two permutations $s$ and $t$ we usually write $s t$ for their composition instead of $s\circ t$ .

2.12.3 Composition isn’t commutative

Composition has one big difference with real number multiplication: the order matters.

Example 2.12.3.

With $\sigma$ and $\tau$ as before,

	$\displaystyle\sigma\tau$	$\displaystyle=\begin{pmatrix}1&2&3\\ 2&3&1\end{pmatrix}$
	$\displaystyle\tau\sigma$	$\displaystyle=\begin{pmatrix}1&2&3\\ 3&1&2\end{pmatrix}$

Comparing this to the example in the previous section, $\sigma\tau$ and $\tau\sigma$ are different. Composition of permutations is not commutative in general.

Definition 2.12.1.

Two permutations $s$ and $t$ are said to commute if $st=ts$ .