Proving the order of a permutation of a finite set
I am going through Gallian's Abstract Algebra and am struggling to understand a proof he gives showing that the order of a permutation of a finite set that is written in disjoint cycle form is the least common multiple of the lengths of the cycles.
There are two major points of contention that I am not understanding, the first of which is an initial claim that a cycle of length $n$ has order $n$. I have looked at proofs of this on this site, but do not follow the logic.
I know for a set $A=\{a_1, a_2, ..., a_n\}$, a permutation $P$ of the set can be written in disjoint cycle form like $(P(a_1), P(a_2), ...P(a_n))$ where $P:{A\to A}$. I also know that an $n$-cycle can be written with any starting value, that is $(a_1,a_2,...,a_n)=(a_2,...,a_n,a_1)$, etc. Finally, I know the identity permutation comes in the form $e=(a_1,a_2,...,a_n)$. I am not sure how to show that $P^n=e$.
With this information, one can imagine two disjoint cycles of lengths $m$ and $n$ and call them $\alpha$ and $\beta$ respectively. Let $L=lcm(m,n)$. Then $\alpha^L=e$ since $L$ is a multiple of $m$, and $m$ is the order of $\alpha$. Similarly, $\beta^L=e$. We'd like to show that $\alpha\beta$ has order $L$.
Since disjoint cycles commute, we can write $(\alpha\beta)^L$ as $\alpha^L\beta^L=ee=e$. From a previous special case of a theorem, we know that if a power of an element yields the idenity, then the order of the element divides the power. So we know the order of $\alpha\beta$, call it $t$, divides $L$
Further, since inverses are unique in groups, we know $\alpha^L=(\beta^L)^{-1}=\beta^{-L}$. Since the cycles are disjoint, no element in $\alpha$ is in $\beta$, and since no power of a disjoint cycle introduces new elements, no element in $\beta^{-L}$ or $\alpha^{L}$ are shared despite their equality. I am confused as to what this means and am not sure how this implies that both most be the identity, and I am not sure why even given this information, we would conclude that $t$ is a multiple of both $m$ and $n$, and thus that $L$ divides $t$ and thus that $L=t$.
As a concrete example, if $m=3, n=4, lcm(m,n)=12$, and $t=24$, then $m$ and $n$ are both divisors of $t$, as is $L$, but 12 is of course not equal to 24.
Any help clearing this issues up would be appreciated.
$\endgroup$ 21 Answer
$\begingroup$There is definitely some confusion here regarding notation for permutations. There are two notations and you seem to have them conflated somewhat.
If you write $P$ as $(P(a_1), P(a_2), \cdots, P(a_n)$) then this is not disjoint cycle form. I will explain what disjoint cycle form is.
If we consider $x$, $P(x)$, $P(P(x))$, and so on, it's fairly straightforward to show that we must eventually get back to $x$, i.e. there exists some $n$ such that $P^n(x) = x$. If we take the minimal such $n$ - i.e. the first time we get back to $x$ - then we call this an $n$-cycle. We write this in cycle notation as $(x, P(x), \cdots, P^{n-1}(x)$). Let's call this cycle $\alpha$ and the elements $\{x, P(x), \cdots, P^{n-1}(x)\}$ the elements of $\alpha$.
If we were to start instead at $P(x)$, then we would get $(P(x), P^2(x), \cdots, P^{n-1}(x), P^n(x))$, and since $P^n(x) = x$, this is the same as $(P(x), P^2(x), \cdots, P^{n-1}(x), x)$. This is why an $n$-cycle can be written with any starting value so long as you keep the order.
If we take $y \in A$ such that $y$ doesn't equal any $P^i(x)$ for any $i$, then we get another cycle $\beta = (y, P(y), \cdots, P^{m-1}(y))$. This is disjoint to our first cycle in the sense that no element of $\alpha$ is an element of $\beta$, and vice versa. (You should check this - show first that $P^i(x)$ never equals $P^j(y)$, for any $i$ or $j$).
If we keep doing this we will eventually use up all the elements of $A$, and get a number of disjoint cycles which include all the elements of $A$. If we call these cycles $\alpha_1, \cdots, \alpha_s$ then we can write $P$ in disjoint cycle notation as $P = \alpha_1 \alpha_2 \cdots \alpha_s$. As you correctly point out, disjoint cycles commute, so it doesn't matter what order we put the cycles in.
In disjoint cycle notation, the identity permutation is $(a_1)(a_2)\cdots(a_n)$ - each element $a_i$ is in its own cycle of order $1$. However there is an easier way to show that an $n$-cycle has order $n$. If we call our $n$-cycle $\alpha$, what does $\alpha^n$ do? It sends $x$ to $P^n(x)$, and similarly it sends $P^i(x)$ to $P^n(P^i(x))$. But we defined $n$ as the least $n$ such that $P^n(x) = x$; applying $P$ to both sides, this also tells us $P^{n+1}(x) = P(x)$, that is, $P^n(P(x)) = P(x)$, and so on, so $P^n(P^i(x)) = P^i(x)$ for all $i$. So $\alpha^n$ is indeed the identity permutation. Further, if $0 < r < n$ then $\alpha^r(x) = P^r(x) \neq x$, so $\alpha^r$ is not the identity and so $n$ is indeed the order of $\alpha$.
Further, since inverses are unique in groups, we know $\alpha^L=(\beta^L)^{-1}=\beta^{-L}$. Since the cycles are disjoint, no element in $\alpha$ is in $\beta$, and since no power of a disjoint cycle introduces new elements, no element in $\beta^{-L}$ or $\alpha^{L}$ are shared despite their equality. I am confused as to what this means and am not sure how this implies that both most be the identity, and I am not sure why even given this information, we would conclude that $t$ is a multiple of both $m$ and $n$, and thus that $L$ divides $t$ and thus that $L=t$.
I think this might be a typo (on the book's part or yours), and should be $\alpha^t=(\beta^t)^{-1}=\beta^{-t}$, where $t$ is the order of $\alpha\beta$. (We already know that $\alpha^L = \beta^L = e$). The point is that since $\alpha$ and $\beta$ are disjoint, $\alpha^t$ and $\beta^{-t}$ are disjoint too, and therefore since they're equal, they must be the identity. This is because we know $\beta^{-t}$ is the identity on the elements of $\alpha$, and $\alpha^t$ is the identity on all the elements of $A$ that are not elements of $\alpha$. Since those two cover the entirety of $A$, $\alpha^t = \beta^{-t}$ must be the identity on all of $A$.
Once we have this, $\alpha^t = \beta^t = e$ implies that $t$ must be a multiple of both $n$ and $m$ - if not, then since $\alpha^t = \alpha^n = e$, we must have $\alpha^{t \mod n} = e$, but $t \mod n < n$, contradicting the fact that the order of $\alpha$ is $n$.
Therefore $t$ is a multiple of the lcm of $n$ and $m$.
$\endgroup$ 2
