Permanent

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

Dla macierzy kwadratowej

A = [ a 1 , 1 ⋯ a 1 , n ⋮ ⋱ ⋮ a n , 1 ⋯ a n , n ] {\displaystyle A={\begin{bmatrix}a_{1,1}&\cdots &a_{1,n}\\\vdots &\ddots &\vdots \\a_{n,1}&\cdots &a_{n,n}\end{bmatrix}}}

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

perm ⁡ ( A ) := ∑ σ ∈ S n ∏ i = 1 n a i , σ ( i ) . {\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 S n , {\displaystyle {\mathcal {S}}_{n},} tj. wszystkie permutacje zbioru liczb 1 , 2 , … , n . {\displaystyle 1,2,\dots ,n.}

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

Oprócz oznaczenia perm ⁡ ( A ) {\displaystyle \operatorname {perm} (A)} stosuje się też zapis per ⁡ ( A ) {\displaystyle \operatorname {per} (A)} w wariantach wielką literą i w notacji beznawiasowej (jeśli nie prowadzi to do niejednoznaczności). Współcześnie właściwie nie spotyka się oznaczenia ∣ + A ∣ + . {\displaystyle {\underset {^{+}}{\mid }}A{\underset {^{+}}{\mid }}.}

Przykłady

perm ⁡ ( a ) = a . {\displaystyle \operatorname {perm} {\begin{pmatrix}a\end{pmatrix}}=a.}

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

perm ⁡ ( a b c d e f g h i ) = a e i + b f g + c d h + a f h + c e g + b d i . {\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 j {\displaystyle j} -tej kolumny:

  perm ⁡ ( A ) = ∑ i = 1 n a i j ⋅ perm ⁡ ( A i j ) , {\displaystyle \operatorname {perm} (A)=\sum _{i=1}^{n}a_{ij}\cdot \operatorname {perm} (A_{ij}),}

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

  perm ⁡ ( A ) = ∑ j = 1 n a i j ⋅ perm ⁡ ( A i j ) . {\displaystyle \operatorname {perm} (A)=\sum _{j=1}^{n}a_{ij}\cdot \operatorname {perm} (A_{ij}).}

Przykład

perm ⁡ ( a b c d e f g h i ) = a ⋅ perm ⁡ ( e f h i ) + b ⋅ perm ⁡ ( d f g i ) + c ⋅ perm ⁡ ( d e g h ) . {\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 B {\displaystyle B} i C {\displaystyle C} będą macierzami o rozmiarach odpowiednio p × n {\displaystyle p\times n} i q × n {\displaystyle q\times n} przy czym p + q = n {\displaystyle p+q=n} zaś macierz A = ( B C ) {\displaystyle A={\big (}{\begin{smallmatrix}B\\C\end{smallmatrix}}{\big )}} macierzą kwadratową n × n . {\displaystyle n\times n.} (Analogicznie można by zdefiniować macierz A ′ = ( B ′ C ′ ) {\displaystyle A'={\big (}{\begin{smallmatrix}B'\\C'\end{smallmatrix}}{\big )}} ).

Wtedy

perm ⁡ ( A ) = ∑ S ⊆ { 1 , 2 , … , n } # S = p perm ⁡ ( B S ) ⋅ perm ⁡ ( C { 1 , 2 , … , n } ∖ S ) , {\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 S {\displaystyle S} zbioru { 1 , … , n } , {\displaystyle \{1,\dots ,n\},} których jest ( n p ) . {\displaystyle {n \choose p}.} Symbol # S {\displaystyle \#S} oznacza moc zbioru S . {\displaystyle S.} Zaś macierze B S {\displaystyle B_{S}} oraz C { 1 , 2 , … , n } ∖ S {\displaystyle C_{\{1,2,\dots ,n\}\setminus S}} są to macierze powstałe przez pozostawienie odpowiednio p {\displaystyle p} i q {\displaystyle q} kolumn w macierzach B {\displaystyle B} i C {\displaystyle C} (a usunięcie pozostałych).

Przykład

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

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

= perm ⁡ ( a b e f ) ⋅ perm ⁡ ( k l o p ) + perm ⁡ ( a c e g ) ⋅ perm ⁡ ( j l n p ) {\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}}}

+ perm ⁡ ( a d e h ) ⋅ perm ⁡ ( j k n o ) + perm ⁡ ( b c f g ) ⋅ perm ⁡ ( i l m p ) {\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}}}

+ perm ⁡ ( b d f h ) ⋅ perm ⁡ ( i k m o ) + perm ⁡ ( c d g h ) ⋅ perm ⁡ ( i j m n ) . {\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

perm ⁡ ( a b ′ + b ″ c d e ′ + e ″ f g h ′ + h ″ i ) = perm ⁡ ( a b ′ c d e ′ f g h ′ i ) + perm ⁡ ( a b ″ c d e ″ f g h ″ i ) . {\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}}.}

