A problem from Herstein's Abstract algebra

[AdrianZ]

Homework Statement

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

The Attempt at a Solution

Suppose that S={x₁,x₂,...,x_n}. Elements of S_n are bijections from S to S. to show that f^k=i it's enough to show that f^k(x_m)=x_m for every m (1<=m<=n)
If f is in S_n, 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 f^k. (because if f(x_s)=x_s, then f²(x_s)=f(x_s)=x_s and by induction It's possible to show that f^k(x_s)=x_s). So, for the elements that are not permuted by f we're done.
Now, We can suppose that x_p is permuted by f and f(x_p)=x_q (x_p$\neq$x_q). if we apply f again, f² will again permute x_p to another member of S and this process of permutation never halts because if finally x_p is mapped to something that is not permuted anymore by f, like x_s, then f^k(x_p)=x_s and f^k(x_s)=x_s which contradicts the fact that f^k 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) f^k(x_p)=x_p (I'm in someway using the pigeonhole principle). this k depends on x_p. (It can be shown by studying permutations of S_n for n>2)
It's easy to show that if f^k(x_p)=x_p then f^nk(x_p)=x_p. since k is dependent to the x_p we choose, let's associate a k_i with every element of S that is permuted. by the same argument we know that f^k_i(x_pi)=x_pi. if we set K=LCM(k_i) then by our previous arguments, It's obvious that for any x_p we'll have f^K(x_p)=x_p. Q.E.D.

I come up with this proof after studying permutations in S₅. 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?

 

[HallsofIvy]

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

 

[AdrianZ]

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

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