Cálculo del permanente

En álgebra lineal, el cálculo del permanente de una matriz es un problema que se piensa que es más difícil que el cálculo del determinante de una matriz, a pesar de la aparente similitud de las definiciones.

El permanente se define de forma similar al determinante, como la suma de productos de conjuntos de elementos de la matriz ubicados en filas y columnas distintas. Sin embargo, si el determinante pondera cada uno de estos productos con un signo ±1 basado en la paridad de los elementos, el permanente los pondera a todos con un signo +1.

Si bien el determinante puede calcularse en tiempo polinómico mediante la eliminación de Gauss-Jordan, generalmente se cree que el permanente no puede calcularse en tiempo polinómico. En teoría de la complejidad computacional, un teorema de Valiant establece que calcular permanentes es #P-difícil, e incluso #P-completo para matrices donde todos los elementos son 0 o 1 Valiant (1979). Esto sitúa el cálculo del permanente en una clase de problemas que se considera aún más difícil de calcular que NP. Se sabe que calcular el permanente es imposible para circuitos ACC⁰ uniformes en el espacio logarítmico. (Allender y Gore, 1994)

El desarrollo de algoritmos exactos y aproximados para calcular el permanente de una matriz es un área de investigación activa.

El permanente de una matriz de n por n, A = (a_i,j), se define como:

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

La suma se extiende a todos los elementos σ del grupo simétrico S_n, es decir, a todas las permutaciones de los números 1, 2, ..., n. Esta fórmula difiere de la fórmula correspondiente para el determinante solo en que, en el determinante, cada producto se multiplica por el signo de la permutación σ, mientras que en esta fórmula cada producto no tiene signo. La fórmula puede traducirse directamente a un algoritmo que la expande de forma ingenua, sumando todas las permutaciones y, dentro de la suma, multiplicando cada entrada de la matriz. Esto requiere n!·n operaciones aritméticas.

El algoritmo exacto general^[1]​ más conocido se debe a Ryser (1963). El método de Ryser se basa en la fórmula de inclusión-exclusión, que se puede expresar como^[2]​ de la siguiente manera: sea ${\displaystyle A_{k}}$ obtenido de A eliminando k columnas, sea ${\displaystyle P(A_{k})}$ el producto de las sumas de filas de ${\displaystyle A_{k}}$ y sea ${\displaystyle \Sigma _{k}}$ la suma de los valores de ${\displaystyle P(A_{k})}$ sobre todos los valores posibles de ${\displaystyle A_{k}}$. Entonces: ${\displaystyle \operatorname {perm} (A)=\sum _{k=0}^{n-1}(-1)^{k}\Sigma _{k}.}$

Puede reescribirse en términos de las entradas de la matriz de la siguiente manera:^[3]​

${\displaystyle \operatorname {perm} (A)=(-1)^{n}\sum _{S\subseteq \{1,\dots ,n\}}(-1)^{|S|}\prod _{i=1}^{n}\sum _{j\in S}a_{ij}.}$

La fórmula de Ryser se puede calcular mediante ${\displaystyle O(2^{n-1}n^{2})}$ operaciones aritméticas, o ${\displaystyle O(2^{n-1}n)}$ procesando los conjuntos ${\displaystyle S}$ en orden según el código Gray.^[4]​

Otra fórmula que parece ser tan rápida como la de Ryser (o quizás incluso el doble) se encuentra en dos tesis doctorales. Véase (Balasubramanian, 1980), (Bax, 1998); y también (Bax y Franklin, 1996). Los métodos para hallar la fórmula son bastante diferentes, relacionados con la combinatoria del álgebra de Muir y con la teoría de diferencias finitas, respectivamente. Otra vía, relacionada con la teoría de invariantes, es mediante la identidad de polarización para un tensor simétrico (Glynn, 2010). La fórmula se generaliza a un número infinito de otras, como encontraron todos estos autores, aunque no está claro si son más rápidas que la básica. Véase (Glynn, 2013).

La fórmula más simple conocida de este tipo (cuando la característica del cuerpo no es dos) es

