Calculando el permanente

Problema de álgebra lineal

En álgebra lineal , el cálculo del permanente de una matriz es un problema que se considera 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 una matriz que se encuentran en filas y columnas distintas. Sin embargo, donde el determinante pondera cada uno de estos productos con un signo ±1 según la paridad del conjunto , el permanente los pondera a todos con un signo +1.

Si bien el determinante se puede calcular en tiempo polinómico mediante eliminación gaussiana , generalmente se cree que el permanente no se puede calcular en tiempo polinómico. En la teoría de la complejidad computacional , un teorema de Valiant establece que calcular permanentes es #P-duro , e incluso #P-completo para matrices en las que todas las entradas son 0 o 1 Valiant (1979). Esto coloca el cálculo del permanente en una clase de problemas que se cree que son incluso más difíciles de calcular que el 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 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

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

La suma se extiende aquí 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 sólo 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 se puede traducir directamente a un algoritmo que expande 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 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: Sea obtenido de A eliminando k columnas, sea el producto de las sumas de las filas de y sea la suma de los valores de sobre todo lo posible . Entonces ${\displaystyle A_{k}}$ ${\displaystyle P(A_{k})}$ ${\displaystyle A_{k}}$ ${\displaystyle \Sigma _{k}}$ ${\displaystyle P(A_{k})}$ ${\displaystyle A_{k}}$

${\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 evaluar mediante operaciones aritméticas o procesando los conjuntos en orden de código Gray . ^[4] ${\displaystyle O(2^{n-1}n^{2})}$ ${\displaystyle O(2^{n-1}n)}$ ${\displaystyle S}$

Fórmula de Balasubramanian-Bax-Franklin-Glynn

Otra fórmula que parece ser tan rápida como la de Ryser (o quizás incluso dos veces más rápida) 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 y 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 de un tensor simétrico (Glynn 2010). La fórmula se generaliza a infinitas otras, como han encontrado todos estos autores, aunque no está claro si son más rápidas que la básica. Ver (Glynn 2013).

La fórmula más simple conocida de este tipo (cuando la característica del campo 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 exterior está sobre todos los vectores . ${\displaystyle 2^{n-1}}$ ${\displaystyle \delta =(\delta _{1}=1,\delta _{2},\dots ,\delta _{n})\in \{\pm 1\}^{n}}$

Casos especiales

Planar y libre de K 3,3

El número de coincidencias perfectas en un gráfico bipartito se cuenta mediante el permanente de la matriz de biaadyacencia del gráfico , y el permanente de cualquier matriz 0-1 se puede interpretar de esta manera como el número de coincidencias perfectas en un gráfico. Para gráficos planos (independientemente de la bipartición), el algoritmo FKT calcula el número de coincidencias perfectas en tiempo polinómico cambiando los signos de un subconjunto cuidadosamente elegido de las entradas en la matriz de Tutte del gráfico, de modo que el pfaffiano de la asimetría resultante . La matriz simétrica (la raíz cuadrada de su determinante ) es el número de coincidencias perfectas. Esta técnica se puede generalizar a gráficos que no contienen ningún subgrafo homeomorfo al gráfico 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 y Minc (1961)) que no existe una aplicación lineal tal que para todas las 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 biadyacencia de grafos bipartitos que tienen una orientación pfaffiana : una orientación de las aristas tal que para cada ciclo par para el cual tiene En 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 gráficos son exactamente aquellos que no contienen un subgrafo homeomorfo a , como se indicó anteriormente. ${\displaystyle T}$ ${\displaystyle \operatorname {per} T(A)=\det A}$ ${\displaystyle n\times n}$ ${\displaystyle A}$ ${\displaystyle C}$ ${\displaystyle G\setminus C}$ ${\displaystyle K_{3,3}}$

Módulo de cálculo un número

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

Hay varias fórmulas dadas por Glynn (2010) para el cálculo del módulo a primo p . En primer lugar, hay uno que utiliza cálculos simbólicos con derivadas parciales.

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

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

donde es la submatriz de inducida por las filas y columnas de indexadas por , y es el complemento de in , 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\}}$

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}}}$$

