# Zeilberger's determinant evaluation problem

Doron Zeilberger posted a question here: http://arxiv.org/abs/1401.1532 of evaluating the determinant of a very sparse matrix. The $2d \times 2d$ matrix $M(d)$ has ones in the pattern $1,0,1,0,1,0,\dots$ in both the subdiagonals and the superdiagonals. And $M_{b-1,2b}=M_{3b+1,2b-1}=-1$, for all $b$. The entries are zero everywhere else.

This matrix happens to be related to the Collatz Conjecture, in that the matrix is nonsingular for all $d$ iff there are no nontrivial cycles of the Collatz function iteration. See http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/detconj.html

If one swaps all odd and even columns, $2b-1$ and $2b$, one gets all ones on the diagonal of this matrix. Then if one performs Gaussian elimination, one gets an upper-triangular matrix with all ones on the diagonal (for any $d$); therefore, the matrix is nonsingular. I verified this on a spreadsheet.

If this doesn't convince you, here is a formal proof:

(Invalid formal proof)

We'll prove the conjecture that $\det M(d)=(−1)^d$, via induction on $d$. It's trivial to check for $d=1,2$.

We'll assume true for $d=k$ and prove true for $d=k+1$. We'll use Laplace expansion (by cofactors) along column $2d−1$ to prove that the $\det M(d)=(−1)^d$. Notice that this column has only one nonzero entry in the last row, namely 1; therefore, $\det M(d)=(−1)^{2d+(2d−1)}M_{2d,2d−1}=−M_{2d,2d−1}$.

Suppose $d$ is odd. Then to evaluate $M_{2d,2d−1}$, we use Laplace expansion along row $2d−1$. Then $M_{2d,2d−1}=(−1)^{(2d−1)+(2d−1)}\det M(d−1)=\det M(d−1)$, since the only nonzero entry is in column $2d$, which is 1. Hence, $\det M(d)=−M_{2d,2d−1}=−\det M(d−1)=(−1)^d$, by the induction hypothesis.

Suppose $d$ is even. Then to evaluate $M_{2d,2d−1}$, again we use Laplace expansion along row $2d−1$. There are two nonzero entries in this row, namely the one in column $2d$, which is 1, and the one in column $d+1$, which is -1. Then we get $M_{2d,2d−1}=(−1)^{(2d−1)+(2d−1)}M(d−1)+(−1)^{(2d−1)+(d+1)}\cdot (−1)\cdot 0=\det M(d−1)$. The last term is zero, because row $d+2$ has all zeroes when column $d+1$ is deleted. Hence, $\det M(d)=−M_{2d,2d−1}=−\det M(d−1)=(−1)^d$, by the induction hypothesis. QED

What am I missing here? This was way too easy.

-
When doing Gaussian elimination to get rid of the -1's below the diagonal you introduce new -1's. It's not clear that if you keep doing this process you don't eventually cancel something on the diagonal. Perhaps you can elaborate. – Nate Jan 10 '14 at 19:45
I checked for this on a spreadsheet. It's clearly not the case, as the new -1's only get introduced above the diagonal, not below or on the diagonal, when adding the rows during the Gaussian elimination process. I also calculated the determinant as $(-1)^d$ when I did Laplace cofactor-expansion and used induction on $d$. – Craig Feinstein Jan 10 '14 at 19:58
Could you please present one of your spreadsheet examples? – Alex R. Jan 10 '14 at 20:19
So to start we have a line of 1's with slope -1, and two lines of -1's with slopes -2 and -2/3. If we we eliminate the line of slope -2 we introduce a new line of -1's of slope -4/3, which are below the diagonal. However if we eliminate this line of -1's we get a new line of slope -8/9, which lies above the diagonal. So yes, I agree that this works. – Nate Jan 10 '14 at 20:30
Ahh wait, if I work with the transpose of what I was doing it only takes one Gaussian elimination step as you suggested. I must have flipped it at some point. – Nate Jan 10 '14 at 20:43

You probably haven't proven that there are no non-trivial finite orbits of the Collatz sequence. You appear to have convinced yourself by testing out some cases with a spreadsheet. Please read Robin Chapman's proof of equivalence, and perhaps ask some questions about it on here if you don't understand it. It should clarify things for you. His proof doesn't rely on any advanced techniques. [Note that there is a mistake on the first page of his proof. When he considers the action of $M(d)$ on the standard basis vectors, he appears to have meant $N(d)$, a matrix he defines in the proof.]

