Permanente (matemáticas)

Polinomio de los elementos de una matriz

En álgebra lineal , la permanente de una matriz cuadrada es una función de la matriz similar al determinante . La permanente, así como el determinante, es un polinomio en las entradas de la matriz. ^[1] Ambos son casos especiales de una función más general de una matriz llamada inmanente .

Definición

La permanente de una matriz n × 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 aquí se extiende sobre todos los elementos σ del grupo simétrico S _n ; es decir, sobre todas las permutaciones de los números 1, 2, ..., n .

Por ejemplo,

$${\displaystyle \operatorname {perm} {\begin{pmatrix}a&b\\c&d\end{pmatrix}}=ad+bc,}$$

y

$${\displaystyle \operatorname {perm} {\begin{pmatrix}a&b&c\\d&e&f\\g&h&i\end{pmatrix}}=aei+bfg+cdh+ceg+bdi+afh.}$$

La definición del permanente de A difiere de la del determinante de A en que no se tienen en cuenta las firmas de las permutaciones.

La permanente de una matriz A se denota por A , perm A o Per A , a veces con paréntesis alrededor del argumento. Minc usa Per( A ) para la permanente de matrices rectangulares, y per( A ) cuando A es una matriz cuadrada. ^[2] Muir y Metzler usan la notación . ^[3] ${\displaystyle {\overset {+}{|}}\quad {\overset {+}{|}}}$

La palabra permanente se originó con Cauchy en 1812 como “funciones simétricas permanentes” para un tipo de función relacionada, ^[4] y fue utilizada por Muir y Metzler ^[5] en el sentido moderno, más específico. ^[6]

Propiedades

Si se considera el permanente como una función que toma n vectores como argumentos, entonces es una función multilineal y es simétrica (lo que significa que cualquier orden de los vectores da como resultado el mismo permanente). Además, dada una matriz cuadrada de orden n : ^[7] ${\displaystyle A=\left(a_{ij}\right)}$

• perm( A ) es invariante bajo permutaciones arbitrarias de las filas y/o columnas de A . Esta propiedad puede escribirse simbólicamente como perm( A ) = perm( PAQ ) para cualquier matriz de permutación de tamaño apropiado P y Q ,
• al multiplicar cualquier fila o columna de A por un escalar s, perm( A ) se convierte en s ⋅perm( A ),
• perm( A ) es invariante bajo transposición , es decir, perm( A ) = perm( A ^T ).
• Si y son matrices cuadradas de orden n entonces, ^[8] donde s y t son subconjuntos del mismo tamaño de {1,2,..., n } y son sus respectivos complementos en ese conjunto. ${\displaystyle A=\left(a_{ij}\right)}$ ${\displaystyle B=\left(b_{ij}\right)}$ $${\displaystyle \operatorname {perm} \left(A+B\right)=\sum _{s,t}\operatorname {perm} \left(a_{ij}\right)_{i\in s,j\in t}\operatorname {perm} \left(b_{ij}\right)_{i\in {\bar {s}},j\in {\bar {t}}},}$$ ${\displaystyle {\bar {s}},{\bar {t}}}$
• Si es una matriz triangular , es decir , siempre que o, alternativamente, siempre que , entonces su permanente (y determinante también) es igual al producto de las entradas diagonales: ${\displaystyle A}$ ${\displaystyle a_{ij}=0}$ ${\displaystyle i>j}$ ${\displaystyle i<j}$ $${\displaystyle \operatorname {perm} \left(A\right)=a_{11}a_{22}\cdots a_{nn}=\prod _{i=1}^{n}a_{ii}.}$$

Relación con los determinantes

La expansión de Laplace por menores para calcular el determinante a lo largo de una fila, columna o diagonal se extiende al permanente ignorando todos los signos. ^[9]

Para cada , ${\textstyle i}$

$${\displaystyle \mathbb {perm} (B)=\sum _{j=1}^{n}B_{i,j}M_{i,j},}$$

donde es la entrada de la i- ésima fila y la j -ésima columna de B , y es la permanente de la submatriz obtenida al eliminar la i -ésima fila y la j -ésima columna de B . ${\displaystyle B_{i,j}}$ ${\textstyle M_{i,j}}$

Por ejemplo, expandiendo a lo largo de la primera columna,

$${\displaystyle {\begin{aligned}\operatorname {perm} \left({\begin{matrix}1&1&1&1\\2&1&0&0\\3&0&1&0\\4&0&0&1\end{matrix}}\right)={}&1\cdot \operatorname {perm} \left({\begin{matrix}1&0&0\\0&1&0\\0&0&1\end{matrix}}\right)+2\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\0&1&0\\0&0&1\end{matrix}}\right)\\&{}+\ 3\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\1&0&0\\0&0&1\end{matrix}}\right)+4\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\1&0&0\\0&1&0\end{matrix}}\right)\\={}&1(1)+2(1)+3(1)+4(1)=10,\end{aligned}}}$$

mientras se expande a lo largo de la última fila da,

$${\displaystyle {\begin{aligned}\operatorname {perm} \left({\begin{matrix}1&1&1&1\\2&1&0&0\\3&0&1&0\\4&0&0&1\end{matrix}}\right)={}&4\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\1&0&0\\0&1&0\end{matrix}}\right)+0\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\2&0&0\\3&1&0\end{matrix}}\right)\\&{}+\ 0\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\2&1&0\\3&0&0\end{matrix}}\right)+1\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\2&1&0\\3&0&1\end{matrix}}\right)\\={}&4(1)+0+0+1(6)=10.\end{aligned}}}$$

Por otra parte, la propiedad multiplicativa básica de los determinantes no es válida para los permanentes. ^[10] Un ejemplo sencillo muestra que esto es así.

$${\displaystyle {\begin{aligned}4&=\operatorname {perm} \left({\begin{matrix}1&1\\1&1\end{matrix}}\right)\operatorname {perm} \left({\begin{matrix}1&1\\1&1\end{matrix}}\right)\\&\neq \operatorname {perm} \left(\left({\begin{matrix}1&1\\1&1\end{matrix}}\right)\left({\begin{matrix}1&1\\1&1\end{matrix}}\right)\right)=\operatorname {perm} \left({\begin{matrix}2&2\\2&2\end{matrix}}\right)=8.\end{aligned}}}$$

A diferencia del determinante, el permanente no tiene una interpretación geométrica fácil; se utiliza principalmente en combinatoria , en el tratamiento de las funciones de Green de los bosones en la teoría cuántica de campos y en la determinación de las probabilidades de estado de los sistemas de muestreo de bosones . ^[11] Sin embargo, tiene dos interpretaciones desde la teoría de grafos : como la suma de los pesos de las coberturas de ciclos de un grafo dirigido y como la suma de los pesos de los emparejamientos perfectos en un grafo bipartito .

Aplicaciones

Tensores simétricos

La permanente surge naturalmente en el estudio de la potencia tensorial simétrica de los espacios de Hilbert . ^[12] En particular, para un espacio de Hilbert , sea la potencia tensorial simétrica n de , que es el espacio de tensores simétricos . Nótese en particular que está abarcado por los productos simétricos de elementos en . Para , definimos el producto simétrico de estos elementos por Si consideramos (como un subespacio de , la k -ésima potencia tensorial de ) y definimos el producto interno en en consecuencia, encontramos que para Aplicando la desigualdad de Cauchy–Schwarz , encontramos que , y que ${\displaystyle H}$ ${\displaystyle \vee ^{k}H}$ ${\displaystyle k}$ ${\displaystyle H}$ ${\displaystyle \vee ^{k}H}$ ${\displaystyle H}$ ${\displaystyle x_{1},x_{2},\dots ,x_{k}\in H}$ $${\displaystyle x_{1}\vee x_{2}\vee \cdots \vee x_{k}=(k!)^{-1/2}\sum _{\sigma \in S_{k}}x_{\sigma (1)}\otimes x_{\sigma (2)}\otimes \cdots \otimes x_{\sigma (k)}}$$ ${\displaystyle \vee ^{k}H}$ ${\displaystyle \otimes ^{k}H}$ ${\displaystyle H}$ ${\displaystyle \vee ^{k}H}$ ${\displaystyle x_{j},y_{j}\in H}$ $${\displaystyle \langle x_{1}\vee x_{2}\vee \cdots \vee x_{k},y_{1}\vee y_{2}\vee \cdots \vee y_{k}\rangle =\operatorname {perm} \left[\langle x_{i},y_{j}\rangle \right]_{i,j=1}^{k}}$$ ${\displaystyle \operatorname {perm} \left[\langle x_{i},x_{j}\rangle \right]_{i,j=1}^{k}\geq 0}$ $${\displaystyle \left|\operatorname {perm} \left[\langle x_{i},y_{j}\rangle \right]_{i,j=1}^{k}\right|^{2}\leq \operatorname {perm} \left[\langle x_{i},x_{j}\rangle \right]_{i,j=1}^{k}\cdot \operatorname {perm} \left[\langle y_{i},y_{j}\rangle \right]_{i,j=1}^{k}}$$

Fundas para bicicletas

Cualquier matriz cuadrada puede ser vista como la matriz de adyacencia de un grafo dirigido ponderado sobre el conjunto de vértices , con representando el peso del arco desde el vértice i hasta el vértice j . Una cobertura de ciclo de un grafo dirigido ponderado es una colección de ciclos dirigidos disjuntos en vértices en el dígrafo que cubre todos los vértices en el grafo. Por lo tanto, cada vértice i en el dígrafo tiene un "sucesor" único en la cobertura de ciclo, y por lo tanto representa una permutación en V . Por el contrario, cualquier permutación en V corresponde a una cobertura de ciclo con arcos desde cada vértice i hasta el vértice . ${\displaystyle A=(a_{ij})_{i,j=1}^{n}}$ ${\displaystyle V=\{1,2,\dots ,n\}}$ ${\displaystyle a_{ij}}$ ${\displaystyle \sigma (i)}$ ${\displaystyle \sigma }$ ${\displaystyle \sigma }$ ${\displaystyle \sigma (i)}$

Si el peso de una cubierta de ciclo se define como el producto de los pesos de los arcos en cada ciclo, entonces lo que implica que Por lo tanto, la permanente de A es igual a la suma de los pesos de todas las cubiertas de ciclo del dígrafo. $${\displaystyle \operatorname {weight} (\sigma )=\prod _{i=1}^{n}a_{i,\sigma (i)},}$$ $${\displaystyle \operatorname {perm} (A)=\sum _{\sigma }\operatorname {weight} (\sigma ).}$$

Combinaciones perfectas

Una matriz cuadrada también puede verse como la matriz de adyacencia de un grafo bipartito que tiene vértices en un lado y en el otro lado, con representando el peso de la arista de vértice a vértice . Si el peso de una correspondencia perfecta que coincide con se define como el producto de los pesos de las aristas en la correspondencia, entonces Por lo tanto, la permanente de A es igual a la suma de los pesos de todas las correspondencias perfectas del grafo. ${\displaystyle A=(a_{ij})}$ ${\displaystyle x_{1},x_{2},\dots ,x_{n}}$ ${\displaystyle y_{1},y_{2},\dots ,y_{n}}$ ${\displaystyle a_{ij}}$ ${\displaystyle x_{i}}$ ${\displaystyle y_{j}}$ ${\displaystyle \sigma }$ ${\displaystyle x_{i}}$ ${\displaystyle y_{\sigma (i)}}$ $${\displaystyle \operatorname {weight} (\sigma )=\prod _{i=1}^{n}a_{i,\sigma (i)}.}$$

Permanentes de matrices (0, 1)

Enumeración

Las respuestas a muchas preguntas de conteo se pueden calcular como permanentes de matrices que solo tienen 0 y 1 como entradas.

Sea Ω( n , k ) la clase de todas las (0, 1)-matrices de orden n con cada suma de fila y columna igual a k . Cada matriz A en esta clase tiene perm( A ) > 0. ^[13] Las matrices de incidencia de los planos proyectivos están en la clase Ω( n ² + n + 1, n + 1) para n un entero > 1. Se han calculado los permanentes correspondientes a los planos proyectivos más pequeños. Para n = 2, 3 y 4 los valores son 24, 3852 y 18,534,400 respectivamente. ^[13] Sea Z la matriz de incidencia del plano proyectivo con n = 2, el plano de Fano . Notablemente, perm( Z ) = 24 = |det ( Z )|, el valor absoluto del determinante de Z . Esto es una consecuencia de que Z sea una matriz circulante y del teorema: ^[14]

Si A es una matriz circulante de la clase Ω( n , k ) entonces si k  > 3, perm( A ) > |det ( A )| y si k  = 3, perm( A ) = |det ( A )|. Además, cuando k  = 3, permutando filas y columnas, A puede ponerse en la forma de una suma directa de e copias de la matriz Z y, en consecuencia, n  = 7 e y perm( A ) = 24 ^e .

Los permanentes también se pueden utilizar para calcular el número de permutaciones con posiciones restringidas (prohibidas). Para el conjunto n estándar {1, 2, ..., n }, sea la matriz (0, 1) donde a _ij = 1 si se permite i  →  j en una permutación y a _ij = 0 en caso contrario. Entonces perm( A ) es igual al número de permutaciones del conjunto n que satisfacen todas las restricciones. ^[9] Dos casos especiales bien conocidos de esto son la solución del problema de desarreglo y el problema de ménage : el número de permutaciones de un conjunto n sin puntos fijos (desarreglos) está dado por ${\displaystyle A=(a_{ij})}$

$${\displaystyle \operatorname {perm} (J-I)=\operatorname {perm} \left({\begin{matrix}0&1&1&\dots &1\\1&0&1&\dots &1\\1&1&0&\dots &1\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&1&1&\dots &0\end{matrix}}\right)=n!\sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}},}$$donde J es la matriz n × n de todos los 1 e I es la matriz identidad, y los números de ménage se dan por

$${\displaystyle {\begin{aligned}\operatorname {perm} (J-I-I')&=\operatorname {perm} \left({\begin{matrix}0&0&1&\dots &1\\1&0&0&\dots &1\\1&1&0&\dots &1\\\vdots &\vdots &\vdots &\ddots &\vdots \\0&1&1&\dots &0\end{matrix}}\right)\\&=\sum _{k=0}^{n}(-1)^{k}{\frac {2n}{2n-k}}{2n-k \choose k}(n-k)!,\end{aligned}}}$$

donde I' es la matriz (0, 1) con entradas distintas de cero en las posiciones ( i , i + 1) y ( n , 1).

Límites

La desigualdad de Bregman-Minc , conjeturada por H. Minc en 1963 ^[15] y demostrada por LM Brégman en 1973, ^[16] da una cota superior para la permanente de una matriz n × n (0, 1). Si A tiene r _i unos en la fila i para cada 1 ≤ i ≤ n , la desigualdad establece que $${\displaystyle \operatorname {perm} A\leq \prod _{i=1}^{n}(r_{i})!^{1/r_{i}}.}$$

Conjetura de van der Waerden

En 1926, Van der Waerden conjeturó que el mínimo permanente entre todas las matrices doblemente estocásticas n × n es n !/ n ⁿ , logrado por la matriz para la cual todas las entradas son iguales a 1/ n . ^[17] Las pruebas de esta conjetura fueron publicadas en 1980 por B. Gyires ^[18] y en 1981 por GP Egorychev ^[19] y DI Falikman; ^[20] La prueba de Egorychev es una aplicación de la desigualdad de Alexandrov-Fenchel . ^[21] Por este trabajo, Egorychev y Falikman ganaron el Premio Fulkerson en 1982. ^[22]

Cálculo

El enfoque ingenuo, utilizando la definición, de calcular permanentes es computacionalmente inviable incluso para matrices relativamente pequeñas. Uno de los algoritmos más rápidos conocidos se debe a HJ Ryser . ^[23] El método de Ryser se basa en una fórmula de inclusión-exclusión que puede darse ^[24] de la siguiente manera: Sea obtenido de A eliminando k columnas, sea el producto de las sumas de filas de , y sea la suma de los valores de sobre todos los posibles . 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: $${\displaystyle \operatorname {perm} (A)=(-1)^{n}\sum _{S\subseteq \{1,\dots ,n\}}(-1)^{|S|}\prod _{i=1}^{n}\sum _{j\in S}a_{ij}.}$$

Se cree que el permanente es más difícil de calcular que el determinante. Mientras que el determinante puede calcularse en tiempo polinomial mediante eliminación gaussiana , la eliminación gaussiana no puede utilizarse para calcular el permanente. Además, calcular el permanente de una matriz (0,1) es #P-completo . Por lo tanto, si el permanente puede calcularse en tiempo polinomial mediante cualquier método, entonces FP  =  #P , que es una afirmación incluso más sólida que P = NP . Sin embargo, cuando las entradas de A son no negativas, el permanente puede calcularse aproximadamente en tiempo polinomial probabilístico , hasta un error de , donde es el valor del permanente y es arbitrario. ^[25] El permanente de un determinado conjunto de matrices semidefinidas positivas es NP-difícil de aproximar dentro de cualquier factor subexponencial. ^[26] Si se imponen condiciones adicionales en el espectro , el permanente puede aproximarse en tiempo polinomial probabilístico: el mejor error alcanzable de esta aproximación es ( es nuevamente el valor del permanente). ^[27] La ​​dificultad en estos casos está estrechamente relacionada con la dificultad de simular experimentos de muestreo de bosones . ${\displaystyle \varepsilon M}$ ${\displaystyle M}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle \varepsilon {\sqrt {M}}}$ ${\displaystyle M}$

Teorema maestro de MacMahon

Otra forma de ver los permanentes es a través de funciones generadoras multivariadas . Sea una matriz cuadrada de orden n . Considere la función generadora multivariada: El coeficiente de in es perm( A ). ^[28] ${\displaystyle A=(a_{ij})}$ $${\displaystyle {\begin{aligned}F(x_{1},x_{2},\dots ,x_{n})&=\prod _{i=1}^{n}\left(\sum _{j=1}^{n}a_{ij}x_{j}\right)\\&=\left(\sum _{j=1}^{n}a_{1j}x_{j}\right)\left(\sum _{j=1}^{n}a_{2j}x_{j}\right)\cdots \left(\sum _{j=1}^{n}a_{nj}x_{j}\right).\end{aligned}}}$$ ${\displaystyle x_{1}x_{2}\dots x_{n}}$ ${\displaystyle F(x_{1},x_{2},\dots ,x_{n})}$

Como generalización, para cualquier secuencia de n números enteros no negativos, defina: como el coeficiente de en ${\displaystyle s_{1},s_{2},\dots ,s_{n}}$ $${\displaystyle \operatorname {perm} ^{(s_{1},s_{2},\dots ,s_{n})}(A)}$$ ${\displaystyle x_{1}^{s_{1}}x_{2}^{s_{2}}\cdots x_{n}^{s_{n}}}$ ${\displaystyle \left(\sum _{j=1}^{n}a_{1j}x_{j}\right)^{s_{1}}\left(\sum _{j=1}^{n}a_{2j}x_{j}\right)^{s_{2}}\cdots \left(\sum _{j=1}^{n}a_{nj}x_{j}\right)^{s_{n}}.}$

El teorema maestro de MacMahon que relaciona permanentes y determinantes es: ^[29] donde I es la matriz identidad de orden n y X es la matriz diagonal con diagonales $${\displaystyle \operatorname {perm} ^{(s_{1},s_{2},\dots ,s_{n})}(A)={\text{ coefficient of }}x_{1}^{s_{1}}x_{2}^{s_{2}}\cdots x_{n}^{s_{n}}{\text{ in }}{\frac {1}{\det(I-XA)}},}$$ ${\displaystyle [x_{1},x_{2},\dots ,x_{n}].}$

Matrices rectangulares

La función permanente se puede generalizar para aplicarla a matrices no cuadradas. De hecho, varios autores hacen de esto la definición de una permanente y consideran la restricción a matrices cuadradas un caso especial. ^[30] Específicamente, para una matriz m  ×  n con m  ≤  n , defina donde P( n , m ) es el conjunto de todas las m -permutaciones del n -conjunto {1,2,...,n}. ^[31] ${\displaystyle A=(a_{ij})}$ $${\displaystyle \operatorname {perm} (A)=\sum _{\sigma \in \operatorname {P} (n,m)}a_{1\sigma (1)}a_{2\sigma (2)}\ldots a_{m\sigma (m)}}$$

El resultado computacional de Ryser para los permanentes también es generalizable. Si A es una matriz m  ×  n con m  ≤  n , sea obtenido a partir de A eliminando k columnas, sea el producto de las sumas de filas de , y sea la suma de los valores de sobre todos los posibles . Entonces ^[10] ${\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}^{m-1}(-1)^{k}{\binom {n-m+k}{k}}\sigma _{n-m+k}.}$$

Sistemas de representantes distintos

La generalización de la definición de permanente a matrices no cuadradas permite utilizar el concepto de forma más natural en algunas aplicaciones. Por ejemplo:

Sean S ₁ , S ₂ , ..., S _m subconjuntos (no necesariamente distintos) de un conjunto n con m  ≤  n . La matriz de incidencia de esta colección de subconjuntos es una matriz m  ×  n (0,1) A . El número de sistemas de representantes distintos (SDR) de esta colección es perm( A ). ^[32]

Véase también

• Calculando el permanente
• Teorema de Bapat-Beg , una aplicación de los permanentes en las estadísticas de orden
• Determinante de Slater , una aplicación de los permanentes en la mecánica cuántica
• Hafniano

Notas

1. Marcus, Marvin ; Minc, Henryk (1965). "Permanentes". Amer. Math. Monthly . 72 (6): 577–591. doi :10.2307/2313846. JSTOR  2313846.
2. Minc (1978)
3. Muir y Metzler (1960)
4. Cauchy, AL (1815), "Mémoire sur les fonctions qui ne peuvent obtenir que deux valeurs égales et de signes contraires par suite des transpositions opérées entre les variables qu'elles renferment.", Journal de l'École Polytechnique , 10 : 91 –169
5. Muir y Metzler (1960)
6. van Lint y Wilson 2001, pág. 108
7. Ryser 1963, págs. 25-26
8. Percus 1971, pág. 2
9. Percus 1971, pág. 12
10. Ryser 1963, pág. 26
11. Aaronson, Scott (14 de noviembre de 2010). "La complejidad computacional de la óptica lineal". arXiv : 1011.3245 [quant-ph].
12. Bhatia, Rajendra (1997). Análisis de matrices . Nueva York: Springer-Verlag. Págs. 16-19. ISBN. 978-0-387-94846-1.
13. Ryser 1963, pág. 124
14. Ryser 1963, pág. 125
15. Minc, Henryk (1963), "Límites superiores para permanentes de matrices (0,1)", Boletín de la Sociedad Matemática Americana , 69 (6): 789–791, doi : 10.1090/s0002-9904-1963-11031-9
16. van Lint y Wilson 2001, pág. 101
17. van der Waerden, BL (1926), "Aufgabe 45", Jber. Alemán. Matemáticas.-Verein. , 35 : 117.
18. Gyires, B. (2022), "La fuente común de varias desigualdades relativas a matrices doblemente estocásticas", Publicationes Mathematicae Institutum Mathematicum Universitatis Debreceniensis , 27 (3–4): 291–304, doi : 10.5486/PMD.1980.27.3- 4.15 , SEÑOR  0604006.
19. Egoryčev, GP (1980), Reshenie problemy van-der-Vardena dlya permanentev (en ruso), Krasnoyarsk: Akad. Nauk SSSR Sibirsk. Otdel. Inst. Fiz., pág. 12, SEÑOR  0602332. Egorychev, GP (1981), "Prueba de la conjetura de van der Waerden para permanentes", Akademiya Nauk SSSR (en ruso), 22 (6): 65–71, 225, MR  0638007Egorychev , GP (1981), "La solución del problema de van der Waerden para permanentes", Advances in Mathematics , 42 (3): 299–305, doi : 10.1016/0001-8708(81)90044-X , MR  0642395.
20. Falikman, DI (1981), "Prueba de la conjetura de van der Waerden sobre la permanente de una matriz doblemente estocástica", Akademiya Nauk Soyuza SSR (en ruso), 29 (6): 931–938, 957, MR  0625097.
21. Brualdi (2006) pág. 487
22. Premio Fulkerson, Mathematical Optimization Society, consultado el 19 de agosto de 2012.
23. Ryser (1963, pág. 27)
24. van Lint y Wilson (2001) pág. 99
25. Jerrum, M. ; Sinclair, A. ; Vigoda, E. (2004), "Un algoritmo de aproximación en tiempo polinomial para la permanente de una matriz con entradas no negativas", Journal of the ACM , 51 (4): 671–697, CiteSeerX 10.1.1.18.9466 , doi :10.1145/1008731.1008738, S2CID  47361920 
26. Meiburg, Alexander (2023). "Inaproximabilidad de permanentes semidefinidos positivos y tomografía de estados cuánticos". Algorithmica . 85 (12): 3828–3854. arXiv : 2111.03142 . doi : 10.1007/s00453-023-01169-1 .
27. Chakhmakhchyan, Levon; Cerf, Nicolas; Garcia-Patron, Raul (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.
28. Percus 1971, pág. 14
29. Percus 1971, pág. 17
30. En particular, Minc (1978) y Ryser (1963) hacen esto.
31. Ryser 1963, pág. 25
32. Ryser 1963, pág. 54

Referencias

• Brualdi, Richard A. (2006). Clases de matrices combinatorias . Enciclopedia de matemáticas y sus aplicaciones. Vol. 108. Cambridge: Cambridge University Press . ISBN 978-0-521-86565-4.Zbl 1106.05001  .
• Minc, Henryk (1978). Permanentes . Enciclopedia de matemáticas y sus aplicaciones. Vol. 6. Con prólogo de Marvin Marcus. Reading, MA: Addison–Wesley. ISSN  0953-4806. OCLC  3980645. Zbl  0401.15005.
• Muir, Thomas; Metzler, William H. (1960) [1882]. Tratado sobre la teoría de los determinantes . Nueva York: Dover. OCLC  535903.
• Percus, JK (1971), Métodos combinatorios , Applied Mathematical Sciences #4, Nueva York: Springer-Verlag, ISBN 978-0-387-90027-8
• Ryser, Herbert John (1963), Matemáticas combinatorias , The Carus Mathematical Monographs #14, The Mathematical Association of America
• van Lint, JH; Wilson, RM (2001), Un curso de combinatoria , Cambridge University Press, ISBN 978-0521422604

Lectura adicional

• Hall Jr., Marshall (1986), Combinatorial Theory (2.ª ed.), Nueva York: John Wiley & Sons, págs. 56-72, ISBN 978-0-471-09138-7Contiene una prueba de la conjetura de Van der Waerden.
• Marcus, M.; Minc, H. (1965), "Permanentes", The American Mathematical Monthly , 72 (6): 577–591, doi :10.2307/2313846, JSTOR  2313846

Enlaces externos

• Permanente en PlanetMath .
• La conjetura permanente de Van der Waerden en PlanetMath .