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

{{эта статья|о математическом понятии|Химическая завивка|о завивке волос}}
'''Пермане́нт''' в математике — числовая [[Функция (математика)|функция]], определённая на множестве всех [[Матрица (математика)|матриц]]; для квадратных матриц похожа на [[детерминант]], и отличается от него лишь в том, что в разложении на перестановки (или на [[Минор (линейная алгебра)|миноры]]) берутся не чередующиеся знаки, а все плюсы. В отличие от детерминанта, определение перманента расширено и на неквадратные матрицы.

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

== Определение ==

=== Перманент квадратной матрицы ===
Пусть <math>A</math> — квадратная матрица размера <math>n \times n</math>, элементы <math>a_{i, j}</math> которой принадлежат некоторому [[Поле (алгебра)|полю]] <math>K</math>.
Перманентом матрицы <math>A</math> называется число:
: <math>\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}</math>,
где сумма берётся по всем [[перестановка]]м <math>\pi</math> чисел от 1 до <math>n</math>.

Например, для матрицы размера <math>2 \times 2</math>:
: <math>\mathrm{Per} \begin{pmatrix} a & b \\ c & d \end{pmatrix} = ad + bc</math>.

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

=== Перманент прямоугольной матрицы ===
Понятие перманента иногда расширяют на случай произвольной прямоугольной матрицы <math>A</math> размера <math>m \times n</math> следующим способом. Если <math>m < n</math>, то:
: <math>\mathrm{Per}(A) = \sum_{\pi} \prod_{i=1}^m a_{i, \pi_i}</math>,
где сумма берётся по всем <math>m</math>-элементным [[Размещение|размещениям]] из множества чисел от 1 до <math>n</math>.

Если же <math>m > n</math>, то:
: <math>\mathrm{Per}(A) = \mathrm{Per}(A^T)</math>.

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

== Свойства ==
Перманент любой [[Диагональная матрица|диагональной]] или [[Треугольная матрица|треугольной]] матрицы равен произведению элементов на её диагонали. В частности, перманент [[Нулевая матрица|нулевой матрицы]] равен нулю, а перманент [[Единичная матрица|единичной матрицы]] — единице.

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

Перманент является [[Линейная функция|линейной функцией]] от строк (или столбцов) матрицы, то есть:
* если умножить любую одну строку (столбец) на некоторое число <math>c</math>, то и значение перманента увеличится в <math>c</math> раз;
* перманент суммы двух матриц, отличающихся лишь одной строкой (столбцом), равен сумме их перманентов.

Аналог [[Разложение Лапласа|разложения Лапласа]] по первой строке матрицы для перманента:
: <math>\mathrm{Per}(A) = \sum_{j=1}^{n} a_{1,j} B_{1,j}</math>, 
где <math>B_{i,j}</math> — перманент матрицы, получающейся из <math>A</math> удалением <math>i</math>-й строки и <math>j</math>-го столбца.
Так, например, для матрицы размера <math>3 \times 3</math>, имеет место:
: <math>
   \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}</math>.

Перманент матрицы порядка <math>n</math> — [[однородная функция]] порядка <math>n</math>:
: <math>\mathrm{Per}(c \cdot A) = c^n \cdot \mathrm{Per}(A)</math>, где <math>c \in K</math> — скаляр.

Если <math>P</math> — [[перестановочная матрица]], то:
: <math>\mathrm{Per}(P) = 1</math>;
: <math>\mathrm{Per}(AP) = \mathrm{Per}(PA) = \mathrm{Per}(A)</math> для любой матрицы <math>A</math> того же порядка.

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

Если <math>A</math> и <math>B</math> — две верхние (или нижние) [[Треугольная матрица|треугольные матрицы]], то:
: <math>\mathrm{Per}(AB) = \mathrm{Per}(BA) = \mathrm{Per}(A) \cdot \mathrm{Per}(B)</math>,

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

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

== Вычисление перманента ==
В отличие от детерминанта, который может быть легко вычислен, например [[Метод Гаусса|методом Гаусса]], вычисление перманента является очень трудоёмкой вычислительной задачей, относящейся к [[Класс сложности|классу сложности]] [[Класс Sharp-P|#P-полных]] задач. Она остаётся #P-полной даже для матриц, состоящих лишь из нулей и единиц<ref>{{статья
|заглавие=The Complexity of Computing the Permanent
|издание={{iw|Theoretical Computer Science (журнал)|Theoretical Computer Science||Theoretical Computer Science (journal)}}
|том=8
|страницы=189—201
|издательство=Elsevier
|doi=10.1016/0304-3975(79)90044-6
|язык=en
|автор=[[Вэлиант, Лесли|Leslie G. Valiant]]
|год=1979
}}</ref>.

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

В декабре 2012 четыре независимые группы исследователей предложили прототип квантового фотонного устройства, вычисляющего перманент матрицы<ref>{{cite web
 |url          = http://lenta.ru/news/2012/12/24/photoncomp/
 |title        = Физики разработали фотонный квантовый компьютер
 |author       = 
 |date         = 2012-12-24
 |work         = 
 |publisher    = [[Лента.ру]]
 |accessdate   = 2012-12-25
 |lang         = ru
 |deadlink     = no
 |archive-date = 2012-12-26
 |archive-url  = https://web.archive.org/web/20121226225706/http://lenta.ru/news/2012/12/24/photoncomp/
}}</ref>.

=== Формула Райзера ===
Вычисление перманента по определению обладает [[Сложность алгоритма|сложностью]] <math>O(n!)</math> (или даже <math>O(n \cdot n!)</math> при «грубой» реализации). Оценку можно значительно улучшить, воспользовавшись формулой Райзера<ref>Ryser H. J., «Combinatorial Mathematics», ''The Carus mathematical monographs'' series, published by [[Mathematical Association of America]], 1963 (есть русский перевод 1966 г.)</ref><ref>{{MathWorld|urlname=RyserFormula|title=Ryser Formula}}</ref>:
: <math>\mathrm{Per}(A) = (-1)^n \sum_{S\subseteq\{1,\dots,n\}} (-1)^{|S|} \prod_{i=1}^n \sum_{j\in S} a_{ij}</math>,
с ней перманент может быть вычислен за время <math>O(2^nn^2)</math> или даже <math>O(2^nn)</math>, если перечислять подмножества по [[Код Грея|коду Грея]].

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

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

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

Кроме того, перманент матрицы <math>A</math> размера <math>n</math>x<math>n</math>, состоящей из одних единиц, можно интерпретировать, как число способов размещения <math>n</math> неатакующих друг друга [[Ладья (шахматы)|ладей]] на шахматной доске размера <math>n</math>x<math>n</math>.<ref>{{Cite journal
|last1=Шевелев
|first1=В.С.
|year=1990
|title=Об одном представлении ладейных многочленов
|journal=УМН
|volume=45
|issue=4(274)
|pages=171–172
|url=http://mi.mathnet.ru/rm4775
|doi=10.1070/RM1990v045n04ABEH002387
}}</ref>

== Примечания ==
{{примечания}}

== Литература ==
* {{книга
|автор = Минк Х.
|заглавие = Перманенты
|место = М. 
|издательство = Мир 
|год = 1982 
|страниц = 211 
}}

== Ссылки ==
{{викисловарь}}
* {{MathWorld|urlname=Permanent|title=Permanent}}
* {{PlanetMath|title=Permanent|urlname=Permanent}}

[[Категория:Матричные инварианты]]
[[Категория:Комбинаторика]]