Перманент

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

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

Определение

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

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

$\mathrm{P}\mathrm{e}\mathrm{r}(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{P}\mathrm{e}\mathrm{r}\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)=ad+bc$.

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

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

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

$\mathrm{P}\mathrm{e}\mathrm{r}(A)=\sum _{\pi }\prod _{i=1}^m{a}_{i,{\pi }_i}$,

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

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

$\mathrm{P}\mathrm{e}\mathrm{r}(A)=\mathrm{P}\mathrm{e}\mathrm{r}(A^T)$.

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

Свойства

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

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

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

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

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

$\mathrm{P}\mathrm{e}\mathrm{r}(A)=\sum _{j=1}^n{a}_{1,j}{B}_{1,j}$,

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

$\mathrm{P}\mathrm{e}\mathrm{r}\left(\begin{array}{ccc}{a}_{11}& a_{12}& a_{13}\\ a_{21}& a_{22}& a_{23}\\ a_{31}& a_{32}& a_{33}\end{array}\right)=a_{11}\mathrm{P}\mathrm{e}\mathrm{r}\left(\begin{array}{cc}{a}_{22}& a_{23}\\ a_{32}& a_{33}\end{array}\right)+a_{12}\mathrm{P}\mathrm{e}\mathrm{r}\left(\begin{array}{cc}{a}_{21}& a_{23}\\ a_{31}& a_{33}\end{array}\right)+a_{13}\mathrm{P}\mathrm{e}\mathrm{r}\left(\begin{array}{cc}{a}_{21}& a_{22}\\ a_{31}& a_{32}\end{array}\right)$.

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

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

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

$\mathrm{P}\mathrm{e}\mathrm{r}(P)=1$;

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

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

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

$\mathrm{P}\mathrm{e}\mathrm{r}(AB)=\mathrm{P}\mathrm{e}\mathrm{r}(BA)=\mathrm{P}\mathrm{e}\mathrm{r}(A)\cdot \mathrm{P}\mathrm{e}\mathrm{r}(B)$,

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

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

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

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

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

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

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

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

$\mathrm{P}\mathrm{e}\mathrm{r}(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$.

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

Литература

• Шаблон:Книга

Ссылки

• Шаблон:MathWorld
• Шаблон:PlanetMath