Перманент
Пермане́нт в математике — числовая функция, определённая на множестве всех матриц; для квадратных матриц похожа на детерминант, и отличается от него лишь в том, что в разложении на перестановки (или на миноры) берутся не чередующиеся знаки, а все плюсы. В отличие от детерминанта, определение перманента расширено и на неквадратные матрицы.
В литературе для обозначения перманента обычно используется одна из следующих нотаций: [math]\displaystyle{ \mathrm{Per}(A) }[/math], [math]\displaystyle{ \mathrm{per } A }[/math] или [math]\displaystyle{ \mathrm{perm } A }[/math].
Определение
Перманент квадратной матрицы
Пусть [math]\displaystyle{ A }[/math] — квадратная матрица размера [math]\displaystyle{ n \times n }[/math], элементы [math]\displaystyle{ a_{i, j} }[/math] которой принадлежат некоторому полю [math]\displaystyle{ K }[/math]. Перманентом матрицы [math]\displaystyle{ A }[/math] называется число:
- [math]\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} }[/math],
где сумма берётся по всем перестановкам [math]\displaystyle{ \pi }[/math] чисел от 1 до [math]\displaystyle{ n }[/math].
Например, для матрицы размера [math]\displaystyle{ 2 \times 2 }[/math]:
- [math]\displaystyle{ \mathrm{Per} \begin{pmatrix} a & b \\ c & d \end{pmatrix} = ad + bc }[/math].
Это определение отличается от аналогичного определения детерминанта лишь тем, что в детерминанте некоторые члены суммы имеют отрицательный знак, в зависимости от знака перестановки [math]\displaystyle{ \pi }[/math].
Перманент прямоугольной матрицы
Понятие перманента иногда расширяют на случай произвольной прямоугольной матрицы [math]\displaystyle{ A }[/math] размера [math]\displaystyle{ m \times n }[/math] следующим способом. Если [math]\displaystyle{ m \lt n }[/math], то:
- [math]\displaystyle{ \mathrm{Per}(A) = \sum_{\pi} \prod_{i=1}^m a_{i, \pi_i} }[/math],
где сумма берётся по всем [math]\displaystyle{ m }[/math]-элементным размещениям из множества чисел от 1 до [math]\displaystyle{ n }[/math].
Если же [math]\displaystyle{ m \gt n }[/math], то:
- [math]\displaystyle{ \mathrm{Per}(A) = \mathrm{Per}(A^T) }[/math].
Или, что эквивалентно, перманент прямоугольной матрицы можно определить как сумму перманентов всех её квадратных подматриц порядка [math]\displaystyle{ \min\{\,n, m\,\} }[/math].
Свойства
Перманент любой диагональной или треугольной матрицы равен произведению элементов на её диагонали. В частности, перманент нулевой матрицы равен нулю, а перманент единичной матрицы — единице.
Перманент не изменяется при транспонировании: [math]\displaystyle{ \mathrm{Per}(A^T) = \mathrm{Per}(A) }[/math]. В отличие от детерминанта, перманент матрицы не изменяется от перестановки строк или столбцов матрицы.
Перманент является линейной функцией от строк (или столбцов) матрицы, то есть:
- если умножить любую одну строку (столбец) на некоторое число [math]\displaystyle{ c }[/math], то и значение перманента увеличится в [math]\displaystyle{ c }[/math] раз;
- перманент суммы двух матриц, отличающихся лишь одной строкой (столбцом), равен сумме их перманентов.
Аналог разложения Лапласа по первой строке матрицы для перманента:
- [math]\displaystyle{ \mathrm{Per}(A) = \sum_{j=1}^{n} a_{1,j} B_{1,j} }[/math],
где [math]\displaystyle{ B_{i,j} }[/math] — перманент матрицы, получающейся из [math]\displaystyle{ A }[/math] удалением [math]\displaystyle{ i }[/math]-й строки и [math]\displaystyle{ j }[/math]-го столбца. Так, например, для матрицы размера [math]\displaystyle{ 3 \times 3 }[/math], имеет место:
- [math]\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} }[/math].
Перманент матрицы порядка [math]\displaystyle{ n }[/math] — однородная функция порядка [math]\displaystyle{ n }[/math]:
- [math]\displaystyle{ \mathrm{Per}(c \cdot A) = c^n \cdot \mathrm{Per}(A) }[/math], где [math]\displaystyle{ c \in K }[/math] — скаляр.
Если [math]\displaystyle{ P }[/math] — перестановочная матрица, то:
- [math]\displaystyle{ \mathrm{Per}(P) = 1 }[/math];
- [math]\displaystyle{ \mathrm{Per}(AP) = \mathrm{Per}(PA) = \mathrm{Per}(A) }[/math] для любой матрицы [math]\displaystyle{ A }[/math] того же порядка.
Если матрица [math]\displaystyle{ A }[/math] состоит из неотрицательных действительных чисел, то [math]\displaystyle{ \mathrm{Per}(A) \geqslant \det A }[/math].
Если [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math] — две верхние (или нижние) треугольные матрицы, то:
- [math]\displaystyle{ \mathrm{Per}(AB) = \mathrm{Per}(BA) = \mathrm{Per}(A) \cdot \mathrm{Per}(B) }[/math],
(в общем случае равенство не выполняется для произвольных [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math], в отличие от аналогичного свойства детерминантов).
Перманент дважды стохастической матрицы порядка [math]\displaystyle{ n }[/math] не менее, чем [math]\displaystyle{ n! / n^n }[/math] (гипотеза ван дер Вардена, доказанная в 1980 году).
Вычисление перманента
В отличие от детерминанта, который может быть легко вычислен, например методом Гаусса, вычисление перманента является очень трудоёмкой вычислительной задачей, относящейся к классу сложности #P-полных задач. Она остаётся #P-полной даже для матриц, состоящих лишь из нулей и единиц[1].
В настоящее время[уточнить] неизвестен алгоритм решения таких задач за полиномиальное от размера матрицы время. Существование подобного полиномиального алгоритма было бы даже более сильным утверждением, чем знаменитое P=NP.
В декабре 2012 четыре независимые группы исследователей предложили прототип квантового фотонного устройства, вычисляющего перманент матрицы[2].
Формула Райзера
Вычисление перманента по определению обладает сложностью [math]\displaystyle{ O(n!) }[/math] (или даже [math]\displaystyle{ O(n \cdot n!) }[/math] при «грубой» реализации). Оценку можно значительно улучшить, воспользовавшись формулой Райзера[3][4]:
- [math]\displaystyle{ \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]\displaystyle{ O(2^nn^2) }[/math] или даже [math]\displaystyle{ O(2^nn) }[/math], если перечислять подмножества по коду Грея.
Приложения
Перманент практически не используется в линейной алгебре, но находит применение в дискретной математике и комбинаторике.
Перманент матрицы [math]\displaystyle{ A }[/math], состоящей из нулей и единиц, можно интерпретировать, как число полных паросочетаний в двудольном графе с матрицей смежности [math]\displaystyle{ A }[/math] (то есть ребро между [math]\displaystyle{ i }[/math]-й вершиной одной доли и [math]\displaystyle{ j }[/math]-й вершиной другой доли существует, если [math]\displaystyle{ a_{ij} = 1 }[/math]).
Перманент произвольной матрицы можно рассматривать как сумму весов всех полных паросочетаний в полном двудольном графе, где под весом паросочетания понимается произведение весов его рёбер, а веса рёбер записаны в элементах матрицы смежности [math]\displaystyle{ A }[/math].
Примечания
- ↑ 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.
- ↑ Физики разработали фотонный квантовый компьютер . Лента.ру (24 декабря 2012). Дата обращения: 25 декабря 2012. Архивировано 26 декабря 2012 года.
- ↑ Ryser H. J., «Combinatorial Mathematics», The Carus mathematical monographs series, published by Mathematical Association of America, 1963 (есть русский перевод 1966 г.)
- ↑ Weisstein, Eric W. Ryser Formula (англ.) на сайте Wolfram MathWorld.
Литература
- Минк Х. Перманенты. — М.: Мир, 1982. — 211 с.
Ссылки
- Weisstein, Eric W. Permanent (англ.) на сайте Wolfram MathWorld.
- Permanent (англ.) на сайте PlanetMath.