Permanent
Z Wikipedii
 |
Ten artykuł wymaga dopracowania zgodnie z zaleceniami edycyjnymi. Po naprawieniu wszystkich błędów można usunąć tę wiadomość. |
W algebrze liniowej, permanent macierzy kwadratowej n × n
jest zdefiniowany jako
Znak sumy dotyczy wszystkich elementów σ grupy symetrycznej 
, tj. wszystkich permutacji zbioru liczb 1,2,...,n.
I tak dla przykładu,
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 krawędzie A1, A2, ..., An po jednej stronie oraz 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]
Spis treści |
[edytuj] 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 wg kolumny j)
(rozwinięcie wg wiersza i)
Ogólniej wzór ten można też wygodnie sformułować w postaci macierzy blokowej np.:
niech 
i 
będą macierzami o rozmiarach odpowiednio 
i 
przy czym 
zaś macierz 
macierzą kwadratową 
. (Analogicznie można by zdefiniować macierz 
.)
Wtedy
gdzie suma jest tworzona ze wszystkich p-elementowych podzbiorów S zbioru { 1, ..., n } (których jest 
. Symbol 
osznacza moc zbioru 
. Zaś macierze 
oraz 
są to macierze powstałe przez pozostawienie odpowiednio 
i 
kolumn w macierzach i (a usunięcie pozostałych).
Wygodnie można to prześledzić na poniższym przykładzie:
Permanent macierzy nie zmienia się przy zamianie kolumn lub wierszy np.:'
(zamiana trzeciej i piątej kolumny)
(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:
Permanent macierzy nie zmienia się przy transpozycji macierzy:
Poza analogiami z wyznacznikiem można jednak wskazać kilka bardzo istotnych różnic. Tak np. w przypadku ogólnym
- Ponieważ ogólnie
, to również 
- 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.
gdzie 
to moc zbioru 
.
W książce Henryka Minca można znaleźć wyczerpujące zestawienie wiedzy na temat permanentu.[3]
[edytuj] Zapis
Najczęściej stosuje się zapis:
lub
.
Warianty pisane wielką literą są dość popularne:
lub
.
Kiedy nie powoduje to niejednoznaczności, nawiasy bywają pomijane np.:
.
Rzadko spotyka się notację:
[edytuj] 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.
[edytuj] Zobacz też
- Wyznacznik
- Twierdzenie Bapata-Bega, przykład zastosowania permantentu w statystykach pozycyjnych
[edytuj] 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, str. 671–697.
- ↑ Henryk Minc: Permanents. Addison-Wesley, Reading MA, 1978.
