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.
Best Answer
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$.
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$.