# Determinant of matrix with $2$'s and the pattern $3\ 1\ 3$

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 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.

• What if we replace $3$ by $2+x$ and $1$ by $2-x$ everywhere? The determinant of the resulting matrix is a monic polynomial $D_n(x)$ in $x$ of degree $n$. At $x=0$ the matrix has rank $1$, so $x^{n-1}$ is a factor of $D_n(x)$. In other words $D_n(x)=x^n+A_nx^{n-1}$ for some sequence of constants $A_n$ that I don't have any idea how to calculate, yet. The answer will, of course, be $D_n(1)$. Nov 12, 2021 at 15:46
• If you want to use row operations the next operations after what you did should be more row operations. Use $R_1$ to cancel the first term in $R_n$. Then use $R_2$ to cancel out the 2nd term in $R_n$. Then use $R_3$ to cancel out the 3rd term in $R_n$. Then use $R_4$ to ... etc. This will give you an upper triangle matrix. Nov 13, 2021 at 10:03
• @Digitallis I've found ways similar to that to come up with an upper triangular matrix, but computing the determinant of that matrix is not so straightforward; you have to keep track of the last entry after every operation. The answers given below seem to provide better methods. Nov 13, 2021 at 20:23

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.

Let $$e$$ be the vector of ones and $$N$$ be the full-sized nilpotent Jordan block. Since $$A_n$$ is a rank-one update of $$B_n=I-N+N^2$$, by Sylvester's determinant lemma we get $$\det(A_n)=\det(B_n+2ee^T)=\det(B_n)(1+2e^TB_n^{-1}e)=1+2e^TB_n^{-1}e.$$ So, we need to find the sum of all entries in $$B_n^{-1}$$. Since $$B_n$$ is a polynomial in $$N$$, so must be its inverse. Let $$B_n^{-1}=c_0I+c_1N+c_2N^2+\cdots+c_{n-1}N^{n-1}$$. The equation $$B_nB_n^{-1}=I$$ gives the recurrence relation $$c_0=c_1=1$$ and $$c_k=c_{k-1}-c_k$$, whose solution is given by a repetition of the pattern $$(1,1,0,-1,-1,0)$$. So, when $$n=6q+r$$, we have \begin{aligned} B_n^{-1} &=(I+N-N^3-N^4)+(N^6+N^7-N^9-N^{10})+\cdots\\ &\quad+(N^{6q-6}+N^{6q-5}-N^{6q-3}-N^{6q-2})\\ &\quad+ \begin{cases} 0&\text{if }r=0,\\ N^{6q}&\text{if }r=1,\\ N^{6q}+N^{6q+1}&\text{if }r=2,3,\\ N^{6q}+N^{6q+1}-N^{6q+3}&\text{if }r=4,\\ N^{6q}+N^{6q+1}-N^{6q+3}-N^{6q+4}&\text{if }r=5.\\ \end{cases} \end{aligned} Since the sum of all entries in $$N^k+N^{k+1}-N^{k+2}-N^{k+3}$$ is equal to $$6$$, we get \begin{aligned} e^TB_n^{-1}e &=\begin{cases} 6q&\text{if }r=0,\\ 6q+r&\text{if }r=1,\\ 6q+r+(r-1)&\text{if }r=2,3,\\ 6q+r+(r-1)-(r-3)&\text{if }r=4,\\ 6q+r+(r-1)-(r-3)-(r-4)&\text{if }r=5\\ \end{cases}\\ &=\begin{cases} n&\text{if }r=0,1,\\ n+1&\text{if }r=2,5,\\ n+2&\text{if }r=3,4.\\ \end{cases} \end{aligned} Thus \begin{aligned} \det(A_n)=1+2e^TB_n^{-1}e &=\begin{cases} 2n+1&\text{if }r=0,1,\\ 2n+3&\text{if }r=2,5,\\ 2n+5&\text{if }r=3,4.\\ \end{cases} \end{aligned}

PS. The form $$B_n=I-N+N^2$$ suggests that there might be a simpler solution that uses generating functions, but I am satisfied with my current answer here.