Powers of a permutation matrix - Part 2

Published on 01 Oct 2023, under:  | mathematics |  linearalgebra |  permutations |   

In Part 1, we saw how every permutation has at least one cycle, and that the size of the cycle is the number of elements in the cycle. If we now consider a permutation that is one big cycle of all the elements in our set, then we can easily see that if we apply the same permutation n times, n being the number of elements in the set, all elements return to the positions with which they started out. So pⁿ = e for such a permutation, where once again, e is the identity.

But what about permutations that are not just one cycle of all elements? What if the permutation consists of a combinations of cycles of different cycles and/or fixed points (elements that remain fixed in their positions upon application of a permutation are called fixed points). To explore this further, let us consider a couple of specific examples.

1. The permutation is one in which two elements in the set switch places, the rest are fixed points - In this case, there is one cycle of size two, and the rest are fixed points, so they are all in cycles of size one. So if we apply the permutation for a second time, both elements that switched places return to their original position, and the rest will have remained in the same position with which they started out. So if p denotes this particular permutation, then p² = 2
2. The permutation consists of two cycles of size k₁ and k₂ respectively - Here, we immediately see that the first cycle with return to its starting arrangement after k₁ applications of the permutation and the second cycle will return to its starting arrangement after k₂ applications. To calculate how many applications of the permutation are needed for both cycles to return to the starting configuration, notice that either cycle will return to the start when the permutation is applied mk times, where m is a positive integer. So this means that if the permutation is applied k₁k₂ times, both cycles will have returned to their original positions (notice that if k₂ = qk₁ then both cycles will return to the starting positions after just k₂ applications of the permutation). That is, p^k₁k₂ = e

Let’s stop here for now, and in Part 3 let’s explore permutations that are a little more complex, and finally try and nail down the answer for any generic permutation.