Hamiltoniánský polynom - Hamiltonian cycle polynomial

V matematice je Hamiltoniánský polynom z n×n-matice je polynom v položkách matice, definovaný jako

${ displaystyle operatorname {ham} (A) = součet _ { sigma v H_ {n}} prod _ {i = 1} ^ {n} a_ {i, sigma (i)}}$

kde ${ displaystyle H_ {n}}$ je sada n-obměny mít přesně jeden cyklus.

Toto je algebraická možnost užitečná v řadě případů pro určení existence a Hamiltonovský cyklus v řízený graf.

Jedná se o zobecnění počtu hamiltonovských cyklů digrafu jako součet produktů obloukových váh jeho hamiltonovských cyklů (z nichž všechny mají stejnou jednotu) pro vážené digrafy s váhami oblouku získanými z daného komutativního kruhu. Mezitím pro neorientovaný vážený graf součet produktů hranových vah jeho hamiltonovských cyklů obsahujících jakoukoli pevnou hranu (i,j) lze vyjádřit jako součin hmotnosti (i,j) a polynom Hamiltonovského cyklu matice přijatý z jeho vážené matice sousedství prostřednictvím permutování jeho řádků a sloupců jakýmkoli permutačním mapováním i na 1 a j na 2 a poté jej odstranit 1- první řádek a 2-nd sloupec.

V (Knezevic & Cohen (2017) ) bylo prokázáno, že

${ displaystyle operatorname {ham} (A) = součet _ {J subseteq {2, tečky, n }} det (-A_ {J}) operatorname {per} (A _ { bar { J}})}$

kde ${ displaystyle A_ {J}}$ je submatice ${ displaystyle A}$ vyvolané řádky a sloupci ${ displaystyle A}$ indexováno podle ${ displaystyle J}$, a ${ displaystyle { bar {J}}}$ je doplňkem ${ displaystyle J}$ v ${ displaystyle {1, tečky, n }}$, zatímco determinant prázdné podmatice je definován jako 1.

Kvůli tomu a Borchardtovým identitám, pro ne-singulární n×n Cauchyova matice ${ displaystyle C (x, y)}$ ${ displaystyle operatorname {ham} (C (x, y)) = { det} (- D_ {1} ^ {2} C ^ {* 2} (x, y) D_ {2} ^ {2} + I _ {/ 1}) operatorname {det} (C (x, y))}$ kde ${ displaystyle D_ {1}, D_ {2}}$ jsou diagonální matice, které tvoří ${ displaystyle D_ {1} C (x, y) D_ {2}}$ unitární (v reálném poli nebo v poli konečné charakteristiky nebo ortogonální v poli komplexních čísel), ${ displaystyle C ^ {* 2} (x, y)}$ je Hadamardovo (vstupní) náměstí ${ displaystyle C (x, y)}$, a ${ displaystyle I _ {/ 1}}$ je identita n×n-matice se vstupem indexů 1,1 nahrazena 0.

V poli charakteristiky 2 rovnost ${ displaystyle operatorname {ham} (A) = součet _ {J subseteq {2, tečky, n }} det (-A_ {J}) operatorname {per} (A _ { bar { J}})}$ promění se v ${ displaystyle operatorname {ham} (A) = součet _ {J subseteq {2, tečky, n }} det (A_ {J}) det (A _ { bar {J}}) }$ co tedy poskytuje příležitost k polynomiálnímu času pro výpočet polynomu Hamiltonovského cyklu jakékoli jednotné matice ${ displaystyle U}$ (tj. takové, že ${ displaystyle U ^ {T} U = I}$ kde ${ displaystyle I}$ je identita n×n-matice), protože v takovém poli se každá menší unitární matice shoduje s jejím algebraickým doplňkem: ${ displaystyle operatorname {ham} (U) = { det} ^ {2} (U + I _ {/ 1})}$ kde ${ displaystyle I _ {/ 1}}$ je identita n×n-matice se vstupem indexů 1,1 nahrazených 0. Proto je-li možné polynomiálně-časově přiřadit váhy z pole charakteristiky 2 k obloukům digrafu, díky nimž je jeho vážená matice sousedství jednotná a má nenulový Hamiltoniánský polynom pak digraph je Hamiltonian. Proto je problém Hamiltonovského cyklu na takových grafech vypočítatelný v polynomiálním čase.

V charakteristice 2 je Hamiltonovský cyklický polynom an n×n-matice je nula, pokud n > 2k, kde k je jeho hodnost nebo je-li involutorní a n > 1.

Kromě toho v libovolném kruhu ${ displaystyle R}$ jehož charakteristika není sudým přirozeným číslem pro jakoukoli symetrii zešikmení n×n-matice ${ displaystyle A}$ existuje formální řada ve formální proměnné ${ displaystyle varepsilon}$ ${ displaystyle U ( varepsilon) = součet _ {n = 0} ^ { infty} U_ {n} varepsilon ^ {n}}$ tak, že je to unitární n×n-matice skončila ${ displaystyle R left ( varepsilon right)}$ a ${ displaystyle U_ {0} = I}$, ${ displaystyle U_ {1} = A}$, zatímco pro všechny ${ displaystyle U ( varepsilon)}$ splnění těchto podmínek ${ displaystyle operatorname {ham} (A)}$ se rovná koeficientu na ${ displaystyle n}$-tá síla ${ displaystyle varepsilon}$ v silové řadě ${ displaystyle operatorname {ham} (U ( varepsilon))}$. A pro jakýkoli prsten ${ displaystyle R}$ sudé charakteristiky totéž platí, když úhlopříčka ${ displaystyle A ^ {2}}$ je násobkem 2. Znamená to, že výpočetní technika, až do ${ displaystyle n}$-tá síla ${ displaystyle varepsilon}$, Hamiltonovský cyklický polynom jednotného n×n-matice nad nekonečným rozšířením libovolného prstence charakteristiky q (ne nutně prime) formální proměnnou ${ displaystyle varepsilon}$ je #${ displaystyle _ {q}}$P-kompletní problém, pokud ${ displaystyle q}$ není 2 a výpočet polynomu Hamiltonovského cyklu a ${ displaystyle k}$-semi-unitární matice (tj n×n-matice ${ displaystyle V}$ takhle ${ displaystyle operatorname {rank} (V ^ {T} V-I ,) = k}$) přes takové prodloužení kteréhokoli prstence charakteristiky 2 je a #${ displaystyle _ {2}}$P-kompletní problém pro každého ${ displaystyle k}$ > 0 (protože jakýkoli ${ displaystyle k}$-semi-unitární matice může být přijata z unitární matice odstraněním ${ displaystyle k}$ řádky a ${ displaystyle k}$ sloupce). Pro ${ displaystyle k = 1}$ druhý příkaz může být znovu formulován jako #${ displaystyle _ {2}}$P-úplnost výpočtu pro danou jednotku n×n-matice ${ displaystyle U}$ nad polem charakteristiky 2, n×n-matice ${ displaystyle H (U)}$ jehož i,j-tý záznam je hamiltonovský cyklus polynomu matice přijatého z ${ displaystyle U}$ prostřednictvím permutování jeho řádků a sloupců jakýmkoli permutačním mapováním i na 1 a j na 2 a poté jej odstranit 1- první řádek a 2-nd sloupec (tj. součet produktů obloukových vah odpovídajících vážených digrafických hamiltonovských patů j na i) pro i ≠ j a nula pro i = j. Tato matice splňuje maticovou rovnici ${ displaystyle U (H (U)) ^ {T} = H (U) U ^ {T}}$, zatímco ${ displaystyle operatorname {ham} left ({ begin {matrix} U & {Ua} a ^ {T} & 0 end {matrix}} right) = (a_ {1} ^ {2} +. .. + a_ {n} ^ {2}) operatorname {ham} (U)}$ kde ${ displaystyle a}$ je libovolný n-vektor.

Navíc by stálo za zmínku, že v charakteristice 2 má polynom Hamiltonovského cyklu své invariantní maticové komprese (částečně analogické s Gaussovou modifikací, která je pro determinant neměnná), s přihlédnutím ke skutečnosti, že ${ displaystyle operatorname {ham} (X) = 0}$ pro všechny t×t-matice ${ displaystyle X}$ mít tři stejné řádky nebo, pokud ${ displaystyle t}$ > 2, dvojice indexů i, j taková, že její i-té a j-té řádky jsou identické a jeho i-tý a j-tý sloupec jsou také identické.

Proto pokud má matice dva stejné řádky s indexy i a j přidáním jednoho z nich ke kterémukoli třetímu se nezmění tento polynom v charakteristice 2, což umožňuje Gaussovskému stylu eliminovat všechny položky jeho i-tý sloupec kromě i,i-th a j,i-té (v případě, že nejsou nula) a odstranit jeho i-tý sloupec a j-tý řádek (výše popsaným způsobem) - pak se polynom Hamiltonovského cyklu počáteční matice rovná tomuto polynomu nové vynásobenému počátečním j,i-tý vstup.

Také v charakteristice 2 a pro matice s více než dvěma řádky se polynom Hamiltonovského cyklu nezmění přidáním i-tý sloupec do j-tý v matici, kde i-th a j-té řádky jsou identické, což zejména přináší identitu

