Disjoint Cycles Cannot Be Inverses

Question

Here is what I am trying to prove:

The order of an element in $S_n$ in its cycle decomposition is equal to the least common multiple of the order of its constituent cycles.

So, assume that $\sigma \in S_n$ is of order $k$ and in its cycle decomposition; take $\sigma = \tau_1 \tau_2 \dots \tau_p$. Then

$\sigma^k = \tau_1^k \dots \tau_p^k$

or

$e = \tau_1^k \dots \tau_p^k$

I want to conclude that $\tau_i^k = e$ for all $i$, but am unsure how to do this. I figure that it has to do with the $\tau_i$'seach being pairwise disjoint cycles, and so whenever you take a power of $\tau_i$ it won't involve any other the other numbers that aren't already in $\tau_i$, which means it can't cancel with any of the other $\tau_j$'s. However, I am having difficulty making this argument more rigorous.

EDIT 1: It seems that I want to prove something like the following: if $\tau = (a_1~\dots a_p)$ is a $p$-cycle, then $\tau^k$ will only involve $a_1$, $a_2$,...,$a_p$ in a nontrivial way.

EDIT 2:Rob, here is an attempt at filling in the details. Suppose there exists an $i$ such that $\tau_i^k \neq e$, which means that it is not the identity permutation. Therefore, there exists a symbol $x$ such that $\tau_i^k(x) \neq e$. Now, $e = \tau_1^k \dots \tau_p^k$ says that $\tau_1^k \dots \tau_p^k$ is in fact the identity permutation and therefore $(\tau_1^k \circ \dots \circ \tau_i^k \circ \dots \circ \tau_p^k)(x)=x$

But since these permutations are disjoint, we have commutativity, and so

$(\tau_1^k \circ \dots \circ \tau_i^k \circ \dots \circ \tau_p^k)(x) = (\tau_1^k \circ \dots \circ \tau_p^k \circ \tau_i^k)(x) = \tau_1^k(\tau_2^k(\dots \tau_p^k(\tau_i^k(x))\dots))$

Since $\tau_i^k(x)$ doesn't appear in any of the $\tau_j^k$'s, where $j \ne i$, then $\tau_j^k(\tau_i^k(x)) = \tau_i^k(x)$. But this means

$\tau_1^k(\tau_2^k(\dots \tau_p^k(\tau_i^k(x))\dots)) = \tau_i^k(x) = x$,

which is a contradiction.

I feel that I am missing something, that this proof isn't yet rigorous enough.

Another question is, why does $x$ and $\tau_i(x)$ appear in the cyclic permutation $\tau_i$?

PS: When responding, feel free to use something other than tau; that was rather annoying to type.

Answer 1

Hint: if $\tau_i^k \neq e$ for some $i$, then $\tau_i^k(x) \neq x$ for some $x$. But then $x$ and $\tau_i(x)$ appear in the cyclic permutation $\tau_i$ but not in the cyclic permutations $ \tau_j$ for $j \neq i$. So what is $(\tau_1^k\ldots\tau_i^k\ldots \tau_p^k)(x)$?

(To give more detail in the light of your edits: if $\tau = (a_1 \, \ldots \, a_k)$, then the $a_i$ comprise precisely the symbols that are not fixed by $\tau$, i.e., the symbols $y$ for which $\tau(y) \neq y$. If $\tau^k(y) \neq y$ then you must have $\tau(y) \neq y$, so $y$ must be one of the $a_i$. For example, if $n=5$ and $\tau = (2\,5\,4)$, then $\tau(x)$ is equal to $x$ if $x \in \{1, 3\}$, while if $x \in \{2, 4, 5\}$, then so are $\tau(x)$ and $\tau^2(x)$).

Answer 2

Apart from the order, the decomposition into disjoint cycles is unique. We consider equal cycles written as $(123)$ or $(231)$, of course.

Why is this? The expression of a permutation as disjoint cycles encodes the permutation itself: in order to find the image of an element, look for the neighbor on its right (if there's the closing parenthesis, we're bounced back to the start). Cycles of length $1$ are usually omitted, but writing them is not a problem.

So if a permutation admits a cycle of length $>1$, it is not the identity, because at least one element is not fixed.

When we write $\sigma = \tau_1 \tau_2 \dots \tau_p$ as a product of disjoint cycles, we can also consider each $\tau_j$ as a permutation on its own, with the action described above for elements that appear in the cycle and fixing all other elements.

This is what allows us to write $\sigma^k = \tau_1^k \dots \tau_p^k$, which may not be a decomposition as disjoint cycles. However, if an element, say $a$, is moved by $\tau_i^k$ to $b$, this action cannot be undone by another $t_j^k$, because $b$ can only appear in the cycles $\tau_i^k$ decomposes into.

Therefore, in order for $\sigma^k$ to be the identity, each $\tau_i^k$ must be the identity.

There's another method for seeing this. When you want to write down the decomposition of $\sigma$ in disjoint cycles, the algorithm is: write an open parenthesis and start from $1$; write $\sigma(1)$ at its right and continue writing images on the right until you get back to $1$. At this point write the closing parenthesis. Restart from the least element not yet written.

For instance, if $\sigma$ is described by the matrix $$ \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 2 & 4 & 3 & 1 & 6 & 5 & 8 & 7 \end{pmatrix} $$ where the image is sitting below each element, the procedure gives $$ (1\,2\,4)(3)(5\,6)(7\,8) $$ You can apply the same method for computing $\sigma^4$: start from $1$ and go right four steps (bouncing to the beginning of the cycle when ) is found); when you get back to the same element you started the cycle with, write ) and continue with another element, if possible. So you get $$ (1\,2\,4)(3)(5)(6)(7)(8) $$

Therefore, in order that $\sigma^k$ is the identity, each element must be sent to itself, so $k$ must be a multiple of each cycle's length; and any common multiple is good as well, so you find the least common multiple as the order.

Answer 3

If the permutation $f$ is a cycle $(a_1,\ldots,a_k)$, then $f$ has the definition $$f(x)=\left\{\begin{array}{ll}a_{i+1}&\mbox{if }x=a_i\\x&\mbox{otherwise}\end{array}\right.$$ Here $i$ is taken modulo $k$.

Now you can apply this formula directly to see that a product of disjoint cycles of length larger than $1$ is not the identity. Let $$\sigma=\tau_1\cdots\tau_p$$ where the cycles $\tau_i$ are disjoint of length greater than $1$. Pick an element $a$ in $\tau_1$. Then $\tau_i(a)=a$ if $i>1$, and $\tau_1(a)\neq a$. Thus $\sigma(a)=\tau_1(a)\neq a$, so $\sigma$ cannot be the identity.