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

Многочлен элементов матрицы

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

Определение

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

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

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

Например,

$${\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 отличается от определения A тем , что сигнатуры перестановок не принимаются во внимание.

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

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

Характеристики

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

• perm( A ) инвариантен относительно произвольных перестановок строк и/или столбцов A . Это свойство можно записать символически как perm( A ) = perm( PAQ ) для любых матриц перестановок P и Q соответствующего размера ,
• умножение любой отдельной строки или столбца A на скаляр s изменяет perm( A ) на s ⋅perm( A ),
• perm( A ) инвариантен относительно транспонирования , то есть perm( A ) = perm( A ^T ).
• Если и являются квадратными матрицами порядка n , то ^[8] где s и t являются подмножествами одинакового размера {1,2,..., n } и являются их соответствующими дополнениями в этом множестве. ${\displaystyle A=\left(a_{ij}\right)}$ ${\displaystyle B=\left(b_{ij}\right)}$ $${\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}}},}$$ ${\displaystyle {\bar {s}},{\bar {t}}}$
• Если — треугольная матрица , т.е. всякий раз, когда или, альтернативно, всякий раз , когда , то ее перманент (а также определитель) равен произведению диагональных элементов: ${\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}.}$$

Отношение к детерминантам

Расширение Лапласа по минорам для вычисления определителя по строке, столбцу или диагонали распространяется на перманент, игнорируя все знаки. ^[9]

Для каждого , ${\textstyle i}$

$${\displaystyle \mathbb {perm} (B)=\sum _{j=1}^{n}B_{i,j}M_{i,j},}$$

где — запись i -й строки и j -го столбца матрицы B , а — постоянная подматрицы, полученной путем удаления i - й строки и j -го столбца матрицы B. ${\displaystyle B_{i,j}}$ ${\textstyle M_{i,j}}$

Например, расширяясь по первому столбцу,

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

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

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

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

Приложения

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

Перманент естественным образом возникает при изучении симметричной тензорной степени гильбертовых пространств . ^[12] В частности, для гильбертова пространства , пусть обозначает -ю симметричную тензорную степень , которая является пространством симметричных тензоров . Заметим, в частности, что охватывается симметричными произведениями элементов в . Для мы определяем симметричное произведение этих элементов как Если мы рассмотрим (как подпространство , k -ю тензорную степень ) и определим скалярное произведение на соответствующим образом, мы найдем, что для Применяя неравенство Коши–Шварца , мы найдем, что , и что ${\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}$ ${\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}}$$

Чехлы для велосипедов

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

Если вес циклического покрытия определяется как произведение весов дуг в каждом цикле, то, подразумевая, что Таким образом, перманент A равен сумме весов всех циклических покрытий орграфа. $${\displaystyle \operatorname {weight} (\sigma )=\prod _{i=1}^{n}a_{i,\sigma (i)},}$$ $${\displaystyle \operatorname {perm} (A)=\sum _{\sigma }\operatorname {weight} (\sigma ).}$$

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

Квадратную матрицу можно также рассматривать как матрицу смежности двудольного графа , имеющего вершины с одной и с другой стороны, с представлением веса ребра от вершины до вершины . Если вес идеального паросочетания, соответствующего вершине , определяется как произведение весов ребер в паросочетании, то Таким образом, перманент A равен сумме весов всех идеальных паросочетаний графа. ${\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 в качестве элементов.

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

Если A — циркулянтная матрица в классе Ω( n , k ), то при k  > 3 perm( A ) > |det ( A )| и при k  = 3 perm( A ) = |det ( A )|. Более того, при k  = 3 путем перестановки строк и столбцов A можно привести к виду прямой суммы e копий матрицы Z и, следовательно, n  = 7 e и perm( A ) = 24 ^e .

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

$${\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 — матрица размером n × n, состоящая из всех единиц, а I — единичная матрица, а числа управления задаются как

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

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

Границы

Неравенство Брегмана–Минца , выдвинутое Х. Минцем в 1963 году ^[15] и доказанное Л. М. Брегманом в 1973 году ^[16], дает верхнюю границу для перманента n × n (0, 1)-матрицы. Если A имеет r _i единиц в строке i для каждого 1 ≤ i ≤ n , неравенство утверждает, что $${\displaystyle \operatorname {perm} A\leq \prod _{i=1}^{n}(r_{i})!^{1/r_{i}}.}$$

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

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

Вычисление

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

Его можно переписать в терминах матричных записей следующим образом: $${\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-полным . Таким образом, если перманент можно вычислить за полиномиальное время любым методом, то FP  =  #P , что является даже более сильным утверждением, чем P = NP . Однако, когда элементы A неотрицательны, перманент можно вычислить приблизительно за вероятностное полиномиальное время с точностью до , где — значение перманента, а — произвольно. ^[25] Перманент определенного набора положительных полуопределенных матриц является NP-трудным для аппроксимации с точностью до любого субэкспоненциального множителя. ^{[26] Если на} спектр наложить дополнительные условия , то перманент может быть аппроксимирован за вероятностное полиномиальное время: наилучшая достижимая ошибка этого приближения равна ( — снова значение перманента). ^[27] Сложность в этих случаях тесно связана с трудностью моделирования экспериментов по выборке бозонов . ${\displaystyle \varepsilon M}$ ${\displaystyle M}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle \varepsilon {\sqrt {M}}}$ ${\displaystyle M}$

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

Другой способ просмотра постоянных — через многомерные производящие функции . Пусть будет квадратной матрицей порядка n . Рассмотрим многомерную производящую функцию: Коэффициент в равен perm( A ). ^[28] ${\displaystyle A=(a_{ij})}$ $${\displaystyle {\begin{aligned}F(x_{1},x_{2},\dots ,x_{n})&=\prod _{i=1}^{n}\left(\sum _{j=1}^{n}a_{ij}x_{j}\right)\\&=\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).\end{aligned}}}$$ ${\displaystyle x_{1}x_{2}\dots x_{n}}$ ${\displaystyle F(x_{1},x_{2},\dots ,x_{n})}$

В качестве обобщения, для любой последовательности из n неотрицательных целых чисел, определим: как коэффициент при ${\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}}.}$

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

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

Перманентную функцию можно обобщить для применения к неквадратным матрицам. Действительно, несколько авторов делают это определением перманента и рассматривают ограничение на квадратные матрицы как особый случай. ^[30] В частности, для матрицы m  ×  n с m  ≤  n , определите, где P( n , m ) — это множество всех m -перестановок n -множества {1,2,...,n}. ^[31] ${\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)}}$$

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

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

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

Пусть S ₁ , S ₂ , ..., S _m будут подмножествами (не обязательно различными) n -множества с m  ≤  n . Матрица инцидентности этого набора подмножеств представляет собой m  ×  n (0,1)-матрицу A . Число систем различных представителей (SDR) этого набора равно perm( A ). ^[32]

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

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

Примечания

1. Маркус, Марвин ; Минк, Генрик (1965). «Перманенты». Amer. Math. Monthly . 72 (6): 577–591. doi :10.2307/2313846. JSTOR  2313846.
2. Минк (1978)
3. Мьюир и Метцлер (1960)
4. Коши, AL (1815), «Mémoire sur les fonctions qui ne peuvent obtenir que deux valeurs égales et de Signes contraires par suite des transpositions opérées entre lesvarium qu'elles renferment.», Journal de l'École Polytechnique , 10 : 91 –169
5. Мьюир и Метцлер (1960)
6. ван Линт и Уилсон 2001, с. 108
7. Райзер 1963, стр. 25 – 26
8. Перкус 1971, стр. 2
9. Percus 1971, стр. 12
10. Ryser 1963, стр. 26
11. Ааронсон, Скотт (14 ноября 2010 г.). «Вычислительная сложность линейной оптики». arXiv : 1011.3245 [quant-ph].
12. Бхатия, Раджендра (1997). Матричный анализ . Нью-Йорк: Springer-Verlag. С. 16–19. ISBN 978-0-387-94846-1.
13. Ryser 1963, стр. 124
14. Райзер 1963, стр. 125
15. Минк, Генрик (1963), «Верхние оценки для перманентов (0,1)-матриц», Бюллетень Американского математического общества , 69 (6): 789–791, doi : 10.1090/s0002-9904-1963-11031-9
16. ван Линт и Уилсон 2001, стр. 101
17. ван дер Варден, BL (1926), «Aufgabe 45», Jber. немецкий. Math.-Verein. , 35 : 117.
18. Гирес, Б. (2022), «Общий источник нескольких неравенств, касающихся дважды стохастических матриц», Publicationes Mathematicae Institutum Mathematicum Universitatis Debreceniensis , 27 (3–4): 291–304, doi : 10.5486/PMD.1980.27.3- 4.15 , МР  0604006.
19. Егорычев, Г.П. (1980), Решение проблемы ван-дер-Вардена для перманентов , Красноярск: Акад. Наук СССР Сибирск. Отдел. Инст. Физ., с. 12, МР  0602332. Егорычев, Г.П. (1981), "Доказательство гипотезы Ван дер Вардена для перманентов", Академия наук СССР , 22 (6): 65–71, 225, MR  0638007. Егорычев, ГП (1981), «Решение проблемы Ван дер Вардена для перманентов», Успехи математики , 42 (3): 299–305, doi : 10.1016/0001-8708(81)90044-X , MR  0642395.
20. Фаликман, Д.И. (1981), «Доказательство гипотезы Ван дер Вардена о перманенте дважды стохастической матрицы», Академия наук Союза ССР , 29 (6): 931–938, 957, MR  0625097.
21. Бруальди (2006) стр.487
22. Премия Фулкерсона, Общество математической оптимизации, получено 19 августа 2012 г.
23. Райзер (1963, стр. 27)
24. ван Линт и Уилсон (2001), с. 99
25. Джеррум, М.; Синклер , А.; Вигода, Э. (2004), «Алгоритм аппроксимации полиномиальным временем для перманента матрицы с неотрицательными элементами», Журнал ACM , 51 (4): 671–697, CiteSeerX 10.1.1.18.9466 , doi :10.1145/1008731.1008738, S2CID  47361920 
26. Мейбург, Александр (2023). «Неаппроксимируемость положительных полуопределенных постоянных и квантовая томография состояний». Algorithmica . 85 (12): 3828–3854. arXiv : 2111.03142 . doi : 10.1007/s00453-023-01169-1 .
27. Чахмахчян, Левон; Серф, Николас; Гарсия-Патрон, Рауль (2017). «Квантовый алгоритм для оценки перманента положительных полуопределенных матриц». Phys. Rev. A. 96 ( 2): 022329. arXiv : 1609.02416 . Bibcode : 2017PhRvA..96b2329C. doi : 10.1103/PhysRevA.96.022329. S2CID  54194194.
28. Перкус 1971, стр. 14
29. Перкус 1971, стр. 17
30. В частности, это делают Минц (1978) и Райзер (1963).
31. Райзер 1963, стр. 25
32. Райзер 1963, стр. 54

Ссылки

• Brualdi, Richard A. (2006). Комбинаторные матричные классы . Энциклопедия математики и ее приложений. Том 108. Кембридж: Cambridge University Press . ISBN 978-0-521-86565-4. Збл  1106.05001.
• Minc, Henryk (1978). Permanents . Энциклопедия математики и ее приложений. Том 6. С предисловием Марвина Маркуса. Reading, MA: Addison–Wesley. ISSN  0953-4806. OCLC  3980645. Zbl  0401.15005.
• Мьюир, Томас; Метцлер, Уильям Х. (1960) [1882]. Трактат о теории определителей . Нью-Йорк: Довер. OCLC  535903.
• Перкус, Дж. К. (1971), Комбинаторные методы , Прикладные математические науки № 4, Нью-Йорк: Springer-Verlag, ISBN 978-0-387-90027-8
• Райзер, Герберт Джон (1963), Комбинаторная математика , Математические монографии Каруса № 14, Математическая ассоциация Америки
• ван Линт, Дж. Х.; Уилсон, Р. М. (2001), Курс комбинаторики , Cambridge University Press, ISBN 978-0521422604

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

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

Внешние ссылки

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