It is well known that every element of $S_n$ can be written as a product of at most $n-1$ transpositions. This theorem is proved in all the books which discuss the permutation groups. But, I find that the following natural question is usually neither discussed nor put in Exercise Section in the book.
Question: Does there always exists an element in $S_n$ which can not be product of $\leq n-2$ transpositions? Can we list the cycle-type of such elements?
The natural guess would be the $n$-cycles in $S_n$ would be the elements which answer the question. But I couldn't prove it. Can you help me? A hint would also be sufficient.
Best Answer
If $\sigma \in S_n$ is a permutation, let $f(\sigma)$ be the number of cycles in the cycle decomposition of $\sigma$, including the 1-cycles as fixed points. Then for any transposition $\tau = (i j)$, we have $f(\sigma\tau)=f(\sigma)\pm 1$, where the sign is $+$ if $i$ and $j$ are in the same cycle in $\sigma$, and $-$ if they are in different cycles in $\sigma$.
From this, and the fact that $f(\mathrm{id}) = n$, it follows that if $\sigma$ is the product of $\le n-2$ transpositions, then $f(\sigma) \ge 2$. Since $f(\text{$n$-cycle}) = 1$, it follows that an $n$-cycle is not the product of $\le n-2$ transpositions.