13
$\begingroup$

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

$\endgroup$
6
  • 2
    $\begingroup$ Are you familiar with group theory? And permutation groups in particular? $\endgroup$
    – Servaes
    Commented Jun 27, 2016 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$
    – user346936
    Commented Jun 27, 2016 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
    Commented Jun 27, 2016 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
    Commented Jun 27, 2016 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$ Commented Jun 27, 2016 at 16:07

2 Answers 2

18
$\begingroup$

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.

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

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.

$\endgroup$

You must log in to answer this question.