Permanente

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 24 de mayo de 2020; las comprobaciones requieren 2 ediciones .

Un permanente en matemáticas es una función numérica definida sobre el conjunto de todas las matrices ; para matrices cuadradas es similar al determinante , y se diferencia de él solo en que en la expansión en permutaciones (o en menores ), no se toman signos alternos, sino todos los más. A diferencia del determinante, la definición de permanente también se extiende a matrices no cuadradas.

En la literatura, se suele utilizar una de las siguientes notaciones para denotar un permanente: , o . $\mathrm {Por} (A)$ $\mathrm {por} A$ $\mathrm {permiso} A$

Definición

Matriz cuadrada permanente

Sea una matriz cuadrada de tamaño , cuyos elementos pertenecen a algún campo . Un número se llama matriz permanente : $A$ $n\veces n$ ${\ estilo de visualización a_ {i, j}}$ $k$ $A$

\mathrm {Per} (A)=\sum_{\pi \in S_{n}}\prod_{i=1}^{n}a_{i,\pi_{i}}=\ suma _{\pi \in S_{n}}a_{1,\pi_{1}}a_{2,\pi_{2}}\cdots a_{n,\pi_{n}}

donde la suma se toma sobre todas las permutaciones de números del 1 al . $\Pi$ $norte$

Por ejemplo, para una matriz de tamaño : ${\ estilo de visualización 2 \ veces 2}$

\mathrm {Por} {\begin{pmatrix}a&b\\c&d\end{pmatrix}}=ad+bc

Esta definición difiere de la definición similar del determinante solo en que en el determinante algunos términos de la suma tienen un signo negativo, dependiendo del signo de la permutación . $\Pi$

Matriz rectangular permanente

El concepto de permanente a veces se extiende al caso de una matriz rectangular arbitraria de tamaño de la siguiente manera. Si , entonces: $A$ $m\veces n$ $m<n$

\mathrm {Por} (A)=\sum_{\pi}\prod_{i=1}^{m}a_{i,\pi_{i}}

donde la suma se toma sobre todas las ubicaciones de elementos del conjunto de números del 1 al . $metro$ $norte$

Si , entonces: ${\ estilo de visualización m> n}$

\mathrm {Por} (A)=\mathrm {Por} (A^{T})

O, de manera equivalente, el permanente de una matriz rectangular puede definirse como la suma de los permanentes de todas sus submatrices cuadradas de orden . ${\ estilo de visualización \ min \ {\, n, m \, \))$

Propiedades

La permanente de cualquier matriz diagonal o triangular es igual al producto de los elementos de su diagonal. En particular, el permanente de la matriz cero es igual a cero, y el permanente de la matriz identidad es igual a uno.

El permanente no cambia al transponer : . A diferencia del determinante, el permanente de una matriz no cambia por la permutación de las filas o columnas de la matriz. $\mathrm {Por} (A^{T})=\mathrm {Por} (A)$

El permanente es una función lineal de las filas (o columnas) de la matriz, es decir:

si multiplica cualquier fila (columna) por un cierto número , entonces el valor del permanente aumentará por un factor de; $C$ $C$
el permanente de la suma de dos matrices que difieren en una sola fila (columna) es igual a la suma de sus permanentes.

Un análogo de la expansión de Laplace para la primera fila de la matriz para el permanente:

{\displaystyle \mathrm {Por} (A)=\sum _{j=1}^{n}a_{1,j}B_{1,j))

donde es el permanente de la matriz obtenida al eliminar la -ésima fila y la -ésima columna. Entonces, por ejemplo, para una matriz de tamaño , se cumple lo siguiente: ${\ estilo de visualización B_ {i, j}}$ $A$ $i$ $j$ $3 veces 3$

\mathrm {Per} {\begin{pmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32} &a_{33}\end{pmatrix}}=a_{11}\mathrm {Por} {\begin{pmatrix}a_{22}&a_{23}\\a_{32}&a_{33}\end{pmatrix}} +a_{12}\mathrm {Por} {\begin{pmatrix}a_{21}&a_{23}\\a_{31}&a_{33}\end{pmatrix}}+a_{13}\mathrm {Por} {\begin{pmatrix}a_{21}&a_{22}\\a_{31}&a_{32}\end{pmatrix}}

La matriz de orden permanente es una función de orden homogénea : $norte$ $norte$

\mathrm {Por} (c\cdot A)=c^{n}\cdot \mathrm {Por} (A)

, donde es un escalar.

c\en K

Si es una matriz de permutación , entonces: $PAGS$

\mathrm {Por} (P)=1

;

\mathrm {Por} (AP)=\mathrm {Por} (PA)=\mathrm {Por} (A)

para cualquier matriz del mismo orden.

A

Si la matriz consta de números reales no negativos, entonces . $A$ $\mathrm {Per} (A)\geqslant \det A$

Si y son dos matrices triangulares superiores (o inferiores) , entonces: $A$ $B$

\mathrm {Por} (AB)=\mathrm {Por} (BA)=\mathrm {Por} (A)\cdot \mathrm {Por} (B)

(en el caso general, la igualdad no se cumple para arbitraria y , en contraste con la propiedad análoga de los determinantes). $A$ $B$

El permanente de una matriz de orden doblemente estocástica al menos ( conjetura de van der Waerden , probada en 1980). $norte$ ${\ estilo de visualización n!/n^{n}}$

Cálculo de un permanente

A diferencia del determinante, que se puede calcular fácilmente, por ejemplo, mediante el método gaussiano , el cálculo del permanente es una tarea computacional que requiere mucho tiempo y pertenece a la clase de complejidad de los problemas #P-completos . Sigue siendo #P-completo incluso para matrices que consisten solo en ceros y unos [1] .

Corrientemente[ aclarar ] no existe un algoritmo conocido para resolver tales problemas en el tiempo que sea polinomial en el tamaño de la matriz. La existencia de tal algoritmo polinomial sería incluso más fuerte que el famoso P=NP .

En diciembre de 2012, cuatro equipos de investigación independientes propusieron un prototipo de dispositivo fotónico cuántico que calcula la matriz permanente [2] .

Fórmula de Raiser

Calcular un permanente es, por definición , complejo (o incluso "aproximadamente") implementado). La estimación se puede mejorar significativamente utilizando la fórmula de Raiser [3] [4] : ${\ estilo de visualización O (n!)}$ $O(n\cdot n!)$

\mathrm {Per} (A)=(-1)^{n}\sum _{S\subseteq \{1,\dots,n\}}(-1)^{|S|}\prod _{i=1}^{n}\sum_{j\in S}a_{ij}

con él, se puede calcular un permanente en el tiempo o incluso enumerando subconjuntos por código Gray . ${\ estilo de visualización O (2 ^ {n} n ^ {2})}$ ${\ estilo de visualización O (2 ^ {n} n)}$

Aplicaciones

El permanente tiene poco o ningún uso en álgebra lineal , pero tiene usos en matemáticas discretas y combinatoria.

El permanente de la matriz , que consta de ceros y unos, se puede interpretar como el número de coincidencias completas en un gráfico bipartito con una matriz de adyacencia (es decir, un borde entre el -ésimo vértice de una parte y el -ésimo vértice de la otra parte existe si ). $A$ $A$ $i$ $j$ $a_{{ij}}=1$

El permanente de una matriz arbitraria se puede considerar como la suma de los pesos de todos los emparejamientos completos en un gráfico bipartito completo, donde el peso de un emparejamiento es el producto de los pesos de sus aristas, y los pesos de las aristas se escriben en los elementos de la matriz de adyacencia . $A$

Notas

↑ Leslie G. Valiente . La Complejidad de Computar lo Permanente (Español) // Informática Teórica . - Elsevier, 1979. - vol. 8 _ - pág. 189-201 . - doi : 10.1016/0304-3975(79)90044-6 .
↑ Los físicos han desarrollado una computadora cuántica fotónica . Lenta.ru (24 de diciembre de 2012). Consultado el 25 de diciembre de 2012. Archivado desde el original el 26 de diciembre de 2012. (Ruso)
↑ Ryser HJ, "Combinatorial Mathematics", Serie de monografías matemáticas de Carus , publicada por la Asociación Matemática de América , 1963 (hay una traducción al ruso de 1966)
↑ Weisstein, Eric W. Ryser Formula en el sitio web de Wolfram MathWorld .

Literatura

Mink H. Permanentes. — M .: Mir, 1982. — 211 p.

Enlaces

Weisstein, Eric W. Permanente (inglés) en el sitio web de Wolfram MathWorld .
Permanente (inglés) en el sitio web de PlanetMath .