7
$\begingroup$

Assume that $\sigma \in S_n$ and $\sigma = \alpha_1 \dots\alpha_s$ is the decomposition of $\sigma$ into disjoint cycles, such that all of the members of $\{1,2,\dots,n\}$ are appeared in the members of $\alpha_1, \dots, \alpha_s$.

Is this statement true?

The minimum number of transpositions needed to decompose $\sigma$ is $n-S$.

$\endgroup$
  • $\begingroup$ I'm curious as to where you found this. Do you have any references? Thanks! $\endgroup$ – Sam Nov 27 '17 at 4:00
6
$\begingroup$

It's true because every cycle of length $k$ can be decomposed as the product of $k-1$ transpositions. The way to see that is to observe that $$(1,2,\ldots,k)= (1,2)(2,3)\ldots(k-1,k)$$ which can be checked directly from the formula (each $i$ goes to $i+1$ modulo $k$)

| cite | improve this answer | |
$\endgroup$
9
$\begingroup$

amakelov explains why $n-S$ transpositions are sufficient. To show that $n-S$ transpositions are necessary, one proves that for a permutation $\sigma$ and a transposition $\tau$, $\sigma\tau$ has one more, or one fewer cycle than $\sigma$. As the identity permutation has $n$ cycles, a product of $k$ transpositions has at least $n-k$ cycles. So if $k<n-S$, a product of $k$ transpositions has more than $S$ cycles.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ thanks! totally missed the other direction. that's very neat $\endgroup$ – amakelov Apr 15 '17 at 7:24

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.