2

Can someone explain how to multiply two permutations? I cannot get myself to understand. Please be very simple and explain each step.

  • Now what if I wanted to write a permutation as a product of simpler permutations? –  Sep 21 '13 at 08:52
  • Also, there is a definition of order that gives m as the order if sigma^m=(1). How does that work? I thought order was the number of transpositions that a permutation could be written in. –  Sep 21 '13 at 08:57
  • A standard way to do this is to decompose it into orbits. $\sigma$ can be decomposed into $(1, \sigma(1), \ldots, \sigma^n(1))\tau$, where $n$ is the lowest integer such that $\sigma^{n+1}(1) = 1$, and $\tau$ is disjoint from all the members in the first cycle. Now you can decompose $\tau$ the same way, using a member of ${1,\ldots,n}$ which does not appear in the cycle. – zarathustra Sep 21 '13 at 08:57
  • Lost me with the sigma^n(1) –  Sep 21 '13 at 09:00

2 Answers2

7

If you have two permutations displayed in this form: $$\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 4 & 2 & 5 & 1\end{pmatrix}$$ and $$\tau = \begin{pmatrix}1 & 2 & 3 & 4 & 5 \\ 5 & 4 & 3 & 2 & 1\end{pmatrix}$$ you can reorder the columns of $\tau$ so that the first line of $\tau$ matches the second line of $\sigma$, and you obtain $\tau = \begin{pmatrix}3 & 4 & 2 & 5 & 1\\ 3 & 2 & 4 & 1 & 5 \end{pmatrix}$, and $\tau\sigma$ now is described by the first line of $\sigma$ and the last line of $\tau$, i.e $$\tau\sigma = \begin{pmatrix}1 & 2 & 3 & 4 & 5\\3 & 2 & 4 & 1 & 5\end{pmatrix}$$

zarathustra
  • 4,891
5

Permutations are nothing but functions, and their product is nothing but function composition. In more details, a permutation on the set $S=\{1,2,3,\cdots ,n \}$ is, by definition, a function $\sigma:S\to S$ which is a bijection. The product of two such permutations $\sigma $ and $\tau $ is the function composition $\sigma \circ \tau $. Since the composition of bijective functions is a bijection, it follows that $\sigma \circ \tau $ is indeed again a permutation.

A common way to represent permutations is using cycle notation. If you are having difficulties with that I suggest you try youtube to find plenty of videos explaining how it works and compute with examples.

Ittay Weiss
  • 79,840
  • 7
  • 141
  • 236