# What are some intuitive ways to find a $3 \times 3$ permutation matrix with $P^3 = I$, $P \ne I$?

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}$$

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

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.

• How did you imply P is not equal to transpose(P) from the previous step ? – Devesh Lohumi Jul 16 at 11:08
• @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.$$ – Ben Grossmann Jul 16 at 11:20
• what happened to the anticyclic shift (1->3->2->1)? – lalala Jul 16 at 17:32

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}.$$

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).$$