Unimodul matrix

Thyra Jørgensen Januar 2, 2017 U 1 0
FONT SIZE:
fontsize_dec
fontsize_inc

I matematik, en unimodul matrix M er en firkantet heltal matrix med determinant +1 eller -1. Ækvivalent, er et helt tal matrix, der er invertibel over heltal: Der er et helt tal matrix N, som er dens inverse. Således hver ligning Mx = b, hvor M og b er heltal begge, og M er unimodul, har et heltal løsning. De unimodul matricer af orden n danne en gruppe, som er angivet.

Eksempler på matricer unimodul

Unimodul matricer udgør en undergruppe af den generelle lineære gruppe under matrix multiplikation, dvs. følgende matricer er unimodul:

  • Enhedsmatrix
  • Enhver unitær matrix
  • Den inverse af en unimodul matrix
  • Produktet af to unimodul matricer

Yderligere:

  • Det Kroneckers produkt af to unimodul matricer er også unimodul. Dette følger siden

Konkrete eksempler indbefatter:

  • Symplektiske matricer
  • Pascal matricer
  • Permutation matricer
  • de tre transformationsmatricerne i det ternære træ primitive Pythagoras tripler

Samlet unimodularity

En helt unimodul matrix er en matrix, for hvilken hvert kvadrat ikke-ental delmatrix er unimodul. En helt unimodul matrix behøver ikke at være firkantet selv. Fra definitionen følger det, at enhver fuldstændig unimodul matrix har kun 0, +1 eller -1 poster. Det modsatte er ikke sandt, det vil sige, en matrix med kun 0, +1 eller -1 poster er ikke nødvendigvis unimodul.

Helt unimodul matricer er ekstremt vigtigt i polyhedrale kombinatorik og kombinatorisk optimering, da de giver en hurtig måde at kontrollere, at et lineært program er integreret. Konkret hvis A er TU og b er integreret, så lineære programmer former som eller har integreret optima, for enhver c. Derfor, hvis A er fuldstændig unimodul og b er integreret i hver yderste punkt af den realistiske region er integreret og dermed den mulige region er en integreret polyeder.

Fælles helt unimodul matricer

1. uorienterede forekomst matrix af en todelt graf, som er koefficientmatricen for todelt matching, er helt unimodul. Mere generelt i tillægget til et papir ved Heller og Tompkins, AJ Hoffman og D. Gale bevise følgende. Lad være en m med n matrix, hvis rækker kan opdeles i to adskilte sæt og. Så følgende fire betingelser tilsammen er tilstrækkelige for A at være helt unimodul:

  • Hver søjle af højst indeholder to ikke-nul poster;
  • Hver post i er 0, 1 eller -1;
  • Hvis to ikke-nul poster i en kolonne af have samme fortegn, så rækken af ​​man er i, og den anden i;
  • Hvis to ikke-nul indgange i en søjle af modsat fortegn, så rækkerne af begge er i, eller begge i.

Det blev realiseret senere, at disse betingelser definerer en forekomst matrix af en afbalanceret underskrevet graf; således dette eksempel siger, at forekomsten matrix af en underskrevet graf er helt unimodul hvis den underskrevne grafen er afbalanceret. Det modsatte er gældende for underskrevne grafer uden halv kanter.

2. De begrænsninger maksimalt flow og minimale omkostninger flow-problemer giver en koefficient matrix med disse egenskaber. Således sådanne netværk flow problemer med bundne heltal kapacitet har en integreret optimal værdi. Bemærk at dette ikke gælder for multi-råvare flow-problemer, hvor det er muligt at have fraktioneret optimal værdi selv med afgrænset heltal kapacitet.

3. Den fortløbende-ones ejendom: hvis A er en 0-1-matrix, hvor for hver række, vises 1s fortløbende, så er A TU.

4. Enhver netværk matrix er TU. Rækkerne af et netværk matrix svarer til et træ T =, hver hvis buer har et vilkårligt orientation.The kolonnerne svarer til et andet sæt C af buer på det samme toppunkt sæt V. For at beregne indrejse ved rækken R og kolonne C = m , se på s-til-t sti P i T; så posten er:

  • 1, hvis bue R vises frem i P,
  • -1 Hvis bue R vises baglæns i P,
  • 0, hvis bue R ikke vises i P.

Se mere i Schrijver.

5. Ghouila-Houri viste, at en matrix er TU IFF for hver delmængde R af rækker, der er en opgave af tegn til rækker, så det underskrevne summen har alle sine indgange i. Dette og flere andre if-and-only-if karakteriseringer er bevist i Schrijver.

6. Hoffman og Kruskal beviste den følgende sætning. Antag er en orienteret graf uden 2-dicycles, er mængden af ​​alle dipaths i, og er 0-1 forekomsten matrix af kontra. Så er fuldstændig unimodul hvis og kun hvis alle simple vilkårligt orienterede cyklus består af skiftevis forlæns og baglæns buer.

7. Antag en matrix har 0- poster og i hver kolonne, posterne er ikke-aftagende fra top til bund. Fujishige viste, at matrixen er TU IFF hver 2-by-2 undermatrix har determinant.

8. Seymour viste sig en fuldstændig karakterisering af alle TU matricer, som vi beskriver her kun uformelt. Seymour sætning er, at en matrix er TU hvis og kun hvis det er en vis naturlig kombination af nogle netværk matricer og nogle kopier af en bestemt 5-by-5 ​​TU matrix.

Konkrete eksempler

1. Følgende matrix er helt unimodul:

Denne matrix opstår som koefficientmatricen af ​​begrænsninger i lineær programmering formulering af det maksimale flow problem på følgende netværk:

2. Enhver matrix af formen

er ikke helt unimodul, da den har en firkantet undermatrix af determinant -2.

Abstrakt lineær algebra

Abstrakt lineær algebra anser matricer med indgange fra enhver kommutativ ring, ikke begrænset til heltal. I denne sammenhæng er en unimodul matrix er en, der er invertibel i ringen; ækvivalent, hvis determinant er en enhed. Denne gruppe betegnes.

Over et felt, unimodul har samme betydning som ikke-singulær. Unimodul her refererer til matrixer med koefficienter i nogle ring, som er krænges over denne ring, og man anvender ikke-singulær at betyde matricer, der er invertibel hele banen.

  Like 0   Dislike 0
Forrige artikel Operation Magistral
Næste artikel Tracy Sachtjen
Kommentarer (0)
Ingen kommentar

Tilføj en kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tegn tilbage: 3000
captcha