Zeilberger's determinant evaluation problem

Question

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.

Answer 1

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$?