${ displaystyle det (D + D ^ {- 1}) operatorname {ham} left ({ begin {matrix} V&A B&U end {matrix}} right) = operatorname {ham} left ({ begin {matrix} V & V + D & A V + D ^ {- 1} & V + D ^ {- 1} + D & A B & B & U end {matrix}} right)}$

pro n×n-matice ${ displaystyle U}$, m×m- matice ${ displaystyle V}$ a úhlopříčka ${ displaystyle D}$, m×n-matice ${ displaystyle A}$ a n×m-matice ${ displaystyle B}$.

Omezení této identity na případ, kdy ${ displaystyle U}$ je unitární, ${ displaystyle VD + DV ^ {T} + AA ^ {T} = I + D ^ {2}}$ a ${ displaystyle BD = UA ^ {T}}$, kde ${ displaystyle I}$ je identita m×m-matice, dělá (2m+n)×(2m+n) -matice v pravé straně unitární rovnice a její Hamiltonův cyklický polynom lze vypočítat, tedy v polynomiálním čase, což tedy zobecňuje výše uvedený vzorec pro polynomial Hamiltonovského cyklu jednotné matice. Kromě toho v charakteristice 2 pro čtvercové matice X, Y ${ displaystyle operatorname {ham} left ({ begin {matrix} X&Y Y&X end {matrix}} right)}$ je čtverec součtu, přes všechny dvojice nerovných indexů i, j, i, j-tého vstupu Y vynásobeného polynomem Hamiltonovského cyklu matice přijatého z X + Y odstraněním jeho i-tá řada a j-tý sloupec (způsobem popsaným výše). Po vložení výše uvedené rovnosti A = B a U = V tedy získáme další rozšíření třídy unitárních matic, kde je polynomial Hamiltonovského cyklu vypočítatelný v polynomiálním čase.

Kromě výše zmíněných kompresních transformací platí v charakteristice 2 následující vztah také pro polynomy hamiltonovského cyklu matice a její částečnou inverzi (pro ${ displaystyle A_ {11}}$ a ${ displaystyle A_ {22}}$ být čtvercový, ${ displaystyle A_ {11}}$ bytost invertibilní ):

${ displaystyle operatorname {ham} left ({ begin {matrix} A_ {11} & A_ {12} A_ {21} & A_ {22} end {matrix}} right) = { det} ^ {2} left (A_ {11} right) operatorname {ham} left ({ begin {matrix} A_ {11} ^ {- 1} & A_ {11} ^ {- 1} A_ {12} A_ {21} A_ {11} ^ {- 1} & A_ {22} + A_ {21} A_ {11} ^ {- 1} A_ {12} end {matrix}} right)}$

a vzhledem k tomu, že hamiltonovský cyklus polynomu nezávisí na diagonálních záznamech matice, přidání libovolné diagonální matice tento polynom také nezmění. Tyto dva typy transformace nekomprimují matici, ale udržují její velikost beze změny. V řadě případů však jejich aplikace umožňuje zmenšit velikost matice některým z výše uvedených operátorů komprese.

Proto existuje řada operátorů komprese matice prováděných v polynomiálním čase a zachování polynomu Hamiltonovského cyklu v charakteristice 2, jejichž sekvenční aplikace spolu s transformací transpozice (využívaná pokaždé, když operátory nechají matici neporušenou), má pro každou matici a určitý limit, který lze definovat jako operátor uzavření komprese. Při použití na třídy matic tak tento operátor mapuje jednu třídu na druhou. Jak bylo prokázáno v (Knezevic & Cohen (2017) ), pokud operátor uzavření komprese mapuje třídu unitárních matic na celou množinu čtvercových matic přes nekonečné pole charakteristiky 2, pak je polynomial Hamiltonovského cyklu vypočítatelný v polynomiálním čase přes jakékoli pole této charakteristiky, což by znamenalo rovnostRP = NP.

Reference

• Knezevic, Anna; Cohen, Greg (2017), Některá fakta o permanentech v konečných charakteristikách, arXiv:1710.01783, Bibcode:2017arXiv171001783K.

• Kogan, Grigoriy (1996), „Výpočet stálic nad poli charakteristiky 3: kde a proč se to stává obtížným“, 37. výroční sympozium o základech informatiky (FOCS '96): 108–114, doi:10.1109 / SFCS.1996.548469, ISBN  0-8186-7594-2

• Cohen, Greg (2010), Nová algebraická technika pro výpočet polynomiálního času číslo modulo 2 hamiltonovských rozkladů a podobných oddílů hranové množiny grafu, arXiv:1005.2281, Bibcode:2010arXiv1005.2281C