Permanent

Szablon:Spis treści 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=\left[\begin{array}{ccc}{a}_{1,1}& \cdots & a_{1,n}\\ ⋮& \ddots & ⋮\\ a_{n,1}& \cdots & a_{n,n}\end{array}\right]$

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

$\mathrm{perm}(A):=\sum _{\sigma \in {𝒮}_n}\prod _{i=1}^n{a}_{i,\sigma (i)}.$

gdzie suma przebiega wszystkie elementy $\sigma$ grupy symetrycznej ${𝒮}_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 $\mathrm{perm}(A)$ stosuje się też zapis $\mathrm{per}(A)$ w wariantach z wielkiej litery 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

$\mathrm{perm}\left(\begin{array}{c}a\end{array}\right)=a.$

$\mathrm{perm}\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)=ad\mathit{+}bc.$

$\mathrm{perm}\left(\begin{array}{ccc}a& b& c\\ d& e& f\\ g& h& i\end{array}\right)=aei\mathit{+}bfg\mathit{+}cdh\mathit{+}afh\mathit{+}ceg\mathit{+}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:

  $\mathrm{perm}(A)=\sum _{i=1}^n{a}_{ij}\cdot \mathrm{perm}(A_{ij}),$

• rozwinięcie według $i$-tego wiersza:

  $\mathrm{perm}(A)=\sum _{j=1}^n{a}_{ij}\cdot \mathrm{perm}(A_{ij}).$

Przykład

$\mathrm{perm}\left(\begin{array}{ccc}a& b& c\\ d& e& f\\ g& h& i\end{array}\right)=a\cdot \mathrm{perm}\left(\begin{array}{cc}e& f\\ h& i\end{array}\right)+b\cdot \mathrm{perm}\left(\begin{array}{cc}d& f\\ g& i\end{array}\right)+c\cdot \mathrm{perm}\left(\begin{array}{cc}d& e\\ g& h\end{array}\right).$

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=\left(\begin{array}{c}B\\ C\end{array}\right)$ macierzą kwadratową $n\times n.$ (Analogicznie można by zdefiniować macierz $A^{\prime }=\left(\begin{array}{c}{B}^{\prime }\\ C^{\prime }\end{array}\right)$).

Wtedy

$\mathrm{perm}(A)=\sum _{\genfrac{}{}{0ex}{}{S\subseteq \{1,2,\dots ,n\}}{\mathrm{\#}S=p}}\mathrm{perm}(B_S)\cdot \mathrm{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 $(\genfrac{}{}{0ex}{}{n}{p}).$ Symbol $\mathrm{\#}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:

$\mathrm{perm}\left(\begin{array}{cccc}a& b& c& d\\ e& f& g& h\\ i& j& k& l\\ m& n& o& p\end{array}\right)$

$=\mathrm{perm}\left(\begin{array}{cc}a& b\\ e& f\end{array}\right)\cdot \mathrm{perm}\left(\begin{array}{cc}k& l\\ o& p\end{array}\right)+\mathrm{perm}\left(\begin{array}{cc}a& c\\ e& g\end{array}\right)\cdot \mathrm{perm}\left(\begin{array}{cc}j& l\\ n& p\end{array}\right)$

$+\mathrm{perm}\left(\begin{array}{cc}a& d\\ e& h\end{array}\right)\cdot \mathrm{perm}\left(\begin{array}{cc}j& k\\ n& o\end{array}\right)+\mathrm{perm}\left(\begin{array}{cc}b& c\\ f& g\end{array}\right)\cdot \mathrm{perm}\left(\begin{array}{cc}i& l\\ m& p\end{array}\right)$

$+\mathrm{perm}\left(\begin{array}{cc}b& d\\ f& h\end{array}\right)\cdot \mathrm{perm}\left(\begin{array}{cc}i& k\\ m& o\end{array}\right)+\mathrm{perm}\left(\begin{array}{cc}c& d\\ g& h\end{array}\right)\cdot \mathrm{perm}\left(\begin{array}{cc}i& j\\ m& n\end{array}\right).$

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

$\mathrm{perm}\left(\begin{array}{ccc}a& b^{\prime }+b^{″}& c\\ d& e^{\prime }+e^{″}& f\\ g& h^{\prime }+h^{″}& i\end{array}\right)=\mathrm{perm}\left(\begin{array}{ccc}a& b^{\prime }& c\\ d& e^{\prime }& f\\ g& h^{\prime }& i\end{array}\right)+\mathrm{perm}\left(\begin{array}{ccc}a& b^{″}& c\\ d& e^{″}& f\\ g& h^{″}& i\end{array}\right).$

$\alpha \cdot \mathrm{perm}\left(\begin{array}{ccc}a& b& c\\ d& e& f\\ g& h& i\end{array}\right)=\mathrm{perm}\left(\begin{array}{ccc}a& b& c\\ \alpha \cdot d& \alpha \cdot e& \alpha \cdot f\\ g& h& i\end{array}\right)=\mathrm{perm}\left(\begin{array}{ccc}a& b& \alpha \cdot c\\ d& e& \alpha \cdot f\\ g& h& \alpha \cdot i\end{array}\right).$

Inne podobieństwa do wyznacznika

Permanent macierzy nie zmienia się przy transpozycji macierzy:

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

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

$\mathrm{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.:

$\mathrm{perm}\left(\begin{array}{ccc}a& b& c\\ d& e& f\\ g& h& i\end{array}\right)=\mathrm{perm}\left(\begin{array}{ccc}a& c& b\\ d& f& e\\ g& i& h\end{array}\right)=\mathrm{perm}\left(\begin{array}{ccc}g& h& i\\ d& e& f\\ a& b& c\end{array}\right).$

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. $\mathrm{perm}(AB)\ne \mathrm{perm}(BA).$

Jeśli $A=\left(\begin{array}{cc}1& 2\\ 3& -1\end{array}\right),B=\left(\begin{array}{cc}1& 2\\ -1& 3\end{array}\right),$

to $\mathrm{perm}AB=\mathrm{perm}\left(\begin{array}{cc}-1& 8\\ 4& 3\end{array}\right)=29,\mathrm{perm}BA=\mathrm{perm}\left(\begin{array}{cc}7& 0\\ 8& -5\end{array}\right)=-35.$

Stąd na ogół $\mathrm{perm}(AB)\ne \mathrm{perm}(A)\cdot \mathrm{perm}(B),$

Także na ogół $\mathrm{perm}(A^2)\ne {(\mathrm{perm}(A))}^2.$

$A^2=\left(\begin{array}{cc}7& 0\\ 0& 7\end{array}\right),\mathrm{perm}A=5,\mathrm{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=\left(\begin{array}{cc}1& 1\\ 1& 1\end{array}\right),\mathrm{perm}(A)=2.$ Odejmując w macierzy $A$ pierwszy wiersz od drugiego, dostaniemy macierz $B=\left(\begin{array}{cc}1& 1\\ 0& 0\end{array}\right)$ oraz $\mathrm{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ą $\epsilon M,$ gdzie $M$ to permanent a $\epsilon >0$ dowolna liczba nieujemna.

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

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

gdzie $\mathrm{\#}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 nA,$ 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

Bibliografia

• Szablon:Cytuj książkę