Перманент

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

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

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

${\displaystyle \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}}}$,

де сума береться за всіма перестановками ${\displaystyle \pi }$ чисел від 1 до ${\displaystyle n}$.

Наприклад, для матриці розміру ${\displaystyle 2\times 2}$:

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

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

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

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

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

Якщо ж ${\displaystyle m>n}$, то:

${\displaystyle \mathrm {Per} (A)=\mathrm {Per} (A^{T})}$.

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

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

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

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

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

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

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

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

${\displaystyle \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}}}$.

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

${\displaystyle \mathrm {Per} (c\cdot A)=c^{n}\cdot \mathrm {Per} (A)}$, де ${\displaystyle c\in K}$ — скаляр.

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

${\displaystyle \mathrm {Per} (P)=1}$;

${\displaystyle \mathrm {Per} (AP)=\mathrm {Per} (PA)=\mathrm {Per} (A)}$ для будь-якої матриці ${\displaystyle A}$ того ж порядку.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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