Find a $4\times 4$ matrix $A$ where $A\neq I$ and $A^2 \neq I$, but $A^3 = I$. Give an example of a $4 \times 4$ matrix where $A \neq I$, $A^2 \neq I$, and $A^3 = I$.
I found a $2 \times 2$ matrix where $A \neq I$ and $A^2 = I$, but this problem is more complex and has me completely stumped.
 A: Let $b_1,b_2,b_3,b_4$ be a basis. Define $A$ such that 
$$Ab_1=b_2, Ab_2=b_3, Ab_3=b_1$$ and $Ab_4=b_4$ and extend $A$ linearly. Then for scalars $\alpha_k$, $k=1,2,3,4$
$$A(\alpha_1b_1+\alpha_2b_2+\alpha_3b_3+\alpha_4b_4)=\alpha_1b_2+\alpha_2b_3+\alpha_3b_1+\alpha_4b_4 \ne\alpha_1b_1+\alpha_2b_2+\alpha_3b_3+\alpha_4b_4$$
and 
$$A^2(\alpha_1b_1+\alpha_2b_2+\alpha_3b_3+\alpha_4b_4)=\alpha_1b_3+\alpha_2b_1+\alpha_3b_2+\alpha_4b_4 \ne\alpha_1b_1+\alpha_2b_2+\alpha_3b_3+\alpha_4b_4$$
while 
$$A^3(\alpha_1b_1+\alpha_2b_2+\alpha_3b_3+\alpha_4b_4)=\alpha_1b_1+\alpha_2b_2+\alpha_3b_3+\alpha_4b_4.$$
A: Nobody has really highlighted the geometric interpretation yet, so I will. You're looking for a linear mapping (in 4 dimensions) that will take a vector $x$ to itself if applied three times in a row, yet will yield distinct intermediate vectors $Ax$, $A^2x$.
Let's start with the 2-dimensional case. There, it's easy to see that the mapping you want is a rotation.  If $A$ represents the rotation by an $n$-th of a full circle (i.e, $360/n$ degree, or $2\pi/n$ red), then $A^n$ rotates by a full circle or equivalently not at all.
The rotation by $\varphi$ rad is given by $\begin{pmatrix} \cos\varphi & \sin\varphi \\ -\sin\varphi & \cos \varphi\end{pmatrix}$. Thus, $$A = \begin{pmatrix} \cos\frac{2\pi}{n} & \sin\frac{2\pi}{n} \\ -\sin\frac{2\pi}{n} & \cos\frac{2\pi}{n}\end{pmatrix}$$ is a mapping with $A^0 \ldots A^{n-1} \neq I$ and $A^n = I$.
To extend this to more than two dimensions, you can simply use the identity mapping for the other dimensions. Or, in the 4-dimensional case, you could also combine two rotation matrixes. The resulting matrix then has block-diagonal form with two $2x2$ blocks.
A: Here is a $2\times2$ example
$$
\begin{bmatrix}
-\frac12&\frac{\sqrt{3}}{2}\\
-\frac{\sqrt{3}}{2}&-\frac12
\end{bmatrix}\tag{1}
$$
This works because it is a matrix representation of $e^{2\pi i/3}=-\frac12+i\frac{\sqrt{3}}{2}$; that is, a rotation by $\frac{2\pi}{3}$. Thus, squaring it gives another $2\times2$ example
$$
\begin{bmatrix}
-\frac12&-\frac{\sqrt{3}}{2}\\
\frac{\sqrt{3}}{2}&-\frac12
\end{bmatrix}\tag{2}
$$
$(1)$ and $(2)$ can easily be extended to $4\times4$ examples in many ways. Here is one using $(1)$:
$$
\begin{bmatrix}
-\frac12&\frac{\sqrt{3}}{2}&0&0\\
-\frac{\sqrt{3}}{2}&-\frac12&0&0\\
0&0&\hspace{7pt}1\hspace{7pt}\vphantom{-\frac12}&0\\
0&0&0&\hspace{5pt}1\hspace{5pt}\vphantom{-\frac12}
\end{bmatrix}\tag{3}
$$
Yet another $2\times2$ matrix:
As Hagen von Eitzen points out, we can consider the unit vectors $u,v,w$, which are separated by $\frac{2\pi}{3}$
$\hspace{5cm}$
and note that $u+v+w=0$ to get that $w=-u-v$. Let $\begin{bmatrix}a\\b\end{bmatrix}$ be a coordinate vector using the basis vectors $\{u,v\}$. Then rotation by $\frac{2\pi}{3}$ has the following action:
$$
\begin{bmatrix}u&v\end{bmatrix}\begin{bmatrix}a\\b\end{bmatrix}\mapsto\begin{bmatrix}v&w\end{bmatrix}\begin{bmatrix}a\\b\end{bmatrix}=\begin{bmatrix}u&v\end{bmatrix}\begin{bmatrix}0&-1\\1&-1\end{bmatrix}\begin{bmatrix}a\\b\end{bmatrix}\tag{4}
$$
Thus, the matrix for rotating by $\frac{2\pi}{3}$ under the basis $\{u,v\}$ is
$$
\begin{bmatrix}0&-1\\1&-1\end{bmatrix}\tag{5}
$$
which, as Gerry Myerson points out, is the companion matrix for $x^2+x+1$. A companion matrix is annihilated by its polynomial, so $(5)$ is annihilated by $x^3-1=(x-1)(x^2+x+1)$.
The square of $(5)$ also satisfies the specified conditions:
$$
\begin{bmatrix}-1&1\\-1&0\end{bmatrix}\tag{6}
$$
The answer given by Marc van Leeuwen uses $(6)$.
A: Here's a $3\times3$: $$\pmatrix{0&1&0\cr0&0&1\cr1&0&0\cr}$$ You should be able to get a $4\times4$ out of this. 
A: $$\begin{pmatrix}-1&1&0&0\\-1&0&0&0\\0&0&1&0\\0&0&0&1\end{pmatrix}$$
A: Since powers of diagonal matrices just raise the elements to those powers individually, we can simply pick a diagonal matrix such that all the diagonal elements are cube roots of $1$. If you're allowed complex matrices, the solution is easy.
