Powers of permutation matrices.

Question

Let $P$ be a permutation matrix obtained by the identity matrix by switching 2 rows $n$ times, (with no two rows switched more than one time).

How to show that $$P^{\ n+1} = I$$?

Is it true that, since $P$ represent a permutation of colums, it's like proving that if we take a set $\{1, \dots m\}$ and have a permutation that switches two elements $n$ times, with no two elements switched more than one time, and we apply this permutation $n+1$ times, we'll return to the original set?

Answer 1

$\DeclareMathOperator{\lcm}{lcm}$

Look at the cycle lengths you produce by switching two rows: switching $12$ and then $34$ will produce two $2$-cycles. The resulting permutation will return to $I$ under power $2$ (it's still an involution).
But if you switch $12$, then $23$, then $34$ you get $2341$ and that's a $4-cycle$. It returns to $I$ under a power $4$, one higher than the number of switches.
Generally, you can produce cycle lengths $c_1, c_2,\dots, c_n $ using $(c_1+1)+(c_2+1)+\dots + (c_n + 1)$ switches.

Such matrix returns to $I$ under power $p= \lcm( c_1,c_2, \dots, c_n)$

If $\sum_{k=1}^m c_k + m < \lcm(c_1, \dots, c_m)$ then your statement is false.

Example: $(2+1)+(3+1)+(5+1) = 13$ switches but $\lcm(2,3,5)= 30$

Answer 2

Ant, cf. http://en.wikipedia.org/wiki/Permutation#Notation read 3.1

Let $n$ be a positive integer. The Landau function $g(n)$ is the largest order of a permutation of length $n$. According to the Wouter post, $g(n)$ is the max of $\lcm(c_1,\cdots,c_k)$ where $c_1+\cdots c_k=n$. $g(n)$ is the sequence A000793 in the Sloane's encyclopedia of integer sequences. For instance $g(10)=30$ (cf. Wouter post again).

EDIT: Ant, I reread your question which is incredibly unclear and now I understand your question (I hope so). You consider a permutation $\sigma$ of $m$ elements that is the product of $n$ $2$-cycles (transposition) $(\tau_i)_i$. What is the order of $\sigma$ ?

Case 1. the supports of the transpositions $\tau_i$ are non-intersecting ; then the $\tau_i$ pairwise commute and $\sigma^2=id$.

Case 2. Some transpositions have common elements. For the sake of simplicity, We assume that $n\geq m$. One can prove that every permutation of $S_m$ can be decomposed in the product of at most $m$ transpositions. Then $\sigma$ can be any element of $S_m$. Finally the order of $\sigma$ is an integer that is at most $g(m)$.

Of course, if $n<m$, then the max of the orders of $\sigma$ is $\leq g(m)$. For instance, let $m=10,n=7$ and $\sigma=(1,2)(3,4,5)(6,7,8,9,10)$. We see that $\sigma$ is a product of $1+2+4=n$ transpositions and its order is $\lcm(2,3,5)=30=g(m)$. If $n<7$, then the max of the order of $\sigma$ is $<g(m)$.