Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Why is $S_5$ generated by any combination of a transposition and a 5-cycle? Is this true for any prime $p$ (in this case $p=5$)?

share|improve this question

1 Answer 1

up vote 10 down vote accepted

Proposition. $S_n$ is generated by a transposition $\tau=(xy)$ and an $n$-cycle $\sigma$ if and only if $|\rm{i}_x-\rm{i}_y|$ is coprime to $n$, where $\rm{i}_m$ denotes the index of $m$ as a letter in $\sigma$.

Proof. Let $\tau=(xy)$, $\sigma=(x_1x_2\ldots x_n)$, and assume w.l.o.g. that $x=x_a$, $y=x_b$ with $a<b$. We may then relabel $1,\ldots, n\longrightarrow x_1,\ldots ,x_n$, so that $\sigma=(12\ldots n)$ and $\tau=(ab)$. Therefore, it suffices to consider an arbitrary transposition $\tau=(ab)$ with the $n$-cycle $\sigma=(12\ldots n)$. Throughout this proof, take all letters modulo $n$ unless otherwise specified. Set $d=\operatorname{gcd}(n,b-a)$.

We begin with $d=1$. Observing that $\sigma^{k}(i)= i+k$, we see that $\sigma^{b-a}(a)= b$, and thus $\sigma^{b-a}$ is an $n$-cycle $\sigma^{b-a}=(ab\ldots)$. Thus again we may suitably relabel $1,\ldots, n$ so that $\tau=(12),\sigma^{b-a}=(1\ldots n)$. We know that conjugating $\tau$ by $\sigma^{k(b-a)}$ yields the transposition $(k,k+1)$, and it is not difficult to see that $\{(12),(23),\ldots,(n-1,n)\}$ generates $S_n$, so we see that $\langle \tau, \sigma^{b-a}\rangle=S_n$. Because $\operatorname{gcd}(b-a,n)=1$, $\sigma^{b-a}$ generates $\langle \sigma \rangle$, and thus we conclude that $S_n=\langle \tau,\sigma\rangle$.

To prove the converse, we will consider the induced action of $\tau$ and $\sigma$ modulo $d>1$, then apply our observations to find an element of $S_n$ which cannot be in $\langle \tau, \sigma \rangle$.

Define $\theta:\langle \tau,\sigma \rangle\rightarrow S_d$ by $\theta(g)=\theta_g$, where $\theta_g(i)=g(i)\mod d$. We must verify that $\theta$ really is a function, that is, that $\theta_g$ is a well-defined permutation in $S_d$ for every $g\in\langle \tau,\sigma \rangle$. By closure in $S_d$ we have that if $\theta_g$ and $\theta_h$ are well defined, then $\theta_g\theta_h=\theta_{gh}$ is as well, so it suffices to check only $\theta_\tau$ and $\theta_\sigma$. In the former case, the assertion is obvious, as $b\equiv a \pmod{d}$ by definition of $d$ and vice versa. In the latter case, we observe that because $d\mid n$, $$i\equiv j \pmod d \Leftrightarrow i+1\equiv j+1\pmod d.$$ Thus $\theta$ is in fact a function (and, moreover, a homomorphism) into $S_d$.

We now use make use of the assumption that $d>1$. Pick a transposition $(ij)\in S_n$ where $i\not\equiv j \pmod d$. By design, $\theta_{(ij)}$ fails to be well-defined, so we must have that $(ij)$ is not in the domain of $\theta$ - that is $(ij)\notin \langle \tau,\sigma \rangle$. In particular, this means that $\langle \tau,\sigma \rangle$ is proper in $S_n$.

Corollary. $S_n$ is generated by any combination of a transposition and an $n$-cycle if and only if $n$ is prime.

Proof. If $n$ is prime, everything's coprime to $n$. Conversely, let $p$ be a prime factor of $n$ and apply the proposition to $\tau=(12),\sigma=(a_1a_2\ldots a_n)$ with $a_1=1$ and $a_{p+1}=2$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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