4

I want to find the minimum number of permutations so that all other permutations can be obtained by multiplying the permutations of this set (taken in any quantity). In other words, I am looking for the minmal cardinality of a generating set.

I tried to imagine permutations as matrices in which each row and each column contain only one unit, with all the elements except these units - the zeros. And study the properties of these matrices but I did not succeed. Please help me to find this minimum cardinality. Thank you in advance.

quid
  • 42,135
Lex
  • 369
  • 1
    Huh? Are you asking for a set of generators of the permutation group? – Daniel McLaury Oct 20 '14 at 20:05
  • @DanielMcLaury it is not very clearly expressed but it seems so. More specifically the minimal cardinality of a set of generators is what is asked for. – quid Oct 20 '14 at 20:07

1 Answers1

6

The two permutations $\sigma= (1,\dots, n)$ and $\tau= (1,2)$ generate $S_n$. Since for $n \ge 3$ the group $S_n$ is not cyclic, this is minimal, for $n\ge 3$, and the number you search is $2$. (For $n=1,2$ one suffices.)

To see that this set is a generating set you can proceed like this.

  1. Recall that the set of all transpositions is a generating set.

  2. Derive the set of adjacent transpositions, so of the form $(j, j+1)$, is a generating set.

  3. Note that $\sigma \tau \sigma^{-1} = (2,3)$ and more generally $\sigma^j \tau \sigma^{-j} = (j+1,j+2)$, which implies the claim by 2. (If you do not want to use $\sigma^{-1}$ directly, note that $\sigma^{-1}= \sigma^{n-1}$.)

If you want a more detailed exposition, see these notes on generating sets by Keith Conrad (especially Theorem 2.5 there); also, the first two claims are quite standard and in particular the first should be in most books that discuss permutations.

quid
  • 42,135