Permanent

Niniejszy artykuł jest częścią cyklu macierze.

Niektóre typy macierzy macierz diagonalna macierz dodatnio określona macierz elementarna macierz hermitowska macierz idempotentna macierz jednostkowa macierz klatkowa macierz nieosobliwa macierz nilpotentna macierz ortogonalna macierz osobliwa macierz rzadka macierz schodkowa macierz skalarna macierz symetryczna macierz trójkątna macierz unitarna macierz wstęgowa macierz zerowa Operacje na macierzach mnożenie przez skalar dodawanie i odejmowanie mnożenie macierzy odwracanie macierzy transpozycja macierzy sprzężenie macierzy operacje elementarne macierz dopełnień algebraicznych macierz dołączona diagonalizacja postać Jordana Inne zagadnienia wyznacznik macierzy ślad macierzy widmo macierzy minor macierzy rząd macierzy wielomian charakterystyczny

edytuj ten szablon

W algebrze liniowej, permanent macierzy kwadratowej n × 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 σ grupy symetrycznej $\mathcal{S}_n$, tj. wszystkich permutacji zbioru liczb 1,2,...,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 dwudzielngo G oznaczmy przez A₁, A₂, ..., A_n wierzchołki po jednej stronie oraz przez B₁, B₂, ..., B_n po drugiej. Wtedy G można przedstawić jako macierz kwadratową n × n A gdzie a_i,j = 1 jeśli istnieje krawędź między wierzchołkami A_i and 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ą εM, gdzie M to permanent a ε > 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.

$\operatorname{perm}(A) = \sum_{i=1}^n a_{ij} \cdot \operatorname{perm}(A_{ij})$ (rozwinięcie wg kolumny $j$)

$\operatorname{perm}(A) = \sum_{j=1}^n a_{ij} \cdot \operatorname{perm}(A_{ij})$ (rozwinięcie wg wiersza $i$)

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

Wtedy

$\operatorname{perm}(A) = \sum_{S \subseteq \{1,2,\ldots,n\} \atop \#S = p} \operatorname{perm}(B_S)\cdot\operatorname{perm}(C_{\{1,2,\ldots,n\}\setminus S})\,$

gdzie suma jest tworzona ze wszystkich p-elementowych podzbiorów S zbioru { 1, ..., n } (których jest $n \choose p$ . Symbol $\#S\;$ osznacza moc zbioru $S\;$. Zaś macierze $B_S\;$ oraz $C_{\{1,2,\ldots,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,\ldots, 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 permantentu w statystykach pozycyjnych