# Getting identity out of a finite number of permutaions

• ELB27
In summary, the permutation matrix P is the result of column switching of the identity matrix, and it can be expressed as P=IE=E where E is an elementary matrix. To prove that after some finite number of column switching of the identity matrix we get it back, assume that l>m and then proceed to show that P^N=I.
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!

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:
ELB27
geoffrey159 said:
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:
geoffrey159 said:
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)

ELB27 said:

## 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
Dick said:
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

ELB27 said:
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.

ELB27 said:
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
geoffrey159 said:
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.

## 1. What is the concept of "getting identity out of a finite number of permutations"?

The concept of "getting identity out of a finite number of permutations" refers to the process of finding a unique combination or arrangement of a set of elements from a limited pool of options. This is often used in mathematics and computer science to solve problems related to pattern recognition, data analysis, and cryptography.

## 2. Why is it important to get identity out of a finite number of permutations?

Getting identity out of a finite number of permutations is important because it allows us to identify and distinguish between different sets of data or patterns. This is crucial in many fields such as genetics, statistics, and computer science where identifying unique combinations can lead to new discoveries, insights, and solutions.

## 3. How is the process of getting identity out of a finite number of permutations typically done?

The process of getting identity out of a finite number of permutations typically involves using mathematical algorithms and techniques such as factorials, combinations, and permutations. These methods allow us to systematically generate and evaluate all possible combinations until a unique or desired arrangement is found.

## 4. What challenges are associated with getting identity out of a finite number of permutations?

One of the main challenges associated with getting identity out of a finite number of permutations is the sheer number of possible combinations that need to be evaluated. As the number of elements and options increase, the number of permutations also increases exponentially, making it a time-consuming and computationally intensive task.

## 5. Are there any real-world applications of getting identity out of a finite number of permutations?

Yes, there are many real-world applications of getting identity out of a finite number of permutations. For example, it is used in cryptography to create unique and secure encryption keys, in genetics to analyze DNA sequences, and in statistics to analyze data and identify patterns. It is also used in other fields such as finance, engineering, and social sciences for various purposes.

• Calculus and Beyond Homework Help
Replies
4
Views
2K
• Linear and Abstract Algebra
Replies
15
Views
4K
• Precalculus Mathematics Homework Help
Replies
69
Views
4K
• Calculus and Beyond Homework Help
Replies
7
Views
1K
• Calculus and Beyond Homework Help
Replies
3
Views
1K
• Calculus and Beyond Homework Help
Replies
8
Views
2K
• Calculus and Beyond Homework Help
Replies
3
Views
898
• Calculus and Beyond Homework Help
Replies
1
Views
2K
• General Math
Replies
2
Views
1K
• Linear and Abstract Algebra
Replies
4
Views
2K