I was working on the following problem (#284) from the book "Putnam and Beyond" (2017):
Solve the system of equations for $x_1, \ldots, x_{100}$: $x_i + x_{i+1} + x_{i+2} = 0$ for $1\le i\le 100$. (Indices wrap around cyclically.)
I solved it (finding the solution $x_i = 0$ for all $i$) by summing all the equations and subtracting the 33 necessary equations to find any given variable.
However, I was wondering if I could apply Cramer's Rule to this system. In order to do so, I would need to demonstrate that the determinant of the coefficient matrix is nonzero.
I used Wolfram|Alpha to compute the generalized determinant $\det A_n$, where $A_n(i,j) = 1$ if $j - i = 0, 1, 2$ and $0$ otherwise, and I noticed that $\det A_n$ seems to always equal $3$. (Example for $n=5$: link.)
Can someone explain how to prove this observation? The only potential approach I see is to generalize $A_n$ to be a function of a variable $x$ (perhaps replacing $1$s along the diagonal), factor it, and evaluate it again. Are there general techniques for such determinants?
Let $C_n$ be the cyclic group of order $n$, generated by $t$. Let $\mathbb{Z}[C_n]$ be the group ring. We have a commutative diagram, where each row is a short exact sequence of $\mathbb{Z}[C_n]$ modules:
\begin{eqnarray*}\begin{array}{ccccccccc} 0&\to& I &\to &\mathbb{Z}[C_n] &\stackrel\epsilon\to &\mathbb{Z}&\to&0\\ &&g\downarrow\,\,\,&&\downarrow f&&\,\,\,\,\,\downarrow3\\ 0&\to& I &\to &\mathbb{Z}[C_n] &\stackrel\epsilon\to &\mathbb{Z}&\to&0 \end{array} \end{eqnarray*} where $f$ is multiplication by $1+t+t^2$. Then the determinant you are looking for is: $${\rm Det}_\mathbb{Z}(f)=3{\rm Det}_\mathbb{Z}(g)$$
Here $I$ is the augmentation ideal and is generated by $1-t$ over $\mathbb{Z}[C_n]$ and $\epsilon$ is the augmentation map, sending $1\mapsto 1$.
Suppose $n=3k$. Then \begin{eqnarray*}&\,\,&g((1-t)(1+t^3+t^6+\cdots +t^{3(k-1)}))\\&=&(1+t+t^2)(1-t)(1+t^3+t^6+\cdots +t^{3(k-1)})=0,\end{eqnarray*} so $g$ has non-trivial kernel and ${\rm Det}_\mathbb{Z}(g)=0$, so your determinant is $0$.
On the other hand, if $n\neq 3k$ for any integer $k$, then we may pick $r$ such that $3r\equiv 1\mod n$.
Then: \begin{eqnarray*}&\,\,&g((1-t)(1+t^3+t^6+\cdots +t^{3(r-1)}))\\&=&(1+t+t^2)(1-t)(1+t^3+t^6+\cdots +t^{3(r-1)})=1-t.\end{eqnarray*} Thus $g$ is surjective and must have determinant $\pm1$, so your determinant is $\pm3$.