Перманент

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

В литературе для обозначения перманента обычно используется одна из следующих нотаций: \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. Архивировано из первоисточника 27 декабря 2012.
  3. Ryser H. J., «Combinatorial Mathematics», The Carus mathematical monographs series, published by Mathematical Association of America, 1963
  4. Weisstein, Eric W. Ryser Formula (англ.) на сайте Wolfram MathWorld.

Литература[править | править исходный текст]

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

Ссылки[править | править исходный текст]

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