Перманент

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

В літературі для позначення перманента зазвичай використовують одне з таких позначень: $\mathrm {Per} (A)$ , $\mathrm {per} A$ або $\mathrm {perm} A$ .

Визначення

Перманент квадратної матриці

Нехай $A$ — квадратна матриця розміру $n\times n$ , елементи $a_{i,j}$ якої належать деякому полю $K$ . Перманентом матриці $A$ називають число:

\mathrm {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$ :

\mathrm {Per} {\begin{pmatrix}a&b\\c&d\end{pmatrix}}=ad+bc

.

Це визначення відрізняється від аналогічного визначення детермінанта лише тим, що в детермінанті деякі члени суми від'ємні, залежно від знаку перестановки $\pi$ .

Перманент прямокутної матриці

Поняття перманента іноді розширюють на випадок довільної прямокутної матриці $A$ розміру $m\times n$ таким способом. Якщо $m<n$ , то:

\mathrm {Per} (A)=\sum _{\pi }\prod _{i=1}^{m}a_{i,\pi _{i}}

,

де сума береться за всіма $m$ -елементними розміщеннями з множини чисел від 1 до $n$ .

Якщо ж $m>n$ , то:

\mathrm {Per} (A)=\mathrm {Per} (A^{T})

.

Або, що еквівалентно, перманент прямокутної матриці можна визначити як суму перманентів усіх її квадратних підматриць порядку $\min\{\,n,m\,\}$ .

Властивості

Перманент будь-якої діагональної або трикутної матриці дорівнює добутку елементів на її діагоналі. Зокрема, перманент нульової матриці дорівнює нулю, а перманент одиничної матриці — одиниці.

Перманент не змінюється при транспонуванні: $\mathrm {Per} (A^{T})=\mathrm {Per} (A)$ . На відміну від детермінанта, перманент матриці не змінюється від перестановки рядків або стовпців матриці.

Перманент є лінійною функцією від рядків (або стовпців) матриці, тобто:

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

Аналог розкладу Лапласа за першим рядком матриці для перманента:

\mathrm {Per} (A)=\sum _{j=1}^{n}a_{1,j}B_{1,j}

,

де $B_{i,j}$ — перманент матриці, отримуваної з $A$ видаленням $i$ -го рядка та $j$ -го стовпця. Так, наприклад, для матриці розміру $3\times 3$ , має місце:

\mathrm {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}\mathrm {Per} {\begin{pmatrix}a_{22}&a_{23}\\a_{32}&a_{33}\end{pmatrix}}+a_{12}\mathrm {Per} {\begin{pmatrix}a_{21}&a_{23}\\a_{31}&a_{33}\end{pmatrix}}+a_{13}\mathrm {Per} {\begin{pmatrix}a_{21}&a_{22}\\a_{31}&a_{32}\end{pmatrix}}

.

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

\mathrm {Per} (c\cdot A)=c^{n}\cdot \mathrm {Per} (A)

, де

c\in K

— скаляр.

Якщо $P$ — матриця перестановки, то:

\mathrm {Per} (P)=1

;

\mathrm {Per} (AP)=\mathrm {Per} (PA)=\mathrm {Per} (A)

для будь-якої матриці

A

того ж порядку.

Якщо матриця $A$ складається з невід'ємних дійсних чисел, то $\mathrm {Per} (A)\geqslant \det A$ .

Якщо $A$ і $B$ — дві верхні (або нижні) трикутні матриці, то:

\mathrm {Per} (AB)=\mathrm {Per} (BA)=\mathrm {Per} (A)\cdot \mathrm {Per} (B)

,

(в загальному випадку рівність не виконується для довільних $A$ і $B$ , на відміну від аналогічної властивості визначників).

Перманент двічі стохастичної матриці порядку $n$ не менший, ніж $n!/n^{n}$ (гіпотеза ван дер Вардена, доведена 1980 року).

Обчислення перманента

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

Нині^{[уточнити]} невідомий алгоритм розв'язання таких задач за поліноміальний від розміру матриці час. Існування подібного поліноміального алгоритму було б навіть сильнішим твердженням, ніж знамените P=NP.

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

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

Обчислення перманента за визначенням має складність $O(n!)$ (або навіть $O(n\cdot n!)$ за «грубої» реалізації). Оцінку можна значно поліпшити, скориставшись формулою Райзера[3]:

\mathrm {Per} (A)=(-1)^{n}\sum _{S\subseteq \{1,\dots ,n\}}(-1)^{|S|}\prod _{i=1}^{n}\sum _{j\in S}a_{ij}

,

за якою перманент можна обчислити за час $O(2^{n}n^{2})$ або навіть $O(2^{n}n)$ , якщо перелічувати підмножини за кодом Грея.

Застосування

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

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

Перманент довільної матриці можна розглядати як суму ваг усіх повних парувань у повному двочастковому графі, де під вагою парування розуміється добуток ваг його ребер, а ваги ребер записано в елементах матриці суміжності $A$ .

Примітки

Leslie G. Valiant. The Complexity of Computing the Permanent // Theoretical Computer Science. — Elsevier, 1979. — Vol. 8 (23 January). — P. 189—201. — DOI:10.1016/0304-3975(79)90044-6.
Физики разработали фотонный квантовый компьютер (рос.). Lenta.ru. 24 грудня 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.(англ.)

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Leslie G. Valiant. The Complexity of Computing the Permanent // Theoretical Computer Science. — Elsevier, 1979. — Vol. 8 (23 January). — P. 189—201. — DOI:10.1016/0304-3975(79)90044-6.

[2] Физики разработали фотонный квантовый компьютер (рос.). Lenta.ru. 24 грудня 2012. Процитовано 25 грудня 2012.

[3] Ryser H. J., «Combinatorial Mathematics», The Carus mathematical monographs series, published by Mathematical Association of America, 1963 (есть русский перевод 1966 г.)