6

I'm working on the following problem and I've made some promising progress:

Show that for $n>3$, each element of the symmetric group $S_n$ is a product of permutations which have no fixed point. (ie $n$-cycles)

I've figured this out for $n$ even. Heres how you'd do it. Take $n=6$ as an example. Note that $$(1 2 3 4 5 6)^2 = (1 3 5)(2 4 6) = (1 2)(1 3 5 2 4 6)$$

So $$(1 2) = (1 2 3 4 5 6)^2(6 4 2 5 3 1)$$

Now that we've generated one 2-cycle, we can generate all of them in the same way. I'm having trouble getting this idea to work for $n$ odd though. I'm curious to see if anyone else knows how to do it either using this idea or some other idea.

Source: Fall 1996

iYOA
  • 1,388
  • 8
  • 20
  • 2
    It's not just n-cycles. For example, this is untrue when $n=5$. You need to allow things like $(12)(345)$. – Steve D Aug 09 '18 at 02:46
  • 1
    For odd $n\gt1$ you need more than just the $n$-cycles, because the $n$-cycles are even permutations. – bof Aug 09 '18 at 02:51
  • 1
    Oh wow! then my method also works if I can automatically use those as well. I was trying to create elements like $(12)(345)$ through some combination of $n$-cycles. Since $(12)(345) = (13)(12345)$ which means $(12)(345)(54321) = (13)$. – iYOA Aug 09 '18 at 03:12

2 Answers2

2

The subgroup $G\subset S_n$ generated by elements with no fixed points is normal, as $g^h(x) = x$ iff $g(h x) = hx$. Write down an odd such element to prove the result for $n\geq 5$; the case $n = 4$ can be handled directly.

anomaly
  • 25,364
  • 5
  • 44
  • 85
  • 1
    This works for $S_4$ too, since all proper normal subgroups are contained in $A_4$. – Steve D Aug 09 '18 at 03:08
  • I don't get what you mean by $hx$. Is $x$ some element of $Sn$ that we are acting on via $G$? I was thinking you could prove this by using the fact that the conjugate of an element in $S_n$ has the same cycle structure, so it must also be generated by elements with no fixed points. Would that also work? But once you prove this, how do you know that generates the entire group? Do we use the fact that $A_n$ is simple for $n>4$ and then use some strong cayley's theorem/2nd isomorphism ideas? – iYOA Aug 09 '18 at 03:25
  • $S_n$ acts on the set ${1, \dots, n}$ in the obvious way. As for the method of proof, there are many different approaches, but this is about a 1-line proof; don't overcomplicate it. – anomaly Aug 09 '18 at 04:01
2

Recently I showed a stronger statement. if n > 3, then any permutation is the product of a derangement (permutation with no fixed point) and an n-cycle (which is also a derangement). Let $S_n$ permute {1,2,...,n}. First I prove that every permutation is conjugate to a non-successor permutation; i.e., a permutation p such that for no i is p(i)=i+1 (and p(n) is not 1). For n=4, every permutation is conjugate to one of (), (13), (13)(24), (132), and (1432) all of which are non-successor. If n>=5, if p is an n-cycle, select i relatively prime to n and not 1. Then (1 1+i ... 1+(n-1)i) is non-successor. If p has a fixed point, then by induction p|{1,2,...n-1} is in $S_{n-1}$ and is non-successor. Relabel (that is the same as conjugating) {1, ..., n} so that n is the fixed point. Then p|{1,...,n-1}(n) is non-successor. If p contains a transposition, relabel so the transposition is (n-1 n). p|{1,...,(n-2)} by induction is non-successor (if it is in $S_3$, use (132))so p|{1...(n-2)}(n-1 n) is non-successor. If p contains a 3 cycle but no 2-cycle, a similar argument can be made, noting that n in this case has to be >=6. If all cycles of p are 4 or higher, then break p into two chunks of size 4 or higher, express the chunks as non-successor by induction and put them back together. // From this we show that any permutation p is the product of a derangement and an n-cycle. p = x*{1 n n-1 n-2... 2}. For all i, x does not take i into i+1 since it is non-successor (conjugate if necessary). Therefore, multiplying by the n-cycle does not take i into i. Therefore p is the product of a derangement and an n-cycle.

jimvb13
  • 663
  • Awesome! I hope you don't mind me writing my own condensed version of your argument: let $\sigma=(1,2,\cdots,n)$ and let $\rho\in S_n$ be any permutation. If for all $i$ we have $\rho(i)\neq i+1=\sigma(i)$, then $\sigma^{-1}\rho(i)\neq i$ and then $\rho=\sigma(\sigma^{-1}\rho)$ is a product of an $n$-cycle and a derangement. Since cycles and derangements are preserved under conjugation, it's enough to show $\rho$ has this property up to conjugation.... – Steve D Aug 10 '18 at 02:35
  • Consider the cycle decomposition of $\rho$. If there is a maximal "run" like $(\cdots, i, i+1,\cdots, i+k,\cdots)$, then conjugating by $(i,i+k)(i+1,i+k-1)\cdots$ removes this run (it reverses it), so it's no longer a run as long as $k>1$. If $k=1$, then we have a transposition $(i,i+1)$, and conjugation by $(i+1,i+2)$ removes the run [this is where you need $n>2$]. Since there are only a finite number of runs, this process eventually puts $\rho$ in the required form. – Steve D Aug 10 '18 at 02:39