When you've understood this proof, you will see that your process of Gaussian elimination will end up with a cancellation on the diagonal if and only there is a nontrivial cycle of the Collatz sequence with values between $2$ and $2d+1$. It's not enough to stare at some examples and say there cannot be a cancellation. In fact its almost guaranteed that every example you can feasibly try on a spreadsheet will lead to no cancellation since the Collatz conjecture is known to hold for $n \leq 5\times2^{60}$.

As for your second argument, it shows signs of ability, but I believe it be flawed as well. You've attempted to prove the conjecture by induction by using Laplace expansion. You are correct that column $2d-1$ of $M(d)$ has as its only nonzero entry a $1$ in the $2d_{th}$ row. Thus $\det(M(d)) = (-1)\det(M_{2d,2d-1}(d))$ is true, where $M_{2d,2d-1}(d)$ is the minor of $M(d)$ at position $(2d, 2d-1)$. Everything is Ok up to here, but I've found counterexamples to your following assertions. I encourage you to take a look at $M(7)$ and $M(9)$ for example, to see that your assertions about the number of nonzero entries in row $2d-1$ of the minor $M_{2d,2d-1}$ don't always hold.

The following was unable to convince you that you may not have proven that its impossible to cancel something on the diagonal when performing Gaussian elimination as above. I'm going to leave it up in case someone else finds it helpful.

For each positive integer $d$ let $M^{\prime}(d)$ be the $2d\times 2d$ matrix with entries in $\left\{-1,0,1\right\}$ such that for $1 \leq a \leq 2d$ and $1 \leq b \leq d$

$$M^{\prime}_{a,2b-1} = \left\{\begin{array}{lr} 1 & : a = 2b\\ -1& : a = 3b+3\\ 0 & : \mbox{otherwise}\end{array} \right.$$

$$M^{\prime}_{a,2b} = \left\{\begin{array}{lr} 1 & : a = 2b-1\\ -1& : a = b-1\\ 0 & : \mbox{otherwise}\end{array} \right.$$

and consider the conjecture that $\det(M^{\prime}(d)) = (-1)^{d}$ for each positive integer $d$.

This is equivalent to whether or not there exist non-trivial cycles in the Collatz like sequence

$$x_{n} = \left\{\begin{array}{lr} \frac{x_{n-1}}{2} & : x_{n-1} \mbox{ even}\\ \frac{3x_{n-1}+3}{2} & : x_{n} \mbox{ odd}\end{array} \right.$$

It is known that there do exist non-trivial cycles of this related sequence. So in this case the determinant conjecture must be false. In fact, I've verified that for $d \geq 5$, $\det(M^{\prime}(d)) = 0$. Can you explain why your argument wouldn't also work for $M^{\prime}(d)$?

For each odd positive integer $k$, we can formulate a similar determinant problem corresponding to the Collatz like sequence

$$x_{n} = \left\{\begin{array}{lr} \frac{x_{n-1}}{2} & : x_{n-1} \mbox{ even}\\ \frac{3x_{n-1}+k}{2} & : x_{n} \mbox{ odd}\end{array} \right.$$

For $k > 1$, each of these sequences have non-trivial finite orbits. Can you explain why your argument doesn't work for any odd $k > 1$?

-
I changed my excel spreadsheet formula to "=IF(MOD(C$2,2)=0,IF($B3=C$2-1,1,IF($B3=C$2/2-1,-1,0)),IF($B3=C$2+1,1,IF($B3=3*(‌​C$2+1)/2+3,-1,0)))". – Craig Feinstein Jan 13 '14 at 22:31 When I switched odd and even columns as I did with the original matrix, I couldn't do Gaussian elimination without getting nonzero stuff caught below the diagonal with your matrix. This is when$k=3\$. These problems happened immediately when I tried Gaussian elimination. – Craig Feinstein Jan 13 '14 at 22:36
Everything is clear once you put it in a spreadsheet. – Craig Feinstein Jan 13 '14 at 22:41
Thank you @AlbertSteppi. I agree that I made a mistake that doesn't appear to be easily fixable. – Craig Feinstein Jan 14 '14 at 2:18
Looking at it again @AlbertSteppi, I agree with you that the informal part is lacking too. The stuff on the upper triangle could play a role in the Gaussian elimination later on. It's a complicated problem. Thanks again for your help!!! – Craig Feinstein Jan 14 '14 at 14:08