1. Not finding help here? Sign up for a free 30min 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!

Abstract Algebra: Permutations and Disjoint Cycles

  1. Mar 20, 2014 #1
    1. The problem statement, all variables and given/known data

    Theorem 8.1 of Dan Saracino:
    Let f ε S[itex]_{n}[/itex]. Then there exist disjoint cycles f[itex]_{1}[/itex],f[itex]_{2}[/itex]
    .. in S such that f= f[itex]_{1}[/itex]°f[itex]_{2}[/itex]...

    In proving this theorem, it considers a finite group S_n={1,2,..,n} and chooses x_1 ε S_n. Then it defines x_2= f(x_1), x_3=f(x_2) and so on. The part I do not understand is "because S_n is a finite set, the sequence x_1, x_2 , x_3... must have a repetition. So there must be a first element in the sequence which is the same as the previous element. "

    Q: Does a finite set imply that for any sequence of its elements, there HAS to be a repetition?
    Q: If so, why should the FIRST element get repeated?

    2. Relevant equations

    Mentioned above.

    3. The attempt at a solution
    Trying to understand things...
     
  2. jcsd
  3. Mar 20, 2014 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Saying that ##f \in S_n## means f is a 1-1 and onto function from {1,2,...,n} to {1,2,...,n}. So your sequence has to have a repeated element just because the number of choices is finite. Suppose it repeats, so ##x_k=x_l## with k>1. That would mean ##f(x_{k-1})=x_k## and ##f(x_{l-1})=x_l=x_k##. What do you conclude from that?
     
  4. Mar 20, 2014 #3
    x_l = x_k simply imply that f is 1-1.
     
  5. Mar 20, 2014 #4
    When you say "... your sequence has to have a repeated element just because the number of choices is finite", could you please give an example of it? Isn't the sequence {1,2,3} finite despite there being no repetition?
     
  6. Mar 20, 2014 #5

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    You have to keep going. That sequence says f(1)=2, f(2)=3 then next element would be f(3). You have to make a choice for that too.
     
  7. Mar 20, 2014 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Not quite. What would that tell you about ##x_{l-1}## and ##x_{k-1}##?
     
  8. Mar 20, 2014 #7
    If you are taking x_k to be the first index then x_{k-1} is suggesting an element of zero index, but we started off with index 1.
     
  9. Mar 20, 2014 #8
    But why should x_k be the first element? when there can be different representations for the same cycle eg {1,5,7}={7,1,5}, we can't really fix the first element, or can we?
     
  10. Mar 20, 2014 #9

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    You PICK the first element of the cycle. It can be anything. No, this procedure doesn't fix the first element.
     
  11. Mar 20, 2014 #10

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    That's part of it. If the first element is the repeating one, then there is no problem because there is no zero index element to worry about. If the first repetition isn't the first, then what kind of problem do you have?
     
    Last edited: Mar 20, 2014
  12. Mar 20, 2014 #11
    You answered that in your last to last reply. The proof is constructed this way that i pick first element.
    What I was thinking was what if some other element, lying in the middle somewhere, got repeated, but then we can write a representation such that this element becomes the first element.
    So, thank you!
     
  13. Mar 20, 2014 #12

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Part of your original question was a good one. You want to know why some string like, say, S = x1,x2,x3,x4,x5,x3 could not occur; it has a repetitition, but the cycle does not come back to x1. Well, remember that f(.) is 1:1 onto, so look at g = f^(-1), the inverse of f. Using g and starting at the end of the string above we would get x3,x5,x4,x3,x2,x1, and that is where we now have a serious problem: when we get to x3 (from x4) we suddenly have two choices for g(x3); namely x5 and x2. But, g must also be 1:1 and onto, so that could not happen. Therefore, the original string S cannot occur.
     
  14. Mar 22, 2014 #13
    The string S cannot be called a cycle. Its not 1-1, hence it can't have an inverse. Although I understand what you have stated but I think giving the example i.e the string S, would have been enough :smile:
    Thank you!
     
  15. Mar 22, 2014 #14

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    The function f is 1:1 onto, not the string S. The point is that in the example I gave you the element x3 has two pre-images under f, namely x2 and x5, and that cannot happen for a 1:1 onto map f. Therefore, the given string x2 = f(x1), x3 = f(x2), x4 = f(x3), x5 = f(x4), x3 = f(x5)cannot occur: it yields a contradiction. It would be perfectly OK for a cycle such as x2 = f(x1), x3 = f(x2), x1 = f(x3); there would be no contradiction there.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Abstract Algebra: Permutations and Disjoint Cycles
Loading...