En álgebra lineal , el cálculo de la permanente de una matriz es un problema que se cree 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 manera similar al determinante, como una suma de productos de conjuntos de entradas de la matriz que se encuentran en distintas filas y columnas. Sin embargo, cuando el determinante pondera cada uno de estos productos con un signo de ± 1 basado en la paridad del conjunto , el permanente los pondera a todos con un signo de +1.
Si bien el determinante se puede calcular en tiempo polinomial mediante eliminación gaussiana , generalmente se cree que el permanente no se puede calcular en tiempo polinomial. En la teoría de la complejidad computacional , un teorema de Valiant establece que calcular permanentes es # P-difícil , e incluso # P-completo para matrices en las que todas las entradas son 0 o 1 Valiant (1979) . Esto coloca el cálculo de lo permanente en una clase de problemas que se cree que son incluso más difíciles de calcular que NP . Se sabe que calcular el permanente es imposible para los circuitos ACC 0 uniformes en el espacio logs ( Allender & Gore 1994)
El desarrollo de algoritmos tanto exactos como aproximados para calcular la permanente de una matriz es un área activa de investigación.
Definición y algoritmo ingenuo
El permanente de una matriz n- por- n A = ( a i, j ) se define como
La suma aquí 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 se diferencia 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 en un algoritmo que amplía ingenuamente la fórmula, sumando todas las permutaciones y dentro de la suma multiplicando cada entrada de la matriz. Esto requiere n! n operaciones aritméticas.
Fórmula de Ryser
El algoritmo exacto general más conocido [1] se debe a HJ Ryser ( 1963 ). El método de Ryser se basa en una fórmula de inclusión-exclusión que se puede dar [2] de la siguiente manera: Seaser obtenido de A borrando k columnas, sea ser el producto de las sumas de fila de , y deja ser la suma de los valores de sobre todo lo posible . Luego
Puede reescribirse en términos de las entradas de la matriz de la siguiente manera [3]
La fórmula de Ryser se puede evaluar usando operaciones aritméticas, o procesando los conjuntos en el orden del código Gray . [4]
Fórmula de Balasubramanian-Bax-Franklin-Glynn
Otra fórmula que parece ser tan rápida como la de Ryser (o quizás incluso el doble) se encuentra en los dos Ph.D. tesis ver ( Balasubramanian 1980 ), ( Bax 1998 ); también ( Bax y Franklin 1996 ). Los métodos para encontrar la fórmula son bastante diferentes, ya que están relacionados con la combinatoria del álgebra de Muir y con la teoría de diferencias finitas, respectivamente. Otra forma, relacionada con la teoría invariante, es a través de la identidad de polarización para un tensor simétrico ( Glynn 2010 ). La fórmula se generaliza a infinitos otros, como lo encuentran todos estos autores, aunque no está claro si son más rápidos que el básico. Ver ( Glynn 2013 ).
La fórmula conocida más simple de este tipo (cuando la característica del campo no es dos) es
donde la suma externa está por encima de todo vectores .
Casos especiales
Planar y K 3,3 -free
El número de emparejamientos perfectos en un gráfico bipartito se cuenta por el permanente de la matriz de biadjacencia del gráfico , y el permanente de cualquier matriz 0-1 puede interpretarse de esta manera como el número de emparejamientos perfectos en un gráfico. Para gráficos planos (independientemente de la 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 gráfico, de modo que el Pfaffian del sesgo resultante La matriz simétrica (la raíz cuadrada de su determinante ) es el número de emparejamientos perfectos. Esta técnica se puede generalizar a grafos que no contienen subgrafos homeomorfos al grafo bipartito completo K 3,3 . [5]
George Pólya había hecho la pregunta [6] de cuándo es posible cambiar los signos de algunas de las entradas de una matriz 01 A para que el determinante de la nueva matriz sea el permanente de A. No todas las matrices 01 son "convertibles" de esta forma; de hecho se sabe ( Marcus & Minc (1961) ) que no existe un mapa lineal tal que para todos matrices . La caracterización de las matrices "convertibles" fue dada por Little (1975) quien demostró que tales matrices son precisamente aquellas que son la matriz de biadjacencia de grafos bipartitos que tienen una orientación pfaffiana : una orientación de las aristas tal que para cada ciclo par para cual tiene una coincidencia perfecta, hay un número impar de bordes dirigidos a lo largo de C (y, por lo tanto, un número impar con la orientación opuesta). También se demostró que estas gráficas son exactamente aquellas que no contienen un subgrafo homeomorfo a, como anteriormente.
Módulo de cálculo un número
Módulo 2, el permanente es el mismo que el determinante, ya que También se puede calcular módulo a tiempo por . Sin embargo, es UP-difícil calcular el módulo permanente cualquier número que no sea una potencia de 2. Valiant (1979)
Hay varias fórmulas dadas por Glynn (2010) para el cálculo módulo a primo p . Primero, hay uno que usa cálculos simbólicos con derivadas parciales.
En segundo lugar, para p = 3 existe la siguiente fórmula para una matriz n × n, involucrando a los menores principales de la matriz ( Kogan (1996) ):
dónde es la submatriz de inducida por las filas y columnas de indexado por , y es el complemento de en , 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:
donde en ambas fórmulas la suma se toma sobre todas las tuplas (p-1) que son particiones del conjunto en subconjuntos p-1, algunos de ellos posiblemente vacíos.
La primera fórmula posee un análogo para el hafnian de un simétrico y una p impar:
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 al determinante como al permanente produce el polinomio del ciclo hamiltoniano (definido como dónde es el conjunto de n-permutaciones que tienen un solo ciclo):
Esta fórmula implica las siguientes identidades en los campos de la característica 3:
para cualquier invertible
para cualquier unitario , es decir, una matriz cuadrada tal que dónde es la matriz de identidad del tamaño correspondiente,
dónde es la matriz cuyas entradas son los cubos de las correspondientes entradas de .
También se demostró ( Kogan (1996) ) que, si definimos una matriz cuadrada como k-semi-unitario cuando , la permanente de una matriz 1-semi-unitaria se puede calcular en tiempo polinómico sobre campos de la característica 3, mientras que para k > 1 el problema se convierte en # 3-P-completo . (Una teoría paralela concierne al polinomio del ciclo hamiltoniano en la característica 2: mientras que calcularlo en las matrices unitarias es factible en tiempo polinómico, el problema es # 2-P-completo para los k-semi-unitarios para cualquier k > 0). Este último resultado se extendió esencialmente en 2017 ( Knezevic & Cohen (2017) ) y se comprobó que en la característica 3 existe una fórmula simple que relaciona las permanentes de una matriz cuadrada y su inversa parcial (para y siendo cuadrado, siendo invertible ):
y permite reducir en tiempo polinomial el cálculo de la 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 de la permanente de una ( n - k ) × ( n - k ) - o ( n - k +1) × ( n - k +1) -matriz correspondientemente, habiendo introducido un operador de compresión (análogo a la modificación gaussiana aplicada para calcular el determinante ) que "conserva" lo permanente en la característica 3. (De manera análoga, vale la pena señalar que el polinomio del ciclo hamiltoniano en la característica 2 también posee sus compresiones matriciales invariantes, teniendo en cuenta el hecho de que ham ( A ) = 0 para cualquier n × n -matriz A que tiene tres filas iguales o, si n > 2, un par de índices i , j tales que sus filas i -ésima y j -ésima son idénticas y sus columnas i -ésima y j -ésima son idénticas también .) El cierre de ese operador definido como el límite de su aplicación secuencial junto con la transpuesta transforma ción (utilizada cada vez que el operador deja la matriz intacta) es también un mapeo de operador, cuando se aplica a clases de matrices, una clase a otra. Mientras que el operador de compresión mapea la clase de matrices 1-semi-unitarias en sí mismo y las clases de matrices unitarias y 2-semi-unitarias, el cierre por compresión de la clase 1-semi-unitaria (así como la clase de matrices recibidas desde los unitarios a través de la sustitución de una fila por un vector de fila arbitrario: la permanente de dicha matriz es, a través de la expansión de Laplace, la suma de las permanentes de matrices 1-semi-unitarias y, en consecuencia, calculable en tiempo polinómico) aún se desconoce y tensamente relacionado con el problema general de la complejidad computacional de la permanente en la característica 3 y la pregunta principal de P versus NP : como se mostró en ( Knezevic & Cohen (2017) ), si tal compresión-cierre es el conjunto de todos los cuadrados matrices sobre un campo 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-semi-unitarias) entonces el permanente es computable en tiempo polinomial en esta característica .
Además, se formuló el problema de encontrar y clasificar posibles análogos de las compresiones de preservación permanente existentes en la característica 3 para otras características primarias ( Knezevic & Cohen (2017) ), dando la siguiente identidad para una matriz n × ny dos n -vectores (con todas sus entradas del conjunto {0,…, p −1}) y tal que , válido en una característica prima arbitraria p :
donde para una matriz n × m, un n-vector y un vector m , ambos vectores con todas sus entradas del conjunto {0,…, p −1}, denota la matriz recibida de a través de la repetición multiplicado por su i -ésima fila para i = 1,…, n ymultiplicado por 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 se eliminó, y por lo tanto esta noción es una generalización de la noción de submatriz), ydenota el vector n todas cuyas entradas son iguales a la unidad. Esta identidad es una analogía exacta de la fórmula clásica que expresa la menor de una matriz a través de una menor de su inversa y, por lo tanto, demuestra (una vez más) una especie de dualidad entre lo determinante y lo permanente como inmanentes relativos. (En realidad, su propio análogo para el hafnian de un simétrico y un primo impar p es ).
Y, como una generalización aún más amplia para el caso inverso parcial en una característica prima p, para , siendo cuadrado, ser invertible y de tamañoX, y , contiene también la identidad
donde los vectores de multiplicidad de filas / columnas comunes y para la matriz generar los vectores de multiplicidad de filas / columnas correspondientes y , s, t = 1,2, para sus bloques (lo mismo se refiere es la inversa parcial en el lado derecho de la igualdad).
Cálculo aproximado
Cuando las entradas de A son no negativas, la permanente se puede calcular aproximadamente en tiempo polinomial probabilístico , hasta un error de ε M , donde M es el valor de la permanente y ε> 0 es arbitrario. En otras palabras, existe un esquema de aproximación aleatoria en tiempo polinómico (FPRAS) ( Jerrum, Vigoda & Sinclair (2001)
).El paso más difícil en el cálculo es la construcción de un algoritmo para muestrear casi uniformemente del conjunto de todos los emparejamientos perfectos en un gráfico bipartito dado: en otras palabras, un muestreador casi uniforme completamente polinomial (FPAUS). Esto se puede hacer usando un algoritmo de Monte Carlo de cadena de Markov que usa una regla de Metropolis para definir y ejecutar una cadena de Markov cuya distribución es casi uniforme y cuyo tiempo de mezcla es polinomial.
Es posible contar aproximadamente el número de emparejamientos perfectos en un gráfico a través de la autorreductibilidad del permanente, utilizando el FPAUS en combinación con una reducción bien conocida del muestreo al conteo debido a Jerrum, Valiant & Vazirani (1986) denotar el número de combinaciones perfectas en . Aproximadamente, para cualquier ventaja en particular en , muestreando muchas coincidencias en y contando cuántos de ellos coinciden en , se puede obtener una estimación de la relación . El número es entonces , dónde puede aproximarse aplicando el mismo método de forma recursiva.
. DejarOtra clase de matrices para las que se puede calcular aproximadamente la permanente es el conjunto de matrices semidefinidas positivas (el problema de la teoría de la complejidad de aproximar la permanente de tales matrices dentro de un error multiplicativo se considera abierto [7] ). El correspondiente algoritmo aleatorizado se basa en el modelo de muestreo de bosones y utiliza las herramientas propias de la óptica cuántica , para representar el permanente de matrices positivas-semidefinidas como el valor esperado de una determinada variable aleatoria. A continuación, este último se aproxima por su media muestral. [8] Este algoritmo, para un cierto conjunto de matrices positivas-semidefinidas, aproxima su permanente en tiempo polinomial hasta un error aditivo, que es más confiable que el del algoritmo clásico estándar de tiempo polinomial de Gurvits. [9]
Notas
- ^ A partir de 2008, consulte Rempala y Wesolowski (2008)
- ^ van Lint y Wilson (2001) p. 99
- ^ Enciclopedia Concisa de Matemáticas CRC
- ^ Nijenhuis y Wilf (1978)
- ^ Pequeño (1974) , Vazirani (1988)
- ↑ Pólya (1913) , Reich (1971)
- ^ Vea el problema abierto (4) en "Shtetl Optimized: Presentando a algunos británicos a P vs. NP" .
- ^ Chakhmakhchyan, Levon; Cerf, Nicolas; García-Patrón, Raúl (2017). "Un algoritmo de inspiración cuántica para estimar la permanente de matrices semidefinidas positivas". Phys. Rev. A . 96 (2): 022329. arXiv : 1609.02416 . Código bibliográfico : 2017PhRvA..96b2329C . doi : 10.1103 / PhysRevA.96.022329 . S2CID 54194194 .
- ^ Gurvits, Leonid (2005). "Sobre la complejidad de los discriminantes mixtos y problemas relacionados". Fundamentos matemáticos de la informática . Apuntes de conferencias en Ciencias de la Computación. 3618 : 447–458. doi : 10.1007 / 11549345_39 . ISBN 978-3-540-28702-5.
Referencias
- Allender, Eric; Gore, Vivec (1994), "Un circuito uniforme límite inferior para lo permanente", SIAM Journal on Computing , 23 (5): 1026–1049, CiteSeerX 10.1.1.51.3546 , doi : 10.1137 / s0097539792233907
- Balasubramanian, K. (1980), Combinatoria y diagonales de matrices (PDF) , Ph.D. Tesis, Departamento de Estadística, Loyola College, Madrás, India, T073 , Instituto Indio de Estadística, Calcuta
- Bax, Eric (1998), Algoritmos de diferencias finitas para problemas de conteo , Ph.D. Disertación, 223 , Instituto de Tecnología de California
- Bax, Eric; Franklin, J. (1996), Un tamiz de diferencias finitas para calcular el permanente , Caltech-CS-TR-96-04, Instituto de Tecnología de California
- Glynn, David G. (2010), "La permanente de una matriz cuadrada", European Journal of Combinatorics , 31 (7): 1887–1891, doi : 10.1016 / j.ejc.2010.01.010
- Glynn, David G. (2013), "Fórmulas permanentes de Veronesean", Diseños, códigos y criptografía , 68 (1–3): 39–47, doi : 10.1007 / s10623-012-9618-1 , S2CID 36911503
- Jerrum, M .; Sinclair, A .; Vigoda, E. (2001), "Un algoritmo de aproximación polinomial-temporal para el permanente de una matriz con entradas no negativas", Proc. 33º Simposio de Teoría de la Computación , págs. 712–721, doi : 10.1145 / 380752.380877 , ISBN 978-1581133493, S2CID 8368245 , ECCC TR00-079
- Mark Jerrum ; Leslie Valiant ; Vijay Vazirani (1986), "Generación aleatoria de estructuras combinatorias a partir de una distribución uniforme", Informática teórica , 43 : 169-188, doi : 10.1016 / 0304-3975 (86) 90174-X
- Kogan, Grigoriy (1996), "Computación permanente sobre campos de característica 3: dónde y por qué se vuelve difícil", 37º Simposio Anual sobre Fundamentos de la Ciencia de la Computación (FOCS '96) : 108-114, doi : 10.1109 / SFCS.1996.548469 , ISBN 0-8186-7594-2, S2CID 39024286
- Knezevic, Anna; Cohen, Greg (2017), Algunos hechos sobre permanentes en características finitas , arXiv : 1710.01783 , Bibcode : 2017arXiv171001783K
- van Lint, Jacobus Hendricus; Wilson, Richard Michale (2001), Un curso de combinatoria , ISBN 978-0-521-00601-9
- Little, CHC (1974), "Una extensión del método de Kasteleyn de enumerar los factores 1 de gráficos planos", en Holton, D. (ed.), Proc. Segunda Conf. Australiana Matemáticas combinatorias , Lecture Notes in Mathematics, 403 , Springer-Verlag, págs. 63–72
- Little, CHC (1975), "Una caracterización de matrices convertibles (0, 1)", Journal of Combinatorial Theory , Serie B, 18 (3): 187-208, doi : 10.1016 / 0095-8956 (75) 90048- 9
- Marcus, M .; Minc, H. (1961), "Sobre la relación entre lo determinante y lo permanente", Illinois Journal of Mathematics , 5 (3): 376–381, doi : 10.1215 / ijm / 1255630882
- Nijenhuis, Albert; Wilf, Herbert S. (1978), algoritmos combinatorios , Academic Press
- Pólya, G. (1913), "Aufgabe 424", Arch. Matemáticas. Phys. , 20 (3): 27
- Reich, Simeon (1971), "Otra solución de un viejo problema de pólya", American Mathematical Monthly , 78 (6): 649–650, doi : 10.2307 / 2316574 , JSTOR 2316574
- Rempała, Grzegorz A .; Wesolowski, Jacek (2008), Funcionales simétricos en matrices aleatorias y problemas de emparejamientos aleatorios , pág. 4, ISBN 978-0-387-75145-0
- Ryser, Herbert John (1963), Matemáticas combinatorias , The Carus Mathematical Monographs, vol. 14, Asociación Matemática de América
- Vazirani, Vijay V. (1988), "Algoritmos NC para calcular el número de emparejamientos perfectos en gráficos libres de K 3,3 y problemas relacionados", Proc. 1er Taller escandinavo sobre teoría de algoritmos (SWAT '88) , Lecture Notes in Computer Science, 318 , Springer-Verlag, págs. 233–242, doi : 10.1007 / 3-540-19487-8_27 , hdl : 1813/6700 , ISBN 978-3-540-19487-3
- Valiant, Leslie G. (1979), "La complejidad de calcular lo permanente", Informática teórica , Elsevier, 8 (2): 189-201, doi : 10.1016 / 0304-3975 (79) 90044-6
- "Permanente", CRC Concise Encyclopedia of Mathematics , Chapman & Hall / CRC, 2002
Otras lecturas
- Barvinok, A. (2017), "Aproximación de permanentes y hafnianos", Análisis discreto , arXiv : 1601.07518 , doi : 10.19086 / da.1244 , S2CID 397350.