szukanie zaawansowane
 [ Posty: 1 ] 
Autor Wiadomość
Mężczyzna
PostNapisane: 13 lut 2016, o 21:05 
Użytkownik

Posty: 5820
Lokalizacja: Kraków
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 +, a nie jak przy wyznaczniku ze znakiem (+ lub -), tj. zależnym od permutacji wierszy; tj. \mathrm{Per\left( A\right) }= \sum_{\sigma \in S_n} \prod_{i=1}^n  a_{i  \ \sigma(i)}.
W najprostszym przypadku tj. dla macierzy 2 \times 2: \mathrm{Per}{ \left   (\begin{bmatrix} a&b\\c&d \end{bmatrix} \right)} =  ad+bc.

Dla macierzy 3 \times 3:
\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 m \leq n to permanent jest sumą wszystkich iloczynów m elementów z różnych kolumn i wierszy; np. gdy A jest macierzą mającą dwa wierwsze i n>2 kolumnach to

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

\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:
\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 A wymiaru n \times n, o wyrazach nieujemnych, i takiej że suma elementów każdego wiersza i każdej kolumny wynosi 1 jest spełniona nierówność \mathrm{Per\left( A\right) }  \geq \frac{n!}{n^n}.
Poza tym równość zachodzi gdy wszystkie wyrazy macierzy są równe \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. \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. \mathrm{Per\left( AB\right) } i \mathrm{Per\left( BA\right) } są na ogół rożne
(\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 A_1, ..., A_n są podzbiorami zbioru m elementowego X to transwersalą tej rodziny zbiorów jest dowolny ciąg różnych elementów a_1, ...,a_n takich, że a_j \in A_j dla j = 1, ..., n. (np. dla rodzina A_1= \{ 1, 2 , 3 \} ,  \ A_2 = \{   1  , 2 \} ,  \ A_3 = \{  2,  3 \} , \  A_4 = \{  4 \} \} ma transwersalę (2, 1, 3, 4) zaś rodzina 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 A_1, …, A_n zbioru X jest równa \mathrm{Per\left( A\right) } dla macierzy A = (a_{i j}) gdzie a_{i j}= 1 gdy x_j \in A_i oraz gdzie a_{i j}= 0 gdy x_j \notin A_i.


Zadania
1. Obliczyć permanent macierzy
A= \begin{bmatrix} 1&2&0&1\\2&-1&-1&3\\1&2&1& 0\\  0&1&3&1 \end{bmatrix}
2. Niech A = \begin{bmatrix} 2&0&0&4\\0&0&0&1\\0&2&0& 0\\  -1&0&1&0 \end{bmatrix}. Wyznaczyć A^{-1}. Czy dla tej macierzy \mathrm{Per\left( A^{-1}\right) } = \frac{1}{\mathrm{Per\left( A\right) }} ?
3. Sprawdzić hipotezę van der Waerdena gdy 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 A=(a_{i j}) gdzie
\begin{cases}a_{i j} = 1 \ i \neq j \\ a_{i j} = 0 \ i=j \end{cases}.
Udowodnić, że \mathrm{Per\left( A\right) } jest ilością nieporządków (tj. permutacji bez punktów stałych).
5. Wskazać przykład macierzy 3 \times 3 dla której \mathrm{Per\left( A\right) }=0 i \mathrm{det\left( A\right) } \neq 0
6. Obliczyć permanent macierzy
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 R= \{ 1, 2 \} ,  \  \{ 1, 2, 3 \} , \  \{ 2, 4, 5 \} , \ \{ 3, 5 \} , \  \{ 1, 3, 4, 5 \} ?


Żródła

* http://encyklopedia.eduteka.pl/wiki/Permanent

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.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 1 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Wyznaczniki w geometrii  TlustaTeta  0
 Wykazać, że wyznaczniki są równe zero.  isunia  2
 Wyznaczniki. Reguły metody Gaussa.  passat  7
 Równanie liniowe- wyznaczniki  prawyakapit  1
 Wyznaczniki +indukcja matematyncza  divix13  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl