4
$\begingroup$

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

  • 0
    Taking the last line to develop should yield the result easily.2012-11-29

2 Answers 2

3

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

1

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.

  • 0
    (Please, if it is frowned-upon, tell me, and I will provide a cmplete answer.)2012-11-29