Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A problem from Herstein's Abstract algebra

  1. Sep 16, 2011 #1
    1. The problem statement, all variables and given/known data

    if f [itex]\in[/itex] 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[itex]\neq[/itex]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. jcsd
  3. Sep 16, 2011 #2


    User Avatar
    Science Advisor

    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 [itex]x^k[/itex] 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 [itex]x^k[/itex]. Therefore, by the pigeon hole principle as you say, there must be some values, [itex]k_1[/itex] and [itex]k_2[/itex], with [itex]k_1\ne k_2[/itex] but [itex]x^{k_1}= x^{k_2}[/itex].

    We can, without loss of generality, assume that [itex]k_1< k_2[/itex]. It follows that [itex]x^{k_2}x^{-k_1}= x^{k_2-k_1}= i[/itex].
  4. Sep 16, 2011 #3
    I see. so, I had made the problem way harder than It actually was. Was my own proof correct?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook