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

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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