Determinant of the circulant matrix corresponding to the $r$-tuple $(1, 1, 0, 0, \ldots , 0, 0)$

Question

For any integer $r \geq 3$, consider the $r$-tuple $(1, 1, 0, 0, \ldots , 0, 0)$ (involving $r - 2$ zeros) which represents the first row of the corresponding $r \times r$ circulant matrix. Show that the determinant of the corresponding circulant matrix for the $r$-tuple is $1 + (−1)^{r+1}$.

Originally the problem was asked to show that

$$\det \begin{bmatrix} 1 & 1 & 0 & 0 & \ldots & 0 & 0 \\ 0 & 1 & 1 & 0 & \ldots & 0 & 0 \\ 0 & 0 & 1 & 1 & \ldots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \ldots & 1 & 1 \\ 1 & 0 & 0 & 0 & \ldots & 0 & 1 \\ \end{bmatrix} = 1 + (−1)^{r+1}.$$

Then I figured out that the matrix involved in this determinant is a $r×r$ circulant matrix for any integer $r \geq 3$ (otherwise, it doesn't make sense with the $1 + (−1)^{r+1}$ expression).

I don't know much about circulant matrices (just definition). I wanted to solve the problem by induction. But I'm unable to proceed with the induction step. I mean, if $P(r)$ be the statement that the determinant of the corresponding $r×r$ circulant matrix for the $r$-tuple $(1, 1, 0, 0, \ldots , 0, 0)$ is $1 + (−1)^{r+1}$, then if $P(r)$ is true for some integer $k \geq 3$, then how can I show that $P(k+1)$ is true?

Answer 1

There are several possible ways to show this. Let $M_r$ be the $r \times r$ circulant matrix described. Here is an outline of two ways which do not involve induction.

1. Expansion by minors (as described in the comment). Recall that the determinant of an upper (or lower) diagonal matrix is simply the product of the diagonal entries. Hence $$\det M_r = 1 \cdot \left| \begin{matrix} 1 & 1 & 0 & \ldots & 0 \\ 0 & 1 & \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & 0 \\ \vdots & & \ddots &\ddots & 1 \\ 0 & \ldots & \ldots& 0 & 1\end{matrix} \right|_{r-1} + (-1)^{r-1} \left| \begin{matrix} 1 & 0 & \ldots & \ldots & 0 \\ 1 & 1 & \ddots & & \vdots \\ 0 & \ddots & \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots &\ddots & 0 \\ 0 & \ldots & 0 & 1 & 1\end{matrix} \right|_{r-1}.$$ In each case, the minors have determinant $1$ and the result follows.

2. Row reduction. If $m_k$ is the $k^{\rm th}$ row of $M_r$ for $k \in \{1, \ldots, r\}$, then the alternating sum $$\sum_{k=1}^{r-1} (-1)^k m_k = \begin{bmatrix}-1 & 0 & \ldots & 0 & (-1)^{r-1}\end{bmatrix}.$$ Adding this to the last row of $M_r$ yields an upper diagonal matrix whose entries on the main diagonal are all $1$ except the last, which is $1 + (-1)^{r-1}$, and again, the result follows.

Answer 2

You can show this using Laplace expansion :$$\det A_{r\times r}=\begin{vmatrix}1 & 1 & 0 & 0 & \ldots & 0 & 0 \\ 0 & 1 & 1 & 0 & \ldots & 0 & 0 \\ 0 & 0 & 1 & 1 & \ldots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & & \vdots & \vdots \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \ldots & 1 & 1 \\ 1 & 0 & 0 & 0 & \ldots & 0 & 1 \\ \end{vmatrix} = 1\cdot \begin{vmatrix} 1 & 1 & 0 & \ldots & 0 & 0 \\ 0 & 1 & 1 & \ldots & 0 & 0 \\ \vdots & \vdots & \ddots & & \vdots & \vdots \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \ldots & 1 & 1 \\ 0 & 0 & 0 & \ldots & 0 & 1 \\ \end{vmatrix}_{(r-1)\times(r-1)} +\\+(-1)^3\cdot \begin{vmatrix} 0 & 1 & 0 & \ldots & 0 & 0 \\ 0 & 1 & 1 & \ldots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & & \vdots & \vdots \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \ldots & 1 & 1 \\ 1 & 0 & 0 & 0 & \ldots & 0 & 1 \\ \end{vmatrix}_{(r-1)\times(r-1)}$$ The first determinant on the RHS is equal to $1$ for the second you can continue doing Laplace expansion $r-1$ times and you will get $(-1)^{3(r-1)}|1|=(-1)^{r-1}=(-1)^{r+1}$. Thus we can derive the given statement and conclude that it is correct.