Undergrad Eigenvalues of Circulant matrices

[mr.tea]

Hi,
I am studying about circulant matrices, and I have seen that one of the properties of such matrices is the eigenvalues which some combinations of roots of unity.

I am trying to understand why it is like that. In all the places I have searched they just show that it is true, but I would like to know how(obviously it's not a guess...).

Thank you.

 

[StoneTemplePython]

It isn't clear what "how" means in this context but I'll give this a shot.

I assume all matrices are $n$ x$n$

note that any circulant matrix $\mathbf S$ can be written as follows

$\mathbf S = \sum_{k=0}^{n-1} s_k \mathbf P^k$
(you should check this for yourself)

where

$\mathbf P = \begin{bmatrix} 0 & 0 &0 & \cdots &0 & 1\\ 1 & 0 &0 &\cdots &0 & 0\\ 0 & 1 &0 & \cdots &0 &0 \\ 0 & 0 &1& \cdots &0 & 0\\ 0 & 0 &0& \ddots &0 & 0\\ 0 & 0 &0& \cdots &1 & 0 \end{bmatrix}$

$\mathbf P$ can be interpreted as a permutation matrix (that is associated with a connected graph). This means it is unitarily diagonalizable and all of its eigenvalues have magnitude 1.

$\mathbf P$ can further be interpreted as a Companion matrix associated with $p(x) = x^n - 1$, and hence its eigenvalues are nth roots of unity. Hence $\mathbf P= \mathbf F \mathbf \Lambda \mathbf F^*$, where $\mathbf \Lambda$ is a diagonal matrix that contains nth roots of unity, and $\mathbf F$ is the unitary version of the Vandermonde matrix, i.e. discrete Fourier transform matrix.

As an aside, it maybe worth pointing out that Companion matrices are a bit 'brittle' and are always defective unless all of their eigenvalues are unique (i.e. algebraic multiplicity of 1 for each eig). But we know that this matrix cannot be defective because it is a permutation matrix (which must be unitarily diagonalizable) hence we know it has n unique roots.

The fact that $\mathbf P$ is a companion matrix associated with $p(x) = x^n - 1$, and a permutation (read: normal) matrix, and serves as a basis for generating circulant matrices -- those three things lead to the result you're asking about.

Using all of the above we can re-write things as:

$\mathbf S = \sum_{k=0}^{n-1} s_k \mathbf P^k = \sum_{k=0}^{n-1} s_k \big(\mathbf F \mathbf \Lambda \mathbf F^*\big)^k = \sum_{k=0}^{n-1} s_k \mathbf F \mathbf \Lambda^k \mathbf F^* = \sum_{k=0}^{n-1} \mathbf F \big(s_k \mathbf \Lambda^k\big) \mathbf F^* = \mathbf F\big(\sum_{k=0}^{n-1} s_k \mathbf \Lambda^k\big) \mathbf F^*$