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 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 $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 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(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 una matriz triangular, es decir, $a_{ij}=0$, siempre que $i>j$ o, alternativamente, cuando sea $i<j$, entonces su permanente (y su 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

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.​ Por ejemplo, expandiendo 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 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.​ 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

Tensores simétricos

El permanente surge naturalmente en el estudio de la potencia tensorial simétrica en un 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 tensores simétricos. Nótese en particular que $\vee ^{k}H$ es abarcado por los productos simétricos de elementos en $H$. Para $x_{1},x_{2},\dots ,x_{k}\in H$, se define 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 se considera $\vee ^{k}H$ (como un subespacio de $\otimes ^{k}H$, la k-ésima potencia tensorial de $H$) y se define el producto interno en $\vee ^{k}H$ en consecuencia, se encuentra 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 la desigualdad de Cauchy-Bunyakovsky-Schwarz, se obtiene 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}$$

Recubrimiento de ciclos de vértices de un grafo

Cualquier matriz cuadrada $A=(a_{ij})_{i,j=1}^{n}$ puede verse como la 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 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" $\sigma (i)$ en el recubrimiento del ciclo, por lo que $\sigma$ representa una permutación en V. Por el contrario, cualquier permutación $\sigma$ en V corresponde a un recubrimiento de un ciclo con vínculos desde cada vértice i hasta el vértice $\sigma (i)$.

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

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

lo que implica que

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

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

Combinaciones perfectas

Una matriz cuadrada $A=(a_{ij})$ también se puede ver como la matriz de adyacencia de un grafo bipartito que tiene vértices $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 emparejamiento perfecto $\sigma$ que hace coincidir $x_{i}$ con $y_{\sigma (i)}$ se define como el producto de los pesos de los vínculos de la coincidencia, entonces

$\operatorname {peso} (\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 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 cada suma de filas y columnas igual a k. Cada matriz A en esta clase tiene perm(A) > 0.​ 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.​ 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:​

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 permutaciones con posiciones restringidas (prohibidas). Para el conjunto estándar n {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 problema del menaje: el número de permutaciones de un conjunto n sin puntos fijos (restricciones) 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 números de menaje 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

La desigualdad de Bregman-Minc, conjeturada por H. Minc en 1963​ y demostrada 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 todas las matrices doblemente estocásticas de orden n × n es n!/nⁿ, correspondiente a la matriz para la que 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 la desigualdad de Alexandrov-Fenchel.​ 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.​ El método de Ryser se basa en una fórmula de inclusión-exclusión que se puede dar​ de la siguiente manera: Sea $A_{k}$ de A eliminando k columnas, 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}^{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 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 $\varepsilon M$, donde $M$ es el valor del permanente y $\varepsilon >0$ es arbitrario.​ 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 $\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 una función generadora multivariable. Sea $A=(a_{ij})$ una matriz cuadrada de orden n. Considérese 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 $A=(a_{ij})$ de orden m × n con m ≤ n, se define

$\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 de orden m ×n con m ≤ n, obténgase $A_{k}$ de A eliminando k columnas, 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. 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).​

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 (1ª Ed. 1882)). 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