Пфаффиан

Квадратный корень из определителя кососимметричной квадратной матрицы

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

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

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

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

Примеры

${\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 нечетно, поэтому пфаффиан B равен 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.}$

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

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

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

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

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

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

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

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

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

с i _k < j _k и . Позволять ${\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}}}$

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

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

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

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

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

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

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

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

где индекс i может быть выбран произвольно, является ступенчатой ​​функцией Хевисайда и обозначает матрицу A , в которой удалены как i -я, так и j -я строки и столбцы. ^[1] Обратите внимание, как для специального выбора это сводится к более простому выражению: ${\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 }}}).}$

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

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

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

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

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

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

Эквивалентно, мы можем рассмотреть бивектор (что более удобно, когда мы не хотим накладывать ограничение суммирования ): что дает ${\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}.}$

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

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

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

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

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

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

Для кососимметричной матрицы A размером 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).}$

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

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

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

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

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

Как было сказано ранее, то же самое с : где мы определили . ${\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}}$

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

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

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

По спектральной теории кососимметричных вещественных матриц , , где ортогонально и для вещественных чисел . Теперь применим предыдущую теорему, имеем . ${\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)}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где и – кососимметричные матрицы, – общая прямоугольная матрица. ${\displaystyle M}$ ${\displaystyle N}$ ${\displaystyle Q}$

Когда обратимо, то ${\displaystyle M}$

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

Это можно видеть из формулы блочной диагонализации Эйткена, ^{[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}}.}$

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

Аналогично, когда обратимо, имеем ${\displaystyle N}$

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

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

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

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

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

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

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

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

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

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

Поскольку вычисление логарифма матрицы является сложной вычислительной задачей, вместо этого можно вычислить все собственные значения , взять их логарифм и просуммировать их. Эта процедура просто использует это свойство . Это можно реализовать в Mathematica с помощью одного оператора: ${\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] ]]]]]

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

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

Приложения

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

Смотрите также

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

Примечания

1. «Архивная копия» (PDF) . Архивировано из оригинала (PDF) 5 марта 2016 г. Проверено 31 марта 2015 г.{{cite web}}: CS1 maint: archived copy as title (link)
2. Брюйн, де, Н.Г. (1955). «О некоторых кратных интегралах с определителями». Журнал Индийского математического общества . Новая серия. 19 : 133–151. ISSN  0019-5839.{{cite journal}}: CS1 maint: multiple names: authors list (link)
3. AC Эйткен. Определители и матрицы. Оливер и Бойд, Эдинбург, четвертое издание, 1939 г.
4. Чжан, Фучжэнь, изд. Дополнение Шура и его приложения. Том. 4. Springer Science & Business Media, 2006.
5. Банч, Джеймс Р. «Заметки об устойчивом разложении кососимметричных матриц». Математика вычислений 38.158 (1982): 475–479.

Рекомендации

• Кэли, Артур (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. MIT Press.
• Шраудольф, Никол; Каменецкий, Дмитрий (2009). «Эффективный точный вывод в плоских моделях Изинга» (PDF) . Достижения в области нейронных систем обработки информации 21. MIT Press.
• Джелисс, врач общей практики; Чепмен, Робин Дж. (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