Permanente (matemáticas)

polinomio de los elementos de una matriz

En álgebra lineal, el permanente de un matriz cuadrada es una función de la matriz similar al determinante. El permanente, así como el determinante, es el resultado de un polinomio que se calcula a partir de los valores de la matriz.[1]​ Ambos son casos especiales de una función más general de una matriz llamada inmanente.

Definición

editar

El permanente de una matriz n×n A= (ai,j) se define como

 

La suma aquí se extiende sobre todos los elementos σ del grupo simétrico Sn; 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 signaturas 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 "funciones simétricas permanentes" para un tipo relacionado de función,[4]​ y fue utilizada por Muir y Metzler[3]​ en el sentido moderno y más específico.[5]

Propiedades

editar

Si se considera el permanente como una aplicación que toma n vectores como argumentos, entonces es una aplicación 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:[6]

  • perm(A) es invariable 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 permutación P y Q del tamaño apropiado,
  • multiplicar cualquier fila o columna de A por un escalar s cambia perm(A) a s⋅perm(A),
  • perm(A) es invariable bajo la transposición, es decir, perm(A) = perm(AT).
  • Si   y   son matrices cuadradas de orden n, entonces[7]
 
donde s y t son subconjuntos del mismo tamaño de {1,2,...,n} y   son sus respectivos complementos en ese conjunto.
  • Si   es una matriz triangular, es decir,  , siempre que   o, alternativamente, cuando sea  , entonces su permanente (y su determinante también) es igual al producto de las entradas diagonales:
 

Relación con los determinantes

editar

El teorema de Laplace que implica la expansión en menores asociados para calcular el determinante en una fila, columna o diagonal se extiende al permanente ignorando todos los signos.[8]​ Por ejemplo, expandiendo la primera columna,

 

mientras que la expansión en la última fila da,

 

Por otro lado, la propiedad multiplicativa básica de los determinantes no es válida para los permanentes.[9]​ Un ejemplo simple muestra que esto es así.

 

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

Aplicaciones

editar

Tensores simétricos

editar

El permanente surge naturalmente en el estudio de la potencia tensorial simétrica en un espacio de Hilbert.[11]​ En particular, para un espacio de Hilbert  , sea   la potencia tensorial simétrica   de  , que es el espacio de tensores simétricos. Nótese en particular que   es abarcado por los productos simétricos de elementos en  . Para  , se define el producto simétrico de estos elementos por

     

Si se considera   (como un subespacio de  , la k-ésima potencia tensorial de  ) y se define el producto interno en   en consecuencia, se encuentra que para  

     

Aplicando la desigualdad de Cauchy-Bunyakovsky-Schwarz, se obtiene que  , y que

     

Recubrimiento de ciclos de vértices de un grafo

editar

Cualquier matriz cuadrada   puede verse como la matriz de adyacencia de un grafo dirigido ponderado en el conjunto de vértices  , donde   representa el peso del vínculo desde el vértice i hasta el vértice j.

Un recubrimiento de ciclos de un grafo dirigido ponderado es una colección de ciclos directos disjuntos de vértice en el dígrafo que cubre todos los vértices del grafo. Por lo tanto, cada vértice i en el dígrafo tiene un único "sucesor"   en el recubrimiento del ciclo, por lo que   representa una permutación en V. Por el contrario, cualquier permutación   en V corresponde a un recubrimiento de un ciclo con vínculos desde cada vértice i hasta el vértice  .

Si el peso de un recubrimiento de ciclo se define como el producto de los pesos de los arcos en cada ciclo, entonces

 

lo que implica que

 

Así, el permanente de A es igual a la suma de los pesos de todos los recubrimientos de ciclo del dígrafo.

Combinaciones perfectas

editar

Una matriz cuadrada   también se puede ver como la matriz de adyacencia de un grafo bipartito que tiene vértices   en un lado y   en el otro lado, donde   representa el peso de la arista desde el vértice   hasta el vértice  . Si el peso de un emparejamiento perfecto   que hace coincidir   con   se define como el producto de los pesos de los vínculos de la coincidencia, entonces

 

Así, el permanente de A es igual a la suma de los pesos de todos los emparejamientos perfectos del gráfico.

Permanentes de matrices (0, 1)

editar

Enumeración

