Пфаффиан - Pfaffian

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

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

${ 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п × 2п кососимметричный трехдиагональная матрица дается как

${ 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}}$ равно нулю; видеть Спектральная теория кососимметричной матрицы.)

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

Позволять А = (а_{я, j}) быть 2п × 2п кососимметричная матрица. Пфаффианцы А явно определяется формулой

${ 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п это симметричная группа порядка (2п)! а sgn (σ) - подпись из σ.

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

${ Displaystyle альфа = {(i_ {1}, j_ {1}), (i_ {2}, j_ {2}), cdots, (i_ {n}, j_ {n}) }}$

с я_k < j_k и ${ displaystyle i_ {1}$. Позволять

${ 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_ { п} конец {bmatrix}}}$

- соответствующая перестановка. Для данного разбиения α, как указано выше, определим

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

Пфаффианцы А тогда дается

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

Пфаффиан п×п кососимметричная матрица для п odd определяется равным нулю, поскольку определитель нечетной кососимметричной матрицы равен нулю, поскольку для кососимметричной матрицы

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

и для п странно, это подразумевает ${ Displaystyle Det , А = 0}$.

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

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

${ displaystyle operatorname {pf} (A) = sum _ {{j = 1} atop {j neq i}} ^ {2n} (- 1) ^ {i + j + 1 + theta (ij )} a_ {ij} operatorname {pf} (A _ {{ hat { imath}} { hat { jmath}}}),}$

где индекс я можно выбрать произвольно, ${ Displaystyle тета (я-к)}$ это Ступенчатая функция Хевисайда, и ${ Displaystyle А _ {{ шляпа { imath}} { шляпа { jmath}}}}$ обозначает матрицу А с обоими я-й и j-ые строки и столбцы удалены.^[2] Обратите внимание, как для особого выбора ${ displaystyle i = 1}$ это сводится к более простому выражению:

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

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

Каждому кососимметричному 2п×2п матрица А =(а_ij) а бивектор

${ displaystyle omega = sum _ {i$

куда {е₁, е₂, ..., е_2п} - стандартная основа р²ⁿ. Тогда пфаффиан определяется уравнением

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

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

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

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

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

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

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

Разное

Для 2п × 2п кососимметричная матрица А

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

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

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

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

Если А зависит от некоторой переменной Икс_я, то градиент пфаффиана равен

${ 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 }}}верно).}$

Идентификаторы трассировки

Произведение пфаффианов кососимметричных матриц А и B при условии, что А^ТB это положительно определенная матрица можно представить в виде экспоненты

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

Предполагать А и B находятся 2n × 2n кососимметричные матрицы, то

${ Displaystyle mathrm {pf} (A) , mathrm {pf} (B) = { tfrac {1} {n!}} B_ {n} (s_ {1}, s_ {2}, ldots , s_ {n}), qquad mathrm {где} qquad s_ {l} = - { tfrac {1} {2}} (l-1)! , mathrm {tr} ((AB) ^ {l})}$

и B_п(s₁,s₂,...,s_п) находятся Полиномы Белла.

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

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

${ 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:

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

Это разложение включает преобразования конгруэнтности которые позволяют использовать свойство pfaffian ${ 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 конец {pmatrix}}.}$

Численное вычисление пфаффиана

Предполагать А это 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),}$

куда ${ 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}}}$.

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

Pf [x_]: = Модуль [{n = Размеры [x] [[1]] / 2}, I ^ (n ^ 2) Exp [1/2 Всего [Журнал [Собственные значения [Dot [KroneckerProduct [PauliMatrix [2]] , IdentityMatrix [n]], x]]]]]]

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

Приложения

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

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

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

Примечания

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

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

внешняя ссылка

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