I have a set $P$ of permutations of size $s := |P|$.
By repeated application of those permutations I can generate $m$ permutations(or reach $m$ states?) that constitute the set $M$. I am unable to generate the same $m$ permutations with any proper subset of $P$. But I wonder if there is a subset $X$ of $M$ with $|x| < s$ that can generate $M$.

If we were talking about a vector space I could use the Steinitz exchange lemma to proof that there can be no base spanning the wholes space smaller than an existing base with linearly independent vectors. But things are quite different with a permutation group, e.g. the permutations do not commute. How can I prove that my "group base" is minimal?

  • 1
    $\begingroup$ There is no exchange lemma for generating sets of permulation groups. Minimal generating sets need not have the same cardinality. So proving minimality requires arguments on a case by case basis. There are no universally applicable general methods. If you have a particular example you are wondering about you can ask a specific question. $\endgroup$ – Ethan Bolker Aug 1 at 21:28
  • $\begingroup$ @EthanBolker thanks! I've made a specific example: math.stackexchange.com/q/3320160/180934 $\endgroup$ – user2740 Aug 11 at 15:40

Let $n\ge4$. The symmetric group $S_n$ is generated by the $(n-1)$-element set $P=\{(1\ 2),(1\ 3),\dots,(1\ n)\}$ and by no proper subset of $P$, but the $2$-element set $X=\{(1\ 2),(1\ 2\ 3\ \dots n)\}$ also generates $S_n$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.