Consider the following $n\times n $ matrix over some field $F$:
$$M = (m_{i,j})_{i,j=1,\ldots,n} = \begin{bmatrix}
a_1 & a_2 b & a_3 b & \ldots & a_{n-1} b & a_n b \\
a_n & a_1 & a_2 b & \ldots & a_{n-2} b & a_{n-1} b \\
a_{n-1} & a_n & a_1 & \ldots & a_{n-3} b & a_{n-2} \\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
a_3 & a_4 & a_5 & \ldots & a_1 & a_2 b \\
a_2 & a_3 & a_4 & \ldots & a_n & a_1
\end{bmatrix}$$
This is a special kind of Toeplitz matrix, and close to being a circulant matrix (it would be circulant if $b=1$). I am looking for a reference on when such a matrix is non-singular; I know that such a characterisation exists for circular matrices.
The reason I care is that this matrix comes up in a computation of mine as the coefficient matrix in some system of linear equations. From the setup I have that not all $a_i$'s are zero, and $b\ne0$.
Best Answer
Let $$J = \begin{pmatrix} 0 & b & 0 & \ldots & 0 \\ 0 & 0 & b & \ldots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \ldots & b \\ 1 & 0 & 0 & \ldots & 0 \end{pmatrix}$$
Then you have $$M =a_1 I_n + a_2 J + \dfrac{a_3}{b}J^2 + ... + \dfrac{a_n}{b^{n-2}}J^{n-1} = P(J)$$
where $P(X)=a_1 + \displaystyle{\sum_{k=2}^n \dfrac{a_k}{b^{k-2}}X^{k-1}}$.
But $J^n = b^{n-1}I_n$, so $J$ is diagonalizable and its eigenvalues are the $n$ complex $n-$roots of $b^{n-1}$ : let's denote them $\omega_1$, ..., $\omega_n$. You deduce that $M$ is diagonalizable and its eigenvalues are $P(\omega_1), ..., P(\omega_n)$.
Finally, $$\det(M)=\prod_{k=1}^n P(\omega_k)$$
so $M$ is singular iff the two polynomials $$a_1 + \displaystyle{\sum_{k=2}^n \dfrac{a_k}{b^{k-2}}X^{k-1}} \quad \text{and} \quad X^n-b^{n-1}$$
share a root, which is equivalent to saying that
$$\boxed{\text{$M$ is singular } \quad \textit{iff }\quad a_1 + b\displaystyle{\sum_{k=2}^n a_kX^{k-1}} \text{ and } X^n-\dfrac{1}{b} \text{ share a root.}}$$