Polinomio de ciclo hamiltoniano

En matemáticas, el polinomio del ciclo hamiltoniano de una matriz n × n es un polinomio en sus entradas, definido como

${\displaystyle \operatorname {ham} (A)=\sum _{\sigma \in H_{n}}\prod _{i=1}^{n}a_{i,\sigma (i)}}$

donde es el conjunto de n - permutaciones que tienen exactamente un ciclo. ${\displaystyle H_{n}}$

Esta es una opción algebraica útil, en varios casos, para determinar la existencia de un ciclo hamiltoniano en un gráfico dirigido .

Es una generalización del número de ciclos hamiltonianos de un dígrafo como la suma de los productos de los pesos de arco de sus ciclos hamiltonianos (todos iguales a la unidad) para dígrafos ponderados con pesos de arco tomados de un anillo conmutativo dado. Mientras tanto, para un grafo ponderado no dirigido, la suma de los productos de los pesos de las aristas de sus ciclos hamiltonianos que contienen cualquier arista fija ( i , j ) se puede expresar como el producto del peso de ( i , j ) y el polinomio del ciclo hamiltoniano de una matriz recibida de su matriz de adyacencia ponderada al someter sus filas y columnas a cualquier permutación que mapee i a 1 y j a 2 y luego elimine su 1.ª fila y 2.ª columna.

En (Knezevic & Cohen (2017)) se demostró que

${\displaystyle \operatorname {ham} (A)=\sum _{J\subseteq \{2,\dots ,n\}}\det(-A_{J})\operatorname {per} (A_{\bar {J}})}$

donde es la submatriz de inducida por las filas y columnas de indexadas por , y es el complemento de en , mientras que el determinante de la submatriz vacía se define como 1. ${\displaystyle A_{J}}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle J}$ ${\displaystyle {\bar {J}}}$ ${\displaystyle J}$ ${\displaystyle \{1,\dots ,n\}}$

Debido a esto y a las identidades de Borchardt, para una matriz de Cauchy n × n no singular donde son matrices diagonales que hacen unitaria (en un cuerpo real o un cuerpo de característica finita, u ortogonal en el cuerpo de números complejos), es el cuadrado de Hadamard (entrada por entrada) de , y es la matriz identidad n × n con la entrada de índices 1,1 reemplazada por 0. ${\displaystyle C(x,y)}$ ${\displaystyle \operatorname {ham} (C(x,y))={\det }(-D_{1}^{2}C^{*2}(x,y)D_{2}^{2}+I_{/1})\operatorname {det} (C(x,y))}$ ${\displaystyle D_{1},D_{2}}$ ${\displaystyle D_{1}C(x,y)D_{2}}$ ${\displaystyle C^{*2}(x,y)}$ ${\displaystyle C(x,y)}$ ${\displaystyle I_{/1}}$

En un campo de característica 2 la igualdad se convierte en lo que por lo tanto proporciona una oportunidad para calcular en tiempo polinomial el polinomio del ciclo hamiltoniano de cualquier matriz unitaria (es decir, tal que donde es la matriz identidad n × n ), porque en tal campo cada menor de una matriz unitaria coincide con su complemento algebraico: donde es la matriz identidad n × n con la entrada de índices 1,1 reemplazada por 0. Por lo tanto, si es posible asignar en tiempo polinomial pesos de un campo de característica 2 a los arcos de un dígrafo que hacen que su matriz de adyacencia ponderada sea unitaria y que tenga un polinomio de ciclo hamiltoniano distinto de cero, entonces el dígrafo es hamiltoniano. Por lo tanto, el problema del ciclo hamiltoniano es computable en tales grafos en tiempo polinomial. ${\displaystyle \operatorname {ham} (A)=\sum _{J\subseteq \{2,\dots ,n\}}\det(-A_{J})\operatorname {per} (A_{\bar {J}})}$ ${\displaystyle \operatorname {ham} (A)=\sum _{J\subseteq \{2,\dots ,n\}}\det(A_{J})\det(A_{\bar {J}})}$ ${\displaystyle U}$ ${\displaystyle U^{T}U=I}$ ${\displaystyle I}$ ${\displaystyle \operatorname {ham} (U)={\det }^{2}(U+I_{/1})}$ ${\displaystyle I_{/1}}$

En la característica 2, el polinomio del ciclo hamiltoniano de una matriz n × n es cero si n > 2k donde k es su rango o si es involutivo y n > 2.

