Otwórz menu główne
Niniejszy artykuł jest częścią cyklu macierze.
Macierz ikona.png


Niektóre typy macierzy
Cechy niezależne od bazy:
macierz nieosobliwa
macierz osobliwa
macierz zerowa
macierz nilpotentna
macierz idempotentna

macierz ortogonalna
macierz symetryczna
macierz dodatnio określona
macierz antysymetryczna

macierz unitarna
macierz hermitowska

Cechy zależne od bazy:
macierz jednostkowa
macierz skalarna
macierz diagonalna
macierz trójkątna
macierz schodkowa
macierz klatkowa
macierz wstęgowa

macierz elementarna
macierz rzadka


Operacje na macierzach
operacje elementarne

mnożenie przez skalar
dodawanie i odejmowanie

mnożenie macierzy
odwracanie macierzy

transpozycja macierzy
sprzężenie macierzy
macierz dopełnień algebraicznych
macierz dołączona

diagonalizacja
postać Jordana


Niezmienniki
rząd macierzy
wyznacznik macierzy
ślad macierzy
minor macierzy
widmo macierzy
wielomian charakterystyczny

edytuj ten szablon

Permanent macierzy kwadratowej

jest zdefiniowany jako

Znak sumy dotyczy wszystkich elementów grupy symetrycznej tj. wszystkich permutacji zbioru liczb

I tak dla przykładu,

Definicja permanentu macierzy różni się od wzoru dla wyznacznika macierzy tym, że znak permutacji nie jest brany pod uwagę. Permanent można traktować jak przekształcenie liniowe 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 dwudzielnego oznaczmy przez wierzchołki, po jednej stronie oraz przez po 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.

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

WłaściwościEdytuj

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

  • rozwinięcie według kolumny   
  • rozwinięcie według kolumny   

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   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).

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

ZapisEdytuj

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ę:

  •  

PodsumowanieEdytuj

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

PrzypisyEdytuj

  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.
  3. Henryk Minc: Permanents. Addison-Wesley, Reading MA, 1978.