Calcular el permanente

El número de emparejamientos perfectos en un grafo bipartito se cuenta mediante el permanente de la matriz de biadyacencia del grafo , y el permanente de cualquier matriz 0-1 puede interpretarse de esta manera como el número de emparejamientos perfectos en un grafo. Para grafos planares (independientemente de su bipartición), el algoritmo FKT calcula el número de emparejamientos perfectos en tiempo polinomial cambiando los signos de un subconjunto cuidadosamente elegido de las entradas en la matriz de Tutte del grafo, de modo que el pfaffiano de la matriz antisimétrica resultante (la raíz cuadrada de su determinante ) sea el número de emparejamientos perfectos. Esta técnica puede generalizarse a grafos que no contienen ningún subgrafo homeomorfo al grafo bipartito completo K _3,3 . ^{[ 5 ]}

George Pólya planteó la pregunta ^{[ 6 ]} de cuándo es posible cambiar los signos de algunas de las entradas de una matriz 01 A de modo que el determinante de la nueva matriz sea el permanente de A. No todas las matrices 01 son "convertibles" de esta manera; de hecho, se sabe ( Marcus & Minc (1961) ) que no existe una transformación lineal.${\displaystyle T}$de tal manera que${\displaystyle \operatorname {per} T(A)=\det A}$a pesar de${\displaystyle n\times n}$matrices${\displaystyle A}$La caracterización de matrices "convertibles" fue dada por Little (1975), quien demostró que tales matrices son precisamente aquellas que son la matriz de biadyacencia de grafos bipartitos que tienen una orientación pfaffiana : una orientación de las aristas tal que para cada ciclo par${\displaystyle C}$para qué${\displaystyle G\setminus C}$tiene una coincidencia perfecta, hay un número impar de aristas dirigidas a lo largo de C (y por lo tanto un número impar con la orientación opuesta). También se demostró que estos grafos son exactamente aquellos que no contienen un subgrafo homeomorfo a${\displaystyle K_{3,3}}$, como se indicó anteriormente.

Módulo 2, el permanente es el mismo que el determinante, como${\displaystyle (-1)\equiv 1{\pmod {2}}.}$También se puede calcular módulo${\displaystyle 2^{k}}$a tiempo${\displaystyle O(n^{4k-3})}$para${\displaystyle k\geq 2}$Sin embargo, es UP-difícil calcular el permanente módulo cualquier número que no sea una potencia de 2. Valiant (1979)

Glynn (2010) proporciona varias fórmulas para el cálculo módulo un primo p . En primer lugar, hay una que utiliza cálculos simbólicos con derivadas parciales.

Segundo, para p = 3 existe la siguiente fórmula para una matriz n×n:${\displaystyle A}$, que involucra a los principales menores de la matriz ( Kogan (1996) ):

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

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

La expansión anterior se puede generalizar en una característica arbitraria p como el siguiente par de identidades duales: $${\displaystyle {\begin{aligned}\operatorname {per} (A)&=(-1)^{n}\sum _{{J_{1}},\ldots ,{J_{p-1}}}\det(A_{J_{1}})\dotsm \det(A_{J_{p-1}})\\\det(A)&=(-1)^{n}\sum _{{J_{1}},\ldots ,{J_{p-1}}}\operatorname {per} (A_{J_{1}})\dotsm \operatorname {per} (A_{J_{p-1}})\end{aligned}}}$$ donde en ambas fórmulas la suma se toma sobre todas las ( p − 1)-tuplas${\displaystyle {J_{1}},\ldots ,{J_{p-1}}}$que son particiones del conjunto${\displaystyle \{1,\dots ,n\}}$en p − 1 subconjuntos, algunos de ellos posiblemente vacíos.

La fórmula anterior posee un análogo para el hafniano de una simetría${\displaystyle A}$y una p extraña:

$${\displaystyle \operatorname {haf} ^{2}(A)=(-1)^{n}\sum _{{J_{1}},\ldots ,{J_{p-1}}}\det(A_{J_{1}})\dotsm \det(A_{J_{p-1}})(-1)^{|J_{1}|+\dots +|J_{(p-1)/2}|}}$$

con la suma tomada sobre el mismo conjunto de índices. Además, en característica cero una expresión de suma de convolución similar que involucra tanto el permanente como el determinante produce el polinomio del ciclo hamiltoniano (definido como${\textstyle \operatorname {ham} (A)=\sum _{\sigma \in H_{n}}\prod _{i=1}^{n}a_{i,\sigma (i)}}$dónde${\displaystyle H_{n}}$es el conjunto de n-permutaciones que tienen un solo ciclo): $${\displaystyle \operatorname {ham} (A)=\sum _{J\subseteq \{2,\dots ,n\}}\det(A_{J})\operatorname {per} (A_{\bar {J}})(-1)^{|J|}.}$$

