4
$\begingroup$

Looking at permutations I came up with the following question:

Can you find a permutation $S$ of a set of $n$ elements such that by composing this permutation $n!$ times you will describe all the possible permutations of this set.

i.e, all permutation of a given set can be expressed as a composition of this permutation.

But it's not possible:

Proof: (not sure it's the most straightforward proof)

let $S$ be a permutation, it can be decomposed into disjoint cycles. Finding a permutation S that verify the above constraint would mean that the least common multiple of these cycles is n!.

So at least decompose $S$ into one cycle of $n$ elements, one cycle of $n-1$ etc.

But it's impossible since the cycle are disjoints.


Now, may be instead of looking for a single permutation to generate all permutations, I could look at a composition of permutation that will describe all the permutations of a set.

For example, I would like to find $S_1$ and $S_2$ such that $S_1$, $S_1\circ S_2$, $S_1\circ S_2\circ S_1$ etc. describe all the permutations.

With a set of $3$ elements it's pretty easy to find such $S_1$ and $S_2$:

S1 = 1 2 3  //permute first and second element      2 1 3  S2 = 1 2 3  //permute first and third element      3 2 1 

By composing S1, S1°S2 etc... I get

1 2 3  2 1 3 3 1 2 1 3 2 2 3 1  3 2 1 

My question is, what is the minimum number of permutations for a set of n element that will describe all the set. Is there an easy way to get these permutations?

Thanks in advance.


EDIT:

thanks for your answers I rephrased the question on another question : Question on permutation

  • 0
    Thanks I created a new question, you might want to migrate your answer there ?2011-08-24

3 Answers 3

1

If I understand you correctly, you are looking for elements $\sigma_1, \dots, \sigma_m$ of the symmetric group $S_n$ on $n$ elements such that the sequence $\sigma_1$, $\sigma_1\circ\sigma_2$, $\sigma_1\circ\sigma_2\circ\sigma_3, \dots, \sigma_1\circ\dots\circ\sigma_m$, $\sigma_1\circ\dots\circ\sigma_m\circ\sigma_1$, $\sigma_1\circ\dots\circ\sigma_m\circ\sigma_1\circ\sigma_2, \dots, \sigma_1\circ\dots\circ\sigma_m\circ\sigma_1\circ\dots\circ\sigma_m$, $\sigma_1\circ\dots\circ\sigma_m\circ\sigma_1\circ\dots\circ\sigma_m\circ\sigma_1$, $\sigma_1\circ\dots\circ\sigma_m\circ\sigma_1\circ\dots\circ\sigma_m\circ\sigma_1\circ\sigma_2, \dots$ lists every element of $S_n$ exactly once.

Defining $\tau := \sigma_1\circ\dots\circ\sigma_m$ this list can be written as $\tau^0\circ\sigma_1, \dots, \tau^0\circ\sigma_1\circ\dots\circ\sigma_{m-1}$, $\tau^1\circ\sigma_1, \dots, \tau^1\circ\sigma_1\circ\dots\circ\sigma_{m-1}$, $\tau^2\circ\sigma_1, \dots, \tau^2\circ\sigma_1\circ\dots\circ\sigma_{m-1}, \dots$.

Written like this, you see that if $\tau$ has the order $k$ (also called period), the sequence repeats itself after $\dots, \tau^{k-1}\circ\sigma_1\circ\dots\circ\sigma_{m-1}, \tau^k$. So if you pick an element $\tau$ whose order is maximal in $S_n$, you will get $m$ minimal, as you always have

$m = \frac{|S_n|}{k} = \frac{n!}{k}.$

Now pick elements $\tau_1, \dots, \tau_m$ from the different right cosets of the (cyclic) group $\langle \tau \rangle$ generated by $\tau$, where without loss of generality you may take $\tau_m = \tau$. Then define $\sigma_1 := \tau_1$ and $\sigma_i := \tau_{i-1}^{-1}\circ\tau_i$ for $i = 2,\dots, m$.

It is then not to hard to prove that this sequence $\sigma_1, \dots, \sigma_m$ fulfills your conditions and is as short as possible if the order of $\tau$ is chosen maximal among the elements of $S_n$. (If you want to know this order, ask another question ;-)).

  • 0
    [Landau's function](http://mathworld.wolfram.com/LandausFunction.html) is the maximum order of an element in $S_n$2011-08-24
6

The symmetric group on $n$ symbols is not cyclic when $n>2$ (it's not even abelian). Hence it cannot be generated by a single permutation. However, it can always be generated by two permutations, a transposition $(12)$ and a cycle $(123\ldots n)$.

  • 0
    thanks a lot for your answer, the question is a little bit different, I clarified it.2011-08-24
4

(Disclaimer: I'm writing a somewhat detailed answer, since I noticed this came from SO (and the vocabulary in which the question was formulated). Apologies if it's too long-winded for some.)

If I understand correctly, you have a set S of size n, and you want to look at the set of all possible permutations P(S) of that set.¹

That P(S) is the symmetric group of order n, usually noted $S_n$. You want to find a (minimal) generating set of $S_n$.

A generating set of $S_n$ is the set of all transpositions $σ_{i,j}$, for 1 ≤ i,j ≤ n, where $σ_{i,j}$ is the permutation that swaps i and j and leaves all the other elements unchanged ².

To prove that, you want to show that any permutation can be written as a "product" (composition) of transpositions. You'll find numerous proofs of that around, let me just say the gist of it is to proceed by induction on n. Then, given a permutation p of (n+1) elements, you find a product of transpositions q such that (q ∘ p) (n+1) = (n+1) : then (q∘p) is a permutation of n elements, which by induction hypothesis can be written as a product of transpositions, and from that, you can write p itself as a product of transpositions.

That generating set is not minimal: for example, you easily can reduce it to adjacent transpositions (those transpositions of the form (i,i+1), for 1 ≤ i < n), and still have a generating set.

Nonetheless, this allows us to notice that to prove a set of permutations Π is a generating set of $S_n$, it is enough to prove that any adjacent transposition can be written as a product of permutations in Π.

Let us now take a cycle of maximal length, say (1,2,3,...,n), and a single adjacent transposition, say (1,2). You'll notice that for any 0 ≤ i < (n-1)³:

$(1,2,3,...,n)^i(1,2)(1,2,3,...,n)^{-i}$ = (i+1,i+2)

This is the same reasoning we have applied in the link above to show transpositions can be expressed as a product of adjacent transpositions: you "shift" all elements using the cycle, apply your transposition, and then "de-shift" everything.

So, all adjacent transpositions, and therefore all permutations, can be expressed as a product of a cycle of maximal length and a single adjacent transposition. I'll leave showing that generating set is minimal as an exercise.

¹: You'll notice the contents of S are irrelevant, so that we can denote the elements of S as {1,...,n}, representing the actual elements by their indexation.

²: In cycle notation, this is also noted (i,j). We'll keep using cycle notation henceforth.

³: Here, the exponentiation denotes the iterated composition: $p^i$ means applying i times permutation p.

  • 0
    thanks a lot for your answer, the question is a little bit different, I clarified it.2011-08-24