# 2.11 Inverses and composition

## 2.11.1 Inverse of a permutation

Permutations are bijections, so by Theorem 2.9.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.11.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.11.2 Composition of permutations

We know by Theorem 2.9.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.11.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 $st$ for their composition instead of $s\circ t$.

## 2.11.3 Composition isn’t commutative

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

###### Example 2.11.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.11.1.

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