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.