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

-
What have you tried so far? As a hint, notice that there is a permutation which takes it to the identity. –  EuYu Nov 29 '12 at 6:17
An easy way to prove that the matrix is an isometry is to recall the fact that a matrix is unitary iff the map $x \to Ax$ is an isometry i.e. prove that $$\Vert Ax \Vert = \Vert x \Vert$$ –  user17762 Nov 29 '12 at 6:20
I'm not really sure how cyclic shift operators work to begin with, this is the first time I encounter them. –  karlos Nov 29 '12 at 7:18
Ok, so letting $A^t$ be the transpose, then this matrix will have $1$s on the positions immediately below the diagonal, another $1$ on the top rightmost corner and zeros everywhere else, so then $A^tA=I$ so $A$ is unitary. How about the diagonalization part? –  karlos Nov 29 '12 at 7:53
Can you compute the eigenvalues, or where are your problems? –  Julian Kuelshammer Nov 29 '12 at 7:58

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.

-
(Please, if it is frowned-upon, tell me, and I will provide a cmplete answer.) –  yo' Nov 29 '12 at 9:54

$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 $$x_j = \begin{bmatrix} 1 \\ \lambda_j \\ \lambda_j^2 \\ \vdots \\ \lambda_j^{N-1} \end{bmatrix}.$$ 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$.)

-