If you take powers of a permutation, why is some $$ P^k = I $$

Find a 5 by 5 permutation $$ P $$ so that the smallest power to equal I is $$ P^6 = I $$

(This is a challenge question, Combine a 2 by 2 block with a 3 by 3 block.)

I couldn't solve the question anyway, but what does 2 by 2 block mean? Is block another way of saying matrix? Thanks

  • 2
    $\begingroup$ Are you familiar with group theory? And permutation groups in particular? $\endgroup$ – Servaes Jun 27 '16 at 8:29
  • $\begingroup$ Not at all, Our teacher wrote this down while we were being introduced to gaussian elimination and permutation matrices that are required to switch rows and stuff. $\endgroup$ – Xenidia Jun 27 '16 at 10:27
  • $\begingroup$ If you are not familiar with groups you should look in the argument that Servaes was giving in his answer. However the underlying argument is precisly the same you do for finite groups. $\endgroup$ – Maik Pickl Jun 27 '16 at 10:29
  • 5
    $\begingroup$ Could there be some script that automatically downvotes question with an attention grabbing "hard", "difficult", or "challenging" in the title? $\endgroup$ – Carsten S Jun 27 '16 at 12:57
  • 1
    $\begingroup$ Wikipedia: Block matrices. That explains why the term block can be used for submatrix. And if you briefly look at the article, you might see that block matrices might by useful in some situations. $\endgroup$ – Martin Sleziak Jun 27 '16 at 16:07

There are only finitely many ways to permute finitely many things. So in the sequence $$P^1,\ P^2,\ P^3,\ldots$$ of powers of a permutation $P$, there must eventually be two powers that give the same permutation, meaning that $P^i=P^j$ for some $i>j\geq0$. Permutations are reversible so $P$ is invertible, hence $$P^{i-j}=P^iP^{-j}=P^j(P^j)^{-1}=I.$$

And yes, a $2\times2$-block means a $2\times2$-matrix here. The hint suggest to choose a $5\times5$-matrix that has a $2\times2$-matrix and a $3\times3$-matrix on its diagonal, and zeroes elsewhere.

  • $\begingroup$ Yeah, that made sense! Thanks. I couldn't get the hint there. thanks. $\endgroup$ – Xenidia Jun 27 '16 at 11:28
  • 5
    $\begingroup$ I think it could make sense to make explicit that $P$ is invertible, as this is used implicitly. $\endgroup$ – quid Jun 27 '16 at 17:30
  • $\begingroup$ ...and something the OP might want to do later is to show that permutation matrices are orthogonal. $\endgroup$ – J. M. is a poor mathematician Jun 28 '16 at 2:20

Ok, here you go: Note that in a finite group every element has finite order, see for example here for a proof. This means in a finite group $G$ you can find a $n\in \mathbb{N}$ for every $g\in G$ s.t. $g^n=e$.

Now you have a group homomorphism $\varphi:S_n\to Gl_n$ via the following map: take the standardbasis $e_1,\ldots,e_n$ and an element $\sigma \in S_n$, then $\varphi(\sigma)=(e_{\sigma(1)},\ldots,e_{\sigma(n)})$, here I mean the matrix spanned by this vectors. You should check that this is indeed a group morphism.

For a group morphism you have that $\varphi(\sigma)^n=\varphi(\sigma^n)$ and since $S_n$ is a finite group you find a $n \in \mathbb{N}$ s.t. $\varphi(\sigma)^n=\varphi(\sigma^n)=\varphi(id_{S_n})=id_{Gl_n}$.

Now for your last part I suggest you try the matrix that is associated to $(123)(45)$ under the above group morphism.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.