Let for $n\ge 1, D_n$ be the determinant of the $n\times n$ matrix $A_n$ where the entries along the main diagonal (i.e. of the form $(i,i)$ for $1\leq i\leq n$) are all $3$, entries of the form $(i,i+1)$ are equal to $1$, entries of the form $(i, i+2)$ are equal to $3$, and all other entries are $2$. Find, with proof, a formula for the determinant of $D_n$.
For instance, the matrix $A_n$ for $n=4$ is shown below.
$$A_4 =\begin{pmatrix} 3 & 1 & 3 & 2 \\
2 & 3 & 1 & 3\\
2 & 2 & 3 & 1\\
2 & 2 & 2 & 3\end{pmatrix}.$$
I found the following formula after a bit of experimentation, but I wasn't able to prove it: $$D_n = 1 + 12\lfloor \frac{n}6\rfloor + \begin{cases}2,&\text{ if $n\equiv 1\bmod 6$}\\
6,&\text{ if $n\equiv 2\bmod 6$}\\
10, &\text{ if $n\equiv 3\bmod 6$}\\
12, &\text{ if $n\equiv 4 $ or $5\bmod 6$}\\
0,&\text{ otherwise}\end{cases}.$$
One can define $D_0 := 1$. I know $D_2 = 7$ and using row operations. So far, I've come up with the following sequence of operations, but I seem to be stuck after the last step. In the description below, $R_i$ represents the $i$th row and $C_i$ represents the ith column of $A_n$. Suppose $n > 2$.
Perform the operation $R_i \mapsto R_i – R_n$ for $2\leq i < n.$ Then the resulting matrix has all zeroes for entries of the form $(i, j)$ for $i < j$ that are not on the last row. The entries on the last row are $n-1$ $2$'s followed by a $3$. Also, entries along the main diagonal are all $1$'s and the only entry of the form $(i,i+1)$ where $2\leq i <n$ that does not equal $-1$ is $(n-1,n)$, and that entry equals $-2$. Entries of the form $(i,i+2)$ where $2\leq i < n-2$ are equal to one while entry $(n-2,n)$ equals $0$ if it exists.
Now perform the operations $C_i \mapsto C_i – C_1$ for $2\leq i < n$. This removes all the $2$'s on the last row except for the first, and the entries on the top row are $3, -2,0$, followed by $-1$'s and ending with $2$ (the sequence stops whenever $n$ is reached, so if $n=3$, the entries would be $3,-2,0$).
Finally, perform the operations $R_i \mapsto R_i + R_{i+1}$ for $2\leq i\le n-2$.
After performing these operations, for $n=5$, the following matrix is obtained:
$$\begin{pmatrix}
3& -2 & 0 & -1 & 2\\
0 & 1 & 0 & 0 & 2\\
0 & 0 & 1 & 0 & -2\\
0 & 0 & 0 & 1 & -2\\
2 & 0 & 0 & 0 & 3
\end{pmatrix}.$$
I can't seem to "zero out" the $2$ in the bottom left corner, despite trying various row and column operations. I think I should split the proof into cases based on the remainder when $n$ is divided by $6$, which is suggested by the formula at the beginning.
I tried considering other approaches such as finding eigenvalues and deriving a recurrence relation for $D_n$, but those approaches didn't seem to help much.
Best Answer
The formula proposed is indeed correct.
Let $J$ be the all-$1$'s matrix, $I$ the identity, and $N$ the (nilpotent) matrix with $n_{i,j}=\delta_{i,i+1}$.
Then the matrix whose determinant we seek is $A:=2J+I-N+N^2$.
For a moment let us write this as $A=2J+P$, or in terms of columns $A=[2u+p_1,2u+p_2,\dots,2u+p_n]$, with $u$ the all-$1$s vector. Using the linearity of $\det$ as a function of columns, and the fact that $\det$ is zero when two columns are the same, we see that $$ \det A=2\sum_{k=1}^{n}\det[p_1,\dots,p_{k-1},u,p_{k+1},\dots,p_n] +\det P. $$
Now in our case $P$ is upper unitriangular, so its determinant is $1$. Since all the entries of $u$ are $1$ we see that when we expand each of these determinants by this column, and then sum over $k$ all we are doing is summing the cofactors of $P$.
That is $$ \det A= 1+2\times \textrm{ the sum of the cofactors of $I-N+N^2$.} $$
The matrix $I-N+N^2$ is (as we have said) of determinant $1$ and so the sum of its cofactors is exactly the same as the sum of the entries of $(I-N+N^2)^{-1}$.
That is $$ \det A= 1+ 2\times \textrm{the sum of the entries of $(I-N+N^2)^{-1}$.} $$
Let us then find a useful expression for $(1-x+x^2)^{-1}$. Noting that this is the minimal polynomial for the sixth roots of unity we see that $$ (1-x+x^2)^{-1}= \frac{(1-x^2)(1+x+x^3)}{1-x^6}= \frac{(1+x-x^3-x^4}{1-x^6}= (1+x-x^3-x^4)\sum_{k=0}^\infty x^{6k}. $$
This gives us a formula for the entries of our matrix $(I-N+N^2)^{-1}$. There are $1$'s on the diagonal, $1$s on the (partial) diagonal above these, then $0$s, then $-1$s, then $-1$s, then $0$s; after that the pattern repeats.
By simple inspection of these matrices and summing their entries we can check that the proposed formula holds for $n=1,2,3,4,5,6$.
To prove that the formula holds in general we need to check that increasing the dimension by $6$ increases the sum of the entries by $6$.
So let us write $A_n$ for the relevant matrix in dimension $n$. We then have that $$ A_{n+6} =\begin{bmatrix} A_{6} & B\\ O & A_n \end{bmatrix} $$ where $B$ is a matrix of six rows and $n$ columns, these columns being the cyclic permutations of $(1,1,0,-1,-1,0)^T$, so that the column sums of $B$ are all equal to $0$.
With $u$ as the all-$1$'s vector of dimension $6$ and $v$ the all-$1$s vector of dimension $n$ we have that the sum of the entries of $A_{n+6}$ is $$ [u^ T v^T]A_{n+6}\begin{bmatrix} u\\v\end{bmatrix} = u^T A_6 u+ u^T B v+ v^T A_n v, = u^T A_6 u+ v^T A_n v. $$ That is, passing from dimension $n$ to dimension $n+6$ increases the sum of the entries by exactly the sum of the entries of $A_6$, that is by $6$ as required.