Getting identity out of a finite number of permutaions

[ELB27]

Homework Statement

Let $P$ be a permutation matrix. Show that for some $N>0$ P^N := \underbrace{PP...P}_{N \ \text{times}} = I

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$ P^N := \underbrace{PP...P}_{N \ \text{times}} = I

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:
P^l=P^mP^{l-m}=P^m
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:
(P^m)^{-1}P^mP^{l-m}=(P^m)^{-1}P^m
IP^{l-m}=I
P^{l-m}=I
Since we assumed $l>m$ we can define $N:=l-m>0$ and thus have:
P^N=I 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:
P^l=P^mP^{l-m}=P^m
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:
(P^m)^{-1}P^mP^{l-m}=(P^m)^{-1}P^m
IP^{l-m}=I
P^{l-m}=I
Since we assumed $l>m$ we can define $N:=l-m>0$ and thus have:
P^N=I 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.