Sí.
Consideremos las matrices de adyacencia $$ A = \left[\begin{array}{rrrrrrrrrrr} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\\\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{array}\right] $$ y $$ B = \left[ \begin{array}{rrrrrrrrrrr} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\\\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\\\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{array}\right]. $$ Ambas son las matrices de adyacencia de los árboles, y ambas tienen el polinomio característico $$\lambda^{11}-10\lambda^9+34\lambda^7-47\lambda^5+25\lambda^3-4\lambda.$$ Cada árbol tiene exactamente dos vértices de grado 3, separados por un camino de longitud 1 en el caso de $A$ pero de longitud 2 en el caso de $B$ . En particular, los árboles no son isomorfos.
Ahora considere la matriz [EDIT: mejorada, mucho más bonita] $$ C = \left[\begin{array}{rrrrrrrrrrr} 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & -1 \\\\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\\\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\\\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\\\ \end{array}\right] $$ con determinante $-1$ .
Desde $C^{-1}AC = B$ los dos árboles (en 11 vértices) no son isomorfos pero tienen matrices de adyacencia que son conjugadas sobre $\mathbb Z$ .
Ahora explicaré de dónde viene el ejemplo. El par de gráficos fue construido por un método, atribuido a Schwenk, que encontré en el capítulo de Temas de teoría algebraica de grafos (editado por Beineke y Wilson). Las primeras 9 filas y columnas de $A$ en común con $B$ provienen de un árbol particular en 9 vértices que tiene un par de puntos de unión tales que al extender el árbol de la misma manera desde cualquiera de los dos puntos se obtienen espectros isomórficos. Añadir un solo vértice colgante no puede funcionar para este problema, como descubrí usando el truco de Brouwer y van Eijl, mencionado por Chris Godsil, de comparar las formas normales de Smith de polinomios (muy) pequeños en $A$ y $B$ , en este caso $A+2I$ y $B+2I$ . Sin embargo, cuando se añade un camino de longitud dos en cualquiera de los dos vértices especiales, no parece haber ninguna obstrucción de este tipo.
Entonces me puse a intentar conjugar ambos $A$ y $B$ por separado, a la matriz compañera de su polinomio característico mutuo, buscando un vector entero pequeño al azar $x$ para la cual la matriz $X_A = [ x\ Ax\ A^2x\ \ldots\ A^{10}x]$ tiene un determinante $\pm 1$ , y de forma similar $y$ dando $Y_B$ . (El hecho de que lo haya conseguido con bastante facilidad puede tener que ver con el hecho de que $A+I$ es invertible sobre $\mathbb Z$ .) La matriz $X_AY_B^{-1}$ entonces actúa como el $C$ arriba.
[EDIT: La matriz real $C$ que encontré al azar y el primero que publiqué no era tan bonito, con una norma de Frobenius casi diez veces superior al ejemplo actual. Pero tomando las potencias 0 a 10 de $A$ veces $C$ dio un $\mathbb Q$ -para el espacio completo de conjugadores, cuya forma normal de Smith (como 11 vectores en $\mathbb R^{121}$ ) era todo 1 en la diagonal, así que de hecho era un $\mathbb Z$ -base. Al realizar una reducción LLL en esta base reticular, se obtuvo una lista de matrices de menor norma, la tercera de las cuales es la más ilustrativa $C$ dado anteriormente, de determinante $-1$ . Los otros determinantes de la base reducida fueron todos $0$ y $\pm 8$ .]
Tomando la racionalidad $x$ y sin restringir el determinante de $X_A$ da un espacio de posibles matrices racionales $C$ de dimensión 11, que son genéricamente invertibles; variando $y$ da el mismo espacio [EDIT: al igual que multiplicar por la izquierda por potencias (o en el caso más general conmutantes) de $A$ ]. Dado que el espectro de $A$ no tiene raíces repetidas, ésta es también la dimensión del conmutador de $A$ y toda matriz que conjugue $A$ a $B$ se encuentra en este espacio. Partiendo de una base racional, no es difícil encontrar una base exacta para el subespacio de los enteros, y tomando el determinante de un punto general en el entramado de los enteros se obtiene un polinomio entero en 11 variables que toma el valor $1$ o $-1$ si y sólo si las matrices $A$ y $B$ son conjugados sobre $Z$ . Si hay raíces repetidas, hay que trabajar un poco más; en general el espacio completo tiene la dimensión de la suma de los cuadrados de las multiplicidades, y se genera multiplicando por la izquierda por una base del espacio conmutador de $A$ . Se puede producir una base para el conmutador (para una matriz diagonalizable) conjugando primero $A$ a una suma directa de las matrices compañeras para los factores irreducibles del polinomio característico, y luego una a una, para cada $k$ -por- $k$ bloque correspondiente a un $k$ -factor de grado repetido $m$ sustituyendo cada uno de los $k^2$ bloques con poderes $0$ a $m-1$ de la matriz de acompañamiento para ese factor, con $0$ en cualquier otro lugar.