pp ${\displaystyle {J_{1}},\ldots ,{J_{p-1}}}$ ${\displaystyle \{1,\dots ,n\}}$

La primera fórmula posee un análogo para el hafniano de una p simétrica y una impar: ${\displaystyle 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 la característica cero, una expresión de suma de convolución similar que involucra tanto al permanente como al determinante produce el polinomio del ciclo hamiltoniano (definido como dónde está el conjunto de n-permutaciones que tienen un solo ciclo): ${\textstyle \operatorname {ham} (A)=\sum _{\sigma \in H_{n}}\prod _{i=1}^{n}a_{i,\sigma (i)}}$ ${\displaystyle H_{n}}$

$${\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 lo que, por lo tanto, brinda la oportunidad de calcular en tiempo polinomial el polinomio del ciclo hamiltoniano de cualquier unidad unitaria (es decir, tal que ¿ dónde está la identidad n × n -matriz), porque cada menor de dicha matriz coincide con su complemento algebraico: donde está 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 como donde es un subconjunto de { 1, ..., n }, es la matriz identidad n × n con las entradas de los índices k , k reemplazadas por 0 para todo k perteneciente a , y definimos dónde está el conjunto de n-permutaciones que cada ciclo contiene en menos un elemento de . ${\displaystyle \operatorname {ham} (A)=\sum _{J\subseteq \{2,\dots ,n\}}\det(A_{J})\operatorname {det} (A_{\bar {J}})}$ ${\displaystyle U}$ ${\displaystyle U^{\textsf {T}}U=I}$ ${\displaystyle I}$ ${\displaystyle \operatorname {ham} (U)=\operatorname {det} ^{2}(U+I_{/1})}$ ${\displaystyle I_{/1}}$ ${\displaystyle U}$ ${\displaystyle \operatorname {ham_{K}} (U)=\operatorname {det} ^{2}(U+I_{/K})}$ ${\displaystyle K}$ ${\displaystyle I_{/K}}$ ${\displaystyle K}$ ${\textstyle \operatorname {ham_{K}} (A)=\sum _{\sigma \in H_{n}(K)}\prod _{i=1}^{n}a_{i,\sigma (i)}}$ ${\displaystyle H_{n}(K)}$ ${\displaystyle K}$

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

para cualquier invertible ${\displaystyle A}$

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

para cualquier matriz unitaria , es decir, cuadrada tal que donde está la matriz identidad del tamaño correspondiente, ${\displaystyle U}$ ${\displaystyle U}$ ${\displaystyle U^{\textsf {T}}U=I}$ ${\displaystyle I}$

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

donde está la matriz cuyas entradas son los cubos de las entradas correspondientes de . ${\displaystyle V}$ ${\displaystyle U}$

También se demostró (Kogan (1996)) que, si definimos una matriz cuadrada como k-semi-unitaria cuando , el permanente de una matriz 1-semi-unitaria es computable en tiempo polinomial sobre campos de característica 3, mientras que para k > 1 el problema pasa a ser #3-P-completo . (Una teoría paralela se refiere al polinomio del ciclo hamiltoniano en la característica 2: si bien calcularlo en 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 fue esencialmente ampliado en 2017 (Knezevic & 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 y siendo cuadrado, siendo invertible ): ${\displaystyle A}$ ${\displaystyle \operatorname {rank} (A^{\textsf {T}}A-I)=k}$ ${\displaystyle A_{11}}$ ${\displaystyle A_{22}}$ ${\displaystyle A_{11}}$

$${\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) correspondientemente, por lo que se ha introducido un operador de compresión (analógico a la modificación gaussiana aplicada para calcular el determinante ) que "preserva" el permanente en la característica 3. (Analógicamente, valdría 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 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 transpuesta (utilizada cada vez que el operador deja la matriz intacta) también es un mapeo 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 desde unitarios hasta la sustitución de una fila por un vector de fila arbitrario (el permanente de dicha matriz es, mediante la expansión de Laplace, la suma de los permanentes de matrices 1 semiunitarias y, en consecuencia, computable en tiempo polinomial) aún se desconoce y tensamente relacionado con el problema general de la complejidad computacional del permanente en la característica 3 y la cuestión principal de P versus NP : como se mostró en (Knezevic & Cohen (2017)), si tal cierre de compresión 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 semiunitarias), entonces el permanente es computable en tiempo polinómico 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 principales (Knezevic & Cohen (2017)), dando la siguiente identidad para una matriz n × n y dos n -vectores (que tienen todas sus entradas del conjunto {0, ..., p − 1}) y tales que , válidos en una característica prima arbitraria p : ${\displaystyle A}$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\textstyle {\sum _{i=1}^{n}\alpha _{i}=\sum _{j=1}^{n}\beta _{j}}}$

$${\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 , un vector n y un vector m , ambos vectores con todas sus entradas del conjunto {0, ..., p − 1}, denota la matriz recibida mediante tiempos repetidos , es i -ésima fila para i = 1, ..., n y multiplicada 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 fue eliminada, y por lo tanto esta noción es una generalización de la noción de submatriz), y denota el n-vector 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 tanto, demuestra (una vez más) una especie de dualidad entre lo determinante y lo permanente como inmanantes relativos. (En realidad, su propio análogo para el hafniano de un primo p simétrico e impar es ). ${\displaystyle M}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle M^{(x,y)}}$ ${\displaystyle M}$ ${\displaystyle x_{i}}$ ${\displaystyle y_{j}}$ ${\displaystyle {\vec {1}}_{n}}$ ${\displaystyle A}$ ${\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 , siendo cuadrado, invertible y de tamaño x , y , se cumple también la identidad ${\displaystyle A_{11}}$ ${\displaystyle A_{22}}$ ${\displaystyle A_{11}}$ ${\displaystyle {n_{1}}}$ ${\displaystyle {n_{1}}}$ ${\textstyle {\sum _{i=1}^{n}\alpha _{i}=\sum _{j=1}^{n}\beta _{j}}}$

$${\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 y para la matriz generan los correspondientes vectores de multiplicidad fila/columna y , s,t = 1,2, para sus bloques (lo mismo ocurre con la inversa parcial en el lado derecho de la igualdad). ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle A}$ ${\displaystyle \alpha _{s}}$ ${\displaystyle \beta _{t}}$ ${\displaystyle A}$

Cálculo aproximado

Cuando las entradas de A no son negativas, el permanente se puede calcular 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 aleatoria en tiempo totalmente polinómico (FPRAS) (Jerrum, Sinclair y Vigoda (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 todas las coincidencias perfectas en un gráfico bipartito determinado: en otras palabras, un muestreador casi uniforme totalmente polinomial (FPAUS). Esto se puede hacer usando un algoritmo 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 polinómico.

Es posible contar aproximadamente el número de coincidencias perfectas en un gráfico mediante la autorreducibilidad del permanente, utilizando el FPAUS en combinación con una conocida reducción del muestreo al conteo debido a Jerrum, Valiant y Vazirani (1986). Denotemos el número de coincidencias perfectas en . En términos generales, para cualquier ventaja particular en , al muestrear muchas coincidencias en y contar cuántas de ellas coinciden en , se puede obtener una estimación de la relación . El número entonces es , donde se puede aproximar aplicando el mismo método de forma recursiva. ${\displaystyle M(G)}$ ${\displaystyle G}$ ${\displaystyle e}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G\setminus e}$ ${\textstyle \rho ={\frac {M(G)}{M(G\setminus e)}}}$ ${\displaystyle M(G)}$ ${\displaystyle \rho M(G\setminus e)}$ ${\displaystyle M(G\setminus e)}$

Otra clase de matrices para las que la permanente resulta de particular interés son las matrices semidefinidas positivas . ^[7] Usando una técnica de conteo de Stockmeyer, se pueden calcular dentro de la clase , pero esto 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 -difícil ^[8] Si se imponen más restricciones al espectro , se conocen algoritmos más eficientes. Un algoritmo aleatorio 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 semidefinidas positivas como el valor esperado de una variable aleatoria específica. Luego, este último se aproxima por su media muestral. ^[9] Este algoritmo, para un cierto conjunto de matrices semidefinidas positivas, 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. ^[10] ${\displaystyle {\textsf {BPP}}^{\textsf {NP}}}$ ${\displaystyle {\textsf {BPP}}^{\textsf {NP}}}$

Notas

1. A partir de 2008, consulte Rempała y Wesolowski (2008)
2. van Lint y Wilson (2001) pág. 99
3. Enciclopedia concisa de matemáticas CRC
4. Nijenhuis y Wilf (1978)
5. Pequeño (1974), Vazirani (1988)
6. Pólya (1913), Reich (1971)
7. Ver problema abierto (4) en Shtetl Optimized: Presentación de P vs. NP para algunos británicos, 22 de julio de 2015
8. Meiburg, Alexander (2023), "Inaproximabilidad de permanentes semidefinidos positivos y tomografía de estado cuántico", Algorithmica , 85 (12): 3828–3854, arXiv : 2111.03142 , doi : 10.1007/s00453-023-01169-1
9. Chakhmakhchyan, Levon; Cerf, Nicolás; 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 , Bibcode : 2017PhRvA..96b2329C, doi : 10.1103/PhysRevA.96.022329, S2CID  54194194
10. Gurvits, Leonid (2005), "Sobre la complejidad de los discriminantes mixtos y problemas relacionados", Fundamentos matemáticos de la informática 2005 , Lecture Notes in Computer Science, vol. 3618, págs. 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, vol. T073, Instituto Indio de Estadística, Calcuta
• Bax, Eric (1998), Algoritmos de diferencias finitas para problemas de conteo , Ph.D. Disertación, vol. 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), "El 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 del Veronés", 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 en tiempo polinómico para el permanente de una matriz con entradas no negativas", Proc. 33º Simposio sobre Teoría de la Computación , págs. 712–721, doi :10.1145/380752.380877, ISBN 978-1581133493, S2CID  8368245, ECCC  TR00-079
• Jerrum, Marcos ; Valiente, Leslie ; Vazirani, Vijay (1986), "Generación aleatoria de estructuras combinatorias a partir de una distribución uniforme", Ciencias de la Computación Teórica , 43 : 169–188, doi :10.1016/0304-3975(86)90174-X
• Kogan, Grigoriy (1996), "Computación de permanentes en campos de característica 3: dónde y por qué se vuelve difícil", Actas de la 37ª Conferencia sobre los fundamentos de la informática , págs. 108-114, doi :10.1109/SFCS.1996.548469, ISBN 0-8186-7594-2, S2CID  39024286
• Knezevic, Anna; Cohen, Greg (2017), Algunos datos sobre permanentes en características finitas , arXiv : 1710.01783 , Bibcode :2017arXiv171001783K
• van Lint, Jacobus Hendricus; Wilson, Richard Michale (2001), Un curso de combinatoria , Cambridge University Press, ISBN 978-0-521-00601-9
• Little, CHC (1974), "Una extensión del método de Kasteleyn para enumerar los factores 1 de gráficos planos", en Holton, D. (ed.), Proc. 2da Conferencia Australiana. Matemáticas combinatorias , Apuntes de conferencias de matemáticas, vol. 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
• Marco, 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", Arq. Matemáticas. Física. , 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 sobre matrices aleatorias y problemas de coincidencias aleatorias , Springer, p. 4, ISBN 978-0-387-75145-0
• Ryser, Herbert John (1963), Matemáticas combinatorias , Las monografías matemáticas de Carus, vol. 14, Asociación Matemática de América , ISBN 978-1-61444-014-7
• Vazirani, Vijay V. (1988), "Algoritmos NC para calcular el número de coincidencias perfectas en gráficos libres de K _3,3 y problemas relacionados", Proc. 1er taller escandinavo sobre teoría de algoritmos (SWAT '88) , Apuntes de conferencias sobre informática, vol. 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 , 8 (2), Elsevier: 189–201, doi :10.1016/0304-3975(79)90044-6, S2CID  1637832
• "Permanente", Enciclopedia concisa de matemáticas CRC , 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.