Перманент

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

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

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

Определение

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

$\mbox{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$:

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

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

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

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

$\mbox{Per}(A) = \sum_{\pi} \prod_{i=1}^m a_{i, \pi_i},$

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

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

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

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

Свойства

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

  $\mbox{Per}(A^T) = \mbox{Per}(A)$

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

  $\mbox{Per}(A) = \sum_{j=1}^{n} a_{1,j} B_{1,j}$, где $B_{i,j}$ — перманент матрицы, получающейся из $A$ удалением $i$-й строки и $j$-го столбца.

• Так, например, для матрицы размера $3 \times 3$, имеем:

  $\mbox{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} \mbox{Per} \begin{pmatrix} a_{22} & a_{23} \\ a_{32} & a_{33} \end{pmatrix} + a_{12} \mbox{Per} \begin{pmatrix} a_{21} & a_{23} \\ a_{31} & a_{33} \end{pmatrix} + a_{13} \mbox{Per} \begin{pmatrix} a_{21} & a_{22} \\ a_{31} & a_{32} \end{pmatrix}.$

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

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

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

  $\mbox{Per}(P) = 1;$

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

• Если матрица $A$ состоит из неотрицательных действительных чисел, то $\mbox{Per}(A) \geq \det A$.
• Если $A$ и $B$ — две верхние (или нижние) треугольные матрицы, то:

  $\mbox{Per}(AB) = \mbox{Per}(BA) = \mbox{Per}(A) \cdot \mbox{Per}(B).$

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

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

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

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

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

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

Вычисление перманента по определению занимает $O(n!)$ времени. Его можно значительно улучшить, воспользовавшись формулой Райзера:^[3][4]

$\mbox{Per}(A) = (-1)^n \sum_{S\subseteq\{1,\dots,n\}} (-1)^{|S|} \prod_{i=1}^n \sum_{j\in S} a_{ij}.$

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

Приложения

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

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

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

Примечания

1. ↑ Leslie G. Valiant (1979). «The Complexity of Computing the Permanent». Theoretical Computer Science (Elsevier) 8: 189–201. DOI:10.1016/0304-3975(79)90044-6.
2. ↑ Физики разработали фотонный квантовый компьютер  (рус.). Лента.ру (24 декабря 2012). Проверено 25 декабря 2012.
3. ↑ Ryser H. J., «Combinatorial Mathematics», The Carus mathematical monographs series, published by Mathematical Association of America, 1963
4. ↑ Ryser Formula — from Wolfram MathWorld

Ссылки

В Викисловаре есть статья «перманент»

• http://mathworld.wolfram.com/Permanent.html
• http://planetmath.org/encyclopedia/Permanent.html