Permanente (matemáticas)

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.​ Ambos son casos especiales de una función más general de una matriz llamada inmanente.

Definición

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

$$\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,

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

y

$$\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 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.​ Muir y Metzler usan la notación ${\overset {+}{|}}\quad {\overset {+}{|}}$.​

La palabra permanente se originó con Cauchy en 1812 como "funciones simétricas permanentes" para un tipo relacionado de función,​ y fue utilizada por Muir y Metzler​ en el sentido moderno y más específico.​

Propiedades

Si uno ve el permanente como un mapa que toma "n" vectores como argumentos, entonces es un multilinear map 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 $A=\left(a_{ij}\right)$ de orden n:​

• 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 permutation matrices P y Q del tamaño apropiado,
• multiplicar cualquier fila o columna de A por scalar s cambia perm(A) a s⋅perm(A),
• perm(A) es invariable bajo transposition, es decir, perm(A) = perm(A^T).
• Si $A=\left(a_{ij}\right)$ y $B=\left(b_{ij}\right)$ son matrices cuadradas de orden n entonces,​
  $$\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 ${\bar {s}},{\bar {t}}$ son sus respectivos complementos en ese conjunto.
• Si $A$ es un matriz triangular, es decir, $a_{ij}=0$, siempre que $i>j$ o, alternativamente, cuando sea $i<j$, entonces su permanente (y determinante también) es igual al producto de las entradas diagonales:
  $$\operatorname {perm} \left(A\right)=a_{11}a_{22}\cdots a_{nn}=\prod _{i=1}^{n}a_{ii}.$$

Relación con los determinantes

teorema de Laplace de Laplace para calcular el determinante en una fila, columna o diagonal se extiende al permanente ignorando todos los signos.​ Por ejemplo, expandiendo en la primera columna,

