2
$\begingroup$

If one is given the length of a permutation and the number of cycles, is it possible to determine the parity of the permutation?

Oddly enough, there's no definition in the text I'm reading for cycle decomposition. I'm assuming it means the permutation $\sigma$ written as a product of disjoint cycles.

I also know a permutation is odd if and only if there are an odd number of even length cycles. (But I know this because of Wikipedia.)

So how does one determine the parity of a permutation?

$\endgroup$
4
$\begingroup$

Yes. If you let $c$ be the number of disjoint cycles in the cycle decomposition, you can find the sign of the permutation as

$$\operatorname{sgn}{\sigma}=(-1)^{n-c},$$

where $n$ is the number of objects you are permuting.

For example, take $(12)(3)$. This swaps $1$ and $2$ and leaves $3$ fixed. We have $n=3$, $c=2$, so we get $(-1)^{3-2}=-1$. The transposition has a negative sign, as expected.

You should be able to prove this by using the criterion you mentioned in your question. For example, if we have 2 cycles and three total elements, exactly one must be even. So the permutation is odd. A similar parity analysis should suffice in the general case.

$\endgroup$
1
$\begingroup$

A transposition is odd, so is any cycle of even length. A cycle of odd length is even, as it can be written as a product of even number of transpositions: it's good to know that $$(1234..n)=(12)(23)(34)..((n-1)n)\,.$$ So, if the disjoint cycle decomposition of a permutation $\sigma$ has even number of cycles of even length, then it is even (${\rm sgn\,}\sigma=+1$), else it is odd (${\rm sgn\,}\sigma=-1$).

$\endgroup$

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.