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

В литературе для обозначения перманента обычно используется одна из следующих нотаций: , или .

Определение

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

где сумма берётся по всем перестановкам чисел от 1 до .

Например, для матрицы размера :

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

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

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

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

Если же , то:

.

Или, что эквивалентно, перманент прямоугольной матрицы можно определить как сумму перманентов всех её квадратных подматриц порядка ;

Свойства

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

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

  , где  — перманент матрицы, получающейся из удалением -й строки и -го столбца.

• Так, например, для матрицы размера , имеем:

  

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

  , где  — скаляр.

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

  для любой матрицы того же порядка.

• Если матрица состоит из неотрицательных действительных чисел, то .
• Если и  — две верхние (или нижние) треугольные матрицы, то:

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

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

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

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

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

Вычисление перманента по определению занимает времени. Его можно значительно улучшить, воспользовавшись формулой Райзера:^[2][3]

Формула Райзера может быть вычислена за время или даже , если перечислять подмножества по коду Грея.

Приложения

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

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

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

Примечания