Interested Article - Перманент

Пермане́нт в математике — числовая функция , определённая на множестве всех матриц ; для квадратных матриц похожа на детерминант , и отличается от него лишь в том, что в разложении на перестановки (или на миноры ) берутся не чередующиеся знаки, а все плюсы. В отличие от детерминанта, определение перманента расширено и на неквадратные матрицы.

В литературе для обозначения перманента обычно используется одна из следующих нотаций: $\mathrm {Per} (A)$ , $\mathrm {per} A$ или $\mathrm {perm} A$ .

Определение

Перманент квадратной матрицы

Пусть $A$ — квадратная матрица размера $n\times n$ , элементы $a_{i,j}$ которой принадлежат некоторому полю $K$ . Перманентом матрицы $A$ называется число:

\mathrm {Per} (A)=\sum _{\pi \in S_{n}}\prod _{i=1}^{n}a_{i,\pi _{i}}=\sum _{\pi \in S_{n}}a_{1,\pi _{1}}a_{2,\pi _{2}}\cdots a_{n,\pi _{n}}

,

где сумма берётся по всем перестановкам $\pi$ чисел от 1 до $n$ .

Например, для матрицы размера $2\times 2$ :

\mathrm {Per} {\begin{pmatrix}a&b\\c&d\end{pmatrix}}=ad+bc

.

Это определение отличается от аналогичного определения детерминанта лишь тем, что в детерминанте некоторые члены суммы имеют отрицательный знак, в зависимости от знака перестановки $\pi$ .

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

Понятие перманента иногда расширяют на случай произвольной прямоугольной матрицы $A$ размера $m\times n$ следующим способом. Если $m<n$ , то:

\mathrm {Per} (A)=\sum _{\pi }\prod _{i=1}^{m}a_{i,\pi _{i}}

,

где сумма берётся по всем $m$ -элементным размещениям из множества чисел от 1 до $n$ .

Если же $m>n$ , то:

\mathrm {Per} (A)=\mathrm {Per} (A^{T})

.

Или, что эквивалентно, перманент прямоугольной матрицы можно определить как сумму перманентов всех её квадратных подматриц порядка $\min\{\,n,m\,\}$ .

Свойства

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

Перманент не изменяется при транспонировании : $\mathrm {Per} (A^{T})=\mathrm {Per} (A)$ . В отличие от детерминанта, перманент матрицы не изменяется от перестановки строк или столбцов матрицы.

Перманент является линейной функцией от строк (или столбцов) матрицы, то есть:

если умножить любую одну строку (столбец) на некоторое число $c$ , то и значение перманента увеличится в $c$ раз;
перманент суммы двух матриц, отличающихся лишь одной строкой (столбцом), равен сумме их перманентов.

Аналог разложения Лапласа по первой строке матрицы для перманента:

\mathrm {Per} (A)=\sum _{j=1}^{n}a_{1,j}B_{1,j}

,

где $B_{i,j}$ — перманент матрицы, получающейся из $A$ удалением $i$ -й строки и $j$ -го столбца. Так, например, для матрицы размера $3\times 3$ , имеет место:

\mathrm {Per} {\begin{pmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33}\end{pmatrix}}=a_{11}\mathrm {Per} {\begin{pmatrix}a_{22}&a_{23}\\a_{32}&a_{33}\end{pmatrix}}+a_{12}\mathrm {Per} {\begin{pmatrix}a_{21}&a_{23}\\a_{31}&a_{33}\end{pmatrix}}+a_{13}\mathrm {Per} {\begin{pmatrix}a_{21}&a_{22}\\a_{31}&a_{32}\end{pmatrix}}

.

Перманент матрицы порядка $n$ — однородная функция порядка $n$ :

\mathrm {Per} (c\cdot A)=c^{n}\cdot \mathrm {Per} (A)

, где

c\in K

— скаляр.

Если $P$ — перестановочная матрица , то:

\mathrm {Per} (P)=1

;

\mathrm {Per} (AP)=\mathrm {Per} (PA)=\mathrm {Per} (A)

для любой матрицы

A

того же порядка.

Если матрица $A$ состоит из неотрицательных действительных чисел, то $\mathrm {Per} (A)\geqslant \det A$ .

Если $A$ и $B$ — две верхние (или нижние) треугольные матрицы , то:

\mathrm {Per} (AB)=\mathrm {Per} (BA)=\mathrm {Per} (A)\cdot \mathrm {Per} (B)

,

(в общем случае равенство не выполняется для произвольных $A$ и $B$ , в отличие от аналогичного свойства детерминантов).

Перманент дважды стохастической матрицы порядка $n$ не менее, чем $n!/n^{n}$ ( гипотеза ван дер Вардена , доказанная в 1980 году).

Вычисление перманента

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

В настоящее время ^{[

уточнить

]} неизвестен алгоритм решения таких задач за полиномиальное от размера матрицы время. Существование подобного полиномиального алгоритма было бы даже более сильным утверждением, чем знаменитое P=NP .

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

Формула Райзера

Вычисление перманента по определению обладает сложностью $O(n!)$ (или даже $O(n\cdot n!)$ при «грубой» реализации). Оценку можно значительно улучшить, воспользовавшись формулой Райзера :

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

,

с ней перманент может быть вычислен за время $O(2^{n}n^{2})$ или даже $O(2^{n}n)$ , если перечислять подмножества по коду Грея .

Приложения

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

Перманент матрицы $A$ , состоящей из нулей и единиц, можно интерпретировать, как число полных паросочетаний в двудольном графе с матрицей смежности $A$ (то есть ребро между $i$ -й вершиной одной доли и $j$ -й вершиной другой доли существует, если $a_{ij}=1$ ).

Перманент произвольной матрицы можно рассматривать как сумму весов всех полных паросочетаний в полном двудольном графе, где под весом паросочетания понимается произведение весов его рёбер, а веса рёбер записаны в элементах матрицы смежности $A$ .

Примечания

Leslie G. Valiant . The Complexity of Computing the Permanent (англ.) // . — Elsevier, 1979. — Vol. 8 . — P. 189—201 . — doi : .
. Лента.ру (24 декабря 2012). Дата обращения: 25 декабря 2012. 26 декабря 2012 года.
Ryser H. J., «Combinatorial Mathematics», The Carus mathematical monographs series, published by Mathematical Association of America , 1963 (есть русский перевод 1966 г.)
Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .