9
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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)$. $\endgroup$ Nov 12, 2021 at 15:46
  • $\begingroup$ 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. $\endgroup$
    – Digitallis
    Nov 13, 2021 at 10:03
  • $\begingroup$ @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. $\endgroup$
    – user3472
    Nov 13, 2021 at 20:23

2 Answers 2

5
+50
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .