Permanent

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Permanentfunkcja przyporządkowująca każdej macierzy kwadratowej stopnia o współczynnikach z pierścienia przemiennego pewien element tego pierścienia. Podobnie jak wyznacznik permanent jest wielomianem stopnia z zmiennymi, w którym każdy składnik ma 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 wierszach/kolumnach, traktowanych jako wektory przestrzeni liniowej wymiaru

Definicja[edytuj | edytuj kod]

Dla macierzy kwadratowej

permanent definiuje się jako

gdzie suma przebiega wszystkie elementy grupy symetrycznej tj. wszystkie permutacje zbioru liczb

Definicja permanentu macierzy różni się więc od wzoru permutacyjnego dla wyznacznika macierzy tym, że znak permutacji nie jest brany pod uwagę.

Oprócz oznaczenia stosuje się też zapis 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

Przykłady

Własności[edytuj | edytuj kod]

Rozwinięcie względem wiersza/kolumny[edytuj | edytuj kod]

Podobnie, jak dla wyznacznika macierzy, można do obliczania permanentu użyć wzoru analogicznego do rozwinięcie Laplace’a:

  • rozwinięcie według -tej kolumny:
  • rozwinięcie według -tego wiersza:
Przykład

Ogólniej można rozważać rozwinięcie względem grupy wierszy/kolumn, wykorzystując pojęcie macierzy blokowej.

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 zbioru których jest Symbol oznacza moc zbioru Zaś macierze oraz są to macierze powstałe przez pozostawienie odpowiednio i kolumn w macierzach i (a usunięcie pozostałych).

Przykład

Rozwinięcie permanentu macierzy stopnia 4 przedstawia się następująco:

Liniowość permanentu[edytuj | edytuj kod]

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

Inne podobieństwa do wyznacznika[edytuj | edytuj kod]

Permanent macierzy nie zmienia się przy transpozycji macierzy:

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

Różnice w porównaniu z wyznacznikiem[edytuj | edytuj kod]

  • Permanent macierzy nie zmienia się przy zamianie kolumn lub wierszy, np.:
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.
Jeśli
to
Stąd na ogół
Także na ogół
  • Dodanie/odjęcie do któregoś z wierszy innego lub którejś z kolumn innej, nie zachowuje permanentu macierzy.
Niech Odejmując w macierzy pierwszy wiersz od drugiego, dostaniemy macierz oraz
Stąd brak odpowiednika metody Gaussa stosowanej przy obliczaniu wyznacznika macierzy.

Złożoność obliczeniowa[edytuj | edytuj kod]

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ą gdzie to permanent a dowolna liczba nieujemna[2].

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

gdzie to moc zbioru

Zastosowania[edytuj | edytuj kod]

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 w którym podział wyznaczają wierzchołki z jednej strony oraz z drugiej. Wtedy można przedstawić jako macierz kwadratową gdzie jeśli istnieje krawędź między wierzchołkami i lub 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, np. w twierdzeniu Bapata-Bega.

Zobacz też[edytuj | edytuj kod]

Przypisy[edytuj | edytuj kod]

  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, s. 671–697.

Bibliografia[edytuj | edytuj kod]

  • Henryk Minc: Permanents. Addison-Wesley, Reading MA, 1978.