Unimodulär matris

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 9 november 2021; verifiering kräver 1 redigering .

En unimodulär matris är en kvadratisk matris med heltalskoefficienter , vars determinant är eller . Dessa är exakt de icke- singularmatriser för vilka ekvationen har en heltalslösning för vilken heltalsvektor som helst . $+1$ $-ett$ $A$ $ax=b$ $b$

Egenskaper

Unimodulära matriser bildar en multiplikationsgrupp , dvs. följande matriser är unimodulära:

Identitetsmatris
Invers till unimodulär matris
Produkt av två unimodulära matriser

Helt unimodulär matris

En rektangulär matris kallas helt unimodulär (eller absolut eller helt unimodulär) om alla dess mindreåriga tar värden från mängden . Med andra ord är vilken som helst av dess icke degenererade kvadratiska submatriser unimodulär. ${\displaystyle \{-1,0,+1\))$

Helt unimodulära matriser spelar en viktig roll i teorin om heltals linjär programmering : linjära programmeringsproblem med ett system av begränsningar av formen , där är helt unimodulär och är en heltalsvektor, har integrerade grundläggande genomförbara lösningar , och därför, i synnerhet, kan lösas med ett standardlinjärt programmeringsverktyg - en simplex-metod . $yxa = b$ $A$ $b$

Några exempel på helt unimodulära matriser:

incidensmatrisen för en riktad graf ;
incidensmatrisen för en tvådelad oriktad graf ;
privat exempel: ${\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är polynommatris

Satser

Sats 1: En polynommatris är unimodulär om och bara om alla dess invarianta faktorer är lika med en, dvs. när den är likvärdig med identitetsmatrisen.

Sats 2: En polynommatris är enmodulär om och bara om den är en produkt av matriselement .

Litteratur

Berge K. Grafteori och dess tillämpningar. Kapitel 15. M., IL, 1962.
Papadimitriou H., Steiglitz K. Kombinatorisk optimering . Algoritmer och komplexitet. 1984.
Emelichev V.A. Polyhedra. Räknar. Optimering. Kapitel IV. 1981.