Перманент

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

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

Визначення

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

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

$\mathrm{P}\mathrm{e}\mathrm{r}(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{P}\mathrm{e}\mathrm{r}\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)=ad+bc$.

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

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

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

$\mathrm{P}\mathrm{e}\mathrm{r}(A)=\sum _{\pi }\prod _{i=1}^m{a}_{i,{\pi }_i}$,

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

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

$\mathrm{P}\mathrm{e}\mathrm{r}(A)=\mathrm{P}\mathrm{e}\mathrm{r}(A^T)$.

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

Властивості

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

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

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

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

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

$\mathrm{P}\mathrm{e}\mathrm{r}(A)=\sum _{j=1}^n{a}_{1,j}{B}_{1,j}$,

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

$\mathrm{P}\mathrm{e}\mathrm{r}\left(\begin{array}{ccc}{a}_{11}& a_{12}& a_{13}\\ a_{21}& a_{22}& a_{23}\\ a_{31}& a_{32}& a_{33}\end{array}\right)=a_{11}\mathrm{P}\mathrm{e}\mathrm{r}\left(\begin{array}{cc}{a}_{22}& a_{23}\\ a_{32}& a_{33}\end{array}\right)+a_{12}\mathrm{P}\mathrm{e}\mathrm{r}\left(\begin{array}{cc}{a}_{21}& a_{23}\\ a_{31}& a_{33}\end{array}\right)+a_{13}\mathrm{P}\mathrm{e}\mathrm{r}\left(\begin{array}{cc}{a}_{21}& a_{22}\\ a_{31}& a_{32}\end{array}\right)$.

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

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

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

$\mathrm{P}\mathrm{e}\mathrm{r}(P)=1$;

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

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

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

$\mathrm{P}\mathrm{e}\mathrm{r}(AB)=\mathrm{P}\mathrm{e}\mathrm{r}(BA)=\mathrm{P}\mathrm{e}\mathrm{r}(A)\cdot \mathrm{P}\mathrm{e}\mathrm{r}(B)$,

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

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

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

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

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

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

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

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

$\mathrm{P}\mathrm{e}\mathrm{r}(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$.

Література

• Шаблон:Книга

Посилання

• Шаблон:MathWorld
• Шаблон:PlanetMath