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!

Getting identity out of a finite number of permutaions

  1. May 28, 2015 #1
    1. The problem statement, all variables and given/known data
    Let ##P## be a permutation matrix. Show that for some ##N>0## [tex]P^N := \underbrace{PP...P}_{N \ \text{times}} = I[/tex]

    2. Relevant definitions
    A permutation matrix is a ##n\times n## matrix containing only zeros and ones such that there is exactly one ##1## per row and per column.

    3. The attempt at a solution
    Well, given the above definition, this permutation matrix is simply the result of column switching of the identity matrix. So, ##P## can be expressed as ##P=IE=E## where ##E## is an elementary matrix performing column switching. So, the problem reduces to proving that after some finite number of column switching of the identity matrix we get it back. However, I have no idea how to formally prove it - it seems plausible (there is only a finite number of permutations possible for those columns) but that is not formal.
    So, how to formulate such a proof in a formal manner?

    Any help is greatly appreciated!
     
  2. jcsd
  3. May 28, 2015 #2
    Maybe I have an idea for you:

    From what I read on the internet, if ##\sigma## and ##\sigma '## are two permutations, then ## P_{\sigma \circ \sigma '} = P_\sigma P_{\sigma '} ##

    So take your matrix ##P_\sigma##. You know that you can decompose a permutation into a product of disjoint cycles.
    So ##P_\sigma = P_{c_1 \circ ... \circ c_\mu } = P_{c_1} ... P_{c_\mu}##. The idea behind that is that now your matrix product is commutative.
    Also you know that if you compose a cycle by its length, you get the identity permutation.
    So ## I = P_{id} = P_{c_1}^{l_1} ... P_{c_\mu}^{l_\mu} ##. So if you take ##N ## as the least common multiple of ##(l_1, ..., l_\mu )##, you're done (if what I say is correct)
     
    Last edited: May 28, 2015
  4. May 28, 2015 #3
    Thank you! Indeed, I believe that you are correct about the commutativity part and the idea should work. The only thing that I do not quite get is:
    I didn't quite understand what this means. Could you elaborate?
    (I have only recently been introduced to permutations and I'm not too familiar with their properties)
     
  5. May 28, 2015 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Think about this. There are only a finite number of ##n x n## permutation matrices. So the set of all powers of ##P##, ##P^n## for ##n>0## must contain two elements that are the same, so ##P^l=P^m## for some ##l \ne m##. What can you do with that?
     
  6. May 28, 2015 #5
    Ah, I think I get it.
    Assume ##l>m## (they are arbitrary anyway). Then:
    [tex]P^l=P^mP^{l-m}=P^m[/tex]
    We know that ##P## is invertible. Therefore, ##P^m## is also invertible as a product of invertible matrices ##P##. Multiplying the above by ##(P^m)^{-1}## on the left:
    [tex](P^m)^{-1}P^mP^{l-m}=(P^m)^{-1}P^m[/tex]
    [tex]IP^{l-m}=I[/tex]
    [tex]P^{l-m}=I[/tex]
    Since we assumed ##l>m## we can define ##N:=l-m>0## and thus have:
    [tex]P^N=I[/tex] for some ##N>0##. QED.

    Thanks a lot!

    EDIT: You must be a longtime member of this forum to get such a name before it's taken by someone else :oldbiggrin:
     
  7. May 28, 2015 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Yes, that's it. You're welcome, and yes, been around a while.
     
  8. May 29, 2015 #7
    Yes, if ##c## is a cycle of length ##l_c##, then the permutation ## c^{l_c} = c \circ ... \circ c ## is the identity permutation (it does not permute anything)
    So ##I = P_{c^{l_c}} = P_c^{l_c} ##. But Dick's suggestion is better in my opinion.
     
  9. May 29, 2015 #8
    Thanks! A different approach is always insightful.
     
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: Getting identity out of a finite number of permutaions
Loading...