3
$\begingroup$

Find a $3\times3$ permutation matrix with $P^3 = I$, $P \ne I$?


I reduced the above problem to $P^T = P^2$ and tried solving for all $6$ $3 \times 3$ permutation matrices which yielded

$$P = \begin{pmatrix} 0&1&0\\0 & 0 & 1\\1&0 & 0\end{pmatrix}$$

$\endgroup$
  • $\begingroup$ You can simply apply a permutation of order 3 to the idenitity $3\times 3$-matrix. $\endgroup$ – Mathematician 42 Jul 16 at 8:19
4
$\begingroup$

If you understand what a permutation is, then it is easy to understand that any permutation of the set $\{1,2,3\}$ corresponds to either doing nothing (the permutation associated with $I$), swapping two numbers (e.g. $1 \leftrightarrow 2$), or shifting the numbers cyclically (e.g. $1 \rightarrow2 \rightarrow 3 \rightarrow 1$). Setting aside "doing nothing", it is easy to see that a permutation only "cancels itself out" after three applications if it is a cyclic shift.

This approach can be seen as an application of the cycle decomposition theorem.


Alternatively, a more matrix-based approach: we cannot have $P^2 = I$, because this would imply that $$ P^2 = P^3 \implies (P^2)I = (P^2)P \implies I = P, $$ but we know that $P \neq I$. So, we have $$ P^2 \neq I \implies P^TP^2 \neq P^TI \implies P \neq P^T. $$ In other words, we want a non-symmetric permutation matrix. As it turns out, either of the two such matrices will work.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How did you imply P is not equal to transpose(P) from the previous step ? $\endgroup$ – Devesh Lohumi Jul 16 at 11:08
  • 1
    $\begingroup$ @DeveshLohumi $P$ is orthogonal, which is to say that $P^TP = I$. So, we have $$ P^TP^2 = P^T(PP) = (P^TP)P = P. $$ $\endgroup$ – Ben Grossmann Jul 16 at 11:20
  • $\begingroup$ what happened to the anticyclic shift (1->3->2->1)? $\endgroup$ – lalala Jul 16 at 17:32
3
$\begingroup$

A permutation matrix actually performs a permutation when you multiply it by a vector. In other words, if $x$ is a vector in $\mathbb R^3$ and $P$ is a $3 \times 3$ permutation matrix, then $Px$ is the vector you get my permuting the components of $x$ according to the permutation that $P$ represents.

So you can forget about matrices for the moment and just think about permutations. You need to think of a permutation which has order $3$. A simple choice that comes to mind is the cyclic shift permutation $$ \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} \mapsto \begin{bmatrix} x_2 \\ x_3 \\ x_1 \end{bmatrix}. $$ The matrix that represents this permutation is $$ P = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix}. $$

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

From $P^3 = I, P \ne I$ we ge that the eigenvalues $\lambda_1, \lambda_2, \lambda_3$ of $P$ have to be third roots of unity, not all equal to one. If $\omega$ is a nontrivial third root of unity, then the options are $$\{1,1,\omega\},\{1,1,\omega^2\},\{1,\omega,\omega\},\{1,\omega^2,\omega^2\},\{\omega,\omega,\omega\},\{\omega^2,\omega^2,\omega^2\},\{\omega,\omega,\omega^2\},\{\omega,\omega^2,\omega^2\},\{1,\omega,\omega^2\}$$

The first four options are eliminated since $1 = \det P = \lambda_1\lambda_2\lambda_3$. The second four options are discarded by considering the trace $$\operatorname{Tr} P = \lambda_1+\lambda_2+\lambda_3$$ which has to be in $\{0,1,2,3\}$ since $P$ is a permutation matrix. The only remaining option is $\{1,\omega,\omega^2\}$ so $$\operatorname{Tr} P = 1+\omega+\omega^2=0.$$ Hence our solutions are matrices permutation matrices with zeros on the diagonal. This leaves only two options: $$P = \begin{bmatrix} 0&1&0\\0 & 0 & 1\\1&0 & 0\end{bmatrix}, \quad P=\begin{bmatrix} 0&0&1\\1 & 0 & 0\\0&1 & 0\end{bmatrix}.$$ Indeed, these correspond to the only two $3$-cycles: $$(1\,3\,2), \quad (1\,2\,3).$$

| cite | improve this answer | |
$\endgroup$

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.