2 Sets and functions

2.14 Powers and orders

2.14.1 Powers of a permutation

Since the composition of two permutations is another permutation, we can form powers of a permutation by composing it with itself some number of times.

Definition 2.14.1.

Let s be a permutation and let m be an integer. Then

sm={ss(m times)m>0idm=0s1s1(m times)m<0

It’s tedious but straightforward to check that for any integers a, b,

  • sasb=sa+b, and

  • (sa)b=sab

so that some of the usual exponent laws for real numbers hold for composing permutations. The two facts above are called the exponent laws for permutations.

2.14.2 Order of a permutation

Definition 2.14.2.

The order of a permutation σ, written o(σ), is the smallest strictly positive number n such that σn=id.

For example, let

s =(123231)
t =(123213)

You should check that s2id but s3=id, so the order of s is 3, and that tid but t2=id so the order of t is 2.

2.14.3 Order of an m-cycle

Lemma 2.14.1.

The order of an m-cycle is m.

Proof.

Let the m-cycle be a=(a1,,am). If r<m then ar(a1)=ar+1a1, so arid. On the other hand am(a1)=a(am)=a1 and in general am(ai)=ai(ami(ai))=ai(a1)=ai, so am=id. ∎