the associated polynomial of circulant matrix

Question

I tried understanding the circulant matrix with a little more knowledge behind it. In some documents, there is an associated polynomial of the ciculant matrix. $$ g(x) = a_1 + a_2 x+ a_3 x^2 + \cdots + a_n x^{n-1} $$ However, in general, the polynomial is given without introduction. I want to get how it is derived.

Answer 1

Let $\eta$ be the $n\times n$ matrix with entries $$\eta_{ij} = \begin{cases} 1, & i - j\equiv 1 \pmod n\\0,&\text{ otherwise }\end{cases}$$

For any $n \times n$ circulant matrix $C$ with entries $C_{ij} = c_{{\rm mod}(i-j,n)+1}$.

$$C = \left|\begin{matrix} c_1 & c_n & \cdots & c_3 & c_2\\ c_2 & c_1 & c_n& & c_3\\ \vdots & c_2 & c_1 & \ddots & \vdots\\ c_{n-1} & & \ddots & \ddots & c_n\\ c_n & c_{n-1} & \ldots & c_2 & c_1 \end{matrix}\right|, $$ $C$ can be written as a polynomial in $\eta$:

$$C = g(\eta) = c_1 I_n + c_2 \eta + \cdots + c_n \eta^{n-1}$$

The polynomial $g(x) = \sum\limits_{k=1}^n c_k x^{k-1}$ is precisely the polynomial you mentioned.

Because of this representation, a lot of properties of $C$ can be inferred from that of $\eta$.

As an example, the eigenvalues of $\eta$ are $1, \omega, \omega^2, \ldots, \omega^{n-1}$ where $\omega = e^{\frac{2\pi}{n}i}$ is the primitive $n$-root of unity. So eigenvalues of $C$ are $g(1), g(\omega), g(\omega^2),\cdots, g(\omega^{n-1})$. This leads to the sort of famous formula of determinant of circulant matrices:

$$\det(C) = \prod_{\ell=0}^{n-1} g(\omega^\ell)$$