Hafniano

En matemáticas , el hafniano es una función escalar de una matriz simétrica que generaliza la permanente .

El hafniano recibió este nombre por Eduardo R. Caianiello "para conmemorar el fructífero período de estancia en Copenhague (Hafnia en latín)". ^[1]

Definición

El hafniano de una matriz simétrica se define como ${\displaystyle 2n\times 2n}$ ${\displaystyle A}$

${\displaystyle \operatorname {haf} (A)=\sum _{\rho \in P_{2n}^{2}}\prod _{\{i,j\}\in \rho }A_{i,j},}$

donde es el conjunto de todas las particiones del conjunto en subconjuntos de tamaño . ^{[2] [3]} ${\displaystyle P_{2n}^{2}}$ ${\displaystyle \{1,2,\dots ,2n\}}$ ${\displaystyle 2}$

Esta definición es similar a la del pfaffiano , pero difiere en que no se tienen en cuenta las firmas de las permutaciones. Por lo tanto, la relación del hafniano con el pfaffiano es la misma que la relación del permanente con el determinante . ^[4]

Propiedades básicas

El hafniano también puede definirse como

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

donde es el grupo simétrico en . ^[5] Las dos definiciones son equivalentes porque si , entonces es una partición de en subconjuntos de tamaño 2, y como los rangos abarcan , cada partición de este tipo se cuenta exactamente veces. Nótese que este argumento se basa en la simetría de , sin la cual la definición original no está bien definida. ${\displaystyle S_{2n}}$ ${\displaystyle \{1,2,...,2n\}}$ ${\displaystyle \sigma \in S_{2n}}$ ${\displaystyle \{\{\sigma (2i-1),\sigma (2i)\}:i\in \{1,...,n\}\}}$ ${\displaystyle \{1,2,\dots ,2n\}}$ ${\displaystyle \sigma }$ ${\displaystyle S_{2n}}$ ${\displaystyle n!2^{n}}$ ${\displaystyle A}$

El hafniano de una matriz de adyacencia de un grafo es el número de coincidencias perfectas (también conocidas como 1-factores) en el grafo. Esto se debe a que una partición de en subconjuntos de tamaño 2 también puede considerarse como una coincidencia perfecta en el grafo completo . ${\displaystyle \{1,2,\dots ,2n\}}$ ${\displaystyle K_{2n}}$

El hafniano también puede considerarse como una generalización del permanente , ya que el permanente puede expresarse como

${\displaystyle \operatorname {per} (C)=\operatorname {haf} {\begin{pmatrix}0&C\\C^{T}&0\end{pmatrix}}}$. ^[2]

Así como el hafniano cuenta el número de coincidencias perfectas en un gráfico dada su matriz de adyacencia, el permanente cuenta el número de coincidencias en un gráfico bipartito dada su matriz de biadyacencia .

El hafniano también está relacionado con los momentos de distribuciones gaussianas multivariadas . Por el teorema de probabilidad de Wick , el hafniano de una matriz simétrica real puede expresarse como ${\displaystyle 2n\times 2n}$

${\displaystyle \operatorname {haf} (A)=\mathbb {E} _{\left(X_{1},\dots ,X_{2n}\right)\sim {\mathcal {N}}\left(0,A+\lambda I\right)}\left[X_{1}\dots X_{2n}\right],}$

donde es cualquier número lo suficientemente grande como para hacer que . sea semidefinido positivo . Nótese que el hafniano no depende de las entradas diagonales de la matriz y la expectativa en el lado derecho no depende de . ${\displaystyle \lambda }$ ${\displaystyle A+\lambda I}$ ${\displaystyle \lambda }$

Función generadora

