In a Russian text, on the topic of Permutation Groups, the author introduces the concept of the decrement of a permutation defined as follows: (Note that this is my translation of the text, so it might be inaccurate):

Definition: The permutation decrement is the difference between the number of moving elements(*) and the number of independent cycles of length $\geq 2$ in the canonical decomposition of the permutation or, equivalently, the difference between the number of all elements of the set and the number of independent cycles (including 1-cycles) in the canonical decomposition of the permutations.

If the decrement is even, then the permutation is called even. Otherwise, the permutation is called odd.

(*) Moving elements are those that are not mapped to themselves by the permutation. I.e. $a$ is a moving element if $a \in \{ a \space | \space \pi (a_i) \neq a_i , \ \space i \in \{1, ... , n\}\}$. I'm not sure of the formal way of referring to such elements.

Coming to the question, I ran a number of searches on the decrement of a permutation but I can't find the term "decrement" used in any of the textbooks I checked (J. Gallian, M. Artin, Vinberg, Allan Clark and others) thus, I'm guessing it is a non-standard translation. Additionally, most texts seem to use other methods of determining the parity of a permutation (counting the number of transpositions). So, does anyone know of the right terminology for this definition and a source of notes on this concept of a "decrement"?


1 Answer 1


A probably more widespread synonym for this notion of "decrement" is "reflection length", because the "decrement" of a permutation $w \in S_n$ is the minimum number of transpositions needed if you want to write $w$ as a product of transpositions (and from the viewpoint of Coxeter groups, transpositions are reflections). See, e.g., arXiv:1202.4765v3 for an example of the use of this concept.

To prove that the "decrement" of $w$ really is this minimum number, you just need two observations:

(1) When you compose a permutation $\sigma$ with a transposition $t_{i, j}$, the resulting permutation $\sigma \circ t_{i, j}$ will either have one fewer cycle than $\sigma$ or one more cycle than $\sigma$. (More precisely: It will have one fewer cycle if $i$ and $j$ belong to different cycles of $\sigma$, and otherwise it will have one more cycle.)

(2) Every $k$-cycle can be written as a composition of $k-1$ transpositions.

Both should be well-known and easy to prove.

As for the word "decrement", I have seen it in a few places, but I am not sure of its provenance and would not be surprised if it arose from confusion. I prefer using "decrement" as a verb for making something smaller (preferrably by $1$).

American texts tend to define the sign of a permutation using its inversions rather than its cycles (and I agree: inversions are cleaner to work with if you don't want to wave hands). And when they do count cycles, they consider the number of cycles rather than $n$ minus this number. This is probably why you aren't seeing the notion of "decrement" too often.


You must log in to answer this question.

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