Shift Operators! Show that the cyclic shift operator is unitary and determine its diagonalization: $$A=\begin{bmatrix}
       0&1     \\[0.3em]
      &0&1 \\[0.3em]
        & & \ddots \\
&&&.&1\\
1&&&&0
     \end{bmatrix}.$$
 A: $A$ preserves norms, so it's unitary.
Suppose $x = \begin{bmatrix} x_0 \\ x_1 \\ x_2 \\ \vdots \\ x_{N-1} \end{bmatrix}$ is a (nonzero) eigenvector of $A$, with eigenvalue $\lambda$.  Then
\begin{align}
Ax &= 
\begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_{N-1} \\ x_0 \end{bmatrix} \\
&= \lambda \begin{bmatrix} x_0 \\ x_1 \\ x_2 \\ \vdots \\ x_{N-1} \end{bmatrix}
\end{align}
so we see that
\begin{align}
x_1 &= \lambda x_0, \\
x_2 &= \lambda x_1,\\
\vdots & \\
x_{N-1} &= \lambda x_{N-2}, \\
x_0 &= \lambda x_{N-1}.
\end{align}
If $x_0$ were equal to $0$, we would find that $x = 0$, which is not the case.
WLOG, we can assume $x_0 = 1$.  (Otherwise we could just scale $x$ to obtain an
eigenvector whose $0$th component is $1$.)
Using the fact that $x_0 = 1$, we see that
\begin{align}
x_0 &= 1 ,\\
x_1 &= \lambda ,\\
x_2 &= \lambda^2 ,\\
\vdots & \\
x_{N-1} &= \lambda^{N-1}, \\
1 &= \lambda^N.
\end{align}
The last equation shows that $\lambda$ is an $N$th root of unity, which narrows $\lambda$ down to $N$ possible values.  Let $\omega = e^{\frac{2 \pi i}{N}}$.  The
eigenvalues of $A$ are $\lambda_j = \omega^j$, for $j = 0,\ldots, N-1$.
An eigenvector with eigenvalue $\lambda_j$ is
\begin{equation}
x_j = \begin{bmatrix} 1 \\ \lambda_j \\ \lambda_j^2 \\ \vdots \\ \lambda_j^{N-1}
\end{bmatrix}.
\end{equation}
We can normalize $x_j$ so that it's a unit vector.  The orthonormal basis of eigenvectors of $A$ that we obtain, which is called the discrete Fourier basis, is of great importance in math.  It's an orthonormal basis of eigenvectors not just of $A$, but of any circulant matrix.  (This is not surprising, because every circulant matrix is built from powers of $A$.)
A: I'm not sure how much math.SX allows "hint answers". I would like to provide a hint:
Eigenvalue is a root of the characteristic polynomial, which is the determinant 
$$p_A(t)=\begin{vmatrix}
-t & 1 & 0 & 0 & 0\\
0 & -t & 1 & 0 & 0\\
0 & 0 & -t & 1 & 0\\
0 & 0 & 0 & -t & 1\\
1 & 0 & 0 & 0 & -t
\end{vmatrix}$$
(This example is for dimension $5$.) Try to enumerate this determinant for this dimension and find the eigenvalues. You should then be able to generalize the result for other sizes as well.
