Vamos $$A = \begin{pmatrix} 3&1 \\ 0&1 \end{pmatrix}$$ and $$B = \begin{pmatrix} 1&0\\ 1&2 \end{pmatrix}$$ I want to show that the only elements of the semigroup generated by $Un$ and $B$ that have integer eigenvalues are elements of the form $A^n$ and $B^n$, where $n \in \mathbb{N}$. He intentado todas las maneras que puedo pensar. Es posible que un problema como este es indecidible?
Respuestas
¿Demasiados anuncios?
Danimal
Puntos
5721
El problema general de este tipo es indecidible. Más precisamente, no hay ningún algoritmo que toma como entrada dos $n \times n$ entero matrices y decide si el semigroup que generan contiene una matriz en la que todos los autovalores son enteros.
Prueba: Dado dos $n \times n$ entero matrices $A$ e $B$, elegir un primer $p \ge 5$ tal que $p>n$, elija un grado $p$ monic integral polinomio $f(x)$ con la plena grupo simétrico $S_p$ como grupo de Galois, vamos a $C$ ser $p \times p$ matriz de enteros con polinomio característico $f(x)$, y considerar el tensor de productos (productos de Kronecker) $A \otimes C$ e $B \otimes C$. Un elemento de la semigroup generadas por estos dos $np \times np$ matrices tiene la forma $M \otimes C^m$ para algunos $M$ en el semigroup generado por $A$ e $B$ y algunos $m \ge 1$. Cada autovalor de $M$ es de grado en la mayoría de las $n$ sobre $\mathbf{Q}$, pero cada autovalor de $C^m$ es de grado exactamente $p$, por lo que los valores propios de $M \otimes C^m$ son todos los números enteros si y sólo si todos los valores propios de $M$ se $0$, el cual tiene si y sólo si $M$ es nilpotent. Así, el semigroup generado por $A \otimes C$ e $B \otimes C$ contiene una matriz en la que todos los autovalores son enteros si y sólo si el semigroup generado por $A$ e $B$ contiene la matriz cero. Pero la última propiedad es indecidible: consulte el Capítulo 3 de este artículo. Por lo tanto, uno no puede tener un algoritmo que responder el entero autovalor pregunta para $A \otimes C$ e $B \otimes C$ en general.
twk
Puntos
151
Acabo de encontrar este problema. Si usted trata de la matriz $A^nB^m$, entonces su pregunta para tales matrices es equivalente a este número de la teoría de la pregunta: ¿ $9^n+2\cdot 9^n\cdot 2^m-12\cdot 3^n\cdot 2^m+2\cdot 3^n+4^{m}\cdot 9^n+4^{m}+2\cdot 2^m+9$ ser un cuadrado proporcionado $m,n\ne 0$. Tenga en cuenta que si denotamos $3^n$ por $x$, $2^m$ por $y$, obtenemos un polinomio de cuarto grado en $x,y$. Espero número de teóricos que aquí se puede decir algo acerca de este exponencial de la ecuación de Diophantine.
La respuesta al problema con el signo de interrogación es "obviamente NO". Para ser indecidible, usted debe tener un problema masivo. Por $A,B$, se tiene el siguiente problema: dado un producto $W(A,B)$ es cierto que la matriz tiene un número entero valor propio. Que problema es, obviamente, decidable. La cuestión de si esto es cierto para cada palabra $W$ requiere de contestar "sí" o "no" y no es un problema masivo. Todavía se puede pedir si es independiente de ZF o incluso ZFC (o no demostrable en la aritmética de Peano). Lo Bjorn tenía en mente es completamente diferente y mucho más difícil problema cuando se incluyen las $A, B$ en la entrada y preguntar si para este $A$, $B$ algunos de producto $W(A,B)$ no de la forma $A^n, B^m$ tiene un número entero valor propio. Este es un problema masivo que podría ser indecidible (aunque él, por supuesto, no demostrarlo). Pero esto no tiene nada que ver con la pregunta original.
