Пфаффиан

Не путать с функцией Пфаффа , системой Пфаффа или ориентацией Пфаффа .

В математике определитель m × m от всегда кососимметричной матрицы размера можно записать как квадрат многочлена в элементах матрицы, многочлена с целыми коэффициентами, который зависит только m . Когда m нечетно, полином равен нулю. Когда m четно, это ненулевой полином степени m /2, уникальный с точностью до умножения на ±1. Соглашение о кососимметричных трехдиагональных матрицах, приведенное ниже в примерах, затем определяет один конкретный полином, называемый полиномом Пфаффа . Значение этого многочлена, примененное к элементам кососимметричной матрицы, называется пфаффианом этой матрицы. Термин «пфаффианцы» был введен Кэли ( 1852 ), который косвенно назвал их в честь Иоганна Фридриха Пфаффа .

Явно, для кососимметричной матрицы $A$,

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

что было впервые доказано Кэли ( 1849 ), который цитирует Якоби за введение этих полиномов в работы над пфаффовыми системами дифференциальных уравнений. Кэли получает это соотношение, специализируя более общий результат на матрицах, которые отклоняются от кососимметрии только в первой строке и первом столбце. Определителем такой матрицы является произведение пфаффианов двух матриц, полученных путем сначала установки в исходной матрице верхнего левого элемента в ноль, а затем копирования соответственно отрицательного транспонирования первой строки в первый столбец и отрицательного транспонировать первый столбец в первую строку. Это доказывается индукцией путем расширения определителя на миноры и использования приведенной ниже формулы рекурсии.

Примеры

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

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

(3 нечетно, поэтому пфаффиан B равен 0)

$\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.$

Пфаффиан размером 2 n × 2 n кососимметричной трехдиагональной матрицы задается как

$\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}.$

(Обратите внимание, что к этому виду можно привести любую кососимметричную матрицу; см. Спектральную теорию кососимметричной матрицы .)

Формальное определение

Пусть A = ( a _ij ) — 2 n × 2 n кососимметричная матрица размером . Пфаффиан оператора A явно определяется формулой

$\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)}\,,$

где S _{2 n} — симметрическая группа порядка (2 n )! и sn(σ) — сигнатура σ.

Можно использовать кососимметрию A , чтобы избежать суммирования по всем возможным перестановкам . Пусть Π — множество всех разбиений {1, 2, ..., 2 n } на пары без учета порядка. Имеется (2 n )!/(2 ^н п !) = (2 п − 1) !! такие перегородки. Элемент α ∈ Π можно записать как

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

с i _k < j _k и $i_{1}<i_{2}<\cdots <i_{n}$. Позволять

$\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}}$

быть соответствующей перестановкой. Учитывая раздел α, как указано выше, определите

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

Тогда пфаффиан A определяется выражением

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

Пфаффиан n × n кососимметричной матрицы размера для нечетного n определяется равным нулю, поскольку определитель нечетной кососимметричной матрицы равен нулю, поскольку для кососимметричной матрицы $$\det \,A=\det \,A^{\text{T}}=\det \left(-A\right)=(-1)^{n}\det \,A,$$и для n нечетного это означает $\det \,A=0$.

Рекурсивное определение

По соглашению, пфаффиан матрицы 0×0 равен единице. Пфаффиан кососимметричной размером 2 n × 2 n матрицы A с n > 0 можно вычислить рекурсивно как

$\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 }}}),$

где индекс i можно выбрать произвольно, $\theta (i-j)$ – ступенчатая функция Хевисайда , а $A_{{\hat {\imath }}{\hat {\jmath }}}$ обозначает матрицу A , из которой удалены i -я и j -я строки и столбцы. Обратите внимание, что для специального выбора $i=1$ это сводится к более простому выражению:

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

Альтернативные определения

Любой кососимметричной 2 n × 2 n матрице размера A ( a _ij ) можно сопоставить бивектор =

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

где { e ₁ , e ₂ , ..., e _{2 n} } — стандартный базис R ^22н . Тогда пфаффиан определяется уравнением

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

здесь ω ^н обозначает сегментов произведение n копий ω .

Эквивалентно, мы можем рассмотреть бивектор (что более удобно, когда мы не хотим накладывать ограничение суммирования $i<j$): $$\omega '=2\omega =\sum _{i,j}a_{ij}\;e_{i}\wedge e_{j},$$что дает $\omega '^{n}=2^{n}n!\operatorname {pf} (A)\;e_{1}\wedge e_{2}\wedge \cdots \wedge e_{2n}.$

