Pfaffian

Raíz cuadrada del determinante de una matriz cuadrada antisimétrica

En matemáticas , el determinante de una matriz antisimétrica de m por m siempre se puede escribir como el cuadrado de un polinomio en las entradas de la matriz , un polinomio con coeficientes enteros que solo depende de m . Cuando m es impar , el polinomio es cero, y cuando m es par , es un polinomio distinto de cero de grado m /2, y es único hasta la multiplicación por ±1. La convención sobre matrices tridiagonales antisimétricas, que se muestra a continuación en los ejemplos, determina un polinomio específico, llamado polinomio de Pfaff . El valor de este polinomio, cuando se aplica a las entradas de una matriz antisimétrica, se llama el Pfaffiano de esa matriz. El término Pfaffiano fue introducido por Cayley  (1852), quien indirectamente los nombró en honor a Johann Friedrich Pfaff .

Explícitamente, para una matriz antisimétrica , ${\displaystyle A}$

${\displaystyle \operatorname {pf} (A)^{2}=\det(A),}$

que fue probada por primera vez por Cayley  (1849), quien cita a Jacobi por introducir estos polinomios en el trabajo sobre sistemas Pfaffianos de ecuaciones diferenciales . Cayley obtiene esta relación especializando un resultado más general en matrices que se desvían de la simetría oblicua solo en la primera fila y la primera columna. El determinante de dicha matriz es el producto de los Pfaffianos de las dos matrices obtenidas al establecer primero en la matriz original la entrada superior izquierda a cero y luego copiar, respectivamente, la transpuesta negativa de la primera fila a la primera columna y la transpuesta negativa de la primera columna a la primera fila. Esto se demuestra por inducción expandiendo el determinante en menores y empleando la fórmula de recursión a continuación.

Ejemplos

${\displaystyle A={\begin{bmatrix}0&a\\-a&0\end{bmatrix}},\qquad \operatorname {pf} (A)=a.}$

${\displaystyle B={\begin{bmatrix}0&a&b\\-a&0&c\\-b&-c&0\end{bmatrix}},\qquad \operatorname {pf} (B)=0.}$

(3 es impar, por lo que el Pfaffian de B es 0)

${\displaystyle \operatorname {pf} {\begin{bmatrix}0&a&b&c\\-a&0&d&e\\-b&-d&0&f\\-c&-e&-f&0\end{bmatrix}}=af-be+dc.}$

El Pfaffian de una matriz tridiagonal antisimétrica de 2 n × 2 n se da como

${\displaystyle \operatorname {pf} {\begin{bmatrix}0&a_{1}&0&0\\-a_{1}&0&0&0\\0&0&0&a_{2}\\0&0&-a_{2}&0&\ddots \\&&&\ddots &\ddots &\\&&&&&0&a_{n}\\&&&&&-a_{n}&0\end{bmatrix}}=a_{1}a_{2}\cdots a_{n}.}$

(Tenga en cuenta que cualquier matriz antisimétrica puede reducirse a esta forma; consulte Teoría espectral de una matriz antisimétrica ).

Definición formal

Sea A = ( a _ij ) una matriz antisimétrica de 2 n × 2 n . El pfaffiano de A se define explícitamente mediante la fórmula

${\displaystyle \operatorname {pf} (A)={\frac {1}{2^{n}n!}}\sum _{\sigma \in S_{2n}}\operatorname {sgn} (\sigma )\prod _{i=1}^{n}a_{\sigma (2i-1),\sigma (2i)}\,,}$

donde S _{2 n} es el grupo simétrico de grado 2 n y sgn(σ) es la firma de σ.

Se puede hacer uso de la simetría oblicua de A para evitar sumar todas las permutaciones posibles . Sea Π el conjunto de todas las particiones de {1, 2, ..., 2 n } en pares sin tener en cuenta el orden. Hay (2 n )!/(2 ⁿ n !) = (2 n − 1) !! particiones de este tipo. Un elemento α ∈ Π se puede escribir como

${\displaystyle \alpha =\{(i_{1},j_{1}),(i_{2},j_{2}),\cdots ,(i_{n},j_{n})\}}$

con i _k < j _k y . Sea ${\displaystyle i_{1}<i_{2}<\cdots <i_{n}}$

${\displaystyle \pi _{\alpha }={\begin{bmatrix}1&2&3&4&\cdots &2n-1&2n\\i_{1}&j_{1}&i_{2}&j_{2}&\cdots &i_{n}&j_{n}\end{bmatrix}}}$

sea ​​la permutación correspondiente. Dada una partición α como la anterior, defina

${\displaystyle A_{\alpha }=\operatorname {sgn} (\pi _{\alpha })a_{i_{1},j_{1}}a_{i_{2},j_{2}}\cdots a_{i_{n},j_{n}}.}$

El Pfaffian de A viene dado entonces por

${\displaystyle \operatorname {pf} (A)=\sum _{\alpha \in \Pi }A_{\alpha }.}$

El Pfaffian de una matriz antisimétrica n × n para n impar se define como cero, ya que el determinante de una matriz antisimétrica impar es cero, ya que para una matriz antisimétrica y para n impar, esto implica . $${\displaystyle \det A=\det A^{\text{T}}=\det(-A)=(-1)^{n}\det A,}$$ ${\displaystyle \det A=0}$

Definición recursiva

Por convención, el Pfaffian de la matriz 0 × 0 es igual a uno. El Pfaffian de una matriz A 2 n × 2 n antisimétrica con n > 0 se puede calcular recursivamente como

${\displaystyle \operatorname {pf} (A)=\sum _{{j=1} \atop {j\neq i}}^{2n}(-1)^{i+j+1+\theta (i-j)}a_{ij}\operatorname {pf} (A_{{\hat {\imath }}{\hat {\jmath }}}),}$

donde el índice i puede seleccionarse arbitrariamente, es la función escalonada de Heaviside , y denota la matriz A con las filas y columnas i -ésimas y j -ésimas eliminadas. ^[1] Nótese cómo para la elección especial esto se reduce a la expresión más simple: ${\displaystyle \theta (i-j)}$ ${\displaystyle A_{{\hat {\imath }}{\hat {\jmath }}}}$ ${\displaystyle i=1}$

${\displaystyle \operatorname {pf} (A)=\sum _{j=2}^{2n}(-1)^{j}a_{1j}\operatorname {pf} (A_{{\hat {1}}{\hat {\jmath }}}).}$

Definiciones alternativas

A cualquier matriz antisimétrica 2 n × 2 n A = ( a _ij ) se le puede asociar un bivector

${\displaystyle \omega =\sum _{i<j}a_{ij}\;e_{i}\wedge e_{j},}$

donde { e ₁ , e ₂ , ..., e _{2 n} } es la base estándar de R ^{2 n} . El Pfaffian se define entonces por la ecuación

${\displaystyle {\frac {1}{n!}}\omega ^{n}=\operatorname {pf} (A)\;e_{1}\wedge e_{2}\wedge \cdots \wedge e_{2n},}$

Aquí ω ⁿ denota el producto de cuña de n copias de ω .

De manera equivalente, podemos considerar el bivector (que es más conveniente cuando no queremos imponer la restricción de suma ): que da ${\displaystyle i<j}$ $${\displaystyle \omega '=2\omega =\sum _{i,j}a_{ij}\;e_{i}\wedge e_{j},}$$ ${\displaystyle \omega '^{n}=2^{n}n!\operatorname {pf} (A)\;e_{1}\wedge e_{2}\wedge \cdots \wedge e_{2n}.}$

Una generalización no nula del Pfaffian a matrices de dimensión impar se da en el trabajo de de Bruijn sobre integrales múltiples que involucran determinantes. ^[2] En particular, para cualquier matriz m  ×  m A , usamos la definición formal anterior pero establecemos . Para m impar, uno puede entonces demostrar que esto es igual al Pfaffian usual de una matriz simétrica antidesviada de dimensión ( m +1) × ( m +1) donde hemos agregado una ( m +1)ésima columna que consiste en m elementos 1, una ( m +1)ésima fila que consiste en m elementos −1, y el elemento de esquina es cero. Las propiedades usuales de los Pfaffians, por ejemplo la relación con el determinante, entonces se aplican a esta matriz extendida. ${\displaystyle n=\lfloor m/2\rfloor }$

Propiedades e identidades

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 del Pfaffian por la misma constante.
• El intercambio simultáneo de dos filas diferentes y columnas correspondientes cambia el signo del Pfaffian.
• Un múltiplo de una fila y una columna correspondiente sumado a otra fila y una columna correspondiente no cambia el valor del Pfaffian.

Utilizando estas propiedades, los Pfaffians se pueden calcular rápidamente, de forma similar al cálculo de determinantes.

Misceláneas

Para una matriz antisimétrica A de 2 n × 2 n

${\displaystyle \operatorname {pf} (A^{\text{T}})=(-1)^{n}\operatorname {pf} (A).}$

${\displaystyle \operatorname {pf} (\lambda A)=\lambda ^{n}\operatorname {pf} (A).}$

${\displaystyle \operatorname {pf} (A)^{2}=\det(A).}$

Para una matriz arbitraria B de 2 n × 2 n ,

${\displaystyle \operatorname {pf} (BAB^{\text{T}})=\det(B)\operatorname {pf} (A).}$

Sustituyendo en esta ecuación B = A ^m , se obtiene para todo entero m

${\displaystyle \operatorname {pf} (A^{2m+1})=(-1)^{nm}\operatorname {pf} (A)^{2m+1}.}$

Prueba de : ${\displaystyle \operatorname {pf} (BAB^{\text{T}})=\det(B)\operatorname {pf} (A)}$

Como dijimos anteriormente, lo mismo con : donde definimos . ${\displaystyle A\rightarrow \sum _{ij}A_{ij}e_{i}\wedge e_{j}{\xrightarrow[{}]{\wedge n}}{2^{n}n!}Pf(A)e_{1}\wedge \cdots \wedge e_{2n}.}$ ${\displaystyle BAB^{\mathrm {T} }}$ $${\displaystyle {\begin{aligned}&BAB^{\mathrm {T} }\rightarrow \sum _{ijkl}B_{ik}B_{jl}A_{kl}e_{i}\wedge e_{j}=\sum _{kl}A_{kl}f_{k}\wedge f_{l}\\&\xrightarrow {\wedge n} {2^{n}n!}Pf(A)f_{1}\wedge \cdots \wedge f_{2n}={2^{n}n!}Pf(BAB^{\mathrm {T} })e_{1}\wedge \cdots \wedge e_{2n},\end{aligned}}}$$ ${\displaystyle f_{k}=\sum _{i}B_{ik}e_{i}}$

Ya que la prueba está terminada. ${\displaystyle f_{1}\wedge \cdots \wedge f_{2n}=\det(B)e_{1}\wedge \cdots \wedge e_{2n},}$

Prueba de : ${\displaystyle \operatorname {pf} (A)^{2}=\det(A)}$

Como es una ecuación de polinomios, basta con demostrarla para matrices reales, y se aplicaría automáticamente también para matrices complejas . ${\displaystyle \operatorname {pf} (A)^{2}=\det(A)}$

Por la teoría espectral de matrices reales antisimétricas , , donde es ortogonal y para números reales . Ahora apliquemos el teorema anterior, tenemos . ${\displaystyle A=Q\Sigma Q^{\mathrm {T} }}$ ${\displaystyle Q}$ $${\displaystyle \Sigma ={\begin{bmatrix}0&a_{1}&0&0\\-a_{1}&0&0&0\\0&0&0&a_{2}\\0&0&-a_{2}&0&\ddots \\&&&\ddots &\ddots &\\&&&&&0&a_{n}\\&&&&&-a_{n}&0\end{bmatrix}}}$$ ${\displaystyle a_{k}}$ ${\displaystyle pf(A)^{2}=pf(\Sigma )^{2}\det(Q)^{2}=pf(\Sigma )^{2}=\left(\prod a_{i}\right)^{2}=\det(A)}$

Identidades derivadas

Si A depende de alguna variable x _i , entonces el gradiente de un Pfaffian está dado por

${\displaystyle {\frac {1}{\operatorname {pf} (A)}}{\frac {\partial \operatorname {pf} (A)}{\partial x_{i}}}={\frac {1}{2}}\operatorname {tr} \left(A^{-1}{\frac {\partial A}{\partial x_{i}}}\right),}$

