Permanent

Wstęp

Permanent to funkcja matematyczna, która przypisuje każdej macierzy kwadratowej stopnia n, posiadającej współczynniki z pierścienia przemiennego, pewien element tego pierścienia. W podobny sposób jak wyznacznik macierzy, permanent jest wielomianem stopnia n z n² zmiennymi. Każdy składnik permanentu ma n czynników, z których każde dwa pochodzą z różnych kolumn i wierszy danej macierzy. Permanent jest symetryczną formą wieloliniową na wierszach i kolumnach, które traktowane są jako wektory przestrzeni liniowej wymiaru n.

Definicja permanentu

Dla macierzy kwadratowej A, definiowanej jako:

A =
[a_1,1 … a_1,n; … ; a_n,1 … a_n,n]

permanent oznaczany jako perm(A) definiuje się wzorem:

perm(A) := ∑_{σ ∈ Sn}∏_i=1ⁿa_i,σ(i).

Suma ta przebiega przez wszystkie permutacje zbioru liczb od 1 do n. Warto zauważyć, że definicja permanentu różni się od wzoru dla wyznacznika tym, że znak permutacji nie jest uwzględniany.

Zapis i notacja

Oprócz oznaczenia perm(A), stosuje się również zapis per(A) oraz warianty z wielką literą i bez nawiasów, jeśli nie prowadzi to do niejednoznaczności. Współczesna notacja rzadko używa symbolu |A|⁺, który był stosowany w przeszłości.

Przykłady obliczeń permanentu

Rozważmy kilka podstawowych przykładów obliczenia permanentu:

• perm( [a] ) = a.
• perm( [a b; c d] ) = ad + bc.
• perm( [a b c; d e f; g h i] ) = aei + bfg + cdh + afh + ceg + bdi.

Własności permanentu

Rozwinięcie względem wiersza/kolumny

Podobnie jak w przypadku wyznacznika, dla permanentu można zastosować wzór rozwinięcia Laplace’a. Rozwinięcie według j-tej kolumny można zapisać jako:

perm(A) = ∑_i=1ⁿa_ij·perm(A_ij)

A rozwinięcie według i-tego wiersza można opisać analogicznie:

perm(A) = ∑_j=1ⁿa_ij·perm(A_ij)

Liniowość permanentu

Permanent jest funkcją liniową względem swoich wierszy i kolumn. Oznacza to, że:

• Zamiana jakiegoś wiersza/kolumny na sumę odpowiada zamianie permanentu na sumę permanentów.
• Pomnożenie któregoś z wierszy/kolumn przez skalar skutkuje pomnożeniem przez tę liczbę wartości permanentu.

Zachowanie przy transpozycji macierzy

Permanent macierzy nie zmienia się przy transpozycji macierzy:

perm(A) = perm(A^T)

Złożoność obliczeniowa obliczania permanentu

Obliczenie permanentu staje się coraz bardziej skomplikowane wraz ze wzrostem rozmiaru macierzy. O ile wyznacznik może być obliczany w czasie wielomianowym dzięki eliminacji Gaussa, o tyle dla permanentu nie znaleziono jeszcze algorytmu o czasie obliczeń mniejszym niż wykładniczym. Wyjątek stanowią macierze 0-1, gdzie obliczenie permanentu jest problemem #P-zupełnym.

Prawdopodobnościowe metody obliczania permanentu

Dla macierzy o elementach nieujemnych istnieje możliwość obliczenia permanentu z dowolną dokładnością w czasie wielomianowym. Algorytmy te opierają się na metodach probabilistycznych i pozwalają na uzyskanie przybliżonego wyniku.

Zastosowania permanentu w matematyce i informatyce

Póki co, permanent nie ma prostych interpretacji geometrycznych, jednak jest szeroko wykorzystywany w kombinatoryce. Używa się go do opisu skojarzenia doskonałego grafów dwudzielnych. W kontekście grafów, G może być przedstawiony jako macierz kwadratowa n×n A, gdzie a_ij=1 oznacza istnienie krawędzi między wierzchołkami A_i i B_j.

Kombinatoryka i statystyki nieparametryczne

Permanent znajduje także zastosowanie do definiowania statystyk nieparametrycznych, takich jak twierdzenie Bapata-Bega. Dzięki swoim właściwościom, pozwala na lepsze zrozumienie zjawisk związanych z kombinacjami i permutacjami.

Zakończenie

Permanenty to istotny element teorii macierzy i kombinatoryki, odgrywający kluczową rolę w wielu dziedzinach matematyki. Pomimo swojej złożoności obliczeniowej oraz braku efektywnych algorytmów dla ogólnych przypadków, mają one znaczące zastosowania praktyczne. Poznanie ich właściwości oraz zastosowań otwiera nowe możliwości w badaniach nad strukturami matematycznymi oraz algorytmami komputerowymi.

---

Artykuł sporządzony na podstawie: Wikipedia (PL).