Composition of Permutations is not Commutative

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a set.

Let $\map \Gamma S$ denote the set of permutations on $S$.

Let $\pi, \rho$ be elements of $\map \Gamma S$

Then it is not necessarily the case that:

$\pi \circ \rho = \rho \circ \pi$

where $\circ$ denotes composition.


Proof

Proof by Counterexample:

Let $S := \set {1, 2, 3}$.

Let:

\(\displaystyle \pi\) \(:=\) \(\displaystyle \dbinom {1 \ 2 \ 3} {2 \ 3 \ 1}\)
\(\displaystyle \rho\) \(:=\) \(\displaystyle \dbinom {1 \ 2 \ 3} {1 \ 3 \ 2}\)


Then:

\(\displaystyle \pi \circ \rho\) \(=\) \(\displaystyle \dbinom {1 \ 2 \ 3} {2 \ 3 \ 1} \circ \dbinom {1 \ 2 \ 3} {1 \ 3 \ 2}\)
\(\displaystyle \) \(=\) \(\displaystyle \dbinom {1 \ 2 \ 3} {3 \ 2 \ 1}\)


while:

\(\displaystyle \rho \circ \pi\) \(=\) \(\displaystyle \dbinom {1 \ 2 \ 3} {1 \ 3 \ 2} \circ \dbinom {1 \ 2 \ 3} {2 \ 3 \ 1}\)
\(\displaystyle \) \(=\) \(\displaystyle \dbinom {1 \ 2 \ 3} {2 \ 1 \ 3}\)
\(\displaystyle \) \(\ne\) \(\displaystyle \pi \circ \rho\)

$\blacksquare$


Sources