Перманент

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

В літературі для позначення перманента зазвичай використовують одне з таких позначень: $\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-повною навіть для матриць, що складаються лише з нулів і одиниць.

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

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

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

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

$\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$.

Література

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

Посилання

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