# A problem from Herstein's Abstract algebra

1. Sep 16, 2011

1. The problem statement, all variables and given/known data

if f $\in$ Sn show that there is some positive integer k, depending on f, such that fk=i. (from baby Herstein).

3. The attempt at a solution

Suppose that S={x1,x2,...,xn}. Elements of Sn are bijections from S to S. to show that fk=i it's enough to show that fk(xm)=xm for every m (1<=m<=n)
If f is in Sn, then f may stabilize(not permute) a finite number of elements and permutes the other elements. the elements that are not permuted by f will also be stabilized by fk. (because if f(xs)=xs, then f2(xs)=f(xs)=xs and by induction It's possible to show that fk(xs)=xs). So, for the elements that are not permuted by f we're done.
Now, We can suppose that xp is permuted by f and f(xp)=xq (xp$\neq$xq). if we apply f again, f2 will again permute xp to another member of S and this process of permutation never halts because if finally xp is mapped to something that is not permuted anymore by f, like xs, then fk(xp)=xs and fk(xs)=xs which contradicts the fact that fk is bijective. Since this process never halts and S is a finite set and f is a bijection, then finally after k times (2<=k<=n) fk(xp)=xp (I'm in someway using the pigeonhole principle). this k depends on xp. (It can be shown by studying permutations of Sn for n>2)
It's easy to show that if fk(xp)=xp then fnk(xp)=xp. since k is dependent to the xp we choose, let's associate a ki with every element of S that is permuted. by the same argument we know that fki(xpi)=xpi. if we set K=LCM(ki) then by our previous arguments, It's obvious that for any xp we'll have fK(xp)=xp. Q.E.D.

I come up with this proof after studying permutations in S5. I know that the way I've explained my proof might be a little bit confusing but I hope that it's understandable. Is my proof correct? and if yes, is there any other way to prove it in a simpler way?

2. Sep 16, 2011

### HallsofIvy

Staff Emeritus
Actually, you don't even need to know that this is a group of permutations. This is true for any finite group. Consider the set of all $x^k$ where k is any positive integer. There are an infinite number of possible values for k but only a finite number of possible values for $x^k$. Therefore, by the pigeon hole principle as you say, there must be some values, $k_1$ and $k_2$, with $k_1\ne k_2$ but $x^{k_1}= x^{k_2}$.

We can, without loss of generality, assume that $k_1< k_2$. It follows that $x^{k_2}x^{-k_1}= x^{k_2-k_1}= i$.

3. Sep 16, 2011

I see. so, I had made the problem way harder than It actually was. Was my own proof correct?