Permanent

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
Niniejszy artykuł jest częścią cyklu macierze.
Macierz ikona.png


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 A1, A2, ..., An wierzchołki po jednej stronie oraz przez B1, B2, ..., Bn po drugiej. Wtedy G można przedstawić jako macierz kwadratową n × n A gdzie ai,j = 1 jeśli istnieje krawędź między wierzchołkami Ai and Bj lub ai,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[1].

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[2].

Właściwości[edytuj | edytuj kod]

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 według kolumny j)
\operatorname{perm}(A) = \sum_{j=1}^n   a_{ij} \cdot \operatorname{perm}(A_{ij}) (rozwinięcie według 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[3].

Zapis[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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ż[edytuj | edytuj kod]

Przypisy

  1. Leslie Valiant The complexity of computing the permanent. Theoretical Computer Science, 47(1):85–93, 1979.
  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, str. 671–697.
  3. Henryk Minc: Permanents. Addison-Wesley, Reading MA, 1978.