Permanent

Permanent macierzy kwadratowej $n\times n$

$A={\begin{pmatrix}a_{1,1}&a_{1,2}&\cdots &a_{1,n-1}&a_{1,n}\\a_{2,1}&a_{2,2}&\cdots &a_{2,n-1}&a_{2,n}\\\vdots &\vdots &\ddots &\vdots &\vdots \\a_{n-1,1}&a_{n-1,2}&\cdots &a_{n-1,n-1}&a_{n-1,n}\\a_{n,1}&a_{n,2}&\cdots &a_{n,n-1}&a_{n,n}\end{pmatrix}}$

jest zdefiniowany jako

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

Znak sumy dotyczy wszystkich elementów $\sigma$ grupy symetrycznej ${\mathcal {S}}_{n},$ tj. wszystkich permutacji zbioru liczb $1,2,\dots ,n.$

I tak dla przykładu,

$\operatorname {perm} {\begin{pmatrix}a&b\\c&d\end{pmatrix}}=ad+bc.$

Definicja permanentu macierzy $A$ różni się od wzoru dla wyznacznika macierzy $A$ tym, że znak permutacji nie jest brany pod uwagę. Permanent można traktować jak przekształcenie liniowe $n$ argumentów wektorowych, wtedy określimy permanent jako przekształcenie wieloliniowe.

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. I tak, dla grafu dwudzielnego $G$ oznaczmy przez $A_{1},A_{2},\dots ,A_{n}$ wierzchołki, po jednej stronie oraz przez $B_{1},B_{2},\dots ,B_{n}$ po 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. Permament macierzy jest równy liczbie skojarzeń doskonałych grafu.

Permanent macierzy znajduje też zastosowanie do opisu czy definicji statystyk nieparametrycznych a dokładniej pozycyjnych.

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.

Właściwości

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

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

Ogólniej wzór ten można też wygodnie sformułować w postaci macierzy blokowej, np.:

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).

Wygodnie można to prześledzić na poniższym przykładzie:

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

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

${}\;\;\;\operatorname {perm} {\begin{pmatrix}a&b&c&d&e\\f&g&h&i&j\\k&l&m&n&o\\p&q&r&s&t\\u&v&w&x&y\end{pmatrix}}$

$=\operatorname {perm} {\begin{pmatrix}a&b&e&d&c\\f&g&j&i&h\\k&l&o&n&m\\p&q&t&s&r\\u&v&y&x&w\end{pmatrix}}$    (zamiana trzeciej i piątej kolumny)

$=\operatorname {perm} {\begin{pmatrix}f&g&j&i&h\\a&b&e&d&c\\k&l&o&n&m\\p&q&t&s&r\\u&v&y&x&w\end{pmatrix}}.$    (zamiana pierwszego i drugiego wiersza)

Podobnie jak w przypadku wyznacznika, pomnożenie któregoś z wierszy czy kolumn przez skalar jest równoważne pomnożeniu o tę liczbę permanentu, co najłatwiej znowu prześledzić na przykładzie:

$\alpha \cdot \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&\alpha \cdot c&d\\e&f&\alpha \cdot g&h\\i&j&\alpha \cdot k&l\\m&n&\alpha \cdot o&p\end{pmatrix}}$

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

Permanent macierzy nie zmienia się przy transpozycji macierzy:

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

Poza analogiami z wyznacznikiem można jednak wskazać kilka bardzo istotnych różnic. Tak np. w przypadku ogólnym:

• Ponieważ ogólnie $\operatorname {perm} (AB)\neq \operatorname {perm} (A)\cdot \operatorname {perm} (B),$ to również $\operatorname {perm} (AB)\neq \operatorname {perm} (BA).$
• Przy dodaniu do któregoś z wierszy lub kolumn innego wektora składowego macierzy permanent się zmienia.
• Brak odpowiednika metody Gaussa stosowanej przy obliczaniu wyznacznika macierzy.

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

W książce Henryka Minca można znaleźć wyczerpujące zestawienie wiedzy na temat permanentu.

Zapis

Najczęściej stosuje się zapis:

• $\operatorname {perm} (A)$   lub
• $\operatorname {per} (A).$

Warianty pisane wielką literą są dość popularne:

• $\operatorname {Perm} (A)$   lub
• $\operatorname {Per} (A).$

Kiedy nie powoduje to niejednoznaczności, nawiasy bywają pomijane np.:

• $\operatorname {perm} \;A.$

Rzadko spotyka się notację:

• ${\underset {^{+}}{\mid }}A{\underset {^{+}}{\mid }}.$

Podsumowanie

Mimo podobieństwa w definicji do wyznacznika oraz pewnych zbliżonych własności obliczenie permanentu jest czasochłonne. Jednocześnie należy dodać, że w praktyce spotyka się z problemem obliczenia wyznacznika macierzy znacznie częściej w różnych dziedzinach matematyki niż z zadaniem wyznaczenia permanentu.

Zobacz też

• wyznacznik
• twierdzenie Bapata-Bega, przykład zastosowania permanentu w statystykach pozycyjnych