Пфаффиан

В математике , то определитель из кососимметрических матриц всегда можно записать в виде квадрата многочлена в матричных элементах, многочлен с целыми коэффициентами, зависящих только от размера матрицы. Значение этого полинома, примененное к коэффициентам кососимметричной матрицы, называется пфаффианом этой матрицы. Термин пфаффиан был введен Кэли  ( 1852 г. ), который косвенно назвал их в честь Иоганна Фридриха Пфаффа . Пфаффиан (рассматриваемый как полином) отличен от нуля только при 2 n × 2 nкососимметричные матрицы, в этом случае это многочлен степени n .

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

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

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

Тот факт, что определитель любой кососимметричной матрицы является квадратом многочлена, можно показать, записав матрицу в виде блочной матрицы, затем используя индукцию и исследуя дополнение Шура , которое также является кососимметричным. ^[1]

Примеры [ править ]

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

(Обратите внимание, что любая кососимметричная матрица может быть приведена к этой форме со всеми равными нулю; см. Спектральную теорию кососимметричной матрицы .)${\displaystyle b_{i}}$

Формальное определение [ править ]

Пусть A = ( a _{i, j} ) - кососимметричная матрица размером 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 )! а sgn (σ) - сигнатура σ.

Можно использовать кососимметрию 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 определяется равным нулю, поскольку определитель нечетной кососимметричной матрицы равен нулю, поскольку для кососимметричной матрицы

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

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

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

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

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

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

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

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

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

Свойства и личности [ править ]

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

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

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

Разное [ править ]

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

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

Для произвольного 2 п × 2 п матрицы B ,

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

Производные идентификаторы [ править ]

Если 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 при условии, что A ^T B является положительно определенной матрицей, может быть представлено в виде экспоненты

${\displaystyle {\textrm {pf}}(A)\,{\textrm {pf}}(B)=\exp({\tfrac {1}{2}}\mathrm {tr} \log(A^{\text{T}}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})}$

и B _n ( s ₁ , s ₂ , ..., s _n ) - полиномы Белла .

Матрицы блоков [ править ]

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

${\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^{T}&N\end{pmatrix}}\,}$

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

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

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

Это видно из формулы блочной диагонализации Эйткена, ^{[4] [5] [6]}

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

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

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

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

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

${\displaystyle {\begin{pmatrix}M+QN^{-1}Q^{T}&0\\0&N\end{pmatrix}}={\begin{pmatrix}I&-QN^{-1}\\0&I\end{pmatrix}}{\begin{pmatrix}M&Q\\-Q^{T}&N\end{pmatrix}}{\begin{pmatrix}I&0\\N^{-1}Q^{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})^{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})^{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[KroneckerProduct[PauliMatrix[2], IdentityMatrix[n]], x] ]]]]]

По поводу других эффективных алгоритмов см. ( Wimmer 2012 ).

Приложения [ править ]

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

См. Также [ править ]

• Детерминант
• Модель димера
• Гафнийский
• Полёмино
• Статистическая механика

Примечания [ править ]

Ссылки [ править ]

• Кэли, Артур (1849). "Sur les déterminants gauches" . Журнал für die reine und angewandte Mathematik . 38 : 93–96.CS1 maint: ref=harv (link)
• Кэли, Артур (1852). «К теории перестановок» . Кембриджский и Дублинский математический журнал . VII : 40–51.CS1 maint: ref=harv (link) Печатается в Сборнике математических статей, том 2.
• Kasteleyn, PW (1961). «Статистика димеров на решетке. I. Число расположений димеров на квадратичной решетке». Physica . 27 (12): 1209–1225. Bibcode : 1961Phy .... 27.1209K . DOI : 10.1016 / 0031-8914 (61) 90063-5 .CS1 maint: ref=harv (link)
• Пропп, Джеймс (2004). «Лямбда-определители и домино-мозаики». arXiv : math / 0406301 .CS1 maint: ref=harv (link)
• Глоберсон, Амир; Яаккола, Томми (2007). «Приближенный вывод с использованием разложения планарного графа» (PDF) . Достижения в системах обработки нейронной информации 19 . MIT Press.CS1 maint: ref=harv (link).
• Шраудольф, Никол; Каменецкий, Дмитрий (2009). «Эффективный точный вывод в планарных моделях Изинга» (PDF) . Достижения в системах обработки нейронной информации 21 . MIT Press.CS1 maint: ref=harv (link).
• Jeliss, GP; Чепмен, Робин Дж. (1996). «Доминирование на шахматной доске». Журнал "Игры и головоломки" . 2 (14): 204–5.CS1 maint: ref=harv (link)
• Продавцы, Джеймс А. (2002). «Плитки домино и произведения чисел Фибоначчи и Пелла» . Журнал целочисленных последовательностей . 5 (1): 02.1.2.CS1 maint: ref=harv (link)
• Уэллс, Дэвид (1997). Словарь любопытных и интересных чисел Penguin (отредактированная ред.). п. 182. ISBN. 0-14-026149-4.CS1 maint: ref=harv (link)
• Мьюир, Томас (1882). Трактат по теории детерминант . Macmillan and Co.CS1 maint: ref=harv (link) В сети
• Парамешваран, С. (1954). «Кососимметричные детерминанты». Американский математический ежемесячник . 61 (2): 116. DOI : 10,2307 / 2307800 . JSTOR  2307800 .CS1 maint: ref=harv (link)
• Виммер, М. (2012). «Эффективное численное вычисление пфаффиана для плотных и ленточных кососимметричных матриц». ACM Trans. Математика. Софтв. 38 : 30. arXiv : 1102.3440 . DOI : 10.1145 / 2331130.2331138 .CS1 maint: ref=harv (link)
• де Брюйн, Н.Г. (1955). «О некоторых кратных интегралах с определителями». J. Indian Math. Soc. 19 : 131–151.CS1 maint: ref=harv (link)

Внешние ссылки [ править ]

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