Перманент
Перманент у математиці — числова функція, визначена на множині всіх матриць; для квадратних матриць схожа на детермінант, і відрізняється від нього лише в тому, що в розкладі на перестановки (або на мінори) беруться не почергові знаки, а всі плюси. На відміну від детермінанта, визначення перманента розширено і на неквадратні матриці.
В літературі для позначення перманента зазвичай використовують одне з таких позначень: , або .
Визначення[ред. | ред. код]
Перманент квадратної матриці[ред. | ред. код]
Нехай — квадратна матриця розміру , елементи якої належать деякому полю . Перманентом матриці називають число:
- ,
де сума береться за всіма перестановками чисел від 1 до .
Наприклад, для матриці розміру :
- .
Це визначення відрізняється від аналогічного визначення детермінанта лише тим, що в детермінанті деякі члени суми від'ємні, залежно від знаку перестановки .
Перманент прямокутної матриці[ред. | ред. код]
Поняття перманента іноді розширюють на випадок довільної прямокутної матриці розміру таким способом. Якщо , то:
- ,
де сума береться за всіма -елементними розміщеннями з множини чисел від 1 до .
Якщо ж , то:
- .
Або, що еквівалентно, перманент прямокутної матриці можна визначити як суму перманентів усіх її квадратних підматриць порядку .
Властивості[ред. | ред. код]
Перманент будь-якої діагональної або трикутної матриці дорівнює добутку елементів на її діагоналі. Зокрема, перманент нульової матриці дорівнює нулю, а перманент одиничної матриці — одиниці.
Перманент не змінюється при транспонуванні: . На відміну від детермінанта, перманент матриці не змінюється від перестановки рядків або стовпців матриці.
Перманент є лінійною функцією від рядків (або стовпців) матриці, тобто:
- якщо помножити будь-який один рядок (стовпець) на деяке число , то й значення перманента збільшиться в разів;
- перманент суми двох матриць, що відрізняються лише одним рядком (стовпцем), дорівнює сумі їхніх перманентів.
Аналог розкладу Лапласа за першим рядком матриці для перманента:
- ,
де — перманент матриці, отримуваної з видаленням -го рядка та -го стовпця. Так, наприклад, для матриці розміру , має місце:
- .
Перманент матриці порядку — однорідна функція порядку :
- , де — скаляр.
Якщо — матриця перестановки, то:
- ;
- для будь-якої матриці того ж порядку.
Якщо матриця складається з невід'ємних дійсних чисел, то .
Якщо і — дві верхні (або нижні) трикутні матриці, то:
- ,
(в загальному випадку рівність не виконується для довільних і , на відміну від аналогічної властивості визначників).
Перманент двічі стохастичної матриці порядку не менший, ніж (гіпотеза ван дер Вардена, доведена 1980 року).
Обчислення перманента[ред. | ред. код]
На відміну від детермінанта, який можна легко обчислити, наприклад, методом Гауса, обчислення перманента є дуже трудомісткою обчислювальною задачею, що належить до класу складності #P-повних задач. Вона залишається #P-повною навіть для матриць, що складаються лише з нулів і одиниць[1].
Нині[уточнити] невідомий алгоритм розв'язання таких задач за поліноміальний від розміру матриці час. Існування подібного поліноміального алгоритму було б навіть сильнішим твердженням, ніж знамените P=NP.
У грудні 2012 чотири незалежні групи дослідників запропонували прототип квантового фотонного пристрою, який обчислює перманент матриці[2].
Формула Райзера[ред. | ред. код]
Обчислення перманента за визначенням має складність (або навіть за «грубої» реалізації). Оцінку можна значно поліпшити, скориставшись формулою Райзера[3]:
- ,
за якою перманент можна обчислити за час або навіть , якщо перелічувати підмножини за кодом Грея.
Застосування[ред. | ред. код]
Перманент практично не використовується в лінійній алгебрі, але знаходить застосування в дискретній математиці та комбінаториці.
Перманент матриці , що складається з нулів і одиниць, можна інтерпретувати як число повних парувань у двочастковому графі з матрицею суміжності (тобто ребро між -ю вершиною однієї частки і -ю вершиною іншої частки існує, якщо ).
Перманент довільної матриці можна розглядати як суму ваг усіх повних парувань у повному двочастковому графі, де під вагою парування розуміється добуток ваг його ребер, а ваги ребер записано в елементах матриці суміжності .
Примітки[ред. | ред. код]
- ↑ Leslie G. Valiant. The Complexity of Computing the Permanent // Theoretical Computer Science[en]. — Elsevier, 1979. — Vol. 8 (14 May). — P. 189—201. — DOI: .
- ↑ Физики разработали фотонный квантовый компьютер (рос.). Lenta.ru. 24 грудня 2012. Архів оригіналу за 26 грудня 2012. Процитовано 25 грудня 2012.
- ↑ Ryser H. J., «Combinatorial Mathematics», The Carus mathematical monographs series, published by Mathematical Association of America, 1963 (есть русский перевод 1966 г.)
Література[ред. | ред. код]
- Минк Х. Перманенты. — М. : Мир, 1982. — 211 с.
Посилання[ред. | ред. код]
- Weisstein, Eric W. Permanent(англ.) на сайті Wolfram MathWorld.
- Permanent на PlanetMath.(англ.)