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}$$
 A: 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.
A: 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}.
$$
A: 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).$$