Sea una matriz simétrica compleja arbitraria compuesta de cuatro bloques , , y . Sea un conjunto de variables independientes, y sea una matriz de bloques antidiagonal compuesta de entradas (cada una se presenta dos veces, una vez por cada bloque distinto de cero). Sea la matriz identidad . Entonces se cumple la siguiente identidad: ^[4] ${\displaystyle S={\begin{pmatrix}A&C\\C^{T}&B\end{pmatrix}}=S^{T}}$ ${\displaystyle 2m\times 2m}$ ${\displaystyle m\times m}$ ${\displaystyle A=A^{T}}$ ${\displaystyle B=B^{T}}$ ${\displaystyle C}$ ${\displaystyle C^{T}}$ ${\displaystyle z_{1},\ldots ,z_{m}}$ ${\displaystyle m}$ ${\displaystyle Z={\begin{pmatrix}0&{\textrm {diag}}(z_{1},z_{2},\ldots ,z_{m})\\{\textrm {diag}}(z_{1},z_{2},\ldots ,z_{m})&0\end{pmatrix}}}$ ${\displaystyle z_{j}}$ ${\displaystyle I}$

${\displaystyle {\frac {1}{\sqrt {\det {\big (}I-ZS{\big )}}}}=\sum _{\{n_{k}\}}\operatorname {haf} {\tilde {S}}(\{n_{k}\})\prod _{k=1}^{m}{\frac {z_{k}^{n_{k}}}{n_{k}!}}}$

donde el lado derecho involucra hafnianos de matrices , cuyos bloques , , y se construyen a partir de los bloques , , y respectivamente en la forma introducida en el teorema maestro de MacMahon . En particular, es una matriz construida reemplazando cada entrada en la matriz con un bloque lleno de ; el mismo esquema se aplica a , y . La suma se ejecuta sobre todas las -tuplas de números enteros no negativos , y se supone que . ${\displaystyle {\Big (}2\sum _{k}n_{k}{\Big )}\times {\Big (}2\sum _{k}n_{k}{\Big )}}$ ${\displaystyle {\tilde {S}}(\{n_{k}\})={\begin{pmatrix}{\tilde {A}}(\{n_{k}\})&{\tilde {C}}(\{n_{k}\})\\{\tilde {C}}^{T}(\{n_{k}\})&{\tilde {B}}(\{n_{k}\})\\\end{pmatrix}}}$ ${\displaystyle {\tilde {A}}(\{n_{k}\})}$ ${\displaystyle {\tilde {B}}(\{n_{k}\})}$ ${\displaystyle {\tilde {C}}(\{n_{k}\})}$ ${\displaystyle {\tilde {C}}^{T}(\{n_{k}\})}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle C^{T}}$ ${\displaystyle {\tilde {A}}(\{n_{k}\})}$ ${\displaystyle A_{k,t}}$ ${\displaystyle A}$ ${\displaystyle n_{k}\times n_{t}}$ ${\displaystyle A_{k,t}}$ ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle C^{T}}$ ${\displaystyle \sum _{\{n_{k}\}}}$ ${\displaystyle k}$ ${\displaystyle \operatorname {haf} {\tilde {S}}(\{n_{k}=0|k=1\ldots m\})=1}$

La identidad se puede demostrar ^[4] mediante integrales gaussianas multivariadas y el teorema de probabilidad de Wick .

La expresión del lado izquierdo, , es de hecho una función generadora multivariable para una serie de hafnianos, y el lado derecho constituye su expansión de Taylor multivariable en la vecindad del punto Como consecuencia de la relación dada, el hafniano de una matriz simétrica se puede representar como la siguiente derivada mixta del orden : ${\displaystyle 1{\Big /}{\sqrt {\det {\big (}I-ZS{\big )}}}{\Big .}}$ ${\displaystyle z_{1}=\ldots =z_{m}=0.}$ ${\displaystyle 2m\times 2m}$ ${\displaystyle S}$ ${\displaystyle m}$

${\displaystyle \operatorname {haf} S={\bigg (}\prod _{k=1}^{m}{\frac {\partial }{\partial z_{k}}}{\bigg )}{\Bigg .}{\frac {1}{\sqrt {\det {\big (}I-ZS{\big )}}}}{\Bigg \vert }_{z_{j}=0}.}$

La identidad de la función generadora hafniana escrita arriba puede considerarse como una generalización hafniana del teorema maestro de MacMahon , que introduce la función generadora para matrices permanentes y tiene la siguiente forma en términos de la notación introducida:

${\displaystyle {\frac {1}{\det {\big (}I-{\textrm {diag}}(z_{1},z_{2},\ldots ,z_{m})C{\big )}}}=\sum _{\{n_{k}\}}\operatorname {per} {\tilde {C}}(\{n_{k}\})\prod _{k=1}^{m}{\frac {z_{k}^{n_{k}}}{n_{k}!}}}$

Nótese que el teorema maestro de MacMahon surge como un corolario simple de la identidad de la función generadora hafniana debido a la relación . ${\displaystyle \operatorname {per} (C)=\operatorname {haf} {\begin{pmatrix}0&C\\C^{T}&0\end{pmatrix}}}$

No negatividad

Si es una matriz semidefinida positiva hermítica y es una matriz simétrica compleja, entonces ${\displaystyle C}$ ${\displaystyle n\times n}$ ${\displaystyle B}$ ${\displaystyle n\times n}$

${\displaystyle \operatorname {haf} {\begin{pmatrix}B&C\\{\overline {C}}&{\overline {B}}\end{pmatrix}}\geq 0,}$

donde denota el conjugado complejo de . ^[6] ${\displaystyle {\overline {C}}}$ ${\displaystyle C}$

Una forma sencilla de ver esto cuando es semidefinido positivo es observar que, por el teorema de probabilidad de Wick , cuando es un vector aleatorio normal complejo con media , matriz de covarianza y matriz de relación . ${\displaystyle {\begin{pmatrix}C&B\\{\overline {B}}&{\overline {C}}\\\end{pmatrix}}}$ ${\displaystyle \operatorname {haf} {\begin{pmatrix}B&C\\{\overline {C}}&{\overline {B}}\\\end{pmatrix}}=\mathbb {E} \left[\left|X_{1}\dots X_{n}\right|^{2}\right]}$ ${\displaystyle \left(X_{1},\dots ,X_{n}\right)}$ ${\displaystyle 0}$ ${\displaystyle C}$ ${\displaystyle B}$

Este resultado es una generalización del hecho de que la permanente de una matriz semidefinida positiva hermítica es no negativa. Esto corresponde al caso especial que utiliza la relación . ${\displaystyle B=0}$ ${\displaystyle \operatorname {per} (C)=\operatorname {haf} {\begin{pmatrix}0&C\\C^{T}&0\end{pmatrix}}}$

Hafniano de bucle

El hafniano de bucle de una matriz simétrica se define como ${\displaystyle m\times m}$

${\displaystyle \operatorname {lhaf} (A)=\sum _{\rho \in {\mathcal {M}}}\prod _{(i,j)\in \rho }A_{i,j}}$

donde es el conjunto de todas las coincidencias perfectas del gráfico completo en los vértices con bucles , es decir, el conjunto de todas las formas de particionar el conjunto en pares o singletons (tratando un singleton como el par ). ^[7] Por lo tanto, el hafniano de bucle depende de las entradas diagonales de la matriz, a diferencia del hafniano. ^[7] Además, el hafniano de bucle puede ser distinto de cero cuando es impar. ${\displaystyle {\mathcal {M}}}$ ${\displaystyle m}$ ${\displaystyle \{1,2,\dots ,m\}}$ ${\displaystyle (i)}$ ${\displaystyle (i,i)}$ ${\displaystyle m}$

El hafniano de bucle se puede utilizar para contar el número total de coincidencias en un gráfico (perfecto o no perfecto), también conocido como su índice de Hosoya . Específicamente, si se toma la matriz de adyacencia de un gráfico y se establecen los elementos diagonales en 1, entonces el hafniano de bucle de la matriz resultante es igual al número total de coincidencias en el gráfico. ^[7]

También se puede pensar que el hafniano de bucle incorpora una media en la interpretación del hafniano como un momento gaussiano multivariante. Específicamente, nuevamente por el teorema de probabilidad de Wick , el hafniano de bucle de una matriz simétrica real se puede expresar como ${\displaystyle m\times m}$

${\displaystyle \operatorname {lhaf} (A)=\mathbb {E} _{\left(X_{1},\dots ,X_{m}\right)\sim {\mathcal {N}}\left(\operatorname {diag} \left(A\right),A+\lambda I\right)}\left[X_{1}\dots X_{m}\right],}$

¿Dónde está cualquier número lo suficientemente grande como para ser semidefinido positivo? ${\displaystyle \lambda }$ ${\displaystyle A+\lambda I}$

Cálculo

Calcular el hafniano de una matriz (0,1) es #P-completo , porque calcular el permanente de una matriz (0,1) es #P-completo . ^{[4] [7]}

El hafniano de una matriz se puede calcular en el tiempo. ^[7] ${\displaystyle 2n\times 2n}$ ${\displaystyle O(n^{3}2^{n})}$

Si las entradas de una matriz no son negativas, entonces su hafniano puede aproximarse dentro de un factor exponencial en tiempo polinomial. ^[8]

Véase también

• Permanente
• Pfaffian
• Muestreo de bosones

Referencias

1. F. Guerra, en Imaginación y rigor: ensayos sobre la herencia científica de Eduardo R. Caianiello , editado por Settimo Termini, Springer Science & Business Media, 2006, página 98
2. Alexander Barvinok (13 de marzo de 2017). Combinatoria y complejidad de funciones de partición. Springer. p. 93. ISBN 9783319518299.
3. Barvinok, Alexander; Regts, Guus (2019). "Recuento ponderado de puntos enteros en un subespacio". Combinator. Probab. Comp . 28 : 696–719. arXiv : 1706.05423 . doi :10.1017/S0963548319000105. S2CID  126185737.
4. Kocharovsky, Vitaly V.; Kocharovsky, Vladimir V.; Tarasov, Sergey V. (2022). "El teorema maestro de Hafn". Álgebra lineal y sus aplicaciones . 651 . Elsevier BV: 144–161. doi : 10.1016/j.laa.2022.06.021 . ISSN  0024-3795. S2CID  249935016.
5. Rudelson, Mark; Samorodnitsky, Alex; Zeitouni, Ofer (2016). "Hafnianos, emparejamientos perfectos y matrices gaussianas". Anales de probabilidad . 44 (4): 2858–2888. arXiv : 1409.3905 . doi :10.1214/15-AOP1036. S2CID  14458608.
6. Brádler, Kamil; Friedland, Shmuel; Israel, Robert B. (24 de febrero de 2021). "No negatividad para hafnianos de ciertas matrices". Álgebra lineal y multilineal . 70 (19). Informa UK Limited: 4615–4619. arXiv : 1811.10342 . doi :10.1080/03081087.2021.1892022. ISSN  0308-1087. S2CID  119601142.
7. Björklund, Andreas; Gupt, Brajesh; Quesada, Nicolás (2018). "Una fórmula hafniana más rápida para matrices complejas y su evaluación comparativa en una supercomputadora". arXiv : 1805.12498 [cs.DS].
8. Barvinok, Alexander (1999). "Algoritmos de tiempo polinomial para aproximar discriminantes permanentes y mixtos dentro de un factor simplemente exponencial". Estructuras aleatorias y algoritmos . 14 (1). Wiley: 29–61. doi :10.1002/(sici)1098-2418(1999010)14:1<29::aid-rsa2>3.0.co;2-x. hdl : 2027.42/35110 . ISSN  1042-9832.