Estás cierto en el resultado (P^n!=Id) y tenés ideas ciertas aplicables para la prueba, pero no es exactamente así.
a) Considerá una matriz de permutación, 5 x 5, donde a_13=1, a_21=1, a_32=1, a_45=1 y a_54=1 (el resto de los coeficientes son ceros). En este caso el número de "filas intercambiadas" son 5 (son todas). Pero P^5 no da la identidad. Sin embargo P^6 da la identidad (porque 6 = 3 x 2 y las primeras tes filas forman un ciclo de tes, y las últimas dos, un ciclo de dos).
Por lo tanto P^5!=P^120 da la identidad, pues 6 divide a 120.
Se forman ciclos entre las filas que están intercambiadas, y todos a la misma vez tienen que dar la identidad. En el ejemplo de arriba, un ciclo ente tres filas y otro entre 2 filas.
b) Así, en el caso general n x n, pueden formarse varios ciclos entre filas: c_1, c_2, ..., c_t, con t<n.
Cada ciclo c_i tiene k_i filas en su ciclo.
Entonces k_1 + k_2 + ...+ k_t = n, donde algunos de estos k_i puede valer uno (porque algunos de los coeficientes a_ii puede valer 1).
Luego el primer ciclo de filas en k_1 pasos vuelve a la identidad. El segundo en k_2 pasos, etc.
Entonces P^(k_1)(k_2)...(k_t) = Id.
Pero k_1, k_2, son todos factores menores que n, con lo cual, no es difícil probar que (k_1)(k_2)...(k_t) divide a n! (no tiene porqué dividir a n, pero si divide a n!, como en el ejemplo de arriba).
Por eso: P^(k_1)(k_2)...(k_t) = Id implica que P^n! = Id.
Ya ves que el resultado que escribiste era correcto, y que las ideas andaban cerca.
Saludos
Marcelo