Eigenvectors and Eigenvalues of Shift Matrix

Question

$$S:\mathbb{C}^n\rightarrow\mathbb{C}^n, $$ $$S(x_1,x_2,...,x_n)^T = (x_n,x_1,...,x_{n-1})^T.$$ How can the eigenvalues and eigenvectors of S be calculated? I already have the standard matrix of S which is: \begin{bmatrix} 0 & 0 & 0 & \dots & 0 & 1\\ 1 & 0 & 0 & \dots & 0 & 0\\ 0 & 1 & 0 & \dots & 0 & 0\\ 0 & 0 & 1 & \dots & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \dots & 1 & 0 \end{bmatrix}

Answer 1

To find its eigenvalues, note that $\lambda I - S$ is given by the following matrix: \begin{eqnarray} \begin{pmatrix} \lambda & 0 & 0 & \cdots & 0 & -1 \\ -1 & \lambda & 0 &\cdots & 0 & 0 \\ 0 & -1 & \lambda & \cdots & 0 & 0 \\ 0 & 0 & -1 &\cdots & 0 & 0\\ \vdots & \vdots & \vdots & \ddots& \vdots & \vdots \\ 0 & 0 & 0 &\cdots & -1 & \lambda \end{pmatrix} \tag{1}\label{1} \end{eqnarray} To find the determinant of (\ref{1}), you can use the cofactor procedure as follows. You eliminate the first row and the first column of this matrix and evaluate the determinant of the remaining matrix. Then, you keep the first row eliminated and proceed by eliminating the following columns. This will lead you to: \begin{eqnarray} \det(\lambda I - S)= \lambda \det\begin{pmatrix} \lambda & 0 & \cdots & 0 & 0\\ -1 & \lambda & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & -1 & \lambda \end{pmatrix} +(-1)(-1)^{1+n}\det\begin{pmatrix} -1 & \lambda & 0 & \cdots & 0 \\ 0 & -1 & \lambda & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & -1 \end{pmatrix} \end{eqnarray} But these determinants are easy to calculate because both matrices are triangular, so you only have to multiply the main diagonal elements of each matrix. Thus: $$\det(\lambda I - S) = \lambda^{n}+(-1)^{n}(-1)^{n-1} = \lambda^{n}-1$$ In other words, the eigenvalues of $S$ are the $n$ (complex) roots of $1$. Once you have the eigenvalues, the eigenvectors follow from direct calculations.

Remark: The $n$ factors are due the fact that I'm assuming $S$ is $n\times n$.

Answer 2

Since

$$||Sx|| = ||x||$$

we infer that $\lambda = 1$.

Then solving

$$(S-\lambda I)e = 0$$

we infer that $e=(1,1,...1)$

Answer 3

As Rodrigo de Azevedo's edit to the question indicates, $\ S\ $ is a special case of a circulant matrix:$$ S=\pmatrix{c_0&c_{n-1}&\dots&c_2&c_1\\ c_1&c_0& c_{n-1}&\dots&c_2\\ \vdots&\ddots&\ddots&\ddots&\vdots\\ \vdots&\vdots&\ddots&\ddots&\vdots\\ c_{n-1}& c_{n-2}&\dots&c_1&c_0}\ , $$ where $\ c_1=1\ $ and $\ c_i=0\ $ for $\ i\ne1\ $ in this case.

The eigenvalues of $\ S\ $ are therefore the $\ n^\text{th}\ $ roots of unity, $\ w_j^{n-1}=e^{\frac{2\pi i j(n-1)}{n}}= w_{n-j}\ $, for $\ j=0,1,\dots, n-1\ $, where $\ w_j=e^{\frac{2\pi i j}{n}}\ $. An eigenvector $\ v_j\ $ corresponding to the eigenvalue $\ w_j\ $ is one whose $\ k^\text{th}\ $ entry is $\ w_j^{k-1}\ $: $$ v_j=\pmatrix{ 1& w_j& w_j^2& \dots & w_j^{n-1}}^T\ . $$ With $\ v_j\ $ thus defined, we have \begin{align} S v_j&= \pmatrix{ w_j^{n-1}& 1& w_j& \dots & w_j^{n-2}}^T\\ &= w_j^{n-1}v_j\ . \end{align}