Permanent

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

Dla macierzy kwadratowej

${\displaystyle A={\begin{bmatrix}a_{1,1}&\cdots &a_{1,n}\\\vdots &\ddots &\vdots \\a_{n,1}&\cdots &a_{n,n}\end{bmatrix}}}$

permanent ${\displaystyle \operatorname {perm} (A)}$ definiuje się jako

${\displaystyle \operatorname {perm} (A):=\sum _{\sigma \in {\mathcal {S}}_{n}}\prod _{i=1}^{n}a_{i,\sigma (i)}.}$

gdzie suma przebiega wszystkie elementy ${\displaystyle \sigma }$ grupy symetrycznej ${\displaystyle {\mathcal {S}}_{n},}$ tj. wszystkie permutacje zbioru liczb ${\displaystyle 1,2,\dots ,n.}$

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

Oprócz oznaczenia ${\displaystyle \operatorname {perm} (A)}$ stosuje się też zapis ${\displaystyle \operatorname {per} (A)}$ 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 ${\displaystyle {\underset {^{+}}{\mid }}A{\underset {^{+}}{\mid }}.}$

Przykłady

${\displaystyle \operatorname {perm} {\begin{pmatrix}a\end{pmatrix}}=a.}$

${\displaystyle \operatorname {perm} {\begin{pmatrix}a&b\\c&d\end{pmatrix}}=ad{\boldsymbol {+}}bc.}$

${\displaystyle \operatorname {perm} {\begin{pmatrix}a&b&c\\d&e&f\\g&h&i\end{pmatrix}}=aei{\boldsymbol {+}}bfg{\boldsymbol {+}}cdh{\boldsymbol {+}}afh{\boldsymbol {+}}ceg{\boldsymbol {+}}bdi.}$

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

• rozwinięcie według ${\displaystyle j}$-tej kolumny:

  ${\displaystyle \operatorname {perm} (A)=\sum _{i=1}^{n}a_{ij}\cdot \operatorname {perm} (A_{ij}),}$

• rozwinięcie według ${\displaystyle i}$-tego wiersza:

  ${\displaystyle \operatorname {perm} (A)=\sum _{j=1}^{n}a_{ij}\cdot \operatorname {perm} (A_{ij}).}$

Przykład

${\displaystyle \operatorname {perm} {\begin{pmatrix}a&b&c\\d&e&f\\g&h&i\end{pmatrix}}=a\cdot \operatorname {perm} {\begin{pmatrix}e&f\\h&i\end{pmatrix}}+b\cdot \operatorname {perm} {\begin{pmatrix}d&f\\g&i\end{pmatrix}}+c\cdot \operatorname {perm} {\begin{pmatrix}d&e\\g&h\end{pmatrix}}.}$

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

