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

• – Lord Shark the Unknown Oct 9 '18 at 21:25
• Thank you, I will try to edit – Euler's Disgraced Stepchild Oct 9 '18 at 21:30
• @Euler'sDisgracedStepchild That is a creative name! :-) – xxx--- Jun 9 at 16:09

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

• Thank you. To your point about alpha^t and beta^-t, I understand that they are both equal and disjoint, but to me that seems like two contradictory statements and I am not sure why those two realities would imply that they are the identity. Might you be able to elaborate? – Euler's Disgraced Stepchild Oct 10 '18 at 13:35
• If $\alpha$ is a cyclic permutation of $A$, define $X(\alpha) = \{a \in A: \alpha(a) \neq a\}$, i.e. the set of elements of $A$ which $\alpha$ is not the identity on. Then $\alpha$ and $\beta$ are disjoint iff $X(\alpha) \cap X(\beta) = \emptyset$. If $\alpha = \beta$ and $\alpha$ and $\beta$ are disjoint, this means $X(\alpha) = X(\alpha) \cap X(\alpha) = X(\alpha) \cap X(\beta) = \emptyset$. So $X(\alpha) = \emptyset$, but going back to the definition of $X(\alpha)$, if $X(\alpha) = \emptyset$ then $\alpha(a) = a$ for all $a \in A$, i.e. $\alpha$ is the identity. – Christopher Oct 10 '18 at 14:17