Zeilberger del determinante problema de la evaluación

Question

Doron Zeilberger publicado una pregunta aquí: http://arxiv.org/abs/1401.1532 de evaluar el determinante de una matriz dispersa. El $2d \times 2d$ matriz $M(d)$ tiene en el patrón de $1,0,1,0,1,0,\dots$ tanto en el subdiagonals y la superdiagonals. Y $M_{b-1,2b}=M_{3b+1,2b-1}=-1$, para todos los $b$. Las entradas son cero en todas las demás.

Esta matriz pasa a ser relacionados con la Conjetura de Collatz, en que la matriz es nonsingular para todos los $d$ fib no hay ninguna que no sea trivial ciclos de la Collatz función de iteración. Ver http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/detconj.html

Si uno de los swaps de todos los pares y los impares columnas, $2b-1$$2b$, se obtiene todos unos en la diagonal de esta matriz. Entonces, si se realiza la eliminación Gaussiana, uno recibe una parte superior triangular de la matriz con todos los que están en la diagonal (para cualquier $d$); por lo tanto, la matriz es nonsingular. He comprobado esto en una hoja de cálculo.

Si esto no te convence, aquí es una prueba formal:

(No válido prueba formal)

Vamos a probar la conjetura de que $\det M(d)=(−1)^d$, a través de la inducción en $d$. Es trivial comprobar $d=1,2$.

Suponemos cierto para $d=k$ y demostrar verdadero para $d=k+1$. Vamos a utilizar Laplace en la expansión por cofactores) a lo largo de la columna de $2d−1$ a demostrar que el $\det M(d)=(−1)^d$. Aviso de que esta columna tiene sólo un valor distinto de cero en la entrada de la última fila, a saber: 1; por lo tanto, $\det M(d)=(−1)^{2d+(2d−1)}M_{2d,2d−1}=−M_{2d,2d−1}$.

Supongamos $d$ es impar. A continuación, para evaluar $M_{2d,2d−1}$, hacemos uso de Laplace de expansión a lo largo de la fila $2d−1$. A continuación,$M_{2d,2d−1}=(−1)^{(2d−1)+(2d−1)}\det M(d−1)=\det M(d−1)$, ya que la única entrada es distinto de cero en la columna $2d$, que es 1. Por lo tanto, $\det M(d)=−M_{2d,2d−1}=−\det M(d−1)=(−1)^d$, por la hipótesis de inducción.

Supongamos $d$ es incluso. A continuación, para evaluar $M_{2d,2d−1}$, nuevamente hacemos uso de Laplace de expansión a lo largo de la fila $2d−1$. Hay dos distinto de cero entradas en esta fila, es decir, aquella en la columna $2d$, que es 1, y el uno en la columna $d+1$, que es -1. A continuación, llegamos $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)$. El último término es igual a cero, debido a que la fila $d+2$ tiene todos los ceros cuando la columna $d+1$ es eliminado. Por lo tanto, $\det M(d)=−M_{2d,2d−1}=−\det M(d−1)=(−1)^d$, por la hipótesis de inducción. QED

Lo que me estoy perdiendo aquí? Esto era demasiado fácil.

Answer 1

Usted probablemente no han demostrado que no hay no-trivial finito órbitas de la secuencia de Collatz. Parece que ha convencido a ti mismo probando algunos casos con una hoja de cálculo. Por favor, lea Robin Chapman prueba de equivalencia, y tal vez hacer algunas preguntas acerca de ella aquí si que no lo entiendo. Debería aclarar las cosas para usted. Su prueba no depende de ningún técnicas avanzadas. [Tenga en cuenta que hay un error en la primera página de su prueba. Cuando se considera a la acción de la $M(d)$ en el estándar de los vectores de la base, parece haber significaba $N(d)$, una matriz se define en la prueba.]

Cuando has entendido esta prueba, usted verá que su proceso de eliminación Gaussiana va a terminar con una cancelación de la diagonal si y sólo hay un trivial ciclo de la secuencia de Collatz, con valores entre $2$$2d+1$. No basta con mirar algunos ejemplos y decir que no puede haber una cancelación. De hecho, es casi garantizado que cada ejemplo puede factibles de tratar en una hoja de cálculo, conducen a la no cancelación desde la conjetura de Collatz es conocido a $n \leq 5\times2^{60}$.

En cuanto a tu segundo argumento, muestra signos de capacidad, pero creo que son falsas también. Lo he intentado probar la conjetura por inducción mediante el uso de Laplace de expansión. Estás en lo correcto de que la columna de $2d-1$ $M(d)$ tiene como único distinto de cero de la entrada de un $1$ $2d_{th}$ fila. Por lo tanto $\det(M(d)) = (-1)\det(M_{2d,2d-1}(d))$ es verdadera, donde $M_{2d,2d-1}(d)$ es el menor de $M(d)$ en la posición $(2d, 2d-1)$. Todo está bien hasta aquí, pero me he encontrado contraejemplos para sus siguientes afirmaciones. Os animo a echar un vistazo a $M(7)$ $M(9)$ por ejemplo, para ver que sus afirmaciones sobre el número de distinto de cero entradas en la fila $2d-1$ de la menor $M_{2d,2d-1}$ no siempre se cumple.

El siguiente fue incapaz de convencer a usted que usted puede no haber demostrado que su imposible cancelar algo en la diagonal cuando la realización de eliminación Gaussiana como la anterior. Voy a dejar que en caso de que alguien más lo encuentra útil.

Para cada entero positivo $d$ deje $M^{\prime}(d)$ $2d\times 2d$ matriz con entradas en $\left\{-1,0,1\right\}$ tal que para $1 \leq a \leq 2d$ $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. $$

y considerar la conjetura de que $\det(M^{\prime}(d)) = (-1)^{d}$ para cada entero positivo $d$.

Esto es equivalente a si existe o no existe la no-trivial de los ciclos en la Collatz como secuencia

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

Es conocido que existen no trivial de los ciclos de esta secuencia relacionada. Así que en este caso el determinante conjetura debe ser falsa. De hecho, he comprobado que para $d \geq 5$, $\det(M^{\prime}(d)) = 0$. Puede usted explicar por qué su argumento no también para $M^{\prime}(d)$?

Para cada entero positivo impar $k$, podemos formular una similar determinante problema correspondiente a la Collatz como secuencia

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

Para $k > 1$, cada una de estas secuencias no-trivial finito de las órbitas. Puede usted explicar por qué su argumento no funciona para cualquier extraño $k > 1$?