Además, en un anillo arbitrario cuya característica no es un número natural par, para cualquier matriz n × n antisimétrica existe una serie de potencias en una variable formal tal que es una matriz n × n unitaria sobre y , , mientras que para cualquier que satisface estas condiciones es igual al coeficiente en la -ésima potencia de en la serie de potencias . Y para cualquier anillo de característica par lo mismo es cierto cuando la diagonal de es un múltiplo de 2. Esto implica que calcular, hasta la -ésima potencia de , el polinomio del ciclo hamiltoniano de una matriz unitaria n × n sobre la extensión infinita de cualquier anillo de característica q (no necesariamente prima) por la variable formal es un # problema P-completo si no es 2 y calcular el polinomio del ciclo hamiltoniano de una matriz -semi-unitaria (es decir, una matriz n × n tal que ) sobre tal extensión de cualquier anillo de característica 2 es un # problema P-completo para cualquier > 0 (porque cualquier matriz -semi-unitaria se puede recibir de una matriz unitaria mediante la eliminación de filas y columnas). Para la última afirmación se puede reformular como la # P-completitud del cálculo, para una matriz unitaria dada n × n sobre un cuerpo de característica 2, la matriz n × n cuya i , j -ésima entrada es el polinomio de ciclo hamiltoniano de una matriz recibida de a través de someter sus filas y columnas a cualquier permutación que mapee j a 1 e i a 2 y luego eliminar su 1 -a fila y 2 -da columna (es decir, la suma de los productos de los pesos de arco de las trayectorias hamiltonianas del dígrafo ponderado correspondiente desde el vértice i al vértice j ) para i ≠ j y cero para i = j . Esta matriz satisface la ecuación matricial , mientras que donde es un n-vector arbitrario (lo que se puede interpretar como la computabilidad en tiempo polinomial del polinomio de ciclo hamiltoniano de cualquier 1-semi-unitario m × m ${\displaystyle R}$ ${\displaystyle A}$ ${\displaystyle \varepsilon }$ ${\displaystyle U(\varepsilon )=\sum _{n=0}^{\infty }U_{n}\varepsilon ^{n}}$ ${\displaystyle R\left(\varepsilon \right)}$ ${\displaystyle U_{0}=I}$ ${\displaystyle U_{1}=A}$ ${\displaystyle U(\varepsilon )}$ ${\displaystyle \operatorname {ham} (A)}$ ${\displaystyle n}$ ${\displaystyle \varepsilon }$ ${\displaystyle \operatorname {ham} (U(\varepsilon ))}$ ${\displaystyle R}$ ${\displaystyle AA^{T}}$ ${\displaystyle n}$ ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon }$ ${\displaystyle _{q}}$ ${\displaystyle q}$ ${\displaystyle k}$ ${\displaystyle V}$ ${\displaystyle \operatorname {rank} (V^{T}V-I\,)=k}$ ${\displaystyle _{2}}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k=1}$ ${\displaystyle _{2}}$ ${\displaystyle U}$ ${\displaystyle H(U)}$ ${\displaystyle U}$ ${\displaystyle U(H(U))^{T}=H(U)U^{T}}$ ${\displaystyle \operatorname {ham} \left({\begin{matrix}U&{Ua}\\a^{T}&1\end{matrix}}\right)=(a_{1}^{2}+...+a_{n}^{2})\operatorname {ham} (U)}$ ${\displaystyle a}$-matriz tal que donde es la -ésima columna de con su -ésima entrada reemplazada por 0 y es la identidad m × m -matriz). ${\displaystyle A}$ ${\displaystyle AA^{T}=I+bb^{T}}$ ${\displaystyle b}$ ${\displaystyle m}$ ${\displaystyle A}$ ${\displaystyle m}$ ${\displaystyle I}$

Además, valdría la pena notar que en la característica 2 el polinomio del ciclo hamiltoniano posee sus compresiones matriciales invariantes (en parte análogas a la modificación gaussiana que es invariante para el determinante), teniendo en cuenta el hecho de que para cualquier matriz t × t que tenga tres filas iguales o, si > 2, un par de índices i,j tales que sus i-ésimas y j-ésimas filas sean idénticas y sus i-ésimas y j-ésimas columnas también sean idénticas. ${\displaystyle \operatorname {ham} (X)=0}$ ${\displaystyle X}$ ${\displaystyle t}$

Por lo tanto, si una matriz tiene dos filas iguales con índices i y j, entonces agregar una de ellas a cualquier tercera no cambia este polinomio en la característica 2, lo que permite eliminar al estilo gaussiano todas las entradas de su i -ésima columna excepto las i , i -ésima y j , i -ésima (en caso de que no sean cero) y eliminar su i -ésima columna y j -ésima fila (de la manera descrita anteriormente) – entonces el polinomio del ciclo hamiltoniano de la matriz inicial es igual a este polinomio de la nueva multiplicado por la j , i -ésima entrada inicial.

También en la característica 2 y para matrices con más de dos filas, el polinomio del ciclo hamiltoniano no se modifica al sumar la i -ésima columna a la j -ésima en una matriz donde las i -ésimas y j -ésimas filas son idénticas, lo que, en particular, produce la identidad

