Permanent

Permanent – funkcja przyporządkowująca każdej macierzy kwadratowej stopnia $n$ o współczynnikach z pierścienia przemiennego $R$ pewien element tego pierścienia. Podobnie jak wyznacznik permanent jest wielomianem stopnia $n$ z $n^{2}$ zmiennymi, w którym każdy składnik ma $n$ czynników, z których każde dwa są z różnych kolumn i z różnych wierszy macierzy.

Permanent jest symetryczną formą wieloliniową na $n$ wierszach/kolumnach, traktowanych jako wektory przestrzeni liniowej wymiaru $n.$

Definicja

Dla macierzy kwadratowej

A={\begin{bmatrix}a_{1,1}&\cdots &a_{1,n}\\\vdots &\ddots &\vdots \\a_{n,1}&\cdots &a_{n,n}\end{bmatrix}}

permanent $\operatorname {perm} (A)$ definiuje się jako

\operatorname {perm} (A):=\sum _{\sigma \in {\mathcal {S}}_{n}}\prod _{i=1}^{n}a_{i,\sigma (i)}.

gdzie suma przebiega wszystkie elementy $\sigma$ grupy symetrycznej ${\mathcal {S}}_{n},$ tj. wszystkie permutacje zbioru liczb $1,2,\dots ,n.$

Definicja permanentu macierzy $A$ różni się więc od wzoru permutacyjnego dla wyznacznika macierzy $A$ tym, że znak permutacji nie jest brany pod uwagę.

Oprócz oznaczenia $\operatorname {perm} (A)$ stosuje się też zapis $\operatorname {per} (A)$ w wariantach wielką literą i w notacji beznawiasowej (jeśli nie prowadzi to do niejednoznaczności). Współcześnie właściwie nie spotyka się oznaczenia ${\underset {^{+}}{\mid }}A{\underset {^{+}}{\mid }}.$

Przykłady: $\operatorname {perm} {\begin{pmatrix}a\end{pmatrix}}=a.$; $\operatorname {perm} {\begin{pmatrix}a&b\\c&d\end{pmatrix}}=ad{\boldsymbol {+}}bc.$; $\operatorname {perm} {\begin{pmatrix}a&b&c\\d&e&f\\g&h&i\end{pmatrix}}=aei{\boldsymbol {+}}bfg{\boldsymbol {+}}cdh{\boldsymbol {+}}afh{\boldsymbol {+}}ceg{\boldsymbol {+}}bdi.$

Własności

Rozwinięcie względem wiersza/kolumny

Podobnie, jak dla wyznacznika macierzy, można do obliczania permanentu użyć wzoru analogicznego do rozwinięcie Laplace’a:

rozwinięcie według $j$ -tej kolumny:
$\operatorname {perm} (A)=\sum _{i=1}^{n}a_{ij}\cdot \operatorname {perm} (A_{ij}),$
rozwinięcie według $i$ -tego wiersza:
$\operatorname {perm} (A)=\sum _{j=1}^{n}a_{ij}\cdot \operatorname {perm} (A_{ij}).$

Przykład: $\operatorname {perm} {\begin{pmatrix}a&b&c\\d&e&f\\g&h&i\end{pmatrix}}=a\cdot \operatorname {perm} {\begin{pmatrix}e&f\\h&i\end{pmatrix}}+b\cdot \operatorname {perm} {\begin{pmatrix}d&f\\g&i\end{pmatrix}}+c\cdot \operatorname {perm} {\begin{pmatrix}d&e\\g&h\end{pmatrix}}.$

Ogólniej można rozważać rozwinięcie względem grupy wierszy/kolumn, wykorzystując pojęcie macierzy blokowej.

