1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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