Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
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
1  
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

2 Answers 2

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.

share|improve this answer
    
(Please, if it is frowned-upon, tell me, and I will provide a cmplete answer.) –  tohecz 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 \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$.)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.