editar

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.[12]​ Las matrices de incidencia de los planos proyectivos están en la clase Ω(n2 + 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.[12]​ 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 el teorema:[13]

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 se puede poner en la forma de una suma directa de e copias de la matriz Z y, en consecuencia, n = 7e y perm(A) = 24e.

Los permanentes también se pueden usar para calcular el número de permutaciones con posiciones restringidas (prohibidas). Para el conjunto estándar n {1, 2, ..., n}, sea   la matriz (0, 1) donde aij= 1 si i  → j está permitido en una permutación y aij= 0 en caso contrario. Entonces perm(A) es igual al número de permutaciones del conjunto n que satisfacen todas las restricciones.[8]​ Dos casos especiales bien conocidos de esto son la solución del problema subfactorial y el problema del menaje: el número de permutaciones de un conjunto n sin puntos fijos (restricciones) está dado por

     

donde J es la matriz n×n de todos los 1 e I es la matriz identidad, y los números de menaje 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

editar

La desigualdad de Bregman-Minc, conjeturada por H. Minc en 1963[14]​ y demostrada por L. M. Brégman en 1973,[15]​ proporciona un límite superior para el permanente de una matriz n × n (0, 1). Si A tiene ri unidades en la fila i para cada 1 ≤ in, la desigualdad establece que

 

Conjetura de Van der Waerden

editar

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

Cálculo

editar

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 H. J. Ryser.[22]​ El método de Ryser se basa en una fórmula de inclusión-exclusión que se puede dar[23]​ de la siguiente manera: Sea   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

 

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 complejidad temporal por el procedimiento de eliminación de Gauss-Jordan, la eliminación gaussiana no se puede usar para calcular el permanente. Además, calcular el permanente de una matriz (0,1) es un problema #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, el permanente se puede calcular aproximadamente en tiempo polinomial mediante un algoritmo probabilistico, hasta un error de  , donde   es el valor del permanente y   es arbitrario.[24]​ El 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 nuevamente el valor del permanente).[25]

Teorema maestro de MacMahon

editar

Otra forma de ver los permanentes es a través de una función generadora multivariable. Sea   una matriz cuadrada de orden n. Considérese la función generadora multivariante:

 

El coeficiente de   en   es perm(A).[26]

Como generalización, para cualquier secuencia de n enteros no negativos,   define:

  como el coeficiente de  

en

 

El teorema maestro de MacMahon que relaciona permanentes y determinantes es:[27]

 

donde   es la matriz identidad de orden n y   es la matriz diagonal con diagonal  

Matrices rectangulares

editar

La función permanente se puede generalizar para aplicar a matrices no cuadradas. De hecho, varios autores hacen de esta la definición de un permanente y consideran la restricción a matrices cuadradas como un caso especial.[28]​ Específicamente, para una matriz   de orden m × n con m ≤ n, se define

 

donde P(n,m) es el conjunto de todas las permutaciones m del conjunto n {1,2,...,n}.[29]

El resultado computacional de Ryser para permanentes también se generaliza. Si A es una matriz de orden m ×n con m ≤ n, obténgase   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,[9]

 

Sistemas de representantes distintos

editar

La generalización de la definición de un permanente a matrices no cuadradas permite que el concepto se use de una manera más natural en algunas aplicaciones. Por ejemplo:

Sean S1, S2, ..., Sm subconjuntos (no necesariamente distintos) de un conjunto n con m ≤  n. La matriz de incidencia de esta colección de subconjuntos es una matriz A de orden m × n del tipo (0,1). El número de sistemas de distintos representantes (SDR) de esta colección es perm(A).[30]

Véase también

editar

Referencias

editar
  1. Marcus, Marvin; Minc, Henryk (1965). «Permanents». Amer. Math. Monthly 72 (6): 577-591. JSTOR 2313846. doi:10.2307/2313846. 
  2. Minc (1978)
  3. a b Muir y Metzler (1960)
  4. Cauchy, A. L. (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. van Lint y Wilson, 2001, p. 108
  6. Ryser, 1963, pp. 25 – 26
  7. Percus, 1971, p. 2
  8. a b Percus, 1971, p. 12
  9. a b Ryser, 1963, p. 26
  10. Aaronson, Scott (14 Nov 2010). «The Computational Complexity of Linear Optics». arXiv:1011.3245  [quant-ph]. 
  11. Bhatia, Rajendra (1997). Matrix Analysis. New York: Springer-Verlag. pp. 16-19. ISBN 978-0-387-94846-1. 
  12. a b Ryser, 1963, p. 124
  13. Ryser, 1963, p. 125
  14. Minc, Henryk (1963), «Upper bounds for permanents of (0,1)-matrices», Bulletin of the American Mathematical Society 69 (6): 789-791, doi:10.1090/s0002-9904-1963-11031-9 .
  15. van Lint y Wilson, 2001, p. 101
  16. van der Waerden, B. L. (1926), «Aufgabe 45», Jber. Deutsch. Math.-Verein. 35: 117 ..
  17. Gyires, B. (1980), «The common source of several inequalities concerning doubly stochastic matrices», Publicationes Mathematicae Institutum Mathematicum Universitatis Debreceniensis 27 (3–4): 291-304, MR 604006 ..
  18. Egoryčev, G. P. (1980), Reshenie problemy van-der-Vardena dlya permanentov (en ruso), Krasnoyarsk: Akad. Nauk SSSR Sibirsk. Otdel. Inst. Fiz., p. 12, MR 602332 .. Egorychev, G. P. (1981), «Proof of the van der Waerden conjecture for permanents», Akademiya Nauk SSSR (en ruso) 22 (6): 65-71, 225, MR 638007 .. Egorychev, G. P. (1981), «The solution of van der Waerden's problem for permanents», Advances in Mathematics 42 (3): 299-305, MR 642395, doi:10.1016/0001-8708(81)90044-X ..
  19. Falikman, D. I. (1981), «Proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix», Akademiya Nauk Soyuza SSR (en ruso) 29 (6): 931-938, 957, MR 625097 ..
  20. Brualdi (2006) p.487
  21. Fulkerson Prize, Mathematical Optimization Society, retrieved 2012-08-19.
  22. Ryser (1963, p. 27)
  23. van Lint y Wilson (2001) p. 99
  24. Jerrum, M.; Sinclair, A.; Vigoda, E. (2004), «A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries», Journal of the ACM 51 (4): 671-697, S2CID 47361920, doi:10.1145/1008731.1008738, «citeseerx: 10.1.1.18.9466» .
  25. Chakhmakhchyan, Levon; Cerf, Nicolas; Garcia-Patron, Raul (2017). «A quantum-inspired algorithm for estimating the permanent of positive semidefinite matrices». Phys. Rev. A 96 (2): 022329. Bibcode:2017PhRvA..96b2329C. S2CID 54194194. arXiv:1609.02416. doi:10.1103/PhysRevA.96.022329. 
  26. Percus, 1971, p. 14
  27. Percus, 1971, p. 17
  28. En particular,Minc (1978) y Ryser (1963) lo hacen.
  29. Ryser, 1963, p. 25
  30. Ryser, 1963, p. 54

Bibliografía

editar

Lecturas relacionadas

editar

Enlaces externos

editar