En la característica 2, esta última igualdad se convierte en${\displaystyle \operatorname {ham} (A)=\sum _{J\subseteq \{2,\dots ,n\}}\det(A_{J})\operatorname {det} (A_{\bar {J}})}$lo que por lo tanto brinda la oportunidad de calcular en tiempo polinomial el polinomio del ciclo hamiltoniano de cualquier unidad${\displaystyle U}$(es decir, de tal manera que${\displaystyle U^{\textsf {T}}U=I}$dónde${\displaystyle I}$es la matriz identidad n × n ), porque cada menor de dicha matriz coincide con su complemento algebraico:${\displaystyle \operatorname {ham} (U)=\operatorname {det} ^{2}(U+I_{/1})}$dónde${\displaystyle I_{/1}}$es la matriz identidad n × n con la entrada de los índices 1,1 reemplazada por 0. Además, puede, a su vez, generalizarse aún más para una matriz unitaria n × n.${\displaystyle U}$como${\displaystyle \operatorname {ham_{K}} (U)=\operatorname {det} ^{2}(U+I_{/K})}$dónde${\displaystyle K}$es un subconjunto de {1, ..., n },${\displaystyle I_{/K}}$es la matriz identidad n × n con las entradas de los índices k , k reemplazadas por 0 para todo k perteneciente a${\displaystyle K}$y definimos${\textstyle \operatorname {ham_{K}} (A)=\sum _{\sigma \in H_{n}(K)}\prod _{i=1}^{n}a_{i,\sigma (i)}}$dónde${\displaystyle H_{n}(K)}$es el conjunto de n-permutaciones cuyos ciclos contienen al menos un elemento de${\displaystyle K}$.

Esta fórmula también implica las siguientes identidades sobre cuerpos de característica 3:

para cualquier invertible${\displaystyle A}$

${\displaystyle \operatorname {per} (A^{-1})\operatorname {det} ^{2}(A)=\operatorname {per} (A);}$

para cualquier unidad${\displaystyle U}$, es decir, una matriz cuadrada${\displaystyle U}$de tal manera que${\displaystyle U^{\textsf {T}}U=I}$dónde${\displaystyle I}$es la matriz identidad del tamaño correspondiente,

${\displaystyle \operatorname {per} ^{2}(U)=\det(U+V)\det(-U)}$

dónde${\displaystyle V}$es la matriz cuyas entradas son los cubos de las entradas correspondientes de${\displaystyle U}$.

También se demostró ( Kogan (1996) ) que, si definimos una matriz cuadrada${\displaystyle A}$como k-semiunitario cuando${\displaystyle \operatorname {rank} (A^{\textsf {T}}A-I)=k}$, el permanente de una matriz 1-semiunitaria es computable en tiempo polinomial sobre cuerpos de característica 3, mientras que para k > 1 el problema se vuelve #3-P-completo . (Una teoría paralela se refiere al polinomio del ciclo hamiltoniano en característica 2: mientras que su cálculo en las matrices unitarias es factible en tiempo polinomial, el problema es #2-P-completo para las k-semiunitarias para cualquier k > 0). Este último resultado fue esencialmente extendido en 2017 ( Knezevic y Cohen (2017) ) y se demostró que en característica 3 existe una fórmula simple que relaciona los permanentes de una matriz cuadrada y su inversa parcial (para${\displaystyle A_{11}}$y${\displaystyle A_{22}}$siendo cuadrado,${\displaystyle A_{11}}$siendo invertible ):

$${\displaystyle \operatorname {per} {\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{pmatrix}}=\operatorname {det} ^{2}(A_{11})\operatorname {per} {\begin{pmatrix}A_{11}^{-1}&A_{11}^{-1}A_{12}\\A_{21}A_{11}^{-1}&A_{22}-A_{21}A_{11}^{-1}A_{12}\end{pmatrix}}}$$

y permite reducir en tiempo polinomial el cálculo del permanente de una matriz n × n con un subconjunto de k o k − 1 filas expresables como combinaciones lineales de otro subconjunto (disjunto) de k filas al cálculo del permanente de una matriz ( n − k )×( n − k )- o ( n − k + 1)×( n − k + 1)-, respectivamente, habiendo introducido así un operador de compresión (análogo a la modificación gaussiana aplicada para calcular el determinante) que "preserva" el permanente en característica 3. (Analógicamente, valdría la pena señalar que el polinomio del ciclo hamiltoniano en característica 2 también posee sus compresiones de matriz invariantes, teniendo en cuenta el hecho de que ham( A ) = 0 para cualquier matriz n × n A que tenga tres filas iguales o, si n > 2, un par de índices i , j tales que sus filas i y j son idénticas y sus columnas i y j también son idénticas.) El cierre de ese operador definido como el límite de su aplicación secuencial junto con la transformación de transposición (utilizada cada vez que el operador deja la matriz intacta) es también un operador que mapea, cuando se aplica a clases de matrices, una clase a otra. Mientras que el operador de compresión mapea la clase de matrices 1-semiunitarias a sí mismo y a las clases de matrices unitarias y 2-semiunitarias, el cierre de compresión de la clase 1-semiunitaria (así como la clase de matrices recibidas de las unitarias al reemplazar una fila por un vector fila arbitrario —el permanente de dicha matriz es, a través de la expansión de Laplace, la suma de los permanentes de matrices 1-semiunitarias y, por consiguiente, computable en tiempo polinomial) es aún desconocido y está tensamente relacionado con el problema general de la complejidad computacional del permanente en característica 3 y la cuestión principal de P versus NP : como se demostró en ( Knezevic y Cohen (2017) ), si dicho cierre de compresión es el conjunto de todas las matrices cuadradas sobre un cuerpo de característica 3 o, al menos, contiene una clase de matriz en la que el cálculo del permanente es #3-P-completo (como la clase de matrices 2-semiunitarias), entonces el permanente es computable en tiempo polinomial en esta característica.

