Pfaffiano

Raíz cuadrada del determinante de una matriz cuadrada simétrica sesgada

En matemáticas , el determinante de una matriz asimétrica de m × 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. 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 simétricas sesgadas, que se proporciona 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 simétrica sesgada, se denomina 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 simétrica sesgada , ${\displaystyle A}$

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

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

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 pfaffiano 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 Pfaffiano de una matriz tridiagonal simétrica sesgada de 2 n × 2 n viene dado 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 simétrica sesgada se puede reducir a esta forma; consulte Teoría espectral de una matriz simétrica sesgada ).

Definicion formal

Sea A = ( a _ij ) una matriz sesgada-simé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 orden (2 n )! y sgn(σ) es la firma de σ.

Se puede hacer uso de la simetría sesgada 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) !! tales particiones. 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 . Dejar ${\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 pfaffiano de A viene dado entonces por

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

El Pfaffiano de una matriz asimétrica n × n para n impar se define como cero, ya que el determinante de una matriz asimétrica impar es cero, ya que para una matriz simétrica asimétrica,

$${\displaystyle \det \,A=\det \,A^{\text{T}}=\det \left(-A\right)=(-1)^{n}\det \,A,}$$

n ${\displaystyle \det \,A=0}$

Definición recursiva

Por convención, el Pfaffian de la matriz 0×0 es igual a uno. El Pfaffiano de una matriz A simétrica sesgada de 2 n × 2 n con n > 0 se puede calcular de forma recursiva 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 se puede seleccionar arbitrariamente, es la función escalonada de Heaviside y denota la matriz A con las filas y columnas i -ésima y j- ésima eliminadas. ^[1] Observe 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

Se puede asociar a cualquier matriz simétrica sesgada 2 n × 2 n A = ( a _ij ) 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 pfaffiano se define entonces mediante 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 ): ${\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}.}$

En el trabajo de de Bruijn sobre integrales múltiples que involucran determinantes se ofrece una generalización distinta de cero de Pfaffian a matrices de dimensiones impares. ^[2] En particular, para cualquier matriz A , usamos la definición formal anterior pero establecemos . Para m impar, se puede demostrar que esto es igual al Pfaffiano habitual de una matriz simétrica asimétrica de dimensiones donde hemos agregado una enésima columna que consta de m elementos 1, una enésima fila que consta de m elementos −1 y el elemento de esquina es cero. Las propiedades habituales de los pfaffianos, por ejemplo la relación con el determinante, se aplican a esta matriz extendida. ${\displaystyle m\times m}$ ${\displaystyle n=\lfloor m/2\rfloor }$ ${\displaystyle (m+1)\times (m+1)}$ ${\displaystyle (m+1)}$ ${\displaystyle (m+1)}$

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

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

Misceláneas

Para una matriz A simétrica sesgada 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 B arbitraria 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 todo número 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 se dijo anteriormente, . Lo mismo con : ${\displaystyle A\mapsto \sum _{ij}A_{ij}e_{i}\wedge e_{j}\mapsto ^{\wedge n}{2^{n}n!}Pf(A)e_{1}\wedge \cdots \wedge e_{2n}}$ ${\displaystyle BAB^{\mathrm {T} }}$

$${\displaystyle BAB^{\mathrm {T} }\mapsto \sum _{ijkl}B_{ik}B_{jl}A_{kl}e_{i}\wedge e_{j}=\sum _{kl}A_{il}f_{k}\wedge f_{l}\mapsto ^{\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},}$$

donde definimos . ${\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)}$

Según la teoría espectral de matrices reales asimétricas , donde es ortogonal y ${\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}}}$$

