Pfaffiano
En matemáticas, el determinante de una matriz antisimétrica siempre se puede escribir como el cuadrado de un polinomio que opera sobre los datos de la matriz, un polinomio con coeficientes enteros que solo dependen del tamaño de la matriz. El valor de este polinomio, cuando se aplica a los coeficientes de una matriz antisimétrica, se denomina pfaffiano de la matriz. El término pfaffiano fue introducido por Arthur Cayley (1852) quien adoptó este nombre en memoria de Johann Friedrich Pfaff. El pfaffiano (considerado como un polinomio) no se desvanece solo para matrices antisimétricas de orden 2n×2n, en cuyo caso es un polinomio de grado n.
Explícitamente, para una matriz antisimétrica A,
lo que posiblemente fue demostrado por primera vez por Thomas Muir en 1882 (Muir, 1882).
El hecho de que el determinante de cualquier matriz antisimétrica sea el cuadrado de una expresión polinomial puede demostrarse escribiendo la matriz como una matriz por bloques, utilizando un proceso de inducción y examinando el complemento de Schur, que también es antisimétrico.[1]
Ejemplos
[editar](3 es impar, entonces el pfaffiano de B es 0)
El pfaffiano de una matriz tridiagonal antisimétrica de orden 2n×2n se da como
(Debe tenerse en cuenta que cualquier matriz antisimétrica se puede reducir a esta forma con todos los iguales a cero; véase teoría espectral de matrices antisimétricas)
Definición formal
[editar]Sea A = {ai,j} una matriz antisimétrica de orden 2n×2n. El pfaffiano de A está definido por la ecuación
donde S2n es el grupo simétrico de dimensión (2n)! y sgn (σ) es la signatura de σ.
Se hace uso de la antisimetría de A para evitar tener que sumar todas las posibles permutaciones. Sea Π el conjunto de todas las particiones de {1, 2, ..., 2n} en parejas sin importar el orden. Hay (2n)! / (2nn !) = (2n-1)!! de tales particiones. Un elemento α ∈ Π se puede escribir como
con ik < jk y . Haciendo
la permutación correspondiente. Dada una partición α como la anterior, se define
El pfaffiano de A viene dado por
El pfaffiano de una matriz n×n antisimétrica para n impar se define como cero, ya que el determinante de una matriz antisimétrica impar es cero, ya que para una matriz asimétrica, , y para n impar, esto implica que .
Definición recursiva
[editar]Por convención, el pfaffiano de la matriz 0 × 0 es igual a uno. El pfaffiano de una matriz antisimétrica A de orden 2n×2n con n> 0 se puede calcular recursivamente como
donde el índice i se puede seleccionar arbitrariamente, es la función escalón de Heaviside y indica la matriz A con la i-ésima y j-ésima filas y columnas eliminadas.[2] Obsérvese cómo para la opción especial se reduce a la expresión más simple:
Definiciones alternativas
[editar]Se puede asociar a cualquier matriz antisimétrica de orden 2n×2n A = { aij} un bivector
donde {e1, e2, ..., e2n} es la base estándar de R2n. El pfaffiano entonces se define por la ecuación
donde ωn denota el producto en cuña de n copias de ω.
Una generalización no nula del pfaffiano de matrices de dimensiones impares se da en el trabajo de Bruijn sobre integrales múltiples que involucran determinantes.[3] En particular, para cualquier matriz A de orden mxm, utiliza la definición formal anterior, pero configurando . Para m impar, se puede demostrar que esto es igual al pfaffiano usual de una matriz antisimétrica de orden m+1xm+1, donde se ha agregado una m+1-ésima columna que consiste en m elementos 1, una m+1-ésima fila que consta de m elementos -1, y el elemento de la esquina que es cero. Las propiedades usuales de los pfaffianos, por ejemplo, la relación con el determinante, se aplican a esta matriz extendida.
Propiedades e identidades
[editar]Los pfaffianos tienen las siguientes propiedades, que son similares a las de los determinantes.
- La multiplicación de una fila y una columna por una constante es equivalente a la multiplicación de pfaffiano por la misma constante.
- El intercambio simultáneo de dos filas diferentes y columnas correspondientes cambia el signo de pfaffiano.
- Un múltiplo de una fila y la columna correspondiente agregada a otra fila y columna correspondiente no cambian el valor del pfaffiano.
Usando estas propiedades, los pfaffianos se pueden calcular rápidamente, de forma similar al cálculo de determinantes.
Varios
[editar]Para una matriz antisimétrica A de orden 2n×2n
Para una matriz arbitraria B de orden 2n×2n,
Sustituyendo en esta ecuación B=Am, se obtiene para todo entero m
Identidades derivadas
[editar]Si A depende de alguna variable xi, entonces el gradiente de un pfaffiano viene dado por
y el hessiano de un pfaffiano viene dado por
Identidades subsiguientes
[editar]El producto de los pfaffianos de dos matrices antisimétricas A y B bajo la condición de que ATB es una matriz definida positiva, se puede representar en forma de un exponencial
Suponiendo que A y B son matrices antisimétricas de orden 2n×2n, entonces
y Bn (s1,s2,...,sn) son polinomios de Bell.
Matrices de bloques
[editar]Para una matriz por bloques diagonal
Para una matriz arbitraria M de orden n×n:
A menudo se requiere calcular el pfaffiano de una matriz antisimétrica con la estructura del bloque
donde y son matrices antisimétricas y es una matriz rectangular general.
Cuando es invertible, se tiene que
Esto se puede ver en la fórmula de diagonalización de bloques de Aitken,[4][5][6]
Esta descomposición implica unas transformaciones congruentes que permiten usar la propiedad del pfaffiano .
Del mismo modo, cuando es invertible, se tiene que
como se puede ver al emplear la descomposición
Aplicaciones
[editar]- Existen programas para el cálculo numérico de pfaffianos en varias plataformas (Python, Matlab, Mathematica) (Wimmer, 2012).
- El pfaffiano es un invariante polinomial de una matriz antisimétrica bajo un cambio de base ortogonal apropiado. Como tal, es importante en la teoría de clases características. En particular, se puede usar para definir la clase de Euler de una variedad de Riemann que se usa en el teorema de Gauss-Bonnet generalizado.
- El número de apareamiento (teoría de grafos) en un grafo plano viene dado por un pfaffiano, por lo tanto, es un tiempo polinomial computable a través del algoritmo FKT. Esto es sorprendente dado que para los gráficos generales, el problema es muy difícil (se denomina numeral-P-completo). Este resultado se usa para calcular el número de teselado en dominó de un rectángulo, la función de partición del modelo de Ising en física o del campo aleatorio de Markov en aprendizaje automático (Globerson y Jaakkola, 2007;Schraudolph y Kamenetsky, 2009), donde el gráfico subyacente es plano. También se utiliza para derivar algoritmos eficientes para algunos problemas que de otra manera aparentemente no se pueden resolver, incluida la simulación eficiente de ciertos tipos de computación cuántica restringida. Véase algoritmo holográfico para obtener más información.
Véase también
[editar]Notas
[editar]- ↑ Ledermann, W. "A note on skew-symmetric determinants"
- ↑ «Copia archivada». Archivado desde el original el 5 de marzo de 2016. Consultado el 30 de diciembre de 2017.
- ↑ http://alexandria.tue.nl/repository/freearticles/597510.pdf
- ↑ A. C. Aitken. Determinants and matrices. Oliver and Boyd, Edinburgh, fourth edition, 1939.
- ↑ Zhang, Fuzhen, ed. The Schur complement and its applications. Vol. 4. Springer Science & Business Media, 2006.
- ↑ Bunch, James R. "A note on the stable decompostion of skew-symmetric matrices." Mathematics of Computation 38.158 (1982): 475-479.
Referencias
[editar]- Cayley, Arthur (1852). «On the theory of permutants». Cambridge and Dublin Mathematical Journal VII: 40-51. reimpreso en papeles matemáticos recopilados, volumen 2.
- Kasteleyn, P. W. (1961). «The statistics of dimers on a lattice. I. The number of dimer arrangements on a quadratic lattice». Physica 27 (12): 1209-1225. doi:10.1016/0031-8914(61)90063-5.
- Propp, James (2004). «Lambda-determinants and domino-tilings». .
- Globerson, Amir; Jaakkola, Tommi (2007). «Approximate inference using planar graph decomposition». Advances in Neural Information Processing Systems 19. MIT Press..
- Schraudolph, Nicol; Kamenetsky, Dmitry (2009). «Efficient exact inference in planar Ising models». Advances in Neural Information Processing Systems 21. MIT Press..
- Jeliss, G.P.; Chapman, Robin J. (1996). «Dominizing the Chessboard». The Games and Puzzles Journal 2 (14): 204-5.
- Sellers, James A. (2002). «Domino Tilings and Products of Fibonacci and Pell numbers». Journal of Integer Sequences 5 (1): 02.1.2.
- Wells, David (1997). The Penguin Dictionary of Curious and Interesting Numbers (revised edición). p. 182. ISBN 0-14-026149-4.
- Muir, Thomas (1882). A Treatise on the Theory of Determinants. Macmillan and Co. Online
- Parameswaran, S. (1954). «Skew-Symmetric Determinants». The American Mathematical Monthly 61 (2): 116. JSTOR 2307800. doi:10.2307/2307800.
- Wimmer, M. (2012). «Efficient numerical computation of the Pfaffian for dense and banded skew-symmetric matrices». ACM Trans. Math. Softw. 38: 30. arXiv:1102.3440. doi:10.1145/2331130.2331138.
- de Bruijn, N. G. (1955). «On some multiple integrals involving determinants». J. Indian Math. Soc. 19: 131-151.
Enlaces externos
[editar]- Hazewinkel, Michiel, ed. (2001), «Pfaffiano», Encyclopaedia of Mathematics (en inglés), Springer, ISBN 978-1556080104.
- Pfaffian en PlanetMath.org
- T. Jones, The Pfaffian and the Wedge Product (una demostración de la prueba de la relación Pfaffian / determinante )
- R. Kenyon y A. Okounkov, ¿Qué es ... un dímero?
- (sucesión A004003 en OEIS)
- W. Ledermann "Una nota sobre los determinantes sesgados simétricos" https://www.researchgate.net/publication/231827602_A_note_on_skew-symmetric_determinants