Permanenty a wyznaczniki

Zbiór wzorów, definicji i najczęściej poruszanych problemów z Algebry.
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11264
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3143 razy
Pomógł: 747 razy

Permanenty a wyznaczniki

Post autor: mol_ksiazkowy »

Definicja
Permanent jest definiowany tak jak wyznacznik dla macierzy kwadratowej, z tą różnicą, że wszystkie iloczyny odpowiednich wyrazów są uwzględnione ze znakiem \(\displaystyle{ +}\), a nie jak przy wyznaczniku ze znakiem (\(\displaystyle{ +}\) lub \(\displaystyle{ -}\)), tj. zależnym od permutacji wierszy; tj. \(\displaystyle{ \mathrm{Per\left( A\right) }= \sum_{\sigma \in S_n} \prod_{i=1}^n a_{i \ \sigma(i)}}\).
W najprostszym przypadku tj. dla macierzy \(\displaystyle{ 2 \times 2}\): \(\displaystyle{ \mathrm{Per}{ \left (\begin{bmatrix} a&b\\c&d \end{bmatrix} \right)} = ad+bc}\).

Dla macierzy \(\displaystyle{ 3 \times 3}\):
\(\displaystyle{ \mathrm{Per}{ \left (\begin{bmatrix} a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33}\end {bmatrix} \right) = a_{11}a_{22}a_{33} +a_{12}a_{23}a_{31}+a_{21}a_{32}a_{13}+a_{21}a_{12}a_{33}+ a_{13}a_{22}a_{31} +a_{11}a_{32}a_{23}}}\)

Uwagi: Można obliczać permanent także dla macierzy niekwadratowych: jeśli \(\displaystyle{ m \leq n}\) to permanent jest sumą wszystkich iloczynów \(\displaystyle{ m}\) elementów z różnych kolumn i wierszy; np. gdy \(\displaystyle{ A}\) jest macierzą mającą dwa wierwsze i \(\displaystyle{ n>2}\) kolumnach to

\(\displaystyle{ \mathrm{Per}\left( A\right){} = \sum_{s \neq t} a_{1 s}a_{2 t}}\) np.

\(\displaystyle{ \mathrm{Per} \left (\begin{bmatrix} 1&2&3\\ 6&5&4 \end{bmatrix} \right) = 1 \cdot(5+4)+ 2 \cdot(6+4)+ 3 \cdot (6+5)= 62 = (1+2+3) \cdot (6+5+4) - (1 \cdot 6 + 2 \cdot 5 + 3 \cdot 4)}\)


Wzór Rysera:
\(\displaystyle{ \mathrm{Per\left( A\right) }=(-1)^n \sum_{S \subset \{ 1,...,n \}} (-1)^{|S|} \prod_{i=1}^n \sum_{j \in S} a_{ij}}\)

Hipoteza van der Waerdena
Dla dowolnej macierzy \(\displaystyle{ A}\) wymiaru \(\displaystyle{ n \times n}\), o wyrazach nieujemnych, i takiej że suma elementów każdego wiersza i każdej kolumny wynosi \(\displaystyle{ 1}\) jest spełniona nierówność \(\displaystyle{ \mathrm{Per\left( A\right) } \geq \frac{n!}{n^n}}\).
Poza tym równość zachodzi gdy wszystkie wyrazy macierzy są równe \(\displaystyle{ \frac{1}{n}}\).


Niektóre analogie i różnice z wyznacznikiem
Analogie:
■ Operacja zamiany miejscami kolumn lub wierszy jest niezmiennikiem dla permanentu;
■ Transpozycja macierzy także nie zmienia permanentu (tj. \(\displaystyle{ \mathrm{Per\left( A\right) }=\mathrm{Per\left( A^{T}\right) }}\))
■ Istnienie wzoru - odpowiednika rozwinięcia Laplace’a

Różnice
■ Brak prostych interpretacji geometrycznych permanentu
■ Brak niektórych własności algebraicznych np. \(\displaystyle{ \mathrm{Per\left( AB\right) }}\) i \(\displaystyle{ \mathrm{Per\left( BA\right) }}\) są na ogół rożne
(\(\displaystyle{ \mathrm{Per\left( AB\right) } \neq \mathrm{Per\left( A\right) }\mathrm{Per\left( B\right) }}\)) i innych metod (np. eliminacji Gaussa); jeśli wiersze (kolumny) macierzy tworzą układ liniowo zależny permanent może być niezerowy


