Let \[ A=\begin{pmatrix}a_0&a_1&a_2\\a_2&a_0&a_1\\a_1&a_2&a_0\end{pmatrix}. \] (a) Show \(A=a_0I_3+a_1E+a_2E^2\) for the cyclic shift matrix \(E\).
Find the complex eigenvalues of \(A\).
Generalize to \(n\times n\) circulant matrices.
Solution
Let \[ E= \begin{pmatrix} 0&1&0\\ 0&0&1\\ 1&0&0 \end{pmatrix}. \] Then \[ E^2= \begin{pmatrix} 0&0&1\\ 1&0&0\\ 0&1&0 \end{pmatrix}. \]
1. \(A=a_0I_3+a_1E+a_2E^2\).
Directly, \[ a_0I_3+a_1E+a_2E^2 =\begin{pmatrix} a_0&a_1&a_2\\ a_2&a_0&a_1\\ a_1&a_2&a_0 \end{pmatrix} =A. \] Thus \[ \boxed{A=a_0I_3+a_1E+a_2E^2.} \]
2. With \(\omega=e^{2\pi i/3}\), the eigenvalues of \(A\) are \(a_0+a_1\lambda+a_2\lambda^2\) for \(\lambda\in\{1,\omega,\omega^2\}\).
Let \[ \omega=e^{2\pi i/3}. \] For each \[ \lambda\in\{1,\omega,\omega^2\}, \] the vector \[ v_\lambda= \begin{pmatrix}1\\\lambda\\\lambda^2\end{pmatrix} \] satisfies \[ Ev_\lambda =\begin{pmatrix}\lambda\\\lambda^2\\1\end{pmatrix} =\lambda v_\lambda, \] because \(\lambda^3=1\). The three eigenvalues of \(E\) are distinct, so these vectors form a basis of \(\mathbb C^3\).
Since \(A=a_0I+a_1E+a_2E^2\), \[ Av_\lambda =(a_0+a_1\lambda+a_2\lambda^2)v_\lambda. \] Therefore the eigenvalues of \(A\) are \[ \boxed{ a_0+a_1+a_2, \quad a_0+a_1\omega+a_2\omega^2, \quad a_0+a_1\omega^2+a_2\omega.} \]
3. With \(\zeta=e^{2\pi i/n}\), the \(n\times n\) circulant with first row \((a_0,\ldots,a_{n-1})\) has eigenvalues \(\sum_{r=0}^{n-1}a_r\zeta^{kr}\) for \(k=0,\ldots,n-1\).
Let \(E_n\) be the cyclic shift matrix \[ E_ne_j=e_{j-1} \] with indices read cyclically in the convention matching the displayed three-by-three matrix. An \(n\times n\) circulant with first row \[ (a_0,a_1,\ldots,a_{n-1}) \] has the form \[ C=\sum_{r=0}^{n-1}a_rE_n^r. \]
Let \[ \zeta=e^{2\pi i/n}. \] For \(k=0,\ldots,n-1\), put \[ v_k= \begin{pmatrix} 1\\ \zeta^k\\ \zeta^{2k}\\ \vdots\\ \zeta^{(n-1)k} \end{pmatrix}. \] Then \[ E_nv_k=\zeta^kv_k. \] Hence \[ Cv_k =\left(\sum_{r=0}^{n-1}a_r\zeta^{kr}\right)v_k. \] The \(n\) numbers \(\zeta^k\) are distinct, so the corresponding vectors form a basis. Thus every \(n\times n\) circulant is diagonalized by the Fourier basis, with eigenvalues \[ \boxed{ \lambda_k=\sum_{r=0}^{n-1}a_r\zeta^{kr}, \qquad k=0,\ldots,n-1.} \]