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

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

Определение

Перманент размера n × 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 .

Например,

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

и

$$\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 , иногда в круглых скобках вокруг аргумента. Минк использует Per( A ) для константы прямоугольных матриц и per( A ), когда A является квадратной матрицей. Мьюир и Мецлер используют обозначения ${\overset {+}{|}}\quad {\overset {+}{|}}$.

Слово « постоянный » было предложено Коши в 1812 году как «fonctions symétriques Permanentes» для обозначения родственного типа функций, и использовался Мьюиром и Мецлером в современном, более конкретном смысле.

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

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

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

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

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

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

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

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

Например, разложив по первому столбцу,

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

при расширении вдоль последней строки получаем:

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

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

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

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

Приложения

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

Перманент естественным образом возникает при изучении симметричной тензорной степени гильбертовых пространств . В частности, для гильбертова пространства $H$, позволять $\vee ^{k}H$ обозначают $k$симметричная тензорная степень $H$, которое является пространством симметричных тензоров . Обратите внимание, в частности, что $\vee ^{k}H$ натянута на симметричные произведения элементов в $H$. Для $x_{1},x_{2},\dots ,x_{k}\in H$, мы определяем симметричное произведение этих элементов как $$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)}$$Если мы рассмотрим $\vee ^{k}H$ (как подпространство $\otimes ^{k}H$, k- я тензорная степень $H$) и определим внутренний продукт на $\vee ^{k}H$ соответственно, мы находим, что для $x_{j},y_{j}\in H$$$\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}$$Применяя неравенство Коши–Шварца , находим, что $\operatorname {perm} \left[\langle x_{i},x_{j}\rangle \right]_{i,j=1}^{k}\geq 0$, и это $$\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}$$

Велосипедные чехлы

Основная статья: Обложка цикла Vertex

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

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

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

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

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

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

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

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

Если 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 ^и .

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

$$\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 — единичная матрица, а числа Менажа определяются выражением

$${\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 году. и доказано Л.М. Брегманом в 1973 г., дает верхнюю оценку перманента n × n (0, 1)-матрицы. Если A имеет r _i единиц в строке i для каждого 1 ≤ i ≤ n , неравенство гласит, что $$\operatorname {perm} A\leq \prod _{i=1}^{n}(r_{i})!^{1/r_{i}}.$$

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

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

Вычисление

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

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

Считается, что перманент вычислить сложнее, чем определитель. Хотя определитель можно вычислить за полиномиальное время методом исключения Гаусса , метод исключения Гаусса нельзя использовать для вычисления перманента. Более того, вычисление перманента (0,1)-матрицы является #P-полным . Таким образом, если перманент можно вычислить за полиномиальное время любым методом, то FP = #P , что является даже более сильным утверждением, чем P = NP . Однако, когда элементы A неотрицательны, перманент можно вычислить приблизительно за вероятностно- полиномиальное время с точностью до ошибки $\varepsilon M$, где $M$ это стоимость постоянного и $\varepsilon >0$ является произвольным. Перманент определенного набора положительных полуопределенных матриц NP-трудно аппроксимировать в пределах любого субэкспоненциального множителя. дополнительные условия на спектр , перманент можно аппроксимировать за вероятностно-полиномиальное время: наилучшая достижимая ошибка этого приближения равна Если наложить $\varepsilon {\sqrt {M}}$ ( $M$ снова значение перманента). Твердость в этих случаях тесно связана со сложностью моделирования экспериментов по выборке бозонов .

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

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

Другой способ просмотра перманентов — использование многомерных генерирующих функций . Позволять $A=(a_{ij})$ — квадратная матрица порядка n . Рассмотрим многомерную производящую функцию: $${\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}}$$Коэффициент $x_{1}x_{2}\dots x_{n}$ в $F(x_{1},x_{2},\dots ,x_{n})$ пермь( А ).

В качестве обобщения, для любой последовательности из n неотрицательных целых чисел: $s_{1},s_{2},\dots ,s_{n}$ определять: $$\operatorname {perm} ^{(s_{1},s_{2},\dots ,s_{n})}(A)$$ как коэффициент $x_{1}^{s_{1}}x_{2}^{s_{2}}\cdots x_{n}^{s_{n}}$ в $\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}}.$

Основная теорема Мак-Магона, касающаяся перманентов и определителей: $$\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)}},$$где I порядка n - единичная матрица , а X - диагональная матрица с диагональю $[x_{1},x_{2},\dots ,x_{n}].$

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

Постоянную функцию можно обобщить и применить к неквадратным матрицам. Действительно, некоторые авторы считают это определением перманента и считают ограничение квадратными матрицами особым случаем. В частности, для размера m × n матрицы $A=(a_{ij})$ при m ≤ n определим $$\operatorname {perm} (A)=\sum _{\sigma \in \operatorname {P} (n,m)}a_{1\sigma (1)}a_{2\sigma (2)}\ldots a_{m\sigma (m)}$$где P( n , m ) — множество всех m -перестановок n -множества {1,2,...,n}.

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

См. также

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

Ссылки

• Бруальди, Ричард А. (2006). Комбинаторные матричные классы . Энциклопедия математики и ее приложений. Том. 108. Кембридж: Издательство Кембриджского университета . ISBN  978-0-521-86565-4 . Збл   1106.05001 .
• Минк, Хенрик (1978). Перманенты . Энциклопедия математики и ее приложений. Том. 6. С предисловием Марвина Маркуса. Ридинг, Массачусетс: Аддисон-Уэсли. ISSN   0953-4806 . ОСЛК   3980645 . Збл   0401.15005 .
• Мьюир, Томас; Мецлер, Уильям Х. (1960) [1882]. Трактат по теории определителей . Нью-Йорк: Дувр. OCLC   535903 .
• Перкус, Дж. К. (1971), Комбинаторные методы , Прикладные математические науки № 4, Нью-Йорк: Springer-Verlag, ISBN  978-0-387-90027-8
• Райзер, Герберт Джон (1963), Комбинаторная математика , Математические монографии Каруса № 14, Математическая ассоциация Америки
• ван Линт, Дж. Х.; Уилсон, Р.М. (2001), Курс комбинаторики , издательство Кембриджского университета, 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 .