Trvalý

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 24. května 2020; kontroly vyžadují 2 úpravy .

Permanentka v matematice je numerická funkce definovaná na množině všech matic ; pro čtvercové matice je podobný determinantu a liší se od něj pouze tím, že při expanzi na permutace (nebo na minory ) se neberou střídavá znaménka, ale všechny klady. Na rozdíl od determinantu je definice permanentu rozšířena i na nečtvercové matice.

V literatuře se k označení stálice obvykle používá jeden z následujících zápisů: , nebo . $\mathrm {za} (A)$ $\mathrm {per} A$ $\mathrm {perm} A$

Definice

Čtvercová matice trvalá

Dovolit je čtvercová matice velikosti , jejíž prvky patří do nějakého pole . Číslo se nazývá maticový permanent : $A$ $n\krát n$ $a_{i,j}$ $K$ $A$

\mathrm {Per} (A)=\součet _{\pi \in S_{n}}\prod _{i=1}^{n}a_{i,\pi _{i}}=\ součet _{\pi \in S_{n}}a_{1,\pi _{1}}a_{2,\pi _{2}}\cdots a_{n,\pi _{n}}

kde součet přebírá všechny permutace čísel od 1 do . $\pi$ $n$

Například pro matici velikosti : $2\times 2$

\mathrm {Per} {\begin{pmatrix}a&b\\c&d\end{pmatrix}}=ad+bc

Tato definice se od podobné definice determinantu liší pouze tím, že v determinantu mají některé členy součtu záporné znaménko v závislosti na znaménku permutace . $\pi$

Obdélníková matrice trvalá

Pojem permanent je někdy rozšířen na případ libovolné pravoúhlé matice velikosti následujícím způsobem. Pokud , pak: $A$ $m\krát n$ $m<n$

\mathrm {Per} (A)=\sum _{\pi }\prod _{i=1}^{m}a_{i,\pi _{i}}

kde součet přebírá všechna umístění prvků z množiny čísel od 1 do . $m$ $n$

Pokud , pak: $m>n$

\mathrm {Per} (A)=\mathrm {Per} (A^{T})

Nebo, ekvivalentně, permanent pravoúhlé matice lze definovat jako součet permanentů všech jejích čtvercových podmatic řádu . ${\displaystyle \min\{\,n,m\,\))$

Vlastnosti

Permanent jakékoli diagonální nebo trojúhelníkové matice se rovná součinu prvků na její diagonále. Konkrétně permanent nulové matice je roven nule a permanent matice identity je roven jedné.

Permanentka se při transpozici nemění : . Na rozdíl od determinantu se permanent matice nemění od permutace řádků nebo sloupců matice. $\mathrm {Per} (A^{T})=\mathrm {Per} (A)$

Permanent je lineární funkcí řádků (nebo sloupců) matice, to znamená:

vynásobíte-li libovolný jeden řádek (sloupec) určitým číslem , pak se hodnota permanentu zvýší faktorem; $C$ $C$
permanent součtu dvou matic, které se liší pouze o jeden řádek (sloupec) je roven součtu jejich permanentů.

Analog Laplaceova rozšíření pro první řádek matice pro permanent:

{\displaystyle \mathrm {Per} (A)=\sum _{j=1}^{n}a_{1,j}B_{1,j))

kde je permanent matice získaný vymazáním -tého řádku a -tého sloupce. Takže například pro matici size platí následující: ${\displaystyle B_{i,j))$ $A$ $i$ $j$ $3 krát 3$

\mathrm {Per} {\begin{pmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32} &a_{33}\end{pmatrix}}=a_{11}\mathrm {Per} {\begin{pmatrix}a_{22}&a_{23}\\a_{32}&a_{33}\end{pmatrix}} +a_{12}\mathrm {Per} {\begin{pmatrix}a_{21}&a_{23}\\a_{31}&a_{33}\end{pmatrix}}+a_{13}\mathrm {Per} {\begin{pmatrix}a_{21}&a_{22}\\a_{31}&a_{32}\end{pmatrix}}

Permanent matice objednávek je homogenní objednávková funkce : $n$ $n$