$${\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 en la última fila da,

$${\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.​ Un ejemplo simple muestra que esto es así.

$${\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 del bosón Green's functions en teoría cuántica de campos y en la determinación de las probabilidades de estado de los sistemas boson sampling.​ Sin embargo, tiene dos interpretaciones de teoría de grafos: como la suma de los pesos de los cycle cover de un grafo dirigido y como la suma de los pesos de las coincidencias perfectas en un grafo bipartito.

Aplicaciones

Tensores simétricos

El permanente surge naturalmente en el estudio de la potencia tensorial simétrica de Espacio de Hilbert.​ En particular, para un espacio de Hilbert $H$, sea $\vee ^{k}H$ la potencia tensorial simétrica $k$ de $H$, que es el espacio de symmetric tensors. Nótese en particular que $\vee ^{k}H$ está atravesado por symmetric products de elementos en $H$. Para $x_{1},x_{2},\dots ,x_{k}\in H$, definimos el producto simétrico de estos elementos por

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

Si consideramos $\vee ^{k}H$ (como un subespacio de $\otimes ^{k}H$, el k-ésimo tensor power de $H$) y definimos el producto interno en $\vee ^{k}H$ en consecuencia, encontramos que para $x_{j},y_{j}\in H$

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

Aplicando Desigualdad de Cauchy-Bunyakovsky-Schwarz, encontramos que $\operatorname {perm} \left[\langle x_{i},x_{j}\rangle \right]_{i,j=1}^{k}\geq 0$, y que

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

Cubrebicicletas

Cualquier matriz cuadrada $A=(a_{ij})_{i,j=1}^{n}$ puede verse como el matriz de adyacencia de un grafo dirigido ponderado en el conjunto de vértices $V=\{1,2,\dots ,n\}$, donde $a_{ij}$ representa el peso del arco desde el vértice i hasta el vértice j. Un cycle cover de un grafo dirigido ponderado es una colección de directed cycle 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" $\sigma (i)$ en la cubierta del ciclo, por lo que $\sigma$ representa un permutación en V. Por el contrario, cualquier permutación $\sigma$ en V corresponde a una cubierta de ciclo con arcos desde cada vértice i hasta el vértice $\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

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

lo que implica que

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

Así, 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 $A=(a_{ij})$ también se puede ver como el matriz de adyacencia de un grafo bipartito que tiene vertices $x_{1},x_{2},\dots ,x_{n}$ en un lado y $y_{1},y_{2},\dots ,y_{n}$ en el otro lado, donde $a_{ij}$ representa el peso de la arista desde el vértice $x_{i}$ hasta el vértice $y_{j}$. Si el peso de un perfect matching $\sigma$ que hace coincidir $x_{i}$ con $y_{\sigma (i)}$ se define como el producto de los pesos de los bordes en la coincidencia, entonces

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

Así, el permanente de A es igual a la suma de los pesos de todos los emparejamientos perfectos 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.​ Las matrices de incidencia de plano 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.​ Sea Z la matriz de incidencia del plano proyectivo con n= 2, la Plano de Fano. Sorprendentemente, perm(Z)= 24=|det (Z)|, el valor absoluto del determinante de Z. Esto es una consecuencia de que Z sea un circulant matrix y el teorema:​

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) = 24^e.

Los permanentes también se pueden usar para calcular el número de permutación con posiciones restringidas (prohibidas). Para el conjunto n estándar {1, 2, ..., n}, sea $A=(a_{ij})$ 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.​ Dos casos especiales bien conocidos de esto son la solución del problema subfactorial y el ménage problem: el número de permutaciones de un conjunto n sin puntos fijos (trastornos) está dado por

$$\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 ménage number están dados por

$${\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

El Bregman–Minc inequality, conjeturado por H. Minc en 1963​ y probado por L. M. Brégman en 1973,​ proporciona un límite superior para el permanente de una matriz n × n (0, 1). Si "A" tiene

r_i unidades en la fila i para cada 1 ≤ i ≤ n, la desigualdad establece que

$$\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 todos los n × n doubly stochastic matrices es n!/nⁿ, logrado por la matriz para la cual todas las entradas son iguales a 1/n.​ Las pruebas de esta conjetura fueron publicadas en 1980 por B. Gyires​ y en 1981 por G. P. Egorychev​ y D. I. Falikman;​ La prueba de Egorychev es una aplicación de Alexandrov–Fenchel inequality.​ Por este trabajo, Egorychev y Falikman ganaron el Premio Fulkerson en 1982.​

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 H. J. Ryser.​ Ryser's method se basa en una fórmula inclusion–exclusion que se puede dar​ de la siguiente manera: Sea $A_{k}$ de A eliminando las columnas k, sea $P(A_{k})$ el producto de las sumas de filas de $A_{k}$ y sea $\Sigma _{k}$ sea ​​la suma de los valores de $P(A_{k})$ sobre todos los $A_{k}$ posibles. Después

$$\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:

$$\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 complejidad temporal por 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 #P-complete. 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 approximately en tiempo polinomial probabilistic, hasta un error de $\varepsilon M$, donde $M$ es el valor del permanente y $\varepsilon >0$ es arbitrario.​ El permanente de un cierto conjunto de positive semidefinite matrices también se puede aproximar en tiempo polinomial probabilístico: el mejor error alcanzable de esta aproximación es $\varepsilon {\sqrt {M}}$ ($M$ es nuevamente el valor del permanente).​

Teorema maestro de MacMahon

Otra forma de ver los permanentes es a través de función generadora multivariados. Sea $A=(a_{ij})$ una matriz cuadrada de orden n. Considere la función generadora multivariante:

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

El coeficiente de $x_{1}x_{2}\dots x_{n}$ en $F(x_{1},x_{2},\dots ,x_{n})$ es perm(A).​

Como generalización, para cualquier secuencia de "n" enteros no negativos, $s_{1},s_{2},\dots ,s_{n}$ define:

$$\operatorname {perm} ^{(s_{1},s_{2},\dots ,s_{n})}(A)$$

como el coeficiente de $x_{1}^{s_{1}}x_{2}^{s_{2}}\cdots x_{n}^{s_{n}}$ en $\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:​

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

donde I es la matriz identidad de orden n y X es la matriz diagonal con diagonal $[x_{1},x_{2},\dots ,x_{n}].$

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 un permanente y consideran la restricción a matrices cuadradas como un caso especial.​ Específicamente, para una matriz m × n $A=(a_{ij})$ con m ≤ n, defina

$$\operatorname {perm} (A)=\sum _{\sigma \in \operatorname {P} (n,m)}a_{1\sigma (1)}a_{2\sigma (2)}\ldots a_{m\sigma (m)}$$

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

El resultado computacional de Ryser para permanentes también se generaliza. Si A es una matriz m ×n con m ≤ n, obtenga $A_{k}$ de A' ' eliminando columnas k, sea $P(A_{k})$ el producto de las sumas de filas de $A_{k}$, y sea $\sigma _{k}$ la suma de los valores de $P(A_{k})$ sobre todos los $A_{k}$ posibles. Entonces​

$$\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 un permanente a matrices no cuadradas permite que el concepto se use de una manera más natural en algunas aplicaciones. Por ejemplo:

Sean S₁, S₂, ..., S_m subconjuntos (no necesariamente distintos) de un conjunto n con m ≤  n. El matriz de incidencia de esta colección de subconjuntos es una matriz m × n (0,1) A. El número de systems of distinct representatives (SDR) de esta colección es perm(A).​

Véase también

• Cálculo del permanente
• Teorema Bapat-Beg, una aplicación de permanentes en estadísticos de orden
• Determinante de Slater, una aplicación de permanentes en mecánica cuántica
• Hafniano

Bibliografía

• Brualdi, Richard A. (2006). Combinatorial matrix classes. Encyclopedia of Mathematics and Its Applications 108. Cambridge: Cambridge University Press. ISBN 978-0-521-86565-4. Zbl 1106.05001. 
• Minc, Henryk (1978). Permanents. Encyclopedia of Mathematics and its Applications 6. With a foreword by Marvin Marcus. Reading, MA: Addison–Wesley. ISSN 0953-4806. OCLC 3980645. Zbl 0401.15005. 
• Muir, Thomas; Metzler, William H. (1960). A Treatise on the Theory of Determinants. New York: Dover. OCLC 535903. 
• Percus, J.K. (1971), Combinatorial Methods, Applied Mathematical Sciences #4, New York: Springer-Verlag, ISBN 978-0-387-90027-8 .
• Ryser, Herbert John (1963), Combinatorial Mathematics, The Carus Mathematical Monographs #14, The Mathematical Association of America .
• van Lint, J.H.; Wilson, R.M. (2001), A Course in Combinatorics, Cambridge University Press, ISBN 978-0521422604 .

Lecturas relacionadas

• Hall Jr., Marshall (1986), Combinatorial Theory (2nd edición), New York: John Wiley & Sons, pp. 56–72, ISBN 978-0-471-09138-7 . Contains a proof of the Van der Waerden conjecture.
• Marcus, M.; Minc, H. (1965), «Permanents», The American Mathematical Monthly 72 (6): 577–591, JSTOR 2313846, doi:10.2307/2313846 .

Enlaces externos

• Permanent en PlanetMath.
• Van der Waerden's permanent conjecture en PlanetMath.

• Datos: Q1344007