${\displaystyle \operatorname {perm} (A)={\frac {1}{2^{n-1}}}\left[\sum _{\delta }\left(\prod _{k=1}^{n}\delta _{k}\right)\prod _{j=1}^{n}\sum _{i=1}^{n}\delta _{i}a_{ij}\right],}$

donde la suma externa es sobre todos los vectores ${\displaystyle 2^{n-1}}$ ${\displaystyle \delta =(\delta _{1}=1,\delta _{2},\dots ,\delta _{n})\in \{\pm 1\}^{n}}$.

El número de concordancias perfectas en un grafo bipartito se contabiliza por el permanente de la matriz de adyacencia del grafo, y el permanente de cualquier matriz 0-1 puede ser interpretado de esta manera como el número de emparejamientos perfectos en un grafo. Para un grafo plano (independientemente de su bipartitidad), el algoritmo FKT calcula el número de emparejamientos perfectos en tiempo polinómico modificando los signos de un subconjunto cuidadosamente seleccionado 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 se puede generalizar a grafos que no contienen subgrafos homeomórficos hasta el grafo bipartito completo K_3,3.^[5]​

George Pólya planteó la pregunta^[6]​ de cuándo es posible cambiar el signo de algunas de las entradas de una matriz A de ceros y unos (01) 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 y Minc (1961)) que no existe una función lineal ${\displaystyle T}$ tal que ${\displaystyle \operatorname {per} T(A)=\det A}$ para todas las matrices ${\displaystyle n\times n}$ ${\displaystyle A}$. La caracterización de las matrices convertibles fue dada por Little (1975), quien demostró que dichas matrices son precisamente las que constituyen la matriz de biyacencia de grafos bipartitos que tienen una orientación pfaffiana: una orientación de las aristas tal que para cada ciclo par ${\displaystyle C}$ para el cual ${\displaystyle G\setminus C}$ tiene una correspondencia perfecta, hay un número impar de aristas dirigidas en 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.

En módulo 2, el permanente es igual al determinante, ya que ${\displaystyle (-1)\equiv 1{\pmod {2}}.}$ también se puede calcular el módulo ${\displaystyle 2^{k}}$ en el tiempo ${\displaystyle O(n^{4k-3})}$ para ${\displaystyle k\geq 2}$. Sin embargo, es UP-difícil el calcular el permanente en un módulo cuya base no sea una potencia de 2. Valiant (1979)

Existen varias fórmulas dadas por Glynn (2010) para el cálculo según el módulo de un primo p. Primero, hay una que utilizar cálculos simbólicos con derivadas parciales.

En segundo lugar, para p = 3, existe la siguiente fórmula para una matriz ${\displaystyle A}$ de orden n×n, que involucra los menores de la matriz principal (Kogan (1996)):

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

donde ${\displaystyle A_{J}}$ es la submatriz de ${\displaystyle A}$ inducida por las filas y columnas de ${\displaystyle A}$ indexadas 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.

El desarrollo 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 realiza 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 matriz ${\displaystyle A}$ simétrica y un p impar:

${\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 la característica cero, una expresión de suma de convolución similar que involucra tanto el permanente como el determinante produce el ciclo hamiltoniano polinómico (definido como ${\textstyle \operatorname {ham} (A)=\sum _{\sigma \in H_{n}}\prod _{i=1}^{n}a_{i,\sigma (i)}}$, donde ${\displaystyle H_{n}}$ es el conjunto de n-permutaciones con 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 permite calcular en tiempo polinómico el ciclo hamiltoniano polinómico de cualquier matriz unitaria ${\displaystyle U}$ (es decir, tal que ${\displaystyle U^{\textsf {T}}U=I}$, donde ${\displaystyle I}$ es la matriz identidad n×n), ya que cada menor de dicha matriz coincide con su complemento algebraico: ${\displaystyle \operatorname {ham} (U)=\operatorname {det} ^{2}(U+I_{/1})}$, donde ${\displaystyle I_{/1}}$ es la matriz identidad n×n, con la entrada de los índices k, k reemplazada por 0. Además, puede, a su vez, generalizarse para una matriz unitaria n×n ${\displaystyle U}$ como ${\displaystyle \operatorname {ham_{K}} (U)=\operatorname {det} ^{2}(U+I_{/K})}$, donde ${\displaystyle K}$ es un subconjunto de 1, ..., n. ${\displaystyle I_{/K}}$ es la matriz identidad n×n con las entradas de índices k, k reemplazadas por 0 para todos los k pertenecientes a ${\displaystyle K}$. Se define ${\textstyle \operatorname {ham_{K}} (A)=\sum _{\sigma \in H_{n}(K)}\prod _{i=1}^{n}a_{i,\sigma (i)}}$, donde ${\displaystyle H_{n}(K)}$ es el conjunto de n-permutaciones cuyo ciclo contiene al menos un elemento de ${\displaystyle K}$.

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

• Para cualquier matriz invertible ${\displaystyle A}$

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

• Para cualquier unitary ${\displaystyle U}$, es decir, una matriz cuadrada ${\displaystyle U}$ tal que ${\displaystyle U^{\textsf {T}}U=I}$, donde ${\displaystyle I}$ es la matriz identidad del tamaño correspondiente,

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

donde ${\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 se define una matriz cuadrada ${\displaystyle A}$ como k-semi-unitaria cuando ${\displaystyle \operatorname {rank} (A^{\textsf {T}}A-I)=k}$, el permanente de una matriz 1-semi-unitaria es computable en tiempo polinómico sobre cuerpos de característica 3, mientras que para k > 1 el problema se convierte en #3-P-completo. Una teoría paralela concierne al ciclo hamiltoniano polinómico en característica 2: si bien su cálculo en las matrices unitarias es factible en tiempo polinómico, el problema es #2-P-completo para las k-semi-unitarias para cualquier k > 0. Este último resultado se amplió esencialmente en 2017 (Knezevic y Cohen (2017)) y se demostró que en la 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 cuadradas, ${\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 polinómico 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 subconjuntos (disjuntos) de k filas al cálculo del permanente de una matriz (n - k)×(n - k) o (n - k + 1)×(n - k + 1) correspondientemente, 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 la característica 3. Análogamente, valdría la pena reseñar que el ciclo hamiltoniano polinómico en la característica 2 también posee sus compresiones matriciales invariantes, teniendo en cuenta el hecho de que ham(A) = 0 para cualquier matriz A de orden n×n que tenga tres filas iguales o, si n > 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. El cierre de ese operador definido como el límite de su aplicación secuencial junto con la transformación transpuesta (utilizada cada vez que el operador deja la matriz intacta) también es una correspondencia de operadores cuando se aplica a clases de matrices de una clase a otra. Mientras que el operador de compresión asigna 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 de fila arbitrario (el permanente de tal matriz es, a través de la expansión de Laplace, la suma de las permanentes de matrices 1-semiunitarias y, en consecuencia, computable en tiempo polinómico), es aún desconocida y está tensamente relacionada con el problema general de la complejidad computacional del permanente en la característica 3 y la pregunta principal de P frente a NP: como se demostró en (Knezevic y Cohen (2017)), si tal 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, el cálculo del permanente es #3-P-completo (como la clase de matriz 2-semiunitarias), y entonces el permanente es computable en tiempo polinómico en esta característica.

Además, se formuló el problema de encontrar y clasificar posibles analogías de las compresiones de conservación permanente existentes en la característica 3 para otras características primas (Knezevic y Cohen (2017)), dando la siguiente identidad para una matriz ${\displaystyle A}$ de n×n y dos vectores de n (cuyas entradas pertenecen al conjunto 0, ..., p - 1) ${\displaystyle \alpha }$ y ${\displaystyle \beta }$ tales 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 de orden n×m-${\displaystyle M}$, un n-vector ${\displaystyle x}$ y un m-vector ${\displaystyle y}$, ambos vectores tienen todas sus entradas del conjunto 0, ..., p - 1, ${\displaystyle M^{(x,y)}}$ denota la matriz recibida de ${\displaystyle M}$ a través de la repetición de ${\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 n-vector 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 a través del 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. De hecho, su propio análogo para el hafniano de una matriz ${\displaystyle A}$ simétrica 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 un primo característico p, para ${\displaystyle A_{11}}$, siendo ${\displaystyle A_{22}}$ cuadrada, ${\displaystyle A_{11}}$ invertible y de tamaño ${\displaystyle {n_{1}}}$x${\displaystyle {n_{1}}}$, y ${\textstyle {\sum _{i=1}^{n}\alpha _{i}=\sum _{j=1}^{n}\beta _{j}}}$, se cumple también 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 fila/columna comunes ${\displaystyle \alpha }$ y ${\displaystyle \beta }$ para la matriz ${\displaystyle A}$ generan los vectores de multiplicidad fila/columna correspondientes ${\displaystyle \alpha _{s}}$ y ${\displaystyle \beta _{t}}$, s,t = 1,2, para sus bloques (lo mismo ocurre con el inverso parcial de ${\displaystyle A}$ en el lado derecho de la igualdad).

Cuando las entradas de A son no negativas, el permanente puede calcularse aproximadamente en tiempo polinómico probabilístico, hasta un error de εM, donde M es el valor del permanente y ε > 0 es arbitrario. En otras palabras, existe un esquema de aproximación de tiempo polinómico (FPRAS) (Jerrum, Sinclair y Vigoda (2001)).

El paso más difícil del cálculo es la construcción de un algoritmo para obtener una muestra casi uniforme a partir del conjunto de todos los emparejamientos perfectos en un grafo bipartito dado: en otras palabras, un muestreo casi uniforme completamente polinómico (FPAUS). Esto se puede lograr mediante un algoritmo de un método de Montecarlo basado en cadenas de Markov que utiliza una regla de Metropolis para definir y ejecutar una cadena de Márkov con una distribución casi uniforme y cuyo tiempo de mezclado sea polinómico.

Es posible contar aproximadamente el número de emparejamientos perfectos en un grafo mediante autorreducibilidad del permanente, utilizando el FPAUS en combinación con una conocida reducción de muestreo a conteo debido a Jerrum, Valiant y Vazirani (1986). Sea ${\displaystyle M(G)}$ el número de emparejamientos perfectos en ${\displaystyle G}$. Aproximadamente, para cualquier arista particular ${\displaystyle e}$ en ${\displaystyle G}$, al muestrear muchos emparejamientos en ${\displaystyle G}$ y contar cuántos de ellos son emparejamientos en ${\displaystyle G\setminus e}$, se puede obtener una estimación de la razón ${\textstyle \rho ={\frac {M(G)}{M(G\setminus e)}}}$. El número ${\displaystyle M(G)}$ es entonces ${\displaystyle \rho M(G\setminus e)}$, donde ${\displaystyle M(G\setminus e)}$ puede aproximarse aplicando el mismo método recursivamente.

Otra clase de matrices para las cuales el permanente es de particular interés, son las matrices positivas semidefinidas.^[7]​ Usando una técnica del conteo de Stockmeyer, se pueden calcular dentro de la clase ${\displaystyle {\textsf {BPP}}^{\textsf {NP}}}$, pero esta se considera una clase inviable en general. Es NP-difícil aproximar permanentes de matrices PSD dentro de un factor subexponencial, y se conjetura que es ${\displaystyle {\textsf {BPP}}^{\textsf {NP}}}$-difícil^[8]​ Si se imponen restricciones adicionales en el espectro de una matriz, se conocen algoritmos más eficientes. Un algoritmo aleatorizado se basa en el modelo de muestreo de bosones y usa las herramientas propias de la óptica cuántica, para representar el permanente de matrices semidefinidas positivas como el valor esperado de una variable aleatoria específica. Esta última se aproxima entonces por su media muestral.^[9]​ Este algoritmo, para un conjunto determinado de matrices semidefinidas positivas, aproxima su permanente en tiempo polinómico hasta un error aditivo, lo cual es más fiable que el algoritmo clásico estándar de tiempo polinómico de Gurvits.^[10]​

• Barvinok, A. (2017), «Approximating permanents and hafnians», Discrete Analysis, S2CID 397350, arXiv:1601.07518, doi:10.19086/da.1244 ..