Permanent a systemy różnych reprezentantów (transwersale)
Jeśli zbiory \(\displaystyle{ A_1, ..., A_n}\) są podzbiorami zbioru \(\displaystyle{ m}\) elementowego \(\displaystyle{ X}\) to transwersalą tej rodziny zbiorów jest dowolny ciąg różnych elementów \(\displaystyle{ a_1, ...,a_n}\) takich, że \(\displaystyle{ a_j \in A_j}\) dla \(\displaystyle{ j = 1, ..., n}\). (np. dla rodzina \(\displaystyle{ A_1= \{ 1, 2 , 3 \} , \ A_2 = \{ 1 , 2 \} , \ A_3 = \{ 2, 3 \} , \ A_4 = \{ 4 \} \}}\) ma transwersalę \(\displaystyle{ (2, 1, 3, 4)}\) zaś rodzina \(\displaystyle{ A_1 = \{ 1, 2, 3 \} , \ A_2 = \{ 1, 2 \} , \ A_3 = \{ 1, 3 \} , \ A_4 = \{ 2, 3 \}}\) jej nie ma). Ilość systemów różnych reprezentantów dla rodziny podzbiorów \(\displaystyle{ A_1, …, A_n}\) zbioru \(\displaystyle{ X}\) jest równa \(\displaystyle{ \mathrm{Per\left( A\right) }}\) dla macierzy \(\displaystyle{ A = (a_{i j})}\) gdzie \(\displaystyle{ a_{i j}= 1}\) gdy \(\displaystyle{ x_j \in A_i}\) oraz gdzie \(\displaystyle{ a_{i j}= 0}\) gdy \(\displaystyle{ x_j \notin A_i}\).


Zadania
1. Obliczyć permanent macierzy
\(\displaystyle{ A= \begin{bmatrix} 1&2&0&1\\2&-1&-1&3\\1&2&1& 0\\ 0&1&3&1 \end{bmatrix}}\)
2. Niech \(\displaystyle{ A = \begin{bmatrix} 2&0&0&4\\0&0&0&1\\0&2&0& 0\\ -1&0&1&0 \end{bmatrix}}\). Wyznaczyć \(\displaystyle{ A^{-1}}\). Czy dla tej macierzy \(\displaystyle{ \mathrm{Per\left( A^{-1}\right) } = \frac{1}{\mathrm{Per\left( A\right) }}}\) ?
3. Sprawdzić hipotezę van der Waerdena gdy \(\displaystyle{ A= \begin{bmatrix} \frac{1}{2}&\frac{1}{3}&\frac{1}{6}\\\frac{1}{6}&0&\frac{5}{6}\\\frac{1}{3}&\frac{2}{3}&0 \end{bmatrix}}\)
4. Obliczyć permanent i wyznacznik macierzy \(\displaystyle{ A=(a_{i j})}\) gdzie
\(\displaystyle{ \begin{cases}a_{i j} = 1 \ i \neq j \\ a_{i j} = 0 \ i=j \end{cases}}\).
Udowodnić, że \(\displaystyle{ \mathrm{Per\left( A\right) }}\) jest ilością nieporządków (tj. permutacji bez punktów stałych).
5. Wskazać przykład macierzy \(\displaystyle{ 3 \times 3}\) dla której \(\displaystyle{ \mathrm{Per\left( A\right) }=0}\) i \(\displaystyle{ \mathrm{det\left( A\right) } \neq 0}\)
6. Obliczyć permanent macierzy
\(\displaystyle{ B= \begin{bmatrix} 1&0&0&-1&-1\\3&-1&-1&2&3\\1&1&-2& 0&-2\\ 0&1&3&1&0\\ -1&0 & 0 &1 &3 \end{bmatrix}}\)
stosując rozwinięcie Laplace’a
7. Ile transwersal ma rodzina \(\displaystyle{ R= \{ 1, 2 \} , \ \{ 1, 2, 3 \} , \ \{ 2, 4, 5 \} , \ \{ 3, 5 \} , \ \{ 1, 3, 4, 5 \}}\) ?


Żródła

*

W języku polskim brak jest terminu słownego jako istotne tłumaczenie (istnieje przymiotnik permanentny)

Permanentami zajmowali się matematycy jak: Binet, Muirhead, Schur, itd.

Wyczerpującym źródłem informacji o permatentach jest M. Minc - Permanents , Addison-Wesley, 1978 r.
ODPOWIEDZ