Ненулевое обобщение пфаффиана на нечетномерные матрицы дано в работе де Брейна о кратных интегралах, включающих определители. В частности, для любого $m\times m$-матрица A , мы используем формальное определение, приведенное выше, но полагаем $n=\lfloor m/2\rfloor$. Тогда для нечетного m можно показать, что оно равно обычному пфаффиану $(m+1)\times (m+1)$-мерная кососимметричная матрица, в которую мы добавили $(m+1)$столбец, состоящий из m элементов 1, $(m+1)$-я строка состоит из m элементов −1, а угловой элемент равен нулю. К этой расширенной матрице применяются обычные свойства пфаффианов, например отношение к определителю.

Свойства и личности

Пфаффианы обладают следующими свойствами, аналогичными свойствам определителей.

• Умножение строки и столбца на константу эквивалентно умножению пфаффиана на ту же константу.
• Одновременная замена двух разных строк и соответствующих столбцов меняет знак пфаффиана.
• Кратное число строки и соответствующего столбца, добавленное к другой строке и соответствующему столбцу, не меняет значение пфаффиана.

Используя эти свойства, пфаффианы можно вычислять быстро, подобно вычислению определителей.

Разнообразный

размером 2 n × 2 n Для кососимметричной матрицы A

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

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

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

Для произвольной 2 n × 2 n матрицы B размером

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

Подставив в это уравнение B = A ^м , для всех целых m

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

Доказательство $\operatorname {pf} (BAB^{\text{T}})=\det(B)\operatorname {pf} (A)$:

Как было сказано ранее, $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}.$ То же самое с $BAB^{\mathrm {T} }$: $${\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}}$$где мы определили $f_{k}=\sum _{i}B_{ik}e_{i}$.

С $f_{1}\wedge \cdots \wedge f_{2n}=\det(B)e_{1}\wedge \cdots \wedge e_{2n},$ доказательство закончено.

Доказательство $\operatorname {pf} (A)^{2}=\det(A)$:

С $\operatorname {pf} (A)^{2}=\det(A)$ является уравнением многочленов, его достаточно доказать для вещественных матриц, и оно автоматически применимо и для комплексных матриц.

По спектральной теории кососимметричных вещественных матриц $A=Q\Sigma Q^{\mathrm {T} }$, где $Q$ является ортогональным и $$\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}}$$для действительных чисел $a_{k}$. Теперь применим предыдущую теорему, имеем $pf(A)^{2}=pf(\Sigma )^{2}\det(Q)^{2}=pf(\Sigma )^{2}=\left(\prod a_{i}\right)^{2}=\det(A)$.

Производные тождества

Если A зависит от некоторой переменной x _i , то градиент пфаффиана определяется выражением

${\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),$

а гессиан пфаффиана определяется выражением

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

Отследить личности

Произведение пфаффианов кососимметричных матриц A и B можно представить в виде экспоненты

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

Предположим, что A и B — 2n × 2n кососимметричные матрицы размера , тогда

$\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})$

и Bn ₎ ( s1 _, , s2 _, ... sn _— полиномы Белла .

Блочные матрицы

Для блочно-диагональной матрицы

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

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

Для произвольной размера n × n матрицы M :

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

Часто требуется вычислить пфаффиан кососимметричной матрицы. $S$ с блочной структурой

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

где $M$ и $N$ являются кососимметричными матрицами и $Q$ представляет собой общую прямоугольную матрицу.

Когда $M$ обратима, то есть

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

Это можно видеть из формулы блочной диагонализации Эйткена:

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

Это разложение включает в себя конгруэнтные преобразования , позволяющие использовать свойство Пфаффа. $\operatorname {pf} (BAB^{\mathrm {T} })=\operatorname {det} (B)\operatorname {pf} (A)$.

Аналогично, когда $N$ обратима, то есть

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

как можно увидеть, используя разложение

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

Численный расчет пфаффиана

Предположим, что A — 2n × 2n кососимметричная матрица размера , тогда

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

где $\sigma _{y}$ — вторая матрица Паули , $I_{n}$ является единичной матрицей размерности n , и мы взяли след по логарифму матрицы .

Это равенство основано на тождестве следа

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

и по наблюдению, что ${\textrm {pf}}(\sigma _{y}\otimes I_{n})=(-i)^{n^{2}}$.

Поскольку вычисление логарифма матрицы является сложной вычислительной задачей, вместо этого можно вычислить все собственные значения матрицы. $((\sigma _{y}\otimes I_{n})^{\mathrm {T} }\cdot A)$, возьмите журнал всех этих событий и просуммируйте их. Эта процедура просто использует свойство $\operatorname {tr} {\log {(AB)}}=\operatorname {tr} {\log {(A)}}+\operatorname {tr} {\log {(B)}}$. Это можно реализовать в Mathematica с помощью одного оператора:

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] ]]]]]

Однако этот алгоритм неустойчив, когда пфаффиан велик. Собственные значения $(\sigma _{y}\otimes I_{n})^{\mathrm {T} }\cdot A$ обычно будет комплексным, и логарифм этих комплексных собственных значений обычно считается $[-\pi ,\pi ]$. При суммировании для вещественнозначного пфаффиана аргумент экспоненты будет задан в виде $x+k\pi /2$ для некоторого целого числа $k$. Когда $x$ очень велика, ошибки округления при вычислении результирующего знака комплексной фазы могут привести к ненулевой мнимой составляющей.

Другие (более) эффективные алгоритмы см. в Wimmer 2012 .

Приложения

• Существуют программы численного расчета пфаффиана на различных платформах (Python, Matlab, Mathematica) ( Wimmer 2012 ).
• Пфаффиан — это инвариантный полином кососимметричной матрицы при правильной ортогональной замене базиса. Как таковое это важно в теории характеристических классов . В частности, его можно использовать для определения класса Эйлера риманова многообразия , который используется в обобщенной теореме Гаусса–Бонне .
• Количество идеальных паросочетаний в плоском графе задается пфаффианом, следовательно, его можно вычислить за полиномиальное время с помощью алгоритма FKT . Это удивительно, учитывая, что для общих графов проблема очень сложна (так называемая #P-complete ). Этот результат используется для расчета количества домино разбиений прямоугольника на , статистической суммы моделей Изинга в физике или марковских случайных полей в машинном обучении ( Globerson & Jaakkola 2007 ; Schraudolph & Kamenetsky 2009 ), где основной граф является плоским. . Он также используется для разработки эффективных алгоритмов для некоторых, казалось бы, неразрешимых проблем, включая эффективное моделирование определенных типов ограниченных квантовых вычислений . Прочтите Голографический алгоритм для получения дополнительной информации.

См. также

• Определитель
• Димерная модель
• Порт
• Полимино
• Статистическая механика

Ссылки

• Кэли, Артур (1849). «Сюр-ле-детерминанты неловкости» . Журнал чистой и прикладной математики . 38 :93-96.
• Кэли, Артур (1852). «К теории пермутантов» . Кембриджский и Дублинский математический журнал . VII : 40–51. Перепечатано в Сборнике математических статей, том 2.
• Кастелейн, PW (1961). «Статистика димеров на решетке. I. Число расположений димеров на квадратичной решетке». Физика . 27 (12): 1209–1225. Бибкод : 1961Phy....27.1209K . дои : 10.1016/0031-8914(61)90063-5 .
• Пропп, Джеймс (2004). «Лямбда-определители и домино». arXiv : math/0406301 .
• Глоберсон, Амир; Яаккола, Томми (2007). «Приблизительный вывод с использованием разложения плоского графа» (PDF) . Достижения в области нейронных систем обработки информации 19 . МТИ Пресс.
• Шраудольф, Никол; Каменецкий, Дмитрий (2009). «Эффективный точный вывод в плоских моделях Изинга» (PDF) . Достижения в области нейронных систем обработки информации 21 . МТИ Пресс.
• Джелисс, врач общей практики; Чепмен, Робин Дж. (1996). «Доминирование на шахматной доске». Журнал игр и головоломок . 2 (14): 204–5.
• Селлерс, Джеймс А. (2002). «Плитки домино и произведения чисел Фибоначчи и Пелла» . Журнал целочисленных последовательностей . 5 (1): 02.1.2. Бибкод : 2002JIntS...5...12S .
• Уэллс, Дэвид (1997). Словарь любопытных и интересных чисел Penguin (переработанная редакция). Пингвин. п. 182. ИСБН  0-14-026149-4 .
• Мьюир, Томас (1882). Трактат по теории определителей . Макмиллан и компания онлайн
• Парамесваран, С. (1954). «Кососимметричные определители». Американский математический ежемесячник . 61 (2): 116. дои : 10.2307/2307800 . JSTOR   2307800 .
• Виммер, М. (2012). «Эффективное численное вычисление пфаффиана для плотных и полосчатых кососимметричных матриц». АКМ Транс. Математика. Программное обеспечение 38 : 30.arXiv : 1102.3440 . дои : 10.1145/2331130.2331138 . S2CID   15331538 .
• де Брейн, Н.Г. (1955). «О некоторых кратных интегралах с определителями». Дж. Индийская математика. Соц. 19 : 131–151.

Внешние ссылки

• «Пфаффиан» , Математическая энциклопедия , EMS Press , 2001 [1994]
• Пфаффиан на PlanetMath.org
• Т. Джонс, Пфаффиан и клиновое произведение (демонстрация доказательства соотношения Пфаффиан/детерминант)
• Р. Кеньон и А. Окуньков , Что такое... димер?
• Последовательность OEIS A004003 (Количество плиток домино (или димерных покрытий))
• В. Ледерманн «Заметка о кососимметричных определителях» https://www.researchgate.net/publication/231827602_A_note_on_skew-symmetric_determinants