Постоянный (математика) - Permanent (mathematics)

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

Определение

Перманент п-к-п матрица А = (а_{я, j}) определяется как

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

Сумма здесь распространяется на все элементы σ множества симметричная группа S_п; т.е. по всем перестановки чисел 1, 2, ..., п.

Например,

${\displaystyle \operatorname {perm} {\begin{pmatrix}a&b\\c&d\end{pmatrix}}=ad+bc,}$

и

${\displaystyle \operatorname {perm} {\begin{pmatrix}a&b&c\\d&e&f\\g&h&i\end{pmatrix}}=aei+bfg+cdh+ceg+bdi+afh.}$

Определение перманента А отличается от детерминант из А в этом подписи перестановок не учитываются.

Перманент матрицы A обозначается как А, Пермь А, или Per А, иногда аргумент заключен в круглые скобки. Minc использует Per (А) для перманента прямоугольных матриц и per (А) когда А квадратная матрица.^[2] Мюир и Метцлер используют обозначение ${\displaystyle {\overset {+}{|}}\quad {\overset {+}{|}}}$.^[3]

Слово, постоянный, возникла у Коши в 1812 году как «fonctions symétriques permanentes» для родственного типа функций,^[4] и использовался Мюиром и Мецлером^[5] в современном, более конкретном смысле.^[6]

Свойства и приложения

Если рассматривать перманент как карту, п векторов в качестве аргументов, то это многолинейная карта и он симметричен (это означает, что любой порядок векторов приводит к одному и тому же перманенту). Кроме того, учитывая квадратную матрицу ${\displaystyle A=\left(a_{ij}\right)}$ порядка п:^[7]

• пермь (А) инвариантна относительно произвольных перестановок строк и / или столбцов А. Это свойство можно символически записать как perm (А) = пермь (PAQ) для любого подходящего размера матрицы перестановок п и Q,
• умножение любой отдельной строки или столбца А по скаляр s меняет пермь (А) к s⋅перма (А),
• пермь (А) инвариантен относительно транспозиция, то есть пермь (А) = пермь (А^Т).

Если ${\displaystyle A=\left(a_{ij}\right)}$ и ${\displaystyle B=\left(b_{ij}\right)}$ квадратные матрицы порядка п тогда,^[8]

${\displaystyle \operatorname {perm} \left(A+B\right)=\sum _{s,t}\operatorname {perm} \left(a_{ij}\right)_{i\in s,j\in t}\operatorname {perm} \left(b_{ij}\right)_{i\in {\bar {s}},j\in {\bar {t}}},}$

куда s и т являются подмножествами одинакового размера {1,2, ...,п} и ${\displaystyle {\bar {s}},{\bar {t}}}$ являются их соответствующими дополнениями в этом наборе.

С другой стороны, основное мультипликативное свойство детерминантов не действует для перманентов.^[9] Простой пример показывает, что это так.

${\displaystyle {\begin{aligned}4&=\operatorname {perm} \left({\begin{matrix}1&1\\1&1\end{matrix}}\right)\operatorname {perm} \left({\begin{matrix}1&1\\1&1\end{matrix}}\right)\\&\neq \operatorname {perm} \left(\left({\begin{matrix}1&1\\1&1\end{matrix}}\right)\left({\begin{matrix}1&1\\1&1\end{matrix}}\right)\right)=\operatorname {perm} \left({\begin{matrix}2&2\\2&2\end{matrix}}\right)=8.\end{aligned}}}$

Формула, аналогичная Лапласа для развития определителя по строке, столбцу или диагонали также действует для перманента;^[10] все знаки должны быть проигнорированы навсегда. Например, раскрываясь по первому столбцу,

${\displaystyle {\begin{aligned}\operatorname {perm} \left({\begin{matrix}1&1&1&1\\2&1&0&0\\3&0&1&0\\4&0&0&1\end{matrix}}\right)={}&1\cdot \operatorname {perm} \left({\begin{matrix}1&0&0\\0&1&0\\0&0&1\end{matrix}}\right)+2\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\0&1&0\\0&0&1\end{matrix}}\right)\\&{}+\ 3\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\1&0&0\\0&0&1\end{matrix}}\right)+4\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\1&0&0\\0&1&0\end{matrix}}\right)\\={}&1(1)+2(1)+3(1)+4(1)=10,\end{aligned}}}$

в то время как расширение по последней строке дает,

${\displaystyle {\begin{aligned}\operatorname {perm} \left({\begin{matrix}1&1&1&1\\2&1&0&0\\3&0&1&0\\4&0&0&1\end{matrix}}\right)={}&4\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\1&0&0\\0&1&0\end{matrix}}\right)+0\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\2&0&0\\3&1&0\end{matrix}}\right)\\&{}+\ 0\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\2&1&0\\3&0&0\end{matrix}}\right)+1\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\2&1&0\\3&0&1\end{matrix}}\right)\\={}&4(1)+0+0+1(6)=10.\end{aligned}}}$

Если ${\displaystyle A}$ это треугольная матрица, т.е. ${\displaystyle a_{ij}=0}$, в любое время ${\displaystyle i>j}$ или, альтернативно, когда ${\displaystyle i<j}$, то его перманент (и определитель также) равен произведению диагональных элементов:

${\displaystyle \operatorname {perm} \left(A\right)=a_{11}a_{22}\cdots a_{nn}=\prod _{i=1}^{n}a_{ii}.}$

В отличие от определителя, перманент не имеет простой геометрической интерпретации; он в основном используется в комбинаторика, при лечении бозона Функции Грина в квантовая теория поля, и при определении вероятностей состояний выборка бозонов системы.^[11] Однако в нем есть два теоретико-графовый интерпретации: как сумма весов обложки для велосипедов из ориентированный граф, и как сумма весов идеальных совпадений в двудольный граф.

Симметричные тензоры

Перманент естественно возникает при изучении симметричной тензорной степени Гильбертовы пространства.^[12] В частности, для гильбертова пространства ${\displaystyle H}$, позволять ${\displaystyle \vee ^{k}H}$ обозначить ${\displaystyle k}$симметричная тензорная степень ${\displaystyle H}$, которое является пространством симметричные тензоры. Отметим, в частности, что ${\displaystyle \vee ^{k}H}$ охватывает Симметричные произведения элементов в ${\displaystyle H}$. За ${\displaystyle x_{1},x_{2},\dots ,x_{k}\in H}$, определим симметричное произведение этих элементов как

${\displaystyle x_{1}\vee x_{2}\vee \cdots \vee x_{k}=(k!)^{-1/2}\sum _{\sigma \in S_{k}}x_{\sigma (1)}\otimes x_{\sigma (2)}\otimes \cdots \otimes x_{\sigma (k)}}$

Если мы рассмотрим ${\displaystyle \vee ^{k}H}$ (как подпространство ${\displaystyle \otimes ^{k}H}$, то kth тензорная мощность из ${\displaystyle H}$) и определите внутренний продукт на ${\displaystyle \vee ^{k}H}$ соответственно, мы находим, что для ${\displaystyle x_{j},y_{j}\in H}$

${\displaystyle \langle x_{1}\vee x_{2}\vee \cdots \vee x_{k},y_{1}\vee y_{2}\vee \cdots \vee y_{k}\rangle =\operatorname {perm} \left[\langle x_{i},y_{j}\rangle \right]_{i,j=1}^{k}}$

Применяя Неравенство Коши – Шварца, мы находим, что ${\displaystyle \operatorname {perm} \left[\langle x_{i},x_{j}\rangle \right]_{i,j=1}^{k}\geq 0}$, и это

${\displaystyle \left|\operatorname {perm} \left[\langle x_{i},y_{j}\rangle \right]_{i,j=1}^{k}\right|^{2}\leq \operatorname {perm} \left[\langle x_{i},x_{j}\rangle \right]_{i,j=1}^{k}\cdot \operatorname {perm} \left[\langle y_{i},y_{j}\rangle \right]_{i,j=1}^{k}}$

Чехлы для цикла

Любая квадратная матрица ${\displaystyle A=(a_{ij})}$ можно рассматривать как матрица смежности взвешенного ориентированного графа с ${\displaystyle a_{ij}}$ представляющий вес дуги из вершины я к вершине j. А крышка цикла взвешенного ориентированного графа представляет собой набор вершинно-непересекающихся направленные циклы в орграфе, покрывающем все вершины графа. Таким образом, каждая вершина я в орграфе есть уникальный «преемник» ${\displaystyle \sigma (i)}$ в обложке цикла, и ${\displaystyle \sigma }$ это перестановка на ${\displaystyle \{1,2,\dots ,n\}}$ куда п - количество вершин в орграфе. И наоборот, любая перестановка ${\displaystyle \sigma }$ на ${\displaystyle \{1,2,\dots ,n\}}$ соответствует покрытию цикла, в котором есть дуга из вершины я к вершине ${\displaystyle \sigma (i)}$ для каждого я.

Если вес покрытия цикла определяется как произведение весов дуг в каждом цикле, то

${\displaystyle \operatorname {weight} (\sigma )=\prod _{i=1}^{n}a_{i,\sigma (i)}.}$

Перманент ${\displaystyle n\times n}$ матрица А определяется как

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

куда ${\displaystyle \sigma }$ это перестановка над ${\displaystyle \{1,2,\ldots ,n\}}$. Таким образом, перманент А равна сумме весов всех циклических покрытий орграфа.

Идеальное соответствие

Квадратная матрица ${\displaystyle A=(a_{ij})}$ также можно рассматривать как матрица смежности из двудольный граф у которого есть вершины ${\displaystyle x_{1},x_{2},\dots ,x_{n}}$ с одной стороны и ${\displaystyle y_{1},y_{2},\dots ,y_{n}}$ с другой стороны, с ${\displaystyle a_{ij}}$ представляющий вес ребра из вершины ${\displaystyle x_{i}}$ к вершине ${\displaystyle y_{j}}$. Если вес идеальное соответствие ${\displaystyle \sigma }$ что соответствует ${\displaystyle x_{i}}$ к ${\displaystyle y_{\sigma (i)}}$ определяется как произведение весов ребер в сопоставлении, тогда

${\displaystyle \operatorname {weight} (\sigma )=\prod _{i=1}^{n}a_{i,\sigma (i)}.}$

Таким образом, перманент А равна сумме весов всех совершенных паросочетаний графа.

Перманенты (0, 1) матриц

Перечисление

Ответы на многие вопросы о подсчете могут быть вычислены как постоянные матрицы, которые содержат только 0 и 1 в качестве записей.

Пусть Ω (п,k) - класс всех (0, 1) -матриц порядка п с суммой каждой строки и столбца, равной k. Каждая матрица А в этом классе есть завивка (А) > 0.^[13] Матрицы встречаемости проективные плоскости принадлежат классу Ω (п² + п + 1, п + 1) для п целое число> 1. Вычислены перманенты, соответствующие наименьшим проективным плоскостям. За п = 2, 3 и 4 значения равны 24, 3852 и 18 534 400 соответственно.^[13] Позволять Z - матрица инцидентности проективной плоскости с п = 2, Самолет Фано. Примечательно, что пермь (Z) = 24 = | det (Z) |, модуль определителя Z. Это следствие Z быть циркулянтная матрица и теорема:^[14]

Если А - циркулянтная матрица в классе Ω (п,k) то если k > 3, пермь (А)> | det (А) | и если k = 3, доп. (А) = | det (А) |, Кроме того, когда k = 3, переставляя строки и столбцы, А можно представить в виде прямой суммы е копии матрицы Z и следовательно, п = 7е и завивка (А) = 24^е.

Перманенты также можно использовать для расчета количества перестановки с ограниченными (запрещенными) позициями. Для стандартного п-множество {1, 2, ..., п}, позволять ${\displaystyle A=(a_{ij})}$ - (0, 1) -матрица, где а_ij = 1, если я → j допускается в перестановке и а_ij = 0 в противном случае. Тогда завивка (А) равно количеству перестановок п-множество, удовлетворяющее всем ограничениям.^[10] Два хорошо известных частных случая этого - решение психическое расстройство проблема и проблема с мужем: количество перестановок п-множество без неподвижных точек (неисправностей) определяется выражением

${\displaystyle \operatorname {perm} (J-I)=\operatorname {perm} \left({\begin{matrix}0&1&1&\dots &1\\1&0&1&\dots &1\\1&1&0&\dots &1\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&1&1&\dots &0\end{matrix}}\right)=n!\sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}},}$

куда J это п×п матрица всех единиц и я - единичная матрица, а числа сотрудников даны

${\displaystyle {\begin{aligned}\operatorname {perm} (J-I-I')&=\operatorname {perm} \left({\begin{matrix}0&0&1&\dots &1\\1&0&0&\dots &1\\1&1&0&\dots &1\\\vdots &\vdots &\vdots &\ddots &\vdots \\0&1&1&\dots &0\end{matrix}}\right)\\&=\sum _{k=0}^{n}(-1)^{k}{\frac {2n}{2n-k}}{2n-k \choose k}(n-k)!,\end{aligned}}}$

куда Я' - (0, 1) -матрица с ненулевыми элементами в позициях (я, я + 1) и (п, 1).

Границы

В Неравенство Брегмана – Минка, предположенный Г. Минком в 1963 г.^[15] и доказано Л. М. Брегман в 1973 г.,^[16] дает верхнюю оценку перманента п × п (0, 1) -матрица. Если А имеет р_я один в ряд я для каждого 1 ≤ я ≤ п, неравенство утверждает, что

${\displaystyle \operatorname {perm} A\leq \prod _{i=1}^{n}(r_{i})!^{1/r_{i}}.}$

Гипотеза ван дер Вардена

В 1926 г. Ван дер Варден предположил, что минимальный перманент среди всех п × п дважды стохастические матрицы является п!/п^п, достигается матрицей, все элементы которой равны 1 /п.^[17] Доказательства этой гипотезы были опубликованы в 1980 г. Б. Гиресом.^[18] а в 1981 г. - Г. П. Егорычев.^[19] и Д. И. Фаликман;^[20] Доказательство Егорычева - это приложение Неравенство Александрова – Фенхеля..^[21] За эту работу Егорычев и Фаликман получили премию. Премия Фулкерсона в 1982 г.^[22]

Вычисление

Основные статьи: Вычисление постоянного и Sharp-P-комплектность 01-перманент

Наивный подход, использующий определение, к вычислению перманентов вычислительно невыполним даже для относительно небольших матриц. Один из самых быстрых известных алгоритмов связан с Х. Дж. Райзер.^[23] Метод Райзера основан на включение – исключение формула, которая может быть дана^[24] следующим образом: Пусть ${\displaystyle A_{k}}$ быть полученным от А удалив 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}.}$

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

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

Считается, что перманент труднее вычислить, чем определитель. Хотя определитель можно вычислить в полиномиальное время к Гауссово исключение, Исключение Гаусса нельзя использовать для вычисления перманента. Более того, вычисление перманента (0,1) -матрицы требует # P-complete. Таким образом, если перманент можно вычислить за полиномиальное время любым методом, то FP  = #П, что является даже более сильным утверждением, чем P = NP. Когда записи А неотрицательны, однако перманент можно вычислить примерно в вероятностный полиномиальное время, с погрешностью ${\displaystyle \varepsilon M}$, куда ${\displaystyle M}$ стоимость постоянного и ${\displaystyle \varepsilon >0}$ произвольно.^[25] Перманент определенного набора положительно полуопределенные матрицы также может быть аппроксимирован за вероятностное полиномиальное время: наилучшая достижимая ошибка этого приближения составляет ${\displaystyle \varepsilon {\sqrt {M}}}$ (${\displaystyle M}$ снова значение перманента).^[26]

Основная теорема Мак-Магона

Основная статья: Теорема Мак-Магона Мастер

Другой способ просмотра перманентов - многомерный производящие функции. Позволять ${\displaystyle A=(a_{ij})}$ квадратная матрица порядка п. Рассмотрим многомерную производящую функцию:

${\displaystyle F(x_{1},x_{2},\dots ,x_{n})=\prod _{i=1}^{n}\left(\sum _{j=1}^{n}a_{ij}x_{j}\right)}$

${\displaystyle =\left(\sum _{j=1}^{n}a_{1j}x_{j}\right)\left(\sum _{j=1}^{n}a_{2j}x_{j}\right)\cdots \left(\sum _{j=1}^{n}a_{nj}x_{j}\right).}$

Коэффициент ${\displaystyle x_{1}x_{2}\dots x_{n}}$ в ${\displaystyle F(x_{1},x_{2},\dots ,x_{n})}$ завивка (А).^[27]

В качестве обобщения для любой последовательности п неотрицательные целые числа, ${\displaystyle s_{1},s_{2},\dots ,s_{n}}$ определять:

${\displaystyle \operatorname {perm} ^{(s_{1},s_{2},\dots ,s_{n})}(A)}$ как коэффициент ${\displaystyle x_{1}^{s_{1}}x_{2}^{s_{2}}\cdots x_{n}^{s_{n}}}$ в${\displaystyle \left(\sum _{j=1}^{n}a_{1j}x_{j}\right)^{s_{1}}\left(\sum _{j=1}^{n}a_{2j}x_{j}\right)^{s_{2}}\cdots \left(\sum _{j=1}^{n}a_{nj}x_{j}\right)^{s_{n}}.}$

Основная теорема Мак-Магона относящиеся к перманентам и детерминантам:^[28]

${\displaystyle \operatorname {perm} ^{(s_{1},s_{2},\dots ,s_{n})}(A)={\text{ coefficient of }}x_{1}^{s_{1}}x_{2}^{s_{2}}\cdots x_{n}^{s_{n}}{\text{ in }}{\frac {1}{\det(I-XA)}},}$

куда я это заказ п единичная матрица и Икс - диагональная матрица с диагональю ${\displaystyle [x_{1},x_{2},\dots ,x_{n}].}$

Перманенты прямоугольных матриц

Постоянную функцию можно обобщить для применения к неквадратным матрицам. Действительно, некоторые авторы делают это определение перманента и считают ограничение квадратными матрицами частным случаем.^[29] В частности, для м × п матрица ${\displaystyle A=(a_{ij})}$ с м ≤ п, определять

${\displaystyle \operatorname {perm} (A)=\sum _{\sigma \in \operatorname {P} (n,m)}a_{1\sigma (1)}a_{2\sigma (2)}\ldots a_{m\sigma (m)}}$

где P (п,м) - множество всех м-перестановки п-множество {1,2, ..., n}.^[30]

Вычислительный результат Райзера для перманентов также является обобщающим. Если А является м × п матрица с м ≤ п, позволять ${\displaystyle A_{k}}$ быть полученным от А удалив 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}^{m-1}(-1)^{k}{\binom {n-m+k}{k}}\sigma _{n-m+k}.}$^[9]

Системы различных представителей

Обобщение определения перманентных матриц на неквадратные позволяет использовать эту концепцию более естественным образом в некоторых приложениях. Например:

Позволять S₁, S₂, ..., S_м быть подмножествами (не обязательно различными) п-установить с м ≤ п. В матрица инцидентности этого набора подмножеств является м × п (0,1) -матрица А. Количество системы различных представителей (SDR) этой коллекции - пермь (А).^[31]

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

• Вычисление постоянного
• Теорема Бапата – Бека., применение перманентов в статистика заказов
• Определитель Слейтера, применение перманентов в квантовая механика

Примечания

1. Маркус, Марвин; Минц, Хенрик (1965). «Перманент». Амер. Математика. Ежемесячно. 72 (6): 577–591. Дои:10.2307/2313846. JSTOR  2313846.
2. Minc (1978)
3. Мюир и Метцлер (1960)
4. Коши, А. Л. (1815 г.), «Воспоминания о функциях, которые могут быть использованы для двух валютных операций и знаков, противоположных номинальным операциям перестановки, которые должны быть преобразованы»., Journal de l'École Polytechnique, 10: 91–169
5. Мюир и Метцлер (1960)
6. ван Линт и Уилсон 2001, п. 108
7. Райзер 1963, стр. 25 - 26
8. Перкус 1971, п. 2
9. Райзер 1963, п. 26
10. Перкус 1971, п. 12
11. Ааронсон, Скотт (14 ноября 2010 г.). «Вычислительная сложность линейной оптики». arXiv:1011.3245 [Quant-ph ].
12. Бхатия, Раджендра (1997). Матричный анализ. Нью-Йорк: Springer-Verlag. С. 16–19. ISBN  978-0-387-94846-1.
13. Райзер 1963, п. 124
14. Райзер 1963, п. 125
15. Минц, Хенрик (1963), "Верхние оценки перманентов (0,1) -матриц", Бюллетень Американского математического общества, 69 (6): 789–791, Дои:10.1090 / с0002-9904-1963-11031-9
16. ван Линт и Уилсон 2001, п. 101
17. ван дер Варден, Б. Л. (1926), "Aufgabe 45", Jber. Deutsch. Math.-Verein., 35: 117.
18. Gyires, B. (1980), "Общий источник нескольких неравенств, касающихся дважды стохастических матриц", Publicationes Mathematicae Institutum Mathematicum Universitatis Debreceniensis, 27 (3–4): 291–304, МИСТЕР  0604006.
19. Егорычев, Г. П. (1980), Решение проблемы ван-дер-вардена для перманентов Красноярск: Акад. АН СССР Сиб. Отдел. Inst. Физ., Стр. 12, МИСТЕР  0602332. Егорычев, Г. П. (1981), "Доказательство гипотезы Ван дер Вардена для перманентов", Академия Наук СССР (по-русски), 22 (6): 65–71, 225, МИСТЕР  0638007. Егорычев, Г. П. (1981), "Решение проблемы Ван дер Вардена для перманентов", Успехи в математике, 42 (3): 299–305, Дои:10.1016 / 0001-8708 (81) 90044-Х, МИСТЕР  0642395.
20. Фаликман, Д. И. (1981), "Доказательство гипотезы Ван дер Вардена о перманенте дважды стохастической матрицы", Академия Наук Союза ССР (по-русски), 29 (6): 931–938, 957, МИСТЕР  0625097.
21. Бруальди (2006) с.487
22. Премия Фулкерсона, Mathematical Optimization Society, дата обращения 19 августа 2012.
23. Райзер (1963), п. 27)
24. ван Линт и Уилсон (2001) п. 99
25. Джеррам, М.; Синклер, А.; Вигода, Е. (2004), "Алгоритм полиномиального приближения для перманента матрицы с неотрицательными элементами", Журнал ACM, 51 (4): 671–697, CiteSeerX  10.1.1.18.9466, Дои:10.1145/1008731.1008738
26. Чахмахчян, Левон; Серф, Николас; Гарсия-Патрон, Рауль (2017). «Квантовый алгоритм для оценки перманента положительных полуопределенных матриц». Phys. Ред. А. 96 (2): 022329. arXiv:1609.02416. Bibcode:2017PhRvA..96b2329C. Дои:10.1103 / PhysRevA.96.022329.
27. Перкус 1971, п. 14
28. Перкус 1971, п. 17
29. Особенно, Minc (1978) и Райзер (1963) сделай это.
30. Райзер 1963, п. 25
31. Райзер 1963, п. 54

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

• Бруальди, Ричард А. (2006). Комбинаторные матричные классы. Энциклопедия математики и ее приложений. 108. Кембридж: Издательство Кембриджского университета. ISBN  978-0-521-86565-4. Zbl  1106.05001.
• Минц, Хенрик (1978). Перманенты. Энциклопедия математики и ее приложений. 6. С предисловием Марвина Маркуса. Ридинг, Массачусетс: Аддисон – Уэсли. ISSN  0953-4806. OCLC  3980645. Zbl  0401.15005.
• Мьюир, Томас; Метцлер, Уильям Х. (1960) [1882]. Трактат по теории детерминант. Нью-Йорк: Дувр. OCLC  535903.
• Перкус, J.K. (1971), Комбинаторные методы, Прикладные математические науки № 4, Нью-Йорк: Springer-Verlag, ISBN  978-0-387-90027-8
• Райзер, Герберт Джон (1963), Комбинаторная математика, The Carus Mathematical Monographs # 14, Математическая ассоциация Америки
• van Lint, J.H .; Уилсон, Р. (2001), Курс комбинаторики, Издательство Кембриджского университета, ISBN  978-0521422604

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

• Холл младший, Маршалл (1986), Комбинаторная теория (2-е изд.), Нью-Йорк: John Wiley & Sons, стр. 56–72, ISBN  978-0-471-09138-7 Содержит доказательство гипотезы Ван дер Вардена.
• Marcus, M .; Минц, Х. (1965), "Перманенц", Американский математический ежемесячник, 72 (6): 577–591, Дои:10.2307/2313846, JSTOR  2313846

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

• Постоянный в PlanetMath.
• Постоянная гипотеза Ван дер Вардена в PlanetMath.