Перманент

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

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

В литературе для обозначения перманента обычно используется одна из следующих нотаций: ${\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]

Примечания

1. Leslie G. Valiant. The Complexity of Computing the Permanent (англ.) // Theoretical Computer Science^[англ.]. — Elsevier, 1979. — Vol. 8. — P. 189—201. — doi:10.1016/0304-3975(79)90044-6.
2. Физики разработали фотонный квантовый компьютер  (рус.). Лента.ру (24 декабря 2012). Дата обращения: 25 декабря 2012. Архивировано 26 декабря 2012 года.
3. Ryser H. J., «Combinatorial Mathematics», The Carus mathematical monographs series, published by Mathematical Association of America, 1963 (есть русский перевод 1966 г.)
4. Weisstein, Eric W. Ryser Formula (англ.) на сайте Wolfram MathWorld.
5. Шевелев, В.С. (1990). "Об одном представлении ладейных многочленов". УМН. 45 (4(274)): 171–172. doi:10.1070/RM1990v045n04ABEH002387.

Литература

• Минк Х. Перманенты. — М.: Мир, 1982. — 211 с.

Ссылки

• Weisstein, Eric W. Permanent (англ.) на сайте Wolfram MathWorld.
• Permanent (англ.) на сайте PlanetMath.