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: Powers of a permutation matrix.

  1. Aug 24, 2009 #1
    1. The problem statement, all variables and given/known data

    If you take powers of a permutation matrix,
    why is some [tex] P^k [/tex] eventually equal to [tex] I [/tex]?

    2. Relevant equations


    3. The attempt at a solution

    From the solutions manual of the book:

    There are n! permutation matrices of order n.

    Eventually, two powers of [tex] P [/tex] must be the same:
    [tex] P^r = P^s [/tex]

    Miltiply [tex] (P^-1)^s [/tex] to find [tex] P^{r-s} [/tex].

    Certainly [tex] r-s \leq n! [/tex]

    I do not quite see how this answers the question.
    I understand that there are n! permutation matrices.

    That two powers of P must be the same is also understandable, since taking powers of P just rearranges the rows. Since there are a finite number of ways to rearrange the rows, two powers will eventually be the same.

    The two other points, I do not understand.

    Would someone be so kind to explain this to me in some detail?

  2. jcsd
  3. Aug 24, 2009 #2

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    You are missing two key things here. Eventually two different powers of [itex]P[/itex] must be the same:

    [tex]P^r = P^s\quad, r \ne s[/tex]

    You can assume that [itex]r>s[/itex]. The other thing you are missing is that you need to multiply both sides of the equality by the inverse of [itex]P^s[/itex].

    See if you can take it from here.
  4. Aug 24, 2009 #3
    Hi D H,

    Is this what you are leading me towards:
    [tex] P^r(P^s)^{-1} = P^s(P^s)^{-1} [/tex]

    [tex] P^{(r-s)} = P^0 [/tex]

    [tex] P^{(r-s)} = I [/tex]

    Thank you.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook