# Prove or disprove: The minimum number of transpositions needed to decompose $\sigma$ is $n-S$.

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

• I'm curious as to where you found this. Do you have any references? Thanks!
– Sam
Nov 27, 2017 at 4:00

## 3 Answers

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.

• thanks! totally missed the other direction. that's very neat Apr 15, 2017 at 7:24

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$)

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

• $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$. Apr 5 at 4:58
• 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... Apr 6 at 16:14
• 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. Apr 7 at 3:46