Singular Circulant Matrix

Question

Reffering to the above text, $C(a_0, ..., a_{n-1})$ or $C$ is a $n\times n$ circulant matrix over complex number.
Why $f(x)$ and $1-x^n$ have a common zero if and only if $C$ is singular.
In addition, if $C$ is $n \times n$ circulant matrix over finite field, will this argument still hold.
Thanks.

Answer 1

Sketch: Show that the eigenvectors are the vectors $(1,\eta,\eta^2,\dots,\eta^{n-1})$ where $\eta$ runs through the $n$th roots of unity (in the complex numbers, or over the finite field, this works in either context). Show that the corresponding eigenvalues are the numbers $f(\eta)$, where $\eta$ runs through the $n$th roots of unity. "Singular" is equivalent to "has zero as an eigenvalue" which is equivalent to $f(\eta)=0$ for some $n$th root of unity $\eta$, which is equivalent to $f(x)$ and $1-x^n$ have a common zero.

Answer 2

The determinant of $C(a_0,\ldots,a_{n-1})$ is $$\prod_{\zeta\in\mu_n}f(\zeta)$$ where $\mu_n$ is the set of complex solutions of $X^n=1$, so vanishes iff $f$ and $X^n-1$ have a common zero.

This works also in characteristic $p$ if we take care. Write $n=p^tm$ with $p\nmid m$. Then $X^n-1=(X^m-1)^{p^t}$ and the determinant is now $$\prod_{\zeta\in\mu_m}f(\zeta)^{p^t}$$ where now $\mu_m$ is the set of $m$-th roots of unity in an algebraic closure of $\Bbb F_p$. The upshot is the same: the determinant vanishes iff $f$ and $X^n-1$ have a common zero.

Answer 3

A little longer, more basic approach:

There are 2 legs to this, and both follow from looking at the generator of a Circulant matrix. I.e. observe that any circulant matrix can be written as

$C = a_0 P^0 + a_1 P^1 + ... + a_{n-1} P^{n-1}$
with

$ 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}$

note that $P$ is a Companion matrix associated with the characteristic polynomial $p(x) = x^n-1$ which is your second function (up to negation, which doesn't matter for roots).

leg one
$\text{common root} \longrightarrow \det\big(S\big) = 0$
if they have a common root (i.e. an nth root of unity) then $\mathbf v^* P = \lambda \mathbf v^* $
(The companion matrix has well known eigenvectors -- the moment curve or equivalently slices of a Vandermonde matrix)

then
$\mathbf v^* C = a_0 \mathbf v^* P^0 + a_1 \mathbf v^* P^1 + ... + a_{n-1} \mathbf v^* P^{n-1} = a_0 \lambda^0 \mathbf v^* + a_1 \lambda \mathbf v^* + ... + a_{n-1}\lambda^{n-1} \mathbf v^* =\big(a_0 \lambda^0 + a_1 \lambda + ... + a_{n-1}\lambda^{n-1}\big) \mathbf v^* = 0 \mathbf v^* = \mathbf 0^*$
so $C$ is singular

This argument holds over any field.

leg two
$\text{no common root} \longrightarrow \det\big(S\big) \neq 0$
Working in $\mathbb C$, up to rescaling use the Discrete Fourier Transform matrix $F$ so

$FS = \begin{bmatrix}\big(a_0 \lambda_1^0 + a_1 \lambda_1 + ... + a_{n-1}\lambda_1^{n-1}\big) \mathbf v_1^*\\ \vdots\\ \big(a_0 \lambda_{n-1}^0 + a_1 \lambda_{n-1} + ... + a_{n-1}\lambda_{n-1}^{n-1}\big) \mathbf v_{n-1}^*\\ \big(a_0 \lambda_{n}^0 + a_1 \lambda_{n} + ... + a_{n-1}\lambda_{n}^{n-1}\big) \mathbf v_{n}^* \end{bmatrix} = D F$
where $D$ is a diagonal matrix with no zeros on the diagonal, so

$\det\big(F\big)\det\big(S\big)= \det\big(FS\big)=\det\big(D F\big) = \det\big(D \big)\det\big( F\big)$

$F$ is invertible (and up to rescaling its actually unitary) so we know $\det\big(D \big) = \det\big(S\big) \neq 0$

The circulant matrix is intimately tied in with the discrete fourier transform, so $\mathbb C$ is very natural here. I haven't considered finite fields in this case.