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 . El 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 inmanante .

Definición

El 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 se extiende aquí a 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 las firmas de las permutaciones no se tienen en cuenta.

El 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 utilizan la notación . ^[3] ${\displaystyle {\overset {+}{|}}\quad {\overset {+}{|}}}$

La palabra permanente se originó con Cauchy en 1812 como “fonctions symétriques 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 uno ve el permanente como un mapa que toma n vectores como argumentos, entonces es un mapa multilineal y es simétrico (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 se puede escribir simbólicamente como perm( A ) = perm( PAQ ) para cualquier matriz de permutación P y Q de tamaño apropiado ,
• multiplicar cualquier fila o columna de A por un escalar s cambia perm( A ) a 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] ${\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}}},}$$
  donde s y t son subconjuntos del mismo tamaño de {1,2,..., n } y son sus respectivos complementos en ese conjunto. ${\displaystyle {\bar {s}},{\bar {t}}}$
• Si es una matriz triangular , es decir , siempre o, alternativamente, siempre , entonces su permanente (y también determinante) 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 al ignorar 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 el 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, expandiéndose 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 que la expansión 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 otro lado, la propiedad multiplicativa básica de los determinantes no es válida para los permanentes. ^[10] Un ejemplo sencillo demuestra 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 del bosón de Green 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 teóricas de grafos : como la suma de pesos de coberturas de ciclo de un gráfico dirigido y como la suma de pesos de coincidencias perfectas en un gráfico bipartito .

Aplicaciones

Tensores simétricos

Lo 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 , denotemos la potencia tensor simétrica de , que es el espacio de tensores simétricos . Tenga en cuenta en particular que está abarcado por los productos simétricos de elementos en . Para , definimos el producto simétrico de estos elementos por ${\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)}}$$

kpotencia tensor ${\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}}$$

desigualdad de Cauchy-Schwarz ${\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 verse como la matriz de adyacencia de un gráfico dirigido ponderado en un conjunto de vértices , que representa el peso del arco desde el vértice i al vértice j . Una cobertura de ciclo de un gráfico dirigido ponderado es una colección de ciclos dirigidos separados por vértices en el dígrafo que cubre todos los vértices del gráfico. Por lo tanto, cada vértice i en el dígrafo tiene un "sucesor" único en la cobertura del 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 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 bicicleta se define como el producto de los pesos de los arcos en cada ciclo, entonces

$${\displaystyle \operatorname {weight} (\sigma )=\prod _{i=1}^{n}a_{i,\sigma (i)},}$$

$${\displaystyle \operatorname {perm} (A)=\sum _{\sigma }\operatorname {weight} (\sigma ).}$$

A

Combinaciones perfectas

Una matriz cuadrada también se puede ver como la matriz de adyacencia de un gráfico bipartito que tiene vértices en un lado y en el otro lado, representando el peso del borde de un vértice a otro . Si el peso de una coincidencia perfecta que coincide con se define como el producto de los pesos de los bordes en la coincidencia, entonces ${\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)}.}$$

A

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 matrices (0, 1) de orden n con la suma de cada fila y columna igual a k . Cada matriz A en esta clase tiene perm( A ) > 0. ^[13] Las matrices de incidencia de planos proyectivos están en la clase Ω( n ² + n + 1, n + 1) para n un entero > 1. Las permanentes correspondientes Se han calculado 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 . Sorprendentemente, 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, al permutar filas y columnas, A se puede poner 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 n -conjunto que satisfacen todas las restricciones. ^[9] Dos casos especiales bien conocidos de esto son la solución del problema del trastorno y del problema del ménage : el número de permutaciones de un n -conjunto sin puntos fijos (trastornos) viene 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!}},}$$

Jnn e Inúmeros del ménage

$${\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 un límite superior para el 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}}.}$$

La conjetura de Van der Waerden

En 1926, Van der Waerden conjeturó que el mínimo permanente entre todas las n × n matrices doblemente estocásticas 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 se puede dar ^[24] 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 más de 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:

