Results 1 to 5 of 5

Math Help - r-cycle proof

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    r-cycle proof

    If alpha is an r-cycle, show that alpha^r = (1)

    Can someone show this? Thanks in advance
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21

    Re: r-cycle proof

    Quote Originally Posted by jzellt View Post
    If alpha is an r-cycle, show that alpha^r = (1)

    Can someone show this? Thanks in advance
    Have you tried it? Note that if \alpha=(a_1,\cdots,a_r) then \alpha^k(a_j)=a_{j+k\text{ mod }r}...so?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,153
    Thanks
    591

    Re: r-cycle proof

    it sometimes helps to see an example. let's consider a 4-cycle in S7: α = (1 2 5 7).

    this is the 1-1 function (actually, bijection) which maps:

    1-->2
    2-->5
    3-->3
    4-->4
    5-->7
    6-->6
    7-->1

    if we compose this function with itself, we can see that 3,4 and 6 are never affected, so we only need to worry about 1,2,5 and 7.

    by direct calculation α^2 takes:

    1-->2-->5
    2-->5-->7
    5-->7-->1
    7-->1-->2, that is α^2 is the disjoint pair of 2-cycles: (1 5)(2 7). note that α^2 just takes whatever number is in the n-th place to the (n+2)-th place (mod 4).

    similarly, α^3 takes the number in the n-th position to the number in the (n+3)-th place (mod 4), that is α^3 is the 4-cycle (1 7 5 2).

    now n+3 = n - 1 (mod 4) so α^3 = α^(-1). multiplying both sides by α, or performing the direct calculation again shows α^4 = 1.

    with a k-cycle, you can think of the numbers (some subset of {1,2,...,n}) as being isomorphic to the set {1,2...,k}. which k numbers we are permuting isn't really relelvant, what matters is how many cards the deck we are shuffling has (the cards being the individual numbers, the deck being the set of them-in my example this is the set {1,2,5,7}). so think of a k-cycle as turning a dial with k numbers 1 click. after k clicks, you've come full circle. in my example, we had 4 numbers we were shuffling, so 4 is the relevant piece of information about that cycle. "which" 4 numbers we used doesn't mean that much, all 4-cycles "act alike".
    Last edited by Deveno; September 21st 2011 at 10:52 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176

    Re: r-cycle proof

    Quote Originally Posted by Deveno View Post
    ...this is the 1-1 function...
    A 1-1 function is an injection, but not necessarily a surjection. If two sets are of the same cardinality there is a one-to-one correspondence between them. So, although technically you are correct, you might want to edit your post accordingly...

    (Certainly in the UK we use 1-1 to mean an injection all the time, and wikipedia warns readers of this possible misunderstanding. Personally, I try to avoid using 1-1 for either thing, so as to avoid all this.)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,153
    Thanks
    591

    Re: r-cycle proof

    yes, technically it would be better to read "1-1 correspondence" or "bijection". however, all bijections are 1-1 functions (although not necessarily vice versa). since i am explicitly defining the function for all elements in the domain, there shouldn't be any confusion. in fact i could have omitted the "1-1" entirely and just described it as a function.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] m cycle
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 4th 2011, 11:25 PM
  2. cycle
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 24th 2009, 08:37 AM
  3. cycle
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: March 15th 2009, 10:38 AM
  4. Cycle-cocycle proof (Graph Theory)...
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 27th 2008, 01:08 PM
  5. Replies: 2
    Last Post: December 9th 2007, 02:33 PM

Search Tags


/mathhelpforum @mathhelpforum