Determining the power of permutation matrix of order $N\times N$ to get identity matrix.

Question

This particular 6x6 permutation matrix is P

$$ P = \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ \end{pmatrix}$$

the least power of $P$ that gives identity is $8$. However, lets consider $P_2$

$$ P_2 = \begin{pmatrix} 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 \end{pmatrix} $$ the least power of $P_2$ that gives identity is $6$.

1. How to identify the least power of a permutation matrix for which it turns into identity. 2.If a number is given, say $n$, how to construct a permutation matrix such that the minimum power the matrix has to be raised to get identity is that particular number $n$?

Answer 1

Permutation matrices multiply just like their associated permutations (provided you fix the correspondence so that left and right do not get mixed up). So you are just asking about orders of permutations, which as is well known is computed as the least common multiple of the cycle lengths. In particular a cyclic permutation of length $n$ will dp well for your final question (the associated matrix is also the companion matrix for the monic polynomial $X^n-1$).

Answer 2

There is an isomorphism of groups between the multiplicative group of $n \times n$ permutation matrices and the symmetric group of $n$ elements. In other words,

1. You can think of any permutation matrix $M$ simply as a permutation $\sigma$ on $n$ elements, where $\sigma(i) = j$ iff $M_{i,j} = 1$.
2. Multiplying two permutation matrices is equivalent to taking the composition of their associated permutations: $M_1 \times M_2 = \sigma_1 \circ \sigma_2$ (I suggest working through this to prove it for yourself).

Using the example in your question, $P$ would be represented by the permutation (1 3 2 6)(4 5) in cycle notation (see here). The order of a permutation is the least common multiple of the orders of its cycles, in this case 4 (not 8 which you claimed). For $P_2$ the associated permutation is (1 3 2 6 5 4), which has order 6. For your second question, as pointed out in Marc van Leeuwen's answer, any cyclical permutation of order $n$ would do.