Además, se formuló el problema de encontrar y clasificar cualquier posible análogo de las compresiones que preservan la permanente existentes en característica 3 para otras características primas ( Knezevic y Cohen (2017) ), dando la siguiente identidad para una matriz n × n.${\displaystyle A}$y dos n -vectores (con todas sus entradas en el conjunto {0, ..., p − 1})${\displaystyle \alpha }$y${\displaystyle \beta }$de tal manera que${\textstyle {\sum _{i=1}^{n}\alpha _{i}=\sum _{j=1}^{n}\beta _{j}}}$, válido en una característica prima arbitraria p :

$${\displaystyle \operatorname {per} (A^{(\alpha ,\beta )})=\det ^{p-1}(A)\operatorname {per} (A^{-1})^{((p-1){\vec {1}}_{n}-\beta ,(p-1){\vec {1}}_{n}-\alpha )}\left(\prod _{i=1}^{n}\alpha _{i}!\right)\left(\prod _{j=1}^{n}\beta _{j}!\right)(-1)^{n+\sum _{i=1}^{n}\alpha _{i}}}$$

donde para una matriz n × m${\displaystyle M}$, un vector n${\displaystyle x}$y un vector m${\displaystyle y}$, ambos vectores tienen todas sus entradas del conjunto {0, ..., p − 1},${\displaystyle M^{(x,y)}}$denota la matriz recibida de${\displaystyle M}$mediante repetición${\displaystyle x_{i}}$veces su i -ésima fila para i = 1, ..., n y${\displaystyle y_{j}}$veces su j -ésima columna para j = 1, ..., m (si la multiplicidad de alguna fila o columna es igual a cero, significaría que la fila o columna fue eliminada, y por lo tanto esta noción es una generalización de la noción de submatriz), y${\displaystyle {\vec {1}}_{n}}$denota el vector n-dimensional cuyas entradas son todas iguales a la unidad. Esta identidad es un análogo exacto de la fórmula clásica que expresa el menor de una matriz mediante el menor de su inversa y, por lo tanto, demuestra (una vez más) una especie de dualidad entre el determinante y el permanente como inmanentes relativos. (En realidad, su propio análogo para el hafniano de una matriz simétrica${\displaystyle A}$y un primo impar p es${\textstyle \operatorname {haf} ^{2}(A^{(\alpha ,\alpha )})=\det ^{p-1}(A)\operatorname {haf} ^{2}(A^{-1})^{((p-1){\vec {1}}_{n}-\alpha ,(p-1){\vec {1}}_{n}-\alpha )}\left(\prod _{i=1}^{n}\alpha _{i}!\right)^{2}(-1)^{n(p-1)/2+n+\sum _{i=1}^{n}\alpha _{i}}}$).

Y, como una generalización aún más amplia para el caso inverso parcial en una característica prima p, para${\displaystyle A_{11}}$,${\displaystyle A_{22}}$siendo cuadrado,${\displaystyle A_{11}}$siendo invertible y de tamaño${\displaystyle {n_{1}}}$incógnita${\displaystyle {n_{1}}}$, y${\textstyle {\sum _{i=1}^{n}\alpha _{i}=\sum _{j=1}^{n}\beta _{j}}}$, también se encuentra allí la identidad

$${\displaystyle \operatorname {per} {\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{pmatrix}}^{(\alpha ,\beta )}={\det }^{p-1}(A_{11})\operatorname {per} {\begin{pmatrix}A_{11}^{-1}&A_{11}^{-1}A_{12}\\A_{21}A_{11}^{-1}&A_{22}-A_{21}A_{11}^{-1}A_{12}\end{pmatrix}}^{((p-1){\vec {1}}_{n}-\beta ,(p-1){\vec {1}}_{n}-\alpha )}\left(\prod _{i=1}^{n}\alpha _{1,i}!\right)\left(\prod _{j=1}^{n}\beta _{1,j}!\right)(-1)^{n_{1}+\sum _{i=1}^{n}\alpha _{1,i}}}$$

donde los vectores de multiplicidad de fila/columna comunes${\displaystyle \alpha }$y${\displaystyle \beta }$para la matriz${\displaystyle A}$generar los vectores de multiplicidad de filas/columnas correspondientes${\displaystyle \alpha _{s}}$y${\displaystyle \beta _{t}}$, s,t = 1,2, para sus bloques (las mismas preocupaciones${\displaystyle A}$su inverso parcial en el lado derecho de la igualdad).