Unimodulární matice

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é 9. listopadu 2021; ověření vyžaduje 1 úpravu .

Unimodulární matice je čtvercová matice s celočíselnými koeficienty , jejichž determinantem je nebo . To jsou přesně ty nesingulární matice , pro které má rovnice celočíselné řešení pro libovolný celočíselný vektor . $+1$ $-jeden$ $A$ $sekera=b$ $b$

Vlastnosti

Unimodulární matice tvoří multiplikační grupu , tzn. následující matice jsou unimodulární:

Matice identity
Inverzní k unimodulární matici
Součin dvou unimodulárních matic

Zcela unimodulární matice

Obdélníková matice se nazývá zcela unimodulární (nebo absolutně nebo zcela unimodulární), pokud všechny její vedlejší prvky přebírají hodnoty ze sady . Jinými slovy, kterákoli z jeho nedegenerovaných čtvercových podmatic je unimodulární. ${\displaystyle \{-1,0,+1\))$

Zcela unimodulární matice hrají důležitou roli v teorii celočíselného lineárního programování : úlohy lineárního programování se systémem omezení tvaru , kde je zcela unimodulární a je celočíselným vektorem, mají integrální základní proveditelná řešení , a proto zejména, lze vyřešit standardním nástrojem lineárního programování - simplexní metodou . $sekera = b$ $A$ $b$

Některé příklady zcela unimodulárních matic:

matice výskytu jakéhokoli orientovaného grafu ;
matice výskytu bipartitního neorientovaného grafu ;
soukromý příklad: ${\begin{bmatrix}-1&-1&0&0&0&+1\\+1&0&-1&-1&0&0\\0&+1&+1&0&-1&0\\0&0&0&+1&+1&-1\\\end{bmatrix)).$

Unimodulární polynomiální matice

Věty

Věta 1: Polynomiální matice je unimodulární právě tehdy, když jsou všechny její invariantní faktory rovné jedné, tzn. když je ekvivalentní matici identity.

Věta 2: Polynomiální matice je unimodulární právě tehdy, když je součinem prvků matice .

Literatura

Berge K. Teorie grafů a její aplikace. Kapitola 15. M., IL, 1962.
Papadimitriou H., Steiglitz K. Kombinatorická optimalizace . Algoritmy a složitost. 1984.
Emelichev V.A. Mnohostěn. Počítání. Optimalizace. Kapitola IV. 1981.