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

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

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

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

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

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

Перманент n размера x n матрицы A = ( a _i,j ) определяется как

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

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

Формула дрожи

Самый известный общий точный алгоритм принадлежит Х. Дж. Райзеру ( 1963 ).Метод Райзера основан на формуле включения-исключения , которую можно записать следующим образом: Пусть $A_{k}$ получить из A удалением k столбцов, пусть $P(A_{k})$ быть произведением сумм строк $A_{k}$, и пусть $\Sigma _{k}$ быть суммой значений $P(A_{k})$ из всех возможных $A_{k}$. Затем

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

Его можно переписать с точки зрения элементов матрицы следующим образом:

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

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

Формула Баласубраманиана – Бакса – Франклина – Глинна

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

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

$\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],$

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

Особые случаи

Планарный и К _3,3 -свободный

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

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

Вычисление по модулю числа

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

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

Во-вторых, для p = 3 существует следующая формула для n×n-матрицы $A$ матрицы , с участием главных миноров ( Коган (1996) ):

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

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

Приведенное выше разложение можно обобщить на произвольную характеристику p как следующую пару двойственных тождеств: $${\begin{aligned}\operatorname {per} (A)&=(-1)^{n}\sum _{{J_{1}},\ldots ,{J_{p-1}}}\det(A_{J_{1}})\dotsm \det(A_{J_{p-1}})\\\det(A)&=(-1)^{n}\sum _{{J_{1}},\ldots ,{J_{p-1}}}\operatorname {per} (A_{J_{1}})\dotsm \operatorname {per} (A_{J_{p-1}})\end{aligned}}$$где в обеих формулах сумма берется по всем ( p − 1)-наборам ${J_{1}},\ldots ,{J_{p-1}}$ это разделы множества $\{1,\dots ,n\}$ на p − 1 подмножества, некоторые из которых, возможно, пусты.

Первая формула имеет аналог гафниана симметричного $A$ и нечетное p:

$$\operatorname {haf} ^{2}(A)=(-1)^{n}\sum _{{J_{1}},\ldots ,{J_{p-1}}}\det(A_{J_{1}})\dotsm \det(A_{J_{p-1}})(-1)^{|J_{1}|+\dots +|J_{(p-1)/2}|}$$

с суммой, взятой по тому же набору индексов. Более того, в нулевой характеристике аналогичное выражение суммы свертки, включающее как перманент, так и определитель, дает полином гамильтонова цикла (определяемый как ${\textstyle \operatorname {ham} (A)=\sum _{\sigma \in H_{n}}\prod _{i=1}^{n}a_{i,\sigma (i)}}$ где $H_{n}$ — множество n-перестановок, имеющих только один цикл): $$\operatorname {ham} (A)=\sum _{J\subseteq \{2,\dots ,n\}}\det(A_{J})\operatorname {per} (A_{\bar {J}})(-1)^{|J|}.$$

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

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

для любого обратимого $A$

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

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

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

где $V$ — матрица, элементы которой являются кубами соответствующих записей $U$.

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

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

и позволяет за полиномиальное время свести вычисление перманента n × n -матрицы с подмножеством из k или k - 1 строк, выражаемых в виде линейных комбинаций другого (непересекающегося) подмножества из k строк, к вычислению перманента ( n − k )×( n − k )- или ( n − k + 1) × ( n − k + 1)-матрицу соответственно, тем самым введя оператор сжатия (аналог гауссовой модификации, примененной для вычисления определителя ), который «сохраняет» перманент в характеристике 3. (Аналогично следует отметить, что полином гамильтонова цикла в характеристике 2 также обладает своими инвариантными матричными сжатиями, учитывая тот факт, что ham( A ) = 0 для любого n × n -матрица 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) ), при этом дано следующее тождество для n × n матрицы размера $A$ и два n -вектора (все элементы которых принадлежат набору {0, ..., p − 1}) $\alpha$ и $\beta$ такой, что ${\textstyle {\sum _{i=1}^{n}\alpha _{i}=\sum _{j=1}^{n}\beta _{j}}}$, действительный в произвольной простой характеристике p :

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

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

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

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

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

Приблизительный расчет

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

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

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

Другой класс матриц, для которых перманент представляет особый интерес, — это положительно-полуопределенные матрицы . Используя технику подсчета Стокмейера , их можно вычислить внутри класса ${\textsf {BPP}}^{\textsf {NP}}$, но в целом это считается неосуществимым классом. Аппроксимировать перманенты PSD-матриц в пределах субэкспоненциального множителя NP-трудно, и предполагается, что это будет ${\textsf {BPP}}^{\textsf {NP}}$-жесткий Если наложить дополнительные ограничения на спектр , известны более эффективные алгоритмы. Один рандомизированный алгоритм основан на модели выборки бозонов и использует инструменты, присущие квантовой оптике , для представления перманента положительно-полуопределенных матриц как ожидаемого значения конкретной случайной величины. Последнее затем аппроксимируется его выборочным средним значением. Этот алгоритм для некоторого набора положительно-полуопределенных матриц аппроксимирует их постоянные за полиномиальное время с точностью до аддитивной ошибки, что более надежно, чем у стандартного классического алгоритма с полиномиальным временем Гурвица.

Ссылки

• Аллендер, Эрик; Гор, Вивек (1994), «Нижняя граница постоянного контура для однородной схемы», SIAM Journal on Computing , 23 (5): 1026–1049, CiteSeerX   10.1.1.51.3546 , doi : 10.1137/s0097539792233907
• Баласубраманян, К. (1980), Комбинаторика и диагонали матриц (PDF) , доктор философии. Диссертация, факультет статистики, Колледж Лойолы, Мадрас, Индия, том. T073, Индийский статистический институт, Калькутта
• Бакс, Эрик (1998), Алгоритмы конечных разностей для задач подсчета , доктор философии. Диссертация, вып. 223, Калифорнийский технологический институт
• Бакс, Эрик; Франклин, Дж. (1996), Конечно-разностное сито для расчета постоянного , Caltech-CS-TR-96-04, Калифорнийский технологический институт.
• Глинн, Дэвид Г. (2010), «Перманент квадратной матрицы», European Journal of Combinatorics , 31 (7): 1887–1891, doi : 10.1016/j.ejc.2010.01.010
• Глинн, Дэвид Г. (2013), «Постоянные формулы Веронеса», Designs, Codes and Cryptography , 68 (1–3): 39–47, doi : 10.1007/s10623-012-9618-1 , S2CID   36911503
• Джеррум, М.; Синклер, А.; Вигода, Э. (2001), «Алгоритм аппроксимации с полиномиальным временем для перманента матрицы с неотрицательными элементами», Proc. 33-й симпозиум по теории вычислений , стр. 712–721, doi : 10.1145/380752.380877 , ISBN  978-1581133493 , S2CID   8368245 , ECCC   TR00-079
• Джеррам, Марк ; Валиант, Лесли ; Вазирани, Виджай (1986), «Случайная генерация комбинаторных структур из равномерного распределения», Theoretical Computer Science , 43 : 169–188, doi : 10.1016/0304-3975(86)90174-X
• Коган, Григорий (1996), «Вычисление перманентов над полями характеристики 3: где и почему это становится трудным», Труды 37-й конференции по основам информатики , стр. 108–114, doi : 10.1109/SFCS.1996.548469 , ISBN  0-8186-7594-2 , S2CID   39024286
• Кнежевич, Анна; Коэн, Грег (2017), Некоторые факты о перманентах в конечных характеристиках , arXiv : 1710.01783 , Бибкод : 2017arXiv171001783K
• ван Линт, Якобус Хендрик; Уилсон, Ричард Мишель (2001), Курс комбинаторики , издательство Кембриджского университета, ISBN  978-0-521-00601-9
• Литтл, CHC (1974), «Расширение метода Кастелейна для перечисления 1-факторов плоских графов», в Холтоне, Д. (ред.), Proc. 2-я Австралийская конференция. Комбинаторная математика , Конспект лекций по математике, вып. 403, Springer-Verlag, стр. 63–72.
• Литтл, CHC (1975), «Характеристика конвертируемых (0, 1)-матриц», Журнал комбинаторной теории , серия B, 18 (3): 187–208, doi : 10.1016/0095-8956(75)90048- 9
• Маркус, М.; Минк, Х. (1961), «О связи между определяющим и постоянным», Illinois Journal of Mathematics , 5 (3): 376–381, doi : 10.1215/ijm/1255630882
• Нидженхейс, Альберт; Уилф, Герберт С. (1978), Комбинаторные алгоритмы , Academic Press
• Поля, Г. (1913), «Ауфгабе 424», арх. Математика. Физ. , 20 (3): 27
• Райх, Симеон (1971), «Еще одно решение старой проблемы полиа», American Mathematical Monthly , 78 (6): 649–650, doi : 10.2307/2316574 , JSTOR   2316574
• Ремпала, Гжегож А.; Весоловский, Яцек (2008), Симметричные функционалы на случайных матрицах и задачах случайного сопоставления , Springer, p. 4, ISBN  978-0-387-75145-0
• Райзер, Герберт Джон (1963), Комбинаторная математика , Математические монографии Каруса, Том. 14, Математическая ассоциация Америки , ISBN.  978-1-61444-014-7
• Вазирани, Виджай В. (1988), «NC-алгоритмы для вычисления количества совершенных паросочетаний в _{K 3,3} графах, свободных от , и связанные с ними проблемы», Proc. 1-й скандинавский семинар по теории алгоритмов (SWAT '88) , Конспекты лекций по информатике, том. 318, Springer-Verlag, стр. 233–242, doi : 10.1007/3-540-19487-8_27 , hdl : 1813/6700 , ISBN  978-3-540-19487-3
• Валиант, Лесли Г. (1979), «Сложность вычисления постоянного», Theoretical Computer Science , 8 (2), Elsevier: 189–201, doi : 10.1016/0304-3975(79)90044-6 , S2CID   1637832
• «Постоянный», Краткая математическая энциклопедия CRC , Чепмен и Холл / CRC, 2002 г.

Дальнейшее чтение

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