13

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

Servaes
  • 63,261
  • 7
  • 75
  • 163
  • 2
    Are you familiar with group theory? And permutation groups in particular? – Servaes Jun 27 '16 at 08:29
  • 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. –  Jun 27 '16 at 10:27
  • 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. – Maik Pickl Jun 27 '16 at 10:29
  • 5
    Could there be some script that automatically downvotes question with an attention grabbing "hard", "difficult", or "challenging" in the title? – Carsten S Jun 27 '16 at 12:57
  • 1
    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. – Martin Sleziak Jun 27 '16 at 16:07
  • @CarstenS I am the one who downvoted, and it is not for the title but for the confusing text. – Federico Poloni Aug 28 '16 at 15:25

2 Answers2

18

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.

Servaes
  • 63,261
  • 7
  • 75
  • 163
11

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.

Community
  • 1
Maik Pickl
  • 2,037