2
$\begingroup$

Prove that a permutation in $S_n$ can be written as the product of disjoint transpositions if and only if it is of order $1$ or $2$.

What I did so far:

$\leftarrow$ if $s \in S_n$ is of order $1$ then that means $s=I$ and therefore it can be written as $(11)(22)...(nn)$, which are disjoint transpositions. If it is of order $2$ then it is made up of $1$-cycles and $2$-cycles (since the $lcm$ is the order).

And there is where I had problems. If it is of order $2$ then how can I write it as disjoint transpositions? Also, I am having a hard-time with the other direction.

$\endgroup$
  • $\begingroup$ what do you mean by relatively prime transpositions? $\endgroup$ – Anurag A Jan 19 '16 at 20:41
  • $\begingroup$ Sorry, the word I was looking for is "disjoint" $\endgroup$ – TheNotMe Jan 19 '16 at 20:49
  • 2
    $\begingroup$ $(a \, a)$ is not a transposition. $\endgroup$ – Anurag A Jan 19 '16 at 20:53
2
$\begingroup$

Facts:

  1. Every permutation can be written (essentially uniquely) as a product of disjoint cycles (of different lengths).

  2. The order of a permutation is the lcm of the lengths of those cycles in this representation.

If $\sigma$ is a permutation of order 1 or 2, then $\sigma = c_1 c_2 \ldots c_k$, as a disjoint product of cycles. If one of the lengths of $c_i$ is $>2$, so is the lcm of their orders (it's a multiple of each of those lengths), and so the order of $\sigma$ would be $>2$, which cannot be. So all lengths of cycles $c_i$ are 1 or 2. If all are we have the identity, otherwise a product of disjoint transpositions (we have at least one of order 2). We can leave out the 1-cycles, as is customary.

This is basically the whole argument. The other way round, if $\sigma$ is a product of involutions (at least one non-trivial), the order is clearly 2 (as the lcm of 1's and 2's is just 2).

$\endgroup$
  • $\begingroup$ I understand the cases for order $2$, however, I can not find logic behind order $1$. Suppose $i = s \in S_n$, the identity. How can I write it in terms of disjoint transpositions...? $\endgroup$ – TheNotMe Jan 19 '16 at 21:57
  • $\begingroup$ @TheNotMe the identity is the only element of order 1, and it is the product of 0 transpositions (an empty product). All transpositions in the empty set are disjoint! $\endgroup$ – Matt Samuel Jan 20 '16 at 2:39
0
$\begingroup$

The order of a product of disjoint cycle is the least common multiple of the lengths of the factors.. This is because disjoint cycles commute.

So $(C_1C_2\dots C_n)^k=C_1^kC_2^k\dots C_n^k$. In your case the least common multiple of a bunch of twos is two.

$\endgroup$
  • $\begingroup$ How does that even mention the fact of transpositions being disjoint? I do not see how this can guide me into solving the original question... $\endgroup$ – TheNotMe Jan 19 '16 at 21:45
  • $\begingroup$ you need them to be disjoint so that they commute with each other. $\endgroup$ – Jorge Fernández Hidalgo Jan 19 '16 at 21:47
  • $\begingroup$ transpositions are cycles of length $2$. $\endgroup$ – Jorge Fernández Hidalgo Jan 19 '16 at 21:47
0
$\begingroup$

I will answer without making reference to least common multiple (See Proofwiki Order of Product of Disjoint Permutations) but still making use of that the length of a cycle is equal to its order. Therefore, I do not know any formula for the order of a permutation. I will still be able to answer because I know what the order of a permutation is not.

Proof:

Let $p$ be a permutation in $S_n$. If $p$ is identity, then its order is obviously 1. If $p$ is not identity and a product of disjoint transpositions, then its order is obviously $2$. Conversely, if $p$ has order 1, then $p$ is obviously identity, an empty product of disjoint transpositions. Suppose $p$ has order 2. If $p$ is not a transposition (product of 1 transposition) or a product of disjoint transpositions, then $p$ is:

  1. a product of intersecting transpositions, where we have that not all its transpositions are the same with each other.

  2. $p$ is a cycle of length greater than 2.

  3. $p$ is a product containing a cycle of length greater than 2.

Case 2 contradicts our assumption that $p$ has order 2 because of the length of $p$ is its order, which we know.

In Case 3, while we don't know what the order of $p$ is, we know $p^2 \ne 1$ so the order cannot be 2, another contradiction.

In Case 1, intersecting transpositions will give us a cycle of length greater than 2, which reduces to Case 3. That intersecting transpositions will give us a cycle of length greater than 2 follows from the more general fact that $$(a_1\cdots a_k)=(a_1\cdots a_i)(a_{i}\cdots a_k)$$

Since both that the more general fact in Case 1 and that in Case 2 our deduction the order $p$ is not 2 do not make use of the order of a permutation's being related to a least common multiple, I have proved the result without knowing a formula for the order of a permutation is.

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