Niech $B$ i $C$ będą macierzami o rozmiarach odpowiednio $p\times n$ i $q\times n$ przy czym $p+q=n$ zaś macierz $A={\big (}{\begin{smallmatrix}B\\C\end{smallmatrix}}{\big )}$ macierzą kwadratową $n\times n.$ (Analogicznie można by zdefiniować macierz $A'={\big (}{\begin{smallmatrix}B'\\C'\end{smallmatrix}}{\big )}$ ).

Wtedy

\operatorname {perm} (A)=\sum _{S\subseteq \{1,2,\dots ,n\} \atop \#S=p}\operatorname {perm} (B_{S})\cdot \operatorname {perm} (C_{\{1,2,\dots ,n\}\setminus S}),

gdzie suma jest tworzona ze wszystkich p-elementowych podzbiorów $S$ zbioru $\{1,\dots ,n\},$ których jest ${n \choose p}.$ Symbol $\#S$ oznacza moc zbioru $S.$ Zaś macierze $B_{S}$ oraz $C_{\{1,2,\dots ,n\}\setminus S}$ są to macierze powstałe przez pozostawienie odpowiednio $p$ i $q$ kolumn w macierzach $B$ i $C$ (a usunięcie pozostałych).

Przykład

Rozwinięcie permanentu macierzy stopnia 4 przedstawia się następująco:

{\;\;\;}\operatorname {perm} {\begin{pmatrix}a&b&c&d\\e&f&g&h\\i&j&k&l\\m&n&o&p\end{pmatrix}}

=\operatorname {perm} {\begin{pmatrix}a&b\\e&f\end{pmatrix}}\cdot \operatorname {perm} {\begin{pmatrix}k&l\\o&p\end{pmatrix}}+\operatorname {perm} {\begin{pmatrix}a&c\\e&g\end{pmatrix}}\cdot \operatorname {perm} {\begin{pmatrix}j&l\\n&p\end{pmatrix}}

+\,\operatorname {perm} {\begin{pmatrix}a&d\\e&h\end{pmatrix}}\cdot \operatorname {perm} {\begin{pmatrix}j&k\\n&o\end{pmatrix}}+\operatorname {perm} {\begin{pmatrix}b&c\\f&g\end{pmatrix}}\cdot \operatorname {perm} {\begin{pmatrix}i&l\\m&p\end{pmatrix}}

+\,\operatorname {perm} {\begin{pmatrix}b&d\\f&h\end{pmatrix}}\cdot \operatorname {perm} {\begin{pmatrix}i&k\\m&o\end{pmatrix}}+\operatorname {perm} {\begin{pmatrix}c&d\\g&h\end{pmatrix}}\cdot \operatorname {perm} {\begin{pmatrix}i&j\\m&n\end{pmatrix}}.

Liniowość permanentu

Podobnie jak wyznacznik permanent jest funkcją liniową względem swoich wierszy/kolumn, tj.:

permanent jest addytywny, czyli zamiana jakiegoś wiersza/kolumny na sumę jest równoznaczne z zamianą permanentu na sumę permanentów,
permanent jest jednorodny, czyli pomnożenie któregoś wiersza/kolumny przez skalar jest równoważne pomnożeniu przez tę liczbę permanentu.

Przykłady: $\operatorname {perm} {\begin{pmatrix}a&b'+b''&c\\d&e'+e''&f\\g&h'+h''&i\end{pmatrix}}=\operatorname {perm} {\begin{pmatrix}a&b'&c\\d&e'&f\\g&h'&i\end{pmatrix}}+\operatorname {perm} {\begin{pmatrix}a&b''&c\\d&e''&f\\g&h''&i\end{pmatrix}}.$; $\alpha \cdot \operatorname {perm} {\begin{pmatrix}a&b&c\\d&e&f\\g&h&i\end{pmatrix}}=\operatorname {perm} {\begin{pmatrix}a&b&c\\\alpha \cdot d&\alpha \cdot e&\alpha \cdot f\\g&h&i\end{pmatrix}}=\operatorname {perm} {\begin{pmatrix}a&b&\alpha \cdot c\\d&e&\alpha \cdot f\\g&h&\alpha \cdot i\end{pmatrix}}.$

Inne podobieństwa do wyznacznika

Permanent macierzy nie zmienia się przy transpozycji macierzy:

\operatorname {perm} (A)=\operatorname {perm} (A^{T}).

Permanent macierzy trójkątnej, podobnie jak wyznacznik, jest równy iloczynowi elementów jej przekątnej:

\operatorname {perm} (A)=\prod _{i=1}^{n}a_{ii}.

Różnice w porównaniu z wyznacznikiem

Permanent macierzy nie zmienia się przy zamianie kolumn lub wierszy, np.:

{}\;\;\;\operatorname {perm} {\begin{pmatrix}a&b&c\\d&e&f\\g&h&i\end{pmatrix}}=\operatorname {perm} {\begin{pmatrix}a&c&b\\d&f&e\\g&i&h\end{pmatrix}}=\operatorname {perm} {\begin{pmatrix}g&h&i\\d&e&f\\a&b&c\end{pmatrix}}.

Oznacza to symetryczność formy wieloliniowej określonej na wierszach/kolumnach, podczas gdy wyznacznik jest formą antysymetryczną.

Na ogół permanent iloczynu zależy od kolejności czynników, tj. $\operatorname {perm} (AB)\neq \operatorname {perm} (BA).$

Jeśli

A={\begin{pmatrix}1&2\\3&-1\end{pmatrix}},\quad B={\begin{pmatrix}1&2\\-1&3\end{pmatrix}},

to

\operatorname {perm} AB=\operatorname {perm} {\begin{pmatrix}-1&8\\4&3\end{pmatrix}}=29,\quad \operatorname {perm} BA=\operatorname {perm} {\begin{pmatrix}7&0\\8&-5\end{pmatrix}}=-35.

Stąd na ogół

\operatorname {perm} (AB)\neq \operatorname {perm} (A)\cdot \operatorname {perm} (B),

Także na ogół

\operatorname {perm} (A^{2})\neq \left(\operatorname {perm} (A)\right)^{2}.

A^{2}={\begin{pmatrix}7&0\\0&7\end{pmatrix}},\quad \operatorname {perm} A=5,\quad \operatorname {perm} A^{2}=49.

Dodanie/odjęcie do któregoś z wierszy innego lub którejś z kolumn innej, nie zachowuje permanentu macierzy.

Niech

A={\begin{pmatrix}1&1\\1&1\end{pmatrix}},\quad \operatorname {perm} (A)=2.

Odejmując w macierzy

A

pierwszy wiersz od drugiego, dostaniemy macierz

B={\begin{pmatrix}1&1\\0&0\end{pmatrix}}

oraz

\operatorname {perm} (B)=0.

Stąd brak odpowiednika metody Gaussa stosowanej przy obliczaniu wyznacznika macierzy.

Złożoność obliczeniowa

Obliczenie permanentu wraz z rosnącym rozmiarem macierzy staje się zadaniem bardzo pracochłonnym. Podczas gdy problem obliczenia wyznacznika macierzy może zostać rozwiązany w czasie ograniczonym funkcją wielomianową, gdzie zmienną jest rozmiar macierzy, dla permanentu nieznany jest algorytm szybszy asymptotycznie niż o złożoności wykładniczej. Podstawową różnicę stanowi fakt, że dla wyznacznika macierzy istnieje efektywny i prosty schemat obliczeń tzw. eliminacja Gaussa. Tak np. można wykazać, że obliczenie permanentu macierzy 0-1 (tj. macierzy, w której występują jedynie liczby 0 i 1) jest problemem #P-zupełnym.

Dla macierzy o elementach nieujemnych można jednak policzyć permanent z dowolną dokładnością w czasie wielomianowo zależnym od rozmiaru wejścia. Algorytm ten oparty na metodach probabilistycznych pozwala na obliczenie permanentu z zadaną dokładnością $\varepsilon M,$ gdzie $M$ to permanent a $\varepsilon >0$ dowolna liczba nieujemna.

Wzór Rysera jest podstawą dla jednego z najefektywniejszych (biorąc pod uwagę powyżej opisane ograniczenia) algorytmów:

\operatorname {perm} (A)=(-1)^{n}\sum _{S\subseteq \{1,2,\dots ,n\}}(-1)^{\#S}\prod _{i=1}^{n}\sum _{j\in S}a_{ij},

gdzie $\#S$ to moc zbioru $S.$

Zastosowania

W przeciwieństwie do wyznacznika macierzy permanent nie ma prostej interpretacji geometrycznej. Jest natomiast głównie używany w kombinatoryce. Tak na przykład przy pomocy permanentu można opisać skojarzenie doskonałe grafu dwudzielnego $G,$ w którym podział wyznaczają wierzchołki $A_{1},A_{2},\dots ,A_{n}$ z jednej strony oraz $B_{1},B_{2},\dots ,B_{n}$ z drugiej. Wtedy $G$ można przedstawić jako macierz kwadratową $n\times n\ A,$ gdzie $a_{i,j}=1$ jeśli istnieje krawędź między wierzchołkami $A_{i}$ i $B_{j}$ lub $a_{i,j}=0,$ gdy nie istnieje. Permanent macierzy jest równy liczbie skojarzeń doskonałych grafu.

Permanent macierzy znajduje też zastosowanie do opisu czy definicji statystyk nieparametrycznych, a dokładniej pozycyjnych, np. w twierdzeniu Bapata-Bega.

Zobacz też

wyznacznik

Przypisy

↑ Leslie Valiant, The complexity of computing the permanent, „Theoretical Computer Science”, 47(1):85–93, 1979.
↑ Mark Jerrum, Alistair Sinclair, Eric Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, J.ACM, tom 51, z. 4, 2004, s. 671–697.

Bibliografia

Henryk Minc: Permanents. Addison-Wesley, Reading MA, 1978.

[valiant-1] Leslie Valiant, The complexity of computing the permanent, „Theoretical Computer Science”, 47(1):85–93, 1979.

[jerum-2] Mark Jerrum, Alistair Sinclair, Eric Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, J.ACM, tom 51, z. 4, 2004, s. 671–697.