Getting identity out of a finite number of permutaions

[ELB27]

Homework Statement

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.

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!

 

[geoffrey159]

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)

 

[ELB27]

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)

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:

Also you know that if you compose a cycle by its length, you get the identity permutation.

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)

 

[Dick]

Homework Statement

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.

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!

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?

 

[ELB27]

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?

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

 

[Dick]

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

Yes, that's it. You're welcome, and yes, been around a while.

 

[geoffrey159]

I didn't quite understand what this means. Could you elaborate?

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.

 

[ELB27]

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.

Thanks! A different approach is always insightful.