# A permutation is a product of disjoint transpositions iff its order is $1$ or $2$

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.

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

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

• 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...? – TheNotMe Jan 19 '16 at 21:57
• @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! – Matt Samuel Jan 20 '16 at 2:39

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.

• 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... – TheNotMe Jan 19 '16 at 21:45
• you need them to be disjoint so that they commute with each other. – Jorge Fernández Hidalgo Jan 19 '16 at 21:47
• transpositions are cycles of length $2$. – Jorge Fernández Hidalgo Jan 19 '16 at 21:47

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.