\mathrm {Per} (c\cdot A)=c^{n}\cdot \mathrm {Per} (A)

, kde je skalár.

c\in K

Pokud je permutační matice , pak: $P$

\mathrm {Per} (P)=1

;

\mathrm {Per} (AP)=\mathrm {Per} (PA)=\mathrm {Per} (A)

pro jakoukoli matici stejného řádu.

A

Pokud se matice skládá z nezáporných reálných čísel, pak . $A$ $\mathrm {Za} (A)\geqslant \det A$

Jestliže a jsou dvě horní (nebo dolní) trojúhelníkové matice , pak: $A$ $B$

\mathrm {Per} (AB)=\mathrm {Per} (BA)=\mathrm {Per} (A)\cdot \mathrm {Per} (B)

(obecně rovnost neplatí pro libovolné a , na rozdíl od analogické vlastnosti determinantů). $A$ $B$

Permanent minimálně dvakrát stochastické matice řádu ( van der Waerdenova domněnka , prokázaná v roce 1980). $n$ $n!/n^{n}$

Výpočet trvalého

Na rozdíl od determinantu, který lze snadno vypočítat např. Gaussovou metodou , je výpočet permanentu časově velmi náročnou výpočetní úlohou patřící do třídy složitosti #P-úplných úloh. Zůstává #P-complete i pro matice sestávající pouze z nul a jedniček [1] .

V současné době[ upřesnit ] není znám žádný algoritmus pro řešení takových problémů v čase, který je polynomiální ve velikosti matice. Existence takového polynomiálního algoritmu by byla ještě silnější než slavný P=NP .

V prosinci 2012 navrhly čtyři nezávislé výzkumné týmy prototyp kvantového fotonického zařízení, které vypočítává matricový permanent [2] .

Raiserův vzorec

Počítání permanentu je ze své podstaty složité (nebo dokonce „zhruba“ implementované). Odhad lze výrazně zlepšit použitím Raiserova vzorce [3] [4] : $O(n!)$ $O(n\cdot n!)$

\mathrm {Za} (A)=(-1)^{n}\součet _{S\subseteq \{1,\tečky ,n\}}(-1)^{|S|}\prod _{i=1}^{n}\součet _{j\in S}a_{ij}

s ním lze permanent vypočítat v čase nebo dokonce výčtem podmnožin pomocí Grayova kódu . $O(2^{n}n^{2})$ $O(2^{n}n)$

Aplikace

Trvalý má málo k žádnému použití v lineární algebře , ale má použití v diskrétní matematice a kombinatorice.

Permanent matice skládající se z nul a jedniček lze interpretovat jako počet úplných shod v bipartitním grafu s maticí sousednosti (tj. hranou mezi -tým vrcholem jedné části a -tým vrcholem jiná část existuje, pokud ). $A$ $A$ $i$ $j$ $a_{{ij}}=1$

Permanent libovolné matice lze považovat za součet vah všech úplných párování v úplném bipartitním grafu, kde váha párování je součinem vah jeho hran a váhy hran jsou zapsány v prvky matice sousednosti . $A$

Poznámky

↑ Leslie G. Valiant . The Complexity of Computing the Permanent (anglicky) // Theoretical Computer Science . - Elsevier, 1979. - Sv. 8 . - S. 189-201 . - doi : 10.1016/0304-3975(79)90044-6 .
↑ Fyzici vyvinuli fotonický kvantový počítač . Lenta.ru (24. prosince 2012). Získáno 25. prosince 2012. Archivováno z originálu 26. prosince 2012. (Ruština)
↑ Ryser HJ, "Combinatorial Mathematics", série matematických monografií Carus , vydané Mathematical Association of America , 1963 (existuje ruský překlad z roku 1966)
↑ Weisstein, Eric W. Ryser Formula na webu Wolfram MathWorld .

Literatura

Mink H. Permanentky. — M .: Mir, 1982. — 211 s.

Odkazy

Weisstein, Eric W. Permanent (anglicky) na webových stránkách Wolfram MathWorld .
Permanent (anglicky) na webu PlanetMath .