$${\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. Si bien el determinante se puede calcular en tiempo polinómico mediante eliminación gaussiana , la eliminación gaussiana no se puede utilizar 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 polinómico mediante cualquier método, entonces FP  =  #P , que es una afirmación aún más sólida que P = NP . Sin embargo, cuando las entradas de A no son negativas, el permanente se puede calcular aproximadamente en tiempo polinomial probabilístico , hasta un error de , donde es el valor del permanente y es arbitrario. ^[25] El permanente de un cierto conjunto de matrices semidefinidas positivas es NP-difícil de aproximar dentro de cualquier factor subexponencial. ^[26] Si se imponen más condiciones en el espectro , el permanente se puede aproximar en tiempo polinómico probabilístico: el mejor error alcanzable de esta aproximación es ( es nuevamente el valor del permanente). ^[27] La ​​dureza 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}$

El teorema maestro de MacMahon

Otra forma de ver los permanentes es mediante funciones generadoras multivariadas . Sea una matriz cuadrada de orden n . Considere la función generadora multivariada: ${\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}}}$$

A^[28] ${\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 enteros no negativos, defina: ${\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]

$${\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)}},}$$

InX ${\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 esta la definición de permanente y consideran la restricción a matrices cuadradas como un caso especial. ^[30] Específicamente, para una matriz m  ×  n con m  ≤  n , defina ${\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)}}$$

nmlas mn^[31]

El resultado computacional de Ryser para permanentes también se generaliza. Si A es una matriz de m  ×  n con m  ≤  n , se obtendrá de A eliminando k columnas, será el producto de las sumas de filas de y será 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 distintos representantes.

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 n -conjunto con m  ≤  n . La matriz de incidencia de esta colección de subconjuntos es una matriz A m  ×  n (0,1) . El número de sistemas de representantes distintos (DEG) de esta colección es permanente ( A ). ^[32]

Ver también

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

Notas

1. Marco, Marvin ; Minc, Henryk (1965). "Permanentes". América. Matemáticas. Mensual . 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, pag. 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 [cuántico-ph].
12. Bhatia, Rajendra (1997). Análisis matricial . Nueva York: Springer-Verlag. págs. 16-19. ISBN 978-0-387-94846-1.
13. Ryser 1963, pág. 124
14. Ryser 1963, pag. 125
15. Minc, Henryk (1963), "Límites superiores para permanentes de (0,1) -matrices", Boletín de la Sociedad Matemática Estadounidense , 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 permanenteov (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  0638007. Egorychev, GP (1981), "La solución del problema de van der Waerden para permanentes", Avances en Matemáticas , 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 el permanente de una matriz doblemente estocástica", Akademiya Nauk Soyuza SSR (en ruso), 29 (6): 931–938, 957, MR  0625097.
21. Brualdi (2006) p.487
22. Premio Fulkerson, Sociedad de Optimización Matemática, 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 de tiempo polinómico para el 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, Alejandro (2023). "Inaproximabilidad de permanentes semidefinidos positivos y tomografía de estado cuántico". Algorítmica . 85 (12): 3828–3854. arXiv : 2111.03142 . doi : 10.1007/s00453-023-01169-1 .
27. 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". Física. Rev. A. 96 (2): 022329. arXiv : 1609.02416 . Código Bib : 2017PhRvA..96b2329C. doi : 10.1103/PhysRevA.96.022329. S2CID  54194194.
28. Percus 1971, pag. 14
29. Percus 1971, pag. 17
30. En particular, Minc (1978) y Ryser (1963) hacen esto.
31. Ryser 1963, pag. 25
32. Ryser 1963, pag. 54

Referencias

• Brualdi, Richard A. (2006). Clases de matrices combinatorias . Enciclopedia de Matemáticas y sus aplicaciones. vol. 108. Cambridge: Prensa de la Universidad de Cambridge . 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. Lectura, 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 , Ciencias Matemáticas Aplicadas #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

Otras lecturas

• Hall Jr., Marshall (1986), Teoría combinatoria (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.
• Marco, 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 .