α ⋅ perm ⁡ ( a b c d e f g h i ) = perm ⁡ ( a b c α ⋅ d α ⋅ e α ⋅ f g h i ) = perm ⁡ ( a b α ⋅ c d e α ⋅ f g h α ⋅ i ) . {\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:

perm ⁡ ( A ) = perm ⁡ ( A T ) . {\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:

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

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

perm ⁡ ( a b c d e f g h i ) = perm ⁡ ( a c b d f e g i h ) = perm ⁡ ( g h i d e f a b c ) . {\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. perm ⁡ ( A B ) ≠ perm ⁡ ( B A ) . {\displaystyle \operatorname {perm} (AB)\neq \operatorname {perm} (BA).}

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

to perm ⁡ A B = perm ⁡ ( − 1 8 4 3 ) = 29 , perm ⁡ B A = perm ⁡ ( 7 0 8 − 5 ) = − 35. {\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ół perm ⁡ ( A B ) ≠ perm ⁡ ( A ) ⋅ perm ⁡ ( B ) , {\displaystyle \operatorname {perm} (AB)\neq \operatorname {perm} (A)\cdot \operatorname {perm} (B),}

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

A 2 = ( 7 0 0 7 ) , perm ⁡ A = 5 , perm ⁡ A 2 = 49. {\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 A = ( 1 1 1 1 ) , perm ⁡ ( A ) = 2. {\displaystyle A={\begin{pmatrix}1&1\\1&1\end{pmatrix}},\quad \operatorname {perm} (A)=2.} Odejmując w macierzy A {\displaystyle A} pierwszy wiersz od drugiego, dostaniemy macierz B = ( 1 1 0 0 ) {\displaystyle B={\begin{pmatrix}1&1\\0&0\end{pmatrix}}} oraz perm ⁡ ( B ) = 0. {\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ą ε M , {\displaystyle \varepsilon M,} gdzie M {\displaystyle M} to permanent a ε > 0 {\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:

perm ⁡ ( A ) = ( − 1 ) n ∑ S ⊆ { 1 , 2 , … , n } ( − 1 ) # S ∏ i = 1 n ∑ j ∈ S a i j , {\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 # S {\displaystyle \#S} to moc zbioru S . {\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 G , {\displaystyle G,} w którym podział wyznaczają wierzchołki A 1 , A 2 , … , A n {\displaystyle A_{1},A_{2},\dots ,A_{n}} z jednej strony oraz B 1 , B 2 , … , B n {\displaystyle B_{1},B_{2},\dots ,B_{n}} z drugiej. Wtedy G {\displaystyle G} można przedstawić jako macierz kwadratową n × n   A , {\displaystyle n\times n\ A,} gdzie a i , j = 1 {\displaystyle a_{i,j}=1} jeśli istnieje krawędź między wierzchołkami A i {\displaystyle A_{i}} i B j {\displaystyle B_{j}} lub a i , j = 0 , {\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.