En álgebra lineal , el 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- 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, sobre todas las permutaciones de los números 1, 2, ..., n .
Por ejemplo,
y
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.
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 el permanente de matrices rectangulares, y per ( A ) cuando A es una matriz cuadrada. [2] Muir y Metzler usan la notación. [3]
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 y aplicaciones
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 cuadradade orden n : [7]
- 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 ,
- multiplicar cualquier fila o columna de A por un escalar s cambia la 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]
donde s y t son subconjuntos del mismo tamaño de {1,2, ..., n } y son sus respectivos complementos en ese conjunto.
Por otro lado, la propiedad multiplicativa básica de los determinantes no es válida para los permanentes. [9] Un ejemplo sencillo muestra que esto es así.
Una fórmula similar a la de Laplace para el desarrollo de un determinante a lo largo de una fila, columna o diagonal también es válida para el permanente; [10] todos los signos deben ignorarse para el permanente. Por ejemplo, expandiendo a lo largo de la primera columna,
mientras se expande a lo largo de la última fila da,
Si es una matriz triangular , es decir, cuando sea o, alternativamente, siempre que , entonces su permanente (y determinante también) es igual al producto de las entradas diagonales:
A diferencia del determinante, lo permanente no tiene una interpretación geométrica fácil; se utiliza principalmente en combinatoria , en el tratamiento de las funciones del bosón 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 gráficos : como la suma de pesos de las cubiertas de ciclo de un gráfico dirigido , y como la suma de pesos de emparejamientos perfectos en un gráfico bipartito .
Tensores simétricos
Lo permanente surge naturalmente en el estudio del poder tensorial simétrico de los espacios de Hilbert . [12] En particular, para un espacio de Hilbert, dejar denotar el a potencia tensorial simétrica de , que es el espacio de tensores simétricos . Tenga en cuenta en particular quese extiende por los productos simétricos de elementos en. Para, definimos el producto simétrico de estos elementos por
Si consideramos (como un subespacio de , el k- ésimo poder tensorial de) y definir el producto interior en en consecuencia, encontramos que para
Aplicando la desigualdad de Cauchy-Schwarz , encontramos que, y eso
Cubiertas de ciclo
Cualquier matriz cuadrada puede verse como la matriz de adyacencia de un gráfico dirigido ponderado, conque 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 disjuntos de vértice 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 cubierta del ciclo, y es una permutación dedonde n es el número de vértices en el dígrafo. Por el contrario, cualquier permutación en corresponde a una cubierta de ciclo en la que hay un arco desde el vértice i al vérticepara cada i .
Si el peso de una cubierta de ciclo se define como el producto de los pesos de los arcos en cada ciclo, entonces
El permanente de un la matriz A se define como
dónde es una permutación sobre . Por tanto, el permanente de A es igual a la suma de los pesos de todas las cubiertas de ciclo del dígrafo.
Combinaciones perfectas
Una matriz cuadrada también se puede ver como la matriz de adyacencia de un gráfico bipartito que tiene vértices por un lado y en el otro lado, con que representa el peso del borde del vértice al vértice . Si el peso de una combinación perfecta eso combina a se define como el producto de los pesos de los bordes en la coincidencia, entonces
Por tanto, el permanente de A es igual a la suma de los pesos de todas las coincidencias perfectas del gráfico.
Permanentes de (0, 1) matrices
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 cada suma de filas y columnas 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 2 + n + 1, n + 1) para n un entero> 1. Los permanentes correspondientes a los planos proyectivos más pequeños se han calculado. 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, la ondulación permanente ( Z ) = 24 = | det ( Z ) |, el valor absoluto del determinante de Z . Esto es una consecuencia de que Z es una matriz circulante y el teorema: [14]
- Si A es una matriz circulante en 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 usar para calcular el número de permutaciones con posiciones restringidas (prohibidas). Para el n -set estándar {1, 2, ..., n }, dejesea la matriz (0, 1) donde a ij = 1 si i → j está permitido 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. [10] Dos casos especiales bien conocidos de esto son la solución del problema del trastorno y el problema del ménage : el número de permutaciones de un conjunto n sin puntos fijos (trastornos) viene dado por
donde J es la matriz de n × n todos 1 e I es la matriz de identidad, y los números de ménage están dados por
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 probada por LM Brégman en 1973, [16] da un límite 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
La conjetura de Van der Waerden
En 1926, Van der Waerden conjeturó que el mínimo permanente entre todas las n × n matrices doble estocásticas es n ! / 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 demostración de Egorychev es una aplicación de la desigualdad Alexandrov-Fenchel . [21] Por este trabajo, Egorychev y Falikman ganaron el Premio Fulkerson en 1982. [22]
Cálculo
El enfoque ingenuo, usando la definición, de computar 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:ser 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:
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 se puede calcular en tiempo polinomial por cualquier método, entonces FP = #P , que es una declaración aún más fuerte que P = NP . Sin embargo, cuando las entradas de A no son negativas, la permanente se puede calcular aproximadamente en tiempo polinomial probabilístico , hasta un error de, dónde es el valor de lo permanente y es arbitrario. [25] La permanente de un cierto conjunto de matrices semidefinidas positivas también se puede aproximar en tiempo polinomial probabilístico: el mejor error alcanzable de esta aproximación es (es de nuevo el valor del permanente). [26]
Teorema maestro de MacMahon
Otra forma de ver los permanentes es a través de funciones generadoras multivariadas . Dejarser una matriz cuadrada de orden n . Considere la función generadora multivariante:
El coeficiente de en es permanente ( A ). [27]
Como generalización, para cualquier secuencia de n números enteros no negativos, definir:
- como el coeficiente de en
El teorema maestro de MacMahon que relaciona permanentes y determinantes es: [28]
donde I es la matriz identidad de orden n y X es la matriz diagonal con diagonal
Permanentes de matrices rectangulares
La función permanente se puede generalizar para aplicar 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. [29] Específicamente, para una matriz m × ncon m ≤ n , defina
donde P ( n , m ) es el conjunto de todas las m -permutaciones del n -conjunto {1,2, ..., n}. [30]
El resultado computacional de Ryser para permanentes también se generaliza. Si A es una matriz m × n con m ≤ n , 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
- [9]
Sistemas de representantes distintos
La generalización de la definición de matrices permanentes a no cuadradas permite utilizar el concepto de una manera más natural en algunas aplicaciones. Por ejemplo:
Sean S 1 , S 2 , ..., S m subconjuntos (no necesariamente distintos) de un n -conjunto con m ≤ n . La matriz de incidencia de esta colección de subconjuntos es un m × n (0,1) -matrix A . El número de sistemas de representantes distintos (DEG) de esta colección es permanente ( A ). [31]
Ver también
- Computando lo permanente
- Teorema de Bapat-Beg , una aplicación de permanentes en estadísticas de orden
- Determinante Slater , una aplicación de permanentes en mecánica cuántica
Notas
- ^ Marcus, Marvin; Minc, Henryk (1965). "Permanentes" . Amer. Matemáticas. Mensual . 72 (6): 577–591. doi : 10.2307 / 2313846 . JSTOR 2313846 .
- ↑ Minc (1978)
- ^ Muir y Metzler (1960)
- ^ 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
- ^ Muir y Metzler (1960)
- ↑ van Lint y Wilson , 2001 , p. 108
- ^ Ryser 1963 , págs. 25-26
- ^ Percus 1971 , p. 2
- ↑ a b Ryser , 1963 , p. 26
- ↑ a b Percus , 1971 , p. 12
- ^ Aaronson, Scott (14 de noviembre de 2010). "La complejidad computacional de la óptica lineal". arXiv : 1011,3245 [ quant-ph ].
- ^ Bhatia, Rajendra (1997). Análisis matricial . Nueva York: Springer-Verlag. págs. 16-19. ISBN 978-0-387-94846-1.
- ↑ a b Ryser , 1963 , p. 124
- ↑ Ryser , 1963 , p. 125
- ^ Minc, Henryk (1963), "Límites superiores para permanentes de (0,1) -matrices", Boletín de la American Mathematical Society , 69 (6): 789–791, doi : 10.1090 / s0002-9904-1963-11031- 9
- ↑ van Lint y Wilson , 2001 , p. 101
- ^ van der Waerden, BL (1926), "Aufgabe 45", Jber. Alemán. Math.-Verein. , 35 : 117.
- ^ Gyires, B. (1980), "La fuente común de varias desigualdades relativas a matrices doblemente estocásticas", Publicationes Mathematicae Institutum Mathematicum Universitatis Debreceniensis , 27 (3-4): 291-304, MR 0604006.
- ^ Egoryčev, GP (1980), Reshenie problemy van-der-Vardena dlya permanentov (en ruso), Krasnoyarsk: Akad. Nauk SSSR Sibirsk. Otdel. Inst. Fiz., Pág. 12, MR 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", Advances in Mathematics , 42 (3): 299-305, doi : 10.1016 / 0001-8708 (81) 90044-X , MR 0642395.
- ^ 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.
- ^ Brualdi (2006) p.487
- ^ Premio Fulkerson , Sociedad de optimización matemática, consultado el 19 de agosto de 2012 .
- ↑ Ryser (1963 , p. 27)
- ^ van Lint y Wilson (2001) p. 99
- ^ 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
- ^ 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 .
- ^ Percus 1971 , p. 14
- ^ Percus 1971 , p. 17
- ^ En particular, Minc (1978) y Ryser (1963) hacen esto.
- ↑ Ryser , 1963 , p. 25
- ↑ Ryser , 1963 , p. 54
Referencias
- Brualdi, Richard A. (2006). Clases de matrices combinatorias . Enciclopedia de las matemáticas y sus aplicaciones. 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. 6 . Con un prólogo de Marvin Marcus. Reading, MA: Addison – Wesley. ISSN 0953-4806 . OCLC 3980645 . Zbl 0401.15005 .
- Muir, Thomas; Metzler, William H. (1960) [1882]. Un 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), Combinatorial Theory (2ª ed.), Nueva York: John Wiley & Sons, págs. 56–72, ISBN 978-0-471-09138-7 Contiene una prueba de la conjetura de Van der Waerden.
- Marcus, M .; Minc, H. (1965), "Permanents", 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 .