${\displaystyle \det(D+D^{-1})\operatorname {ham} \left({\begin{matrix}V&A\\B&U\end{matrix}}\right)=\operatorname {ham} \left({\begin{matrix}V&V+D&A\\V+D^{-1}&V+D^{-1}+D&A\\B&B&U\end{matrix}}\right)}$

para una matriz n × n , matrices m × m y diagonal , matriz m × n y matriz n × m . ${\displaystyle U}$ ${\displaystyle V}$ ${\displaystyle D}$ ${\displaystyle A}$ ${\displaystyle B}$

Esta restricción de identidad al caso cuando es unitaria, y , donde es la matriz identidad m × m , hace que la matriz (2 m + n )×(2 m + n ) en el lado derecho de la igualdad sea unitaria y su polinomio de ciclo hamiltoniano sea computable, por lo tanto, en tiempo polinomial, lo que generaliza la fórmula dada anteriormente para el polinomio de ciclo hamiltoniano de una matriz unitaria. Además, en la característica 2 para matrices cuadradas X, Y es el cuadrado de la suma, sobre todos los pares de índices no iguales i,j, de la i,j-ésima entrada de Y multiplicada por el polinomio de ciclo hamiltoniano de la matriz recibida de X+Y al eliminar su i -ésima fila y j -ésima columna (de la manera descrita anteriormente). Por lo tanto, al poner en la igualdad anterior A = B y U = V, recibimos otra extensión de la clase de matrices unitarias donde el polinomio de ciclo hamiltoniano es computable en tiempo polinomial. ${\displaystyle U}$ ${\displaystyle VD+DV^{T}+AA^{T}=I+D^{2}}$ ${\displaystyle BD=UA^{T}}$ ${\displaystyle I}$ ${\displaystyle \operatorname {ham} \left({\begin{matrix}X&Y\\Y&X\end{matrix}}\right)}$

Además de las transformaciones de compresión mencionadas anteriormente, en la característica 2 también es válida la siguiente relación para los polinomios del ciclo hamiltoniano de una matriz y su inversa parcial (para y siendo cuadrada, siendo invertible ): ${\displaystyle A_{11}}$ ${\displaystyle A_{22}}$ ${\displaystyle A_{11}}$

${\displaystyle \operatorname {ham} \left({\begin{matrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{matrix}}\right)={\det }^{2}\left(A_{11}\right)\operatorname {ham} \left({\begin{matrix}A_{11}^{-1}&A_{11}^{-1}A_{12}\\A_{21}A_{11}^{-1}&A_{22}+A_{21}A_{11}^{-1}A_{12}\end{matrix}}\right)}$

y, debido a que el polinomio del ciclo hamiltoniano no depende de las entradas diagonales de la matriz, añadir una matriz diagonal arbitraria tampoco cambia este polinomio. Estos dos tipos de transformación no comprimen la matriz, pero mantienen su tamaño inalterado. Sin embargo, en varios casos su aplicación permite reducir el tamaño de la matriz mediante algunos de los operadores de compresión mencionados anteriormente.

Por lo tanto, existe una variedad de operadores de compresión de matrices realizados en tiempo polinomial y que preservan el polinomio del ciclo hamiltoniano en característica 2 cuya aplicación secuencial, junto con la transformación transpuesta (utilizada cada vez que los operadores dejan la matriz intacta), tiene, para cada matriz, un cierto límite que puede definirse como el operador de compresión-cierre. Cuando se aplica a clases de matrices, ese operador mapea así una clase a otra. Como se demostró en (Knezevic & Cohen (2017)), si la compresión-cierre de la clase de matrices unitarias contiene un subconjunto donde el cálculo de este polinomio es # P-completo ${\displaystyle _{2}}$ entonces el polinomio del ciclo hamiltoniano es computable en tiempo polinomial sobre cualquier cuerpo de esta característica - lo que implicaría la igualdad  RP  =  NP .

Referencias

• Knezevic, Anna; Cohen, Greg (2017), Algunos datos sobre los permanentes en características finitas , arXiv : 1710.01783 , Bibcode :2017arXiv171001783K.

• Kogan, Grigoriy (1996). "Cálculo de permanentes sobre cuerpos de característica 3: dónde y por qué resulta difícil". Actas de la 37.ª Conferencia sobre Fundamentos de la Ciencia de la Computación . pp. 108–114. doi :10.1109/SFCS.1996.548469. ISBN . 0-8186-7594-2. Número de identificación del sujeto  39024286.

• Cohen, Greg (2010), Una nueva técnica algebraica para calcular en tiempo polinomial el número módulo 2 de descomposiciones hamiltonianas y particiones similares del conjunto de aristas de un gráfico , arXiv : 1005.2281 , Bibcode :2010arXiv1005.2281C