11
$\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$
1
  • $\begingroup$ I'm curious as to where you found this. Do you have any references? Thanks! $\endgroup$
    – Sam
    Nov 27, 2017 at 4:00

3 Answers 3

14
$\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.

$\endgroup$
1
  • $\begingroup$ thanks! totally missed the other direction. that's very neat $\endgroup$
    – amakelov
    Apr 15, 2017 at 7:24
8
$\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$)

$\endgroup$
0
$\begingroup$

$d=n-s$ is called the decrement of the permutation $\sigma$. It not always is equal to the minimal number of transpositions needed to write $\sigma$.

Example. Assume for simplicity $n=2$, i.e., we are in $S_2$. The identity permutation $e=(1)(2)$ is of degree $n=2$, and it has $2$ disjoint cycles. Hence its decrement is $d=2-2=0$. But $e$ cannot be written by zero transpositions.

By definition a transposition is a permutation of type $(ij)$, and hence we have to write, say, $e=(12)(12)$. At least two transpositions are needed. You cannot write, say, $e=e$ and call it transpositions decomposition by zero transpositions because $e$ is not a transposition.

By the way, for this very same reason we in the Fundamental theorem of arithmetic require that the integer $n$ must be greater than $1$ to have a decomposition as a product of primes. For, the equality $1=1$ cannot be interpreted as a product of zero primes.

My students had seen this page and discussed the issue with me. Hence I add this remark here.

$\endgroup$
3
  • $\begingroup$ $e$ is not a transposition, but it can be decomposed onto $0$ transpositions. Denoting a sequence of adjacent transpositions $\tau_1, \tau_2, ..., \tau_n$ as $[\tau_1, \tau_2, ..., \tau_n]$ we can write $e = [\space]$. The result of $[\space]$ is $e$. $\endgroup$
    – Alex C
    Apr 5 at 4:58
  • $\begingroup$ Alex C, I see your point: adding some extra formalism to transpositions decomposition one may write $e=[ ]$ to make sure the formula $n-s$ still holds. The only purpose of this new formalism is to justify $n-s$, and it makes the general definition of transpositions decomposition somewhat more complicated... $\endgroup$ Apr 6 at 16:14
  • $\begingroup$ I am saying that the result of application of $0$ transpositions is the identity permutation, meaning the identity permutation can be decomposed to $0$ transpositions. The only purpose of the formalism was to illustrate that simple statement. $\endgroup$
    – Alex C
    Apr 7 at 3:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .