Перманент

Эта статья о математическом понятии; о завивке волос см. Химическая завивка.

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

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

Определение

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

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

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

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

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

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

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

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

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

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

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

Если же ${\displaystyle m>n}$, то:

${\displaystyle \mathrm {Per} (A)=\mathrm {Per} (A^{T})}$.

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

Свойства

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

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

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

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

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

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

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

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

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

${\displaystyle \mathrm {Per} (c\cdot A)=c^{n}\cdot \mathrm {Per} (A)}$, где ${\displaystyle c\in K}$ — скаляр.

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

${\displaystyle \mathrm {Per} (P)=1}$;

${\displaystyle \mathrm {Per} (AP)=\mathrm {Per} (PA)=\mathrm {Per} (A)}$ для любой матрицы ${\displaystyle A}$ того же порядка.

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

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

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

Кроме того, перманент матрицы ${\displaystyle A}$ размера ${\displaystyle n}$x${\displaystyle n}$, состоящей из одних единиц, можно интерпретировать, как число способов размещения ${\displaystyle n}$ неатакующих друг друга ладей на шахматной доске размера ${\displaystyle n}$x${\displaystyle n}$.^[5]