para números reales . Ahora aplicamos el teorema anterior, tenemos . ${\displaystyle a_{k}}$ ${\displaystyle pf(A)^{2}=pf(\Sigma )^{2}\det(Q)^{4}=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 Pfaffiano viene 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 los pfaffianos de las matrices simétricas sesgadas 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 asimétricas de 2n × 2n , 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 de 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 es necesario calcular el pfaffian de una matriz simétrica sesgada con la estructura de bloques ${\displaystyle S}$

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

donde y son matrices asimé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 transformaciones de congruencia que permiten 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 el Pfaffiano numéricamente

Supongamos que A es una matriz simétrica sesgada 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 está la segunda matriz de Pauli , es una matriz identidad de dimensión n y tomamos la traza sobre una matriz logaritmo . ${\displaystyle \sigma _{y}}$ ${\displaystyle I_{n}}$

Esta igualdad se basa en la identidad de la traza.

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

y sobre 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 computacionalmente exigente, en su lugar se pueden calcular todos los valores propios de , tomar el registro de todos ellos y resumirlos. Este procedimiento simplemente explota 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 generalmente se considera que el logaritmo de estos valores propios complejos está en . Bajo la suma, para un Pfaffian de valor real, el argumento del exponencial se dará en la forma de algún número entero . Cuando es muy grande, los errores de redondeo al calcular el signo resultante de la fase compleja pueden llevar 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 conocer otros algoritmos (más) eficientes, consulte Wimmer 2012.

Aplicaciones

• Existen programas para el cálculo numérico del Pfaffiano en varias plataformas (Python, Matlab, Mathematica) (Wimmer 2012).
• El Pfaffiano es un polinomio invariante de una matriz simétrica sesgada 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 generalizado de Gauss-Bonnet .
• El número de coincidencias perfectas en un gráfico plano viene dado por un Pfaffiano, por lo tanto, el tiempo polinómico es computable mediante el algoritmo FKT . Esto es sorprendente dado que para gráficos generales, el problema es muy difícil (el llamado #P-completo ). Este resultado se utiliza para calcular el número de mosaicos 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 gráfico subyacente es plano. . 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. Lea Algoritmo holográfico para obtener más información.

Ver también

• Determinante
• Modelo dímero
• hafniano
• Poliomino
• 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 implican determinantes". Revista de la Sociedad Matemática de la India . Series nuevas. 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 Schur y sus aplicaciones. vol. 4. Springer Science & Business Media, 2006.
5. Bunch, James R. "Una nota sobre la descomposición estable de matrices simétricas sesgadas". 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, Arturo (1852). "Sobre la teoría de los permutantes". Revista matemática de Cambridge y Dublín . VII : 40–51.Reimpreso en Artículos matemáticos recopilados, volumen 2.
• Kasteleyn, PW (1961). "Las estadísticas de dímeros en una red. I. El número de disposiciones de dímeros en una red cuadrática". Física . 27 (12): 1209-1225. Código bibliográfico : 1961Phy....27.1209K. doi :10.1016/0031-8914(61)90063-5.
• Propp, James (2004). "Determinantes lambda y mosaicos de dominó". arXiv : matemáticas/0406301 .
• Globerson, Amir; Jaakkola, Tommi (2007). "Inferencia aproximada mediante descomposición de gráficos planos" (PDF) . Avances en los sistemas de procesamiento de información neuronal 19. MIT Press.
• Schraudolph, Nicol; Kamenetsky, Dmitry (2009). "Inferencia exacta eficiente en modelos planos de Ising" (PDF) . Avances en los sistemas de procesamiento de información neuronal 21. MIT Press.
• Jeliss, médico de cabecera; Chapman, Robin J. (1996). "Dominando el tablero de ajedrez". La Revista de Juegos y Rompecabezas . 2 (14): 204–5.
• Vendedores, James A. (2002). "Azulejos de dominó y productos de los números de Fibonacci y Pell". Diario de secuencias enteras . 5 (1): 02.1.2. Código Bib : 2002JIntS...5...12S.
• Pozos, David (1997). Diccionario pingüino de números curiosos e interesantes (edición revisada). Pingüino. pag. 182.ISBN​ 0-14-026149-4.
• Muir, Thomas (1882). Tratado sobre la teoría de los determinantes. Macmillan y compañía.En línea
• Parameswaran, S. (1954). "Determinantes asimétricos". El Mensual Matemático Estadounidense . 61 (2): 116. doi : 10.2307/2307800. JSTOR  2307800.
• Wimmer, M. (2012). "Cálculo numérico eficiente del Pfaffiano para matrices simétricas sesgadas densas y con bandas". Transmisión ACM. Matemáticas. Software. 38 : 30. arXiv : 1102.3440 . doi :10.1145/2331130.2331138. S2CID  15331538.
• de Bruijn, NG (1955). "Sobre algunas integrales múltiples que implican determinantes". J. Matemáticas indias. Soc. 19 : 131-151.

enlaces externos

• "Pfaffian", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• 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?
• Secuencia OEIS A004003 (Número de mosaicos de dominó (o cubiertas de dímeros))
• W. Ledermann "Una nota sobre los determinantes simétricos sesgados" https://www.researchgate.net/publication/231827602_A_note_on_skew-metric_determinants