# Eigenvalues of Circulant Matrix

I am studying about circulant matrices, and I have seen that one of the properties of such matrices is the eigenvalues which are 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 come?

Thank you.

• Circulant matrices involve cyclic permutations of the coordinate axes, which for odd-dimensional spaces are rotations. (In even-dimensional spaces there’s also a reflection involved.) It seems natural to me for roots of unity to show up in the eigenvalues. – amd Oct 2 '17 at 21:59

Let's define the Forward Shift Matrix:

$$\Pi = \begin{bmatrix} 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & & 0 \\ \vdots & & \ddots & \ddots & \vdots \\ 0 & & & & 1 \\ 1 & 0 & & \cdots & 0 \end{bmatrix}$$

Then any Circulant Matrix can be built as following:

$$C = \sum_{i = 0}^{n - 1} {c}_{i + 1} {\Pi}^{i}$$

Where $c$ is the first row of the Circulant Matrix.
Defining $\omega = \exp \left( \frac{2 \pi i}{n} \right)$ and $\Omega = \operatorname{diag} \left( 1, \omega, {\omega}^{2}, \ldots, {\omega}^{n - 1}. \right)$

Now it is easy to see the Forward Shift Matrix $\Pi$ is diagonalizable by the DFT Matrix $F$:

$$\Pi = {F}^{H} \Omega F$$

Then you see exactly how the combination is done.

Remark
Pay attention that ${\Pi}^{k}, \; k \in \left\{ 0, 1, \ldots, n - 1 \right\}$ is an orthogonal basis with respect to the Frobenius Inner Product.

You could just check their work and try showing that the eigenvectors that they gave you are actually eigenvectors.

Another way of doing that is to note that if $$A$$ is circulent, then $$A - xI$$ is also circulent, so knowing the null space of circulent matrices in general is sufficent to know the eigenvectors of circulent matrices in general.

You can also just search "Circulant Matrix site:.edu" in Google for circulent matrices whose website url has a domain name ending in ".edu" so you tend to get professor's notes and other useful material. E.g. using that method I found in Daryl Geller, Irwin Kra, Sorin Popescu and Santiago Simanca - On Circulant Matrices.

• thanks for your answer, but that's not what I meant to ask. I just wanted to know how did know that that the roots of unity have this role. – Mr. Tea Oct 1 '17 at 21:17