WikiSort.ru - Не сортированное

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

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

Определение

Свойства

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

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

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

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

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

  ${\displaystyle {\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}}.}$

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

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

Примечания

Литература

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

Ссылки

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

• Weisstein, Eric W. Permanent (англ.) на сайте Wolfram MathWorld.
• Permanent (англ.) на сайте PlanetMath.