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

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

ОпределениеПравить

Перманент квадратной матрицыПравить

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

 ,

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

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

 .

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

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

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

 ,

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

Если же  , то:

 .

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

СвойстваПравить

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

Перманент не изменяется при транспонировании:  . В отличие от детерминанта, перманент матрицы не изменяется от перестановки строк или столбцов матрицы.

Перманент является линейной функцией от строк (или столбцов) матрицы, то есть:

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

Аналог разложения Лапласа по первой строке матрицы для перманента:

 ,

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

 .

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

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

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

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

Если матрица   состоит из неотрицательных действительных чисел, то  .

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

 ,

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

Перманент дважды стохастической матрицы порядка   не менее, чем   (гипотеза ван дер Вардена, доказанная в 1980 году).

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

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

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

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

Формула РайзераПравить

Вычисление перманента по определению обладает сложностью   (или даже   при «грубой» реализации). Оценку можно значительно улучшить, воспользовавшись формулой Райзера[3][4]:

 ,

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

ПриложенияПравить

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

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

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

ПримечанияПравить

  1. Leslie G. Valiant. The Complexity of Computing the Permanent (англ.) // Theoretical Computer Science[en]. — Elsevier, 1979. — Vol. 8. — P. 189—201. — doi:10.1016/0304-3975(79)90044-6.
  2. Физики разработали фотонный квантовый компьютер. Лента.ру (24 декабря 2012). Дата обращения 25 декабря 2012.
  3. Ryser H. J., «Combinatorial Mathematics», The Carus mathematical monographs series, published by Mathematical Association of America, 1963 (есть русский перевод 1966 г.)
  4. Weisstein, Eric W. Ryser Formula (англ.) на сайте Wolfram MathWorld.

ЛитератураПравить

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

СсылкиПравить