y el hessiano de un pfaffiano está dado por

${\displaystyle {\frac {1}{\operatorname {pf} (A)}}{\frac {\partial ^{2}\operatorname {pf} (A)}{\partial x_{i}\partial x_{j}}}={\frac {1}{2}}\operatorname {tr} \left(A^{-1}{\frac {\partial ^{2}A}{\partial x_{i}\partial x_{j}}}\right)-{\frac {1}{2}}\operatorname {tr} \left(A^{-1}{\frac {\partial A}{\partial x_{i}}}A^{-1}{\frac {\partial A}{\partial x_{j}}}\right)+{\frac {1}{4}}\operatorname {tr} \left(A^{-1}{\frac {\partial A}{\partial x_{i}}}\right)\operatorname {tr} \left(A^{-1}{\frac {\partial A}{\partial x_{j}}}\right).}$

Rastrear identidades

El producto de las Pfaffianas de las matrices antisimétricas A y B se puede representar en forma de exponencial.

${\displaystyle {\textrm {pf}}(A)\,{\textrm {pf}}(B)=\exp({\tfrac {1}{2}}\mathrm {tr} \log(A^{\text{T}}B)).}$

Supongamos que A y B son matrices antisimétricas de 2 n × 2 n , entonces

${\displaystyle \mathrm {pf} (A)\,\mathrm {pf} (B)={\tfrac {1}{n!}}B_{n}(s_{1},s_{2},\ldots ,s_{n}),\qquad \mathrm {where} \qquad s_{l}=-{\tfrac {1}{2}}(l-1)!\,\mathrm {tr} ((AB)^{l})}$

y B _n ( s ₁ , s ₂ ,..., s _n ) son polinomios de Bell .

Matrices de bloques

Para una matriz diagonal por bloques

${\displaystyle A_{1}\oplus A_{2}={\begin{bmatrix}A_{1}&0\\0&A_{2}\end{bmatrix}},}$

${\displaystyle \operatorname {pf} (A_{1}\oplus A_{2})=\operatorname {pf} (A_{1})\operatorname {pf} (A_{2}).}$

Para una matriz arbitraria n × n M :

${\displaystyle \operatorname {pf} {\begin{bmatrix}0&M\\-M^{\text{T}}&0\end{bmatrix}}=(-1)^{n(n-1)/2}\det M.}$

A menudo se requiere calcular el Pfaffian de una matriz antisimétrica con la estructura de bloques ${\displaystyle S}$

${\displaystyle S={\begin{pmatrix}M&Q\\-Q^{\mathrm {T} }&N\end{pmatrix}}\,}$

donde y son matrices antisimétricas y es una matriz rectangular general. ${\displaystyle M}$ ${\displaystyle N}$ ${\displaystyle Q}$

Cuando es invertible , se tiene ${\displaystyle M}$

${\displaystyle \operatorname {pf} (S)=\operatorname {pf} (M)\operatorname {pf} (N+Q^{\mathrm {T} }M^{-1}Q).}$

Esto se puede ver en la fórmula de diagonalización de bloques de Aitken, ^{[3] [4] [5]}

${\displaystyle {\begin{pmatrix}M&0\\0&N+Q^{\mathrm {T} }M^{-1}Q\end{pmatrix}}={\begin{pmatrix}I&0\\Q^{\mathrm {T} }M^{-1}&I\end{pmatrix}}{\begin{pmatrix}M&Q\\-Q^{\mathrm {T} }&N\end{pmatrix}}{\begin{pmatrix}I&-M^{-1}Q\\0&I\end{pmatrix}}.}$

Esta descomposición implica una transformación de congruencia que permite utilizar la propiedad Pfaffiana . ${\displaystyle \operatorname {pf} (BAB^{\mathrm {T} })=\operatorname {det} (B)\operatorname {pf} (A)}$

De manera similar, cuando es invertible, se tiene ${\displaystyle N}$

${\displaystyle \operatorname {pf} (S)=\operatorname {pf} (N)\operatorname {pf} (M+QN^{-1}Q^{\mathrm {T} }),}$

como se puede ver empleando la descomposición

${\displaystyle {\begin{pmatrix}M+QN^{-1}Q^{\mathrm {T} }&0\\0&N\end{pmatrix}}={\begin{pmatrix}I&-QN^{-1}\\0&I\end{pmatrix}}{\begin{pmatrix}M&Q\\-Q^{\mathrm {T} }&N\end{pmatrix}}{\begin{pmatrix}I&0\\N^{-1}Q^{\mathrm {T} }&I\end{pmatrix}}.}$

Calcular numéricamente el Pfaffian

Supongamos que A es una matriz antisimétrica de 2n × 2n , entonces

${\displaystyle {\textrm {pf}}(A)=i^{(n^{2})}\exp \left({\tfrac {1}{2}}\mathrm {tr} \log((\sigma _{y}\otimes I_{n})^{\mathrm {T} }\cdot A)\right),}$

donde es la segunda matriz de Pauli , es una matriz identidad de dimensión n y tomamos la traza sobre una matriz logarítmica . ${\displaystyle \sigma _{y}}$ ${\displaystyle I_{n}}$

Esta igualdad se basa en la identidad de traza.

${\displaystyle {\textrm {pf}}(A)\,{\textrm {pf}}(B)=\exp \left({\tfrac {1}{2}}\mathrm {tr} \log(A^{\text{T}}B)\right)}$

y en la observación de que . ${\displaystyle {\textrm {pf}}(\sigma _{y}\otimes I_{n})=(-i)^{n^{2}}}$

Dado que calcular el logaritmo de una matriz es una tarea que requiere mucho esfuerzo computacional, se pueden calcular todos los valores propios de , tomar el logaritmo de todos ellos y sumarlos. Este procedimiento simplemente aprovecha la propiedad . Esto se puede implementar en Mathematica con una sola declaración: ${\displaystyle ((\sigma _{y}\otimes I_{n})^{\mathrm {T} }\cdot A)}$ ${\displaystyle \operatorname {tr} {\log {(AB)}}=\operatorname {tr} {\log {(A)}}+\operatorname {tr} {\log {(B)}}}$

Pf[x_] := Module[{n = Dimensions[x][[1]] / 2}, I^(n^2) Exp[ 1/2 Total[ Log[Eigenvalues[ Dot[Transpose[KroneckerProduct[PauliMatrix[2], IdentityMatrix[n]]], x] ]]]]]

Sin embargo, este algoritmo es inestable cuando el Pfaffian es grande. Los valores propios de generalmente serán complejos, y el logaritmo de estos valores propios complejos generalmente se toma como . Bajo la suma, para un Pfaffian de valor real, el argumento del exponencial se dará en la forma para algún entero . Cuando es muy grande, los errores de redondeo al calcular el signo resultante de la fase compleja pueden conducir a un componente imaginario distinto de cero. ${\displaystyle (\sigma _{y}\otimes I_{n})^{\mathrm {T} }\cdot A}$ ${\displaystyle [-\pi ,\pi ]}$ ${\displaystyle x+k\pi /2}$ ${\displaystyle k}$ ${\displaystyle x}$

Para otros algoritmos (más) eficientes, consulte Wimmer 2012.

Aplicaciones

• Existen programas para el cálculo numérico del Pfaffian en varias plataformas (Python, Matlab, Mathematica) (Wimmer 2012).
• El polinomio de Pfaffian es un polinomio invariante de una matriz antisimétrica bajo un cambio de base ortogonal adecuado . Como tal, es importante en la teoría de clases características . En particular, se puede utilizar para definir la clase de Euler de una variedad de Riemann que se utiliza en el teorema de Gauss-Bonnet generalizado .
• El número de emparejamientos perfectos en un grafo planar está dado por un Pfaffian, por lo tanto es tiempo polinomial computable a través del algoritmo FKT . Esto es sorprendente dado que para grafos generales, el problema es muy difícil (denominado #P-completo ). Este resultado se utiliza para calcular el número de teselas de dominó de un rectángulo, la función de partición de los modelos de Ising en física o de los campos aleatorios de Markov en el aprendizaje automático (Globerson y Jaakkola 2007; Schraudolph y Kamenetsky 2009), donde el grafo subyacente es planar. También se utiliza para derivar algoritmos eficientes para algunos problemas aparentemente intratables, incluida la simulación eficiente de ciertos tipos de computación cuántica restringida. Consulte Algoritmo holográfico para obtener más información.

Véase también

• Determinante
• Modelo de dímero
• Hafniano
• Poliominó
• Mecánica estadística

Notas

1. "Copia archivada" (PDF) . Archivado desde el original (PDF) el 5 de marzo de 2016. Consultado el 31 de marzo de 2015 .{{cite web}}: CS1 maint: archived copy as title (link)
2. Bruijn, de, NG (1955). "Sobre algunas integrales múltiples que involucran determinantes". Revista de la Sociedad Matemática de la India . Nueva serie. 19 : 133–151. ISSN  0019-5839.{{cite journal}}: CS1 maint: multiple names: authors list (link)
3. AC Aitken. Determinantes y matrices. Oliver y Boyd, Edimburgo, cuarta edición, 1939.
4. Zhang, Fuzhen, ed. El complemento de Schur y sus aplicaciones. Vol. 4. Springer Science & Business Media, 2006.
5. Bunch, James R. "Una nota sobre la descomposición estable de matrices antisimétricas". Matemáticas de la computación 38.158 (1982): 475-479.

Referencias

• Cayley, Arturo (1849). "Sobre los determinantes gauches". Journal für die reine und angewandte Mathematik . 38 : 93–96.
• Cayley, Arthur (1852). "Sobre la teoría de permutantes". Cambridge and Dublin Mathematical Journal . VII : 40–51.Reimpreso en Collected mathematics papers, volumen 2.
• Kasteleyn, PW (1961). "Las estadísticas de los dímeros en una red. I. El número de disposiciones de dímeros en una red cuadrática". Physica . 27 (12): 1209–1225. doi :10.1016/0031-8914(61)90063-5 .
• Propp, James (2004). "Determinantes lambda y teselas dominó". arXiv : math/0406301 .
• Globerson, Amir; Jaakkola, Tommi (2007). "Inferencia aproximada mediante descomposición de grafos planos" (PDF) . Avances en sistemas de procesamiento de información neuronal 19. MIT Press.
• Schraudolph, Nicol; Kamenetsky, Dmitry (2009). "Inferencia exacta eficiente en modelos de Ising planares" (PDF) . Avances en sistemas de procesamiento de información neuronal 21. MIT Press.
• Jeliss, GP; Chapman, Robin J. (1996). "Dominando el tablero de ajedrez". The Games and Puzzles Journal . 2 (14): 204–5.
• Sellers, James A. (2002). "Teselas de dominó y productos de números de Fibonacci y Pell". Journal of Integer Sequences . 5 (1): 02.1.2. Código Bibliográfico :2002JIntS...5...12S.
• Wells, David (1997). Diccionario Penguin de números curiosos e interesantes (edición revisada). Penguin. pág. 182. ISBN 0-14-026149-4.
• Muir, Thomas (1882). Tratado sobre la teoría de los determinantes. Macmillan and Co.En línea
• Parameswaran, S. (1954). "Determinantes antisimétricos". The American Mathematical Monthly . 61 (2): 116. doi :10.2307/2307800. JSTOR  2307800.
• Wimmer, M. (2012). "Cálculo numérico eficiente del Pfaffian para matrices densas y bandeadas con simetría antisimétrica". ACM Trans. Math. Softw. 38 : 30. arXiv : 1102.3440 . doi :10.1145/2331130.2331138. S2CID  : 15331538.
• de Bruijn, NG (1955). "Sobre algunas integrales múltiples que involucran determinantes". J. Indian Math. Soc. 19 : 131–151.

Enlaces externos

• "Pfaffian", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Pfaffian en PlanetMath.org
• T. Jones, El producto Pfaffian y el producto Wedge (una demostración de la prueba de la relación Pfaffian/determinante)
• R. Kenyon y A. Okounkov , ¿Qué es... un dímero?
• Secuencia OEIS A004003 (Número de teselas de dominó (o recubrimientos de dímeros))
• W. Ledermann "Una nota sobre determinantes antisimétricos" https://www.researchgate.net/publication/231827602_A_note_on_skew-synchronous_determinants