Niech ${\displaystyle B}$ i ${\displaystyle C}$ będą macierzami o rozmiarach odpowiednio ${\displaystyle p\times n}$ i ${\displaystyle q\times n}$ przy czym ${\displaystyle p+q=n}$ zaś macierz ${\displaystyle A={\big (}{\begin{smallmatrix}B\\C\end{smallmatrix}}{\big )}}$ macierzą kwadratową ${\displaystyle n\times n.}$ (Analogicznie można by zdefiniować macierz ${\displaystyle A'={\big (}{\begin{smallmatrix}B'\\C'\end{smallmatrix}}{\big )}}$).

Wtedy

${\displaystyle \operatorname {perm} (A)=\sum _{S\subseteq \{1,2,\dots ,n\} \atop \#S=p}\operatorname {perm} (B_{S})\cdot \operatorname {perm} (C_{\{1,2,\dots ,n\}\setminus S}),}$

gdzie suma jest tworzona ze wszystkich p-elementowych podzbiorów ${\displaystyle S}$ zbioru ${\displaystyle \{1,\dots ,n\},}$ których jest ${\displaystyle {n \choose p}.}$ Symbol ${\displaystyle \#S}$ oznacza moc zbioru ${\displaystyle S.}$ Zaś macierze ${\displaystyle B_{S}}$ oraz ${\displaystyle C_{\{1,2,\dots ,n\}\setminus S}}$ są to macierze powstałe przez pozostawienie odpowiednio ${\displaystyle p}$ i ${\displaystyle q}$ kolumn w macierzach ${\displaystyle B}$ i ${\displaystyle C}$ (a usunięcie pozostałych).

Przykład

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

${\displaystyle {\;\;\;}\operatorname {perm} {\begin{pmatrix}a&b&c&d\\e&f&g&h\\i&j&k&l\\m&n&o&p\end{pmatrix}}}$

${\displaystyle =\operatorname {perm} {\begin{pmatrix}a&b\\e&f\end{pmatrix}}\cdot \operatorname {perm} {\begin{pmatrix}k&l\\o&p\end{pmatrix}}+\operatorname {perm} {\begin{pmatrix}a&c\\e&g\end{pmatrix}}\cdot \operatorname {perm} {\begin{pmatrix}j&l\\n&p\end{pmatrix}}}$

${\displaystyle +\,\operatorname {perm} {\begin{pmatrix}a&d\\e&h\end{pmatrix}}\cdot \operatorname {perm} {\begin{pmatrix}j&k\\n&o\end{pmatrix}}+\operatorname {perm} {\begin{pmatrix}b&c\\f&g\end{pmatrix}}\cdot \operatorname {perm} {\begin{pmatrix}i&l\\m&p\end{pmatrix}}}$

${\displaystyle +\,\operatorname {perm} {\begin{pmatrix}b&d\\f&h\end{pmatrix}}\cdot \operatorname {perm} {\begin{pmatrix}i&k\\m&o\end{pmatrix}}+\operatorname {perm} {\begin{pmatrix}c&d\\g&h\end{pmatrix}}\cdot \operatorname {perm} {\begin{pmatrix}i&j\\m&n\end{pmatrix}}.}$

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

${\displaystyle \operatorname {perm} {\begin{pmatrix}a&b'+b''&c\\d&e'+e''&f\\g&h'+h''&i\end{pmatrix}}=\operatorname {perm} {\begin{pmatrix}a&b'&c\\d&e'&f\\g&h'&i\end{pmatrix}}+\operatorname {perm} {\begin{pmatrix}a&b''&c\\d&e''&f\\g&h''&i\end{pmatrix}}.}$

${\displaystyle \alpha \cdot \operatorname {perm} {\begin{pmatrix}a&b&c\\d&e&f\\g&h&i\end{pmatrix}}=\operatorname {perm} {\begin{pmatrix}a&b&c\\\alpha \cdot d&\alpha \cdot e&\alpha \cdot f\\g&h&i\end{pmatrix}}=\operatorname {perm} {\begin{pmatrix}a&b&\alpha \cdot c\\d&e&\alpha \cdot f\\g&h&\alpha \cdot i\end{pmatrix}}.}$

Permanent macierzy nie zmienia się przy transpozycji macierzy:

${\displaystyle \operatorname {perm} (A)=\operatorname {perm} (A^{T}).}$

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

${\displaystyle \operatorname {perm} (A)=\prod _{i=1}^{n}a_{ii}.}$

• Permanent macierzy nie zmienia się przy zamianie kolumn lub wierszy, np.:

${\displaystyle {}\;\;\;\operatorname {perm} {\begin{pmatrix}a&b&c\\d&e&f\\g&h&i\end{pmatrix}}=\operatorname {perm} {\begin{pmatrix}a&c&b\\d&f&e\\g&i&h\end{pmatrix}}=\operatorname {perm} {\begin{pmatrix}g&h&i\\d&e&f\\a&b&c\end{pmatrix}}.}$

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. ${\displaystyle \operatorname {perm} (AB)\neq \operatorname {perm} (BA).}$

Jeśli ${\displaystyle A={\begin{pmatrix}1&2\\3&-1\end{pmatrix}},\quad B={\begin{pmatrix}1&2\\-1&3\end{pmatrix}},}$

to ${\displaystyle \operatorname {perm} AB=\operatorname {perm} {\begin{pmatrix}-1&8\\4&3\end{pmatrix}}=29,\quad \operatorname {perm} BA=\operatorname {perm} {\begin{pmatrix}7&0\\8&-5\end{pmatrix}}=-35.}$

Stąd na ogół ${\displaystyle \operatorname {perm} (AB)\neq \operatorname {perm} (A)\cdot \operatorname {perm} (B),}$

Także na ogół ${\displaystyle \operatorname {perm} (A^{2})\neq \left(\operatorname {perm} (A)\right)^{2}.}$

${\displaystyle A^{2}={\begin{pmatrix}7&0\\0&7\end{pmatrix}},\quad \operatorname {perm} A=5,\quad \operatorname {perm} A^{2}=49.}$

• Dodanie/odjęcie do któregoś z wierszy innego lub którejś z kolumn innej, nie zachowuje permanentu macierzy.

Niech ${\displaystyle A={\begin{pmatrix}1&1\\1&1\end{pmatrix}},\quad \operatorname {perm} (A)=2.}$ Odejmując w macierzy ${\displaystyle A}$ pierwszy wiersz od drugiego, dostaniemy macierz ${\displaystyle B={\begin{pmatrix}1&1\\0&0\end{pmatrix}}}$ oraz ${\displaystyle \operatorname {perm} (B)=0.}$

Stąd brak odpowiednika metody Gaussa stosowanej przy obliczaniu wyznacznika macierzy.

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ą ${\displaystyle \varepsilon M,}$ gdzie ${\displaystyle M}$ to permanent a ${\displaystyle \varepsilon >0}$ dowolna liczba nieujemna^[2].

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

${\displaystyle \operatorname {perm} (A)=(-1)^{n}\sum _{S\subseteq \{1,2,\dots ,n\}}(-1)^{\#S}\prod _{i=1}^{n}\sum _{j\in S}a_{ij},}$

gdzie ${\displaystyle \#S}$ to moc zbioru ${\displaystyle S.}$

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 ${\displaystyle G,}$ w którym podział wyznaczają wierzchołki ${\displaystyle A_{1},A_{2},\dots ,A_{n}}$ z jednej strony oraz ${\displaystyle B_{1},B_{2},\dots ,B_{n}}$ z drugiej. Wtedy ${\displaystyle G}$ można przedstawić jako macierz kwadratową ${\displaystyle n\times n\ A,}$ gdzie ${\displaystyle a_{i,j}=1}$ jeśli istnieje krawędź między wierzchołkami ${\displaystyle A_{i}}$ i ${\displaystyle B_{j}}$ lub ${\displaystyle a_{i,j}=0,}$ gdy nie istnieje. Permanent 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.

• wyznacznik

• Henryk Minc: Permanents. Addison-Wesley, Reading MA, 1978. Brak numerów stron w książce