Вычисление постоянного

В линейной алгебре , то вычисление перманентный из матрицы является проблемой , которая считается более сложным , чем при вычислении определителя матрицы , несмотря на кажущееся сходство определений.

Перманент определяется аналогично определителю как сумма произведений наборов элементов матрицы, лежащих в разных строках и столбцах. Однако, если определитель взвешивает каждый из этих продуктов со знаком ± 1 на основе четности набора , постоянный элемент взвешивает их все со знаком +1.

Хотя определитель можно вычислить за полиномиальное время методом исключения Гаусса , обычно считается, что перманент нельзя вычислить за полиномиальное время. В теории сложности вычислений , теорема Valiant утверждает , что вычисление перманента является # P-трудно , и даже # P-полной для матриц , в которых все элементы равны 0 или 1 Valiant (1979) . Это помещает вычисление перманента в класс задач, которые, как считается, вычислить еще сложнее, чем NP . Известно, что вычисление перманента невозможно для схем ACC ^0, однородных по пространству журнала ( Allender & Gore 1994).)

Разработка как точных, так и приближенных алгоритмов вычисления перманента матрицы является активной областью исследований.

Определение и наивный алгоритм [ править ]

Перманент в п матрицы с размерностью п матрица = ( _{I, J} ) определяются как

${\ displaystyle \ operatorname {perm} (A) = \ sum _ {\ sigma \ in S_ {n}} \ prod _ {i = 1} ^ {n} a_ {i, \ sigma (i)}.}$

Сумма здесь распространяется на все элементы σ симметрической группы S _n , т.е. на все перестановки чисел 1, 2, ..., n . Эта формула отличается от соответствующей формулы для определителя только тем, что в определителе каждое произведение умножается на знак перестановки σ, в то время как в этой формуле каждое произведение без знака. Формула может быть напрямую переведена в алгоритм, который наивно расширяет формулу, суммируя по всем перестановкам и в сумме, умножая каждую запись матрицы. Это требует n! n арифметических операций.

Формула Райзера [ править ]

Самый известный ^[1] общий точный алгоритм принадлежит HJ Ryser  ( 1963 ). Метод Райзера основан на формуле включения-исключения, которая может быть дана ^[2] следующим образом: пусть получено из A путем удаления k столбцов, пусть будет произведением строковых сумм и пусть будет суммой значений над всем возможным . потом${\ displaystyle A_ {k}}$${\ Displaystyle P (A_ {k})}$${\ displaystyle A_ {k}}$${\ displaystyle \ Sigma _ {k}}$${\ Displaystyle P (A_ {k})}$${\ displaystyle A_ {k}}$

${\ displaystyle \ operatorname {perm} (A) = \ sum _ {k = 0} ^ {n-1} (- 1) ^ {k} \ Sigma _ {k}.}$

Его можно переписать в терминах элементов матрицы следующим образом ^[3]

${\displaystyle \operatorname {perm} (A)=(-1)^{n}\sum _{S\subseteq \{1,\dots ,n\}}(-1)^{|S|}\prod _{i=1}^{n}\sum _{j\in S}a_{ij}.}$

Формулу Райзера можно вычислить с помощью арифметических операций или путем обработки наборов в порядке кода Грея . ^[4]${\displaystyle O(2^{n-1}n^{2})}$${\displaystyle O(2^{n-1}n)}$${\displaystyle S}$

Формула Баласубраманиана – Бакса – Франклина – Глинна [ править ]

Еще одну формулу, которая кажется такой же быстрой, как у Райзера (или, возможно, даже вдвое быстрее), можно найти в двух кандидатских диссертациях. диссертации; см. ( Balasubramanian 1980 ), ( Bax 1998 ); также ( Bax & Franklin 1996 ). Методы нахождения формулы совершенно разные, они связаны с комбинаторикой алгебры Мюра и теорией конечных разностей соответственно. Другой путь, связанный с теорией инвариантов, - это поляризационное тождество для симметричного тензора ( Glynn 2010 ). Формула обобщается на бесконечно много других, как обнаружено всеми этими авторами, хотя неясно, быстрее ли они, чем базовая. См. ( Glynn 2013 ).

Простейшая известная формула этого типа (когда характеристика поля не равна двум):

${\displaystyle \operatorname {perm} (A)={\frac {1}{2^{n-1}}}\left[\sum _{\delta }\left(\prod _{k=1}^{n}\delta _{k}\right)\prod _{j=1}^{n}\sum _{i=1}^{n}\delta _{i}a_{ij}\right],}$

где внешняя сумма берется по всем векторам .${\displaystyle 2^{n-1}}$${\displaystyle \delta =(\delta _{1}=1,\delta _{2},\dots ,\delta _{n})\in \{\pm 1\}^{n}}$

Особые случаи [ править ]

Планар и К _3,3 -свободный [ править ]

Количество идеальных совпадений в двудольном графе подсчитывается с помощью перманента матрицы двойного сопряжения графа , а перманент любой матрицы 0-1 можно интерпретировать таким образом как количество идеальных совпадений в графе. Для плоских графов (независимо от двудольности) алгоритм FKT вычисляет количество точных сопоставлений за полиномиальное время, изменяя знаки тщательно выбранного подмножества элементов в матрице Тутте графа, так что пфаффиан результирующего перекоса - симметричная матрица ( квадратный корень из ее определителя) - количество точных совпадений. Этот метод может быть обобщен на графики , которые не содержат подграф гомеоморфных к полному двудольному графу K _3,3 . ^[5]

Джордж Полиа задал вопрос ^[6] о том, когда можно изменить знаки некоторых элементов матрицы 01 A так, чтобы определитель новой матрицы был перманентом матрицы A. Не все матрицы 01 являются "конвертируемыми" таким образом; на самом деле известно ( Marcus & Minc (1961) ), что не существует линейного отображения, такого, что для всех матриц . Характеристика «конвертируемых» матриц была дана Литтлом (1975), который показал, что такие матрицы - это в точности те, которые являются матрицей взаимосопряженности двудольных графов, которые имеют ориентацию Пфаффа : такую ​​ориентацию ребер, что для каждого четного цикла, для которого${\displaystyle T}$${\displaystyle \operatorname {per} \,T(A)=\det A}$${\displaystyle n\times n}$${\displaystyle A}$${\displaystyle C}$${\displaystyle G\setminus C}$имеет полное совпадение, имеется нечетное количество ребер, направленных вдоль C (и, следовательно, нечетное число с противоположной ориентацией). Также было показано, что эти графы - это именно те графы, которые не содержат подграф, гомеоморфный , как указано выше.${\displaystyle K_{3,3}}$

Вычисление по модулю числа [ править ]

По модулю 2 перманент совпадает с определителем, поскольку он также может быть вычислен по модулю времени для . Однако очень сложно вычислить перманент по модулю любого числа, не являющегося степенью 2. Valiant (1979)${\displaystyle (-1)\equiv 1{\pmod {2}}.}$${\displaystyle 2^{k}}$${\displaystyle O(n^{4k-3})}$${\displaystyle k\geq 2}$

Глинн (2010) приводит различные формулы для вычисления по простому модулю p . Во-первых, есть символьные вычисления с частными производными.

Во-вторых, для p = 3 существует следующая формула для nxn-матрицы , включающая главные миноры матрицы ( Kogan (1996) ): ${\displaystyle A}$

${\displaystyle \operatorname {per} (A)=(-1)^{n}\Sigma _{J\subseteq \{1,\dots ,n\}}\det(A_{J})\det(A_{\bar {J}}),}$

где - подматрица матрицы, индуцированной строками и столбцами матрицы, проиндексированной с помощью , и является дополнением к in , в то время как определитель пустой подматрицы определяется равным 1.${\displaystyle A_{J}}$${\displaystyle A}$${\displaystyle A}$${\displaystyle J}$${\displaystyle {\bar {J}}}$${\displaystyle J}$${\displaystyle \{1,\dots ,n\}}$

(На самом деле это разложение можно обобщить на произвольную характеристику p как следующую пару двойственных тождеств:

${\displaystyle \operatorname {per} (A)=(-1)^{n}\Sigma _{{J_{1}},...,{J_{p-1}}}\det(A_{J_{1}})...\det(A_{J_{p-1}})}$

${\displaystyle \operatorname {det} (A)=(-1)^{n}\Sigma _{{J_{1}},...,{J_{p-1}}}\operatorname {per} (A_{J_{1}})...\operatorname {per} (A_{J_{p-1}})}$

где в обеих формулах сумма берется по всем (p-1) -наборам, которые являются разбиениями набора на p-1 подмножество, некоторые из которых, возможно, пусты.${\displaystyle {J_{1}},...,{J_{p-1}}}$${\displaystyle \{1,\dots ,n\}}$

Первая формула обладает аналогом для гафниана симметричного и нечетного p:${\displaystyle A}$

${\displaystyle \operatorname {haf} ^{2}(A)=(-1)^{n}\Sigma _{{J_{1}},...,{J_{p-1}}}\det(A_{J_{1}})...\det(A_{J_{p-1}})(-1)^{|J_{1}|+...+|J_{(p-1)/2}|}}$

с суммой, взятой по тому же набору индексов. Кроме того, в характеристике нуля аналогичное выражение свертки сумма с участием как постоянного , так и определитель дает гамильтонов цикл многочлен (определяется как , где есть множество п-перестановок , имеющие только один цикл): . В характеристике 2 последнее равенство превращается в то, что, следовательно, дает возможность полиномиально вычислить полином гамильтонова цикла любой унитарной (то есть такой, что где - единичная nxn-матрица), потому что каждый минор такой матрицы совпадает со своим алгебраическим дополнением : где${\displaystyle \operatorname {ham} (A)=\sum _{\sigma \in H_{n}}\prod _{i=1}^{n}a_{i,\sigma (i)}}$${\displaystyle {H_{n}}}$${\displaystyle \operatorname {ham} (A)=\Sigma _{J\subseteq \{2,\dots ,n\}}\det(A_{J})\operatorname {per} (A_{\bar {J}})(-1)^{|J|}}$${\displaystyle \operatorname {ham} (A)=\Sigma _{J\subseteq \{2,\dots ,n\}}\det(A_{J})\operatorname {det} (A_{\bar {J}})}$ ${\displaystyle U}$${\displaystyle U^{T}U=I}$${\displaystyle I}$${\displaystyle \operatorname {ham} (U)=\operatorname {det} ^{2}(U+I_{/1})}$${\displaystyle I_{/1}}$является единичной nxn-матрицей с индексом 1,1, замененным на 0. Более того, она, в свою очередь, может быть дополнительно обобщена для унитарной nxn-матрицы, как где - подмножество {1, ..., n} , является единичной nxn-матрицей с элементами индексов k, k, замененными на 0 для всех k, принадлежащих к , и мы определяем где - множество n-перестановок, каждый цикл которых содержит хотя бы один элемент из .)${\displaystyle U}$${\displaystyle \operatorname {ham_{K}} (U)=\operatorname {det} ^{2}(U+I_{/K})}$${\displaystyle K}$${\displaystyle I_{/K}}$${\displaystyle K}$${\displaystyle \operatorname {ham_{K}} (A)=\sum _{\sigma \in H_{n}{(K)}}\prod _{i=1}^{n}a_{i,\sigma (i)}}$${\displaystyle {H_{n}{(K)}}}$${\displaystyle K}$

Из этой формулы вытекают следующие тождества над полями характеристики 3:

для любого обратимого ${\displaystyle A}$

${\displaystyle \operatorname {per} (A^{-1})\operatorname {det} ^{2}(A)=\operatorname {per} (A)}$;

для любой унитарной , то есть квадратной матрицы такой, что где - единичная матрица соответствующего размера,${\displaystyle U}$${\displaystyle U}$${\displaystyle U^{T}U=I\,}$${\displaystyle I}$

${\displaystyle \operatorname {per} ^{2}(U)=\det(U+V)\det(-U)}$

где - матрица, элементами которой являются кубики соответствующих элементов матрицы .${\displaystyle V}$${\displaystyle U}$

Также было показано ( Kogan (1996) ), что если мы определим квадратную матрицу как k-полуунитарную при = k , перманент 1-полуунитарной матрицы вычислим за полиномиальное время над полями характеристики 3, в то время как для k > 1 задача становится # 3-P-полной . (Параллельная теория касается полинома гамильтонова цикла в характеристике 2: хотя вычисление его на унитарных матрицах возможно за полиномиальное время, проблема # 2-P-полная для k-полуунитарных матриц для любого k> 0). Последний результат был существенно расширен в 2017 г. ( Knezevic & Cohen (2017) ), и было доказано, что в${\displaystyle A}$${\displaystyle rank(A^{T}A-I\,)}$Для характеристики 3 существует простая формула, связывающая перманенты квадратной матрицы и ее частичного обратного (для и, будучи квадратными, будучи обратимыми ):${\displaystyle A_{11}}$${\displaystyle A_{22}}$${\displaystyle A_{11}}$

${\displaystyle \operatorname {per} \left({\begin{matrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{matrix}}\right)=\operatorname {det} ^{2}\left(A_{11}\right)\operatorname {per} \left({\begin{matrix}A_{11}^{-1}&A_{11}^{-1}A_{12}\\A_{21}A_{11}^{-1}&A_{22}-A_{21}A_{11}^{-1}A_{12}\end{matrix}}\right)}$

и это позволяет за полиномиальное время сократить вычисление перманента матрицы размера nxn с подмножеством из k или k-1 строк, выражаемых как линейные комбинации другого (непересекающегося) подмножества из k строк, до вычисления перманента матрицы ( nk) x (nk) - или (n-k + 1) x (n-k + 1) -матрица соответственно, поэтому введен оператор сжатия (аналогичный гауссовской модификации, применяемой для вычисления определителя), который «сохраняет» постоянный в характеристике 3. (Аналогично, стоит отметить, что полином гамильтонова цикла в характеристике2 также обладает своими инвариантными матричными сжатиями, принимая во внимание тот факт, что ham (A) = 0 для любой nxn-матрицы A, имеющей три равных строки, или, если n> 2, пару индексов i, j таких, что ее i -я и j-я строки идентичны, и его i-й и j-й столбцы также идентичны.) Закрытие этого оператора определяется как предел его последовательного применения вместе с преобразованием транспонирования (используется каждый раз, когда оператор покидает матрица без изменений) также является отображением оператора, когда применяется к классам матриц, один класс к другому. В то время как оператор сжатия отображает класс 1-полуунитарных матриц в себя и классы унитарных и 2 -полуунитарных матриц , сжатие-замыкание 1-полуунитарного класса (а также класса полученных матриц от унитарногоединиц путем замены одной строки произвольным вектором-строкой - перманент такой матрицы через разложение Лапласа представляет собой сумму перманентов 1-полуунитарных матриц и, соответственно, вычислимых за полиномиальное время) пока неизвестен и напряженно связанных с общей проблемой вычислительной сложности перманента в характеристике 3 и главным вопросом о сравнении P с NP : как было показано в ( Knezevic & Cohen (2017) ), если такое сжатие-замыкание представляет собой набор всех квадратных матриц над поле характеристики 3 или, по крайней мере, содержит матричный класс, в котором вычисление перманента является # 3-P-полным (как класс 2-полуунитарных матриц), то перманент вычислим за полиномиальное время в этомхарактеристика .

Кроме того, была сформулирована задача нахождения и классификации любых возможных аналогов сохраняющих перманентность сжатий, существующих в характеристике 3 для других простых характеристик ( Knezevic & Cohen (2017) ), при этом дается следующее тождество для матрицы nxn и двух n-векторов (имеющий все свои записи из набора {0, ..., p-1}) и такой, что , действительный в произвольной простой характеристике p:${\displaystyle A}$${\displaystyle \alpha }$${\displaystyle \beta }$${\displaystyle {\sum _{i=1}^{n}\alpha _{i}}={\sum _{j=1}^{n}\beta _{j}}}$

${\displaystyle \operatorname {per} (A^{\left(\alpha ,\beta \right)})=\operatorname {det} ^{p-1}(A)\operatorname {per} \left(A^{-1}\right)^{\left((p-1\right){\vec {1}}_{n}-\beta ,\left(p-1\right){\vec {1}}_{n}-\alpha )}(\prod _{i=1}^{n}\alpha _{i}!)(\prod _{j=1}^{n}\beta _{j}!)\left(-1\right)^{n+\sum _{i=1}^{n}\alpha _{i}}}$

где для nxm-матрицы , n-вектора и m-вектора оба вектора имеют все свои элементы из набора {0, ..., p-1}, обозначает матрицу, полученную через повторение раз ее i-го строка для i = 1, ..., n и умножение на ее j-й столбец для j = 1, ..., m (если кратность некоторой строки или столбца равна нулю, это будет означать, что строка или столбец были удалены, и, следовательно, это понятие является обобщением понятия подматрицы), и${\displaystyle M}$${\displaystyle x}$${\displaystyle y}$${\displaystyle M^{(x,y)}}$${\displaystyle M}$${\displaystyle x_{i}}$${\displaystyle y_{j}}$${\displaystyle {\vec {1}}_{n}}$обозначает n-вектор, все элементы которого равны единице. Это тождество является точным аналогом классической формулы, выражающей минор матрицы через минор ее инверсии, и, следовательно, демонстрирует (еще раз) своего рода двойственность между определителем и перманентом как относительными имманантами. (На самом деле это собственный аналог гафниана симметричного и нечетного простого числа p ).${\displaystyle A}$${\displaystyle \operatorname {haf} ^{2}(A^{\left(\alpha ,\alpha \right)})=\operatorname {det} ^{p-1}(A)\operatorname {haf} ^{2}\left(A^{-1}\right)^{\left((p-1\right){\vec {1}}_{n}-\alpha ,\left(p-1\right){\vec {1}}_{n}-\alpha )}(\prod _{i=1}^{n}\alpha _{i}!)^{2}(-1)^{n(p-1)/2+n+\sum _{i=1}^{n}\alpha _{i}}}$

И, как еще более широкое обобщение для частичного обратного случая в отличной характеристике р, для , будучи квадратным, будучи обратим и размером х , а , имеет место также тождество${\displaystyle A_{11}}$${\displaystyle A_{22}}$${\displaystyle A_{11}}$${\displaystyle {n_{1}}}$${\displaystyle {n_{1}}}$${\displaystyle {\sum _{i=1}^{n}\alpha _{i}}={\sum _{j=1}^{n}\beta _{j}}}$

${\displaystyle \operatorname {per} \left({\begin{matrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{matrix}}\right)^{\left(\alpha ,\beta \right)}=\operatorname {det} ^{p-1}(A_{11})\operatorname {per} \left({\begin{matrix}A_{11}^{-1}&A_{11}^{-1}A_{12}\\A_{21}A_{11}^{-1}&A_{22}-A_{21}A_{11}^{-1}A_{12}\end{matrix}}\right)^{\left((p-1\right){\vec {1}}_{n}-\beta ,\left(p-1\right){\vec {1}}_{n}-\alpha )}(\prod _{i=1}^{n}\alpha _{1,i}!)(\prod _{j=1}^{n}\beta _{1,j}!)\left(-1\right)^{n_{1}+\sum _{i=1}^{n}\alpha _{1,i}}}$

где общие векторы кратности строки / столбца и для матрицы генерируют соответствующие векторы кратности строки / столбца и , s, t = 1,2, для ее блоков (то же самое касается частичного обратного значения в правой части равенства).${\displaystyle \alpha }$${\displaystyle \beta }$${\displaystyle A}$${\displaystyle \alpha _{s}}$${\displaystyle \beta _{t}}$${\displaystyle A}$

Приблизительный расчет [ править ]

Когда элементы A неотрицательны, перманент может быть вычислен приблизительно за вероятностное полиномиальное время с точностью до ε M , где M - значение перманента, а ε> 0 - произвольно. Другими словами, существует полностью полиномиальная схема рандомизированной аппроксимации (FPRAS) ( Jerrum, Vigoda & Sinclair (2001) ). harvtxt error: no target: CITEREFJerrumVigodaSinclair2001 (help)

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

Можно приблизительно подсчитать количество идеальных совпадений на графике с помощью самовосстановления перманента, используя FPAUS в сочетании с хорошо известным сокращением от выборки к подсчету, как это сделали Джеррам, Валиант и Вазирани (1986) . Позвольте обозначить количество совершенных пар в . Грубо говоря, для любого конкретного края в , путем отбора проб много паросочетаний в и подсчете , как многие из них является паросочетание в , можно получить оценку отношения . Тогда число равно , где может быть аппроксимировано рекурсивным применением того же метода. harvtxt error: no target: CITEREFJerrumValiantVazirani1986 (help)${\displaystyle M(G)}$${\displaystyle G}$${\displaystyle e}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G\setminus e}$${\displaystyle \rho ={\frac {M(G)}{M(G\setminus e)}}}$${\displaystyle M(G)}$${\displaystyle \rho M(G\setminus e)}$${\displaystyle M(G\setminus e)}$

Другой класс матриц, для которых перманент может быть вычислен приближенно, - это набор положительно-полуопределенных матриц (теоретико-сложная задача аппроксимации перманента таких матриц с точностью до мультипликативной ошибки считается открытой ^[7] ). Соответствующий рандомизированный алгоритм основан на модели отбора бозонов и использует инструменты, свойственные квантовой оптике , для представления перманента положительно-полуопределенных матриц как ожидаемого значения конкретной случайной величины. Последний затем аппроксимируется его выборочным средним. ^[8]Этот алгоритм для определенного набора положительно-полуопределенных матриц приближает их перманент за полиномиальное время с точностью до аддитивной ошибки, которая более надежна, чем стандартный классический алгоритм Гурвица с полиномиальным временем. ^[9]

Заметки [ править ]

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

Дальнейшее чтение [ править ]

• Барвинок, А. (2017), «Аппроксимация перманентов и гафнианов», Дискретный анализ , arXiv : 1601.07518 , doi : 10.19086 / da.1244 , S2CID  397350.