Smithin normaali muoto - Smith normal form

Matematiikassa Smithin normaali muoto (joskus lyhennetty SNF ) on normaali muoto, joka voidaan määritellä mihin tahansa matriisiin (ei välttämättä neliöön), jonka merkinnät ovat pääidealueella (PID). Smith normaali matriisiksi on diagonaalinen , ja se voidaan saada alkuperäisen matriisin kertomalla vasemmalla ja oikealla käännettävissä neliömatriiseja. Erityisesti kokonaisluvut ovat PID, joten voidaan aina laskea kokonaislukumatriisin Smith-normaali muoto. Smithin normaalilomake on erittäin hyödyllinen työskenneltäessä lopullisesti tuotettujen moduulien kanssa PID: n kautta ja erityisesti vapaan moduulin osamäärän rakenteen päättelemiseksi . Se on nimetty brittiläisen matemaatikon Henry John Stephen Smithin mukaan .

Määritelmä

Olkoon A nollasta poikkeava m × n- matriisi pääidealueen R yli . On olemassa käänteisiä ja -matriiseja S, T siten, että tuote SAT on ${\ displaystyle m \ kertaa m}$${\ displaystyle n \ kertaa n}$

${\ displaystyle {\ begin {pmatrix} \ alpha _ {1} & 0 & 0 && \ cdots && 0 \\ 0 & \ alpha _ {2} & 0 && \ cdots && 0 \\ 0 & 0 & \ ddots &&&& 0 \\\ vdots &&& \ alpha _ {r} &&& \ vdots \\ &&&& 0 && \\ &&&&&& ddots & \\ 0 &&& \ cdots &&& 0 \ end {pmatrix}}.}$

ja lävistäjät tyydyttävät . Tämä on matriisin A Smithin normaali muoto . Elementit ovat ainutlaatuisia jopa kertomalla yksikön ja kutsutaan elementary jakajia , invariantit , tai muuttumaton tekijät . Ne voidaan laskea (kerrottuna yksiköllä) muodossa ${\ displaystyle \ alpha _ {i}}$${\ displaystyle \ alpha _ {i} \ mid \ alpha _ {i + 1} \; \ kaikki \; 1 \ leq i <r}$${\ displaystyle \ alpha _ {i}}$

${\ displaystyle \ alpha _ {i} = {\ frac {d_ {i} (A)} {d_ {i-1} (A)}},}$

missä (kutsutaan i : s tekijä jakaja ) on sama kuin suurin yhteinen tekijä kaikkien alaikäisten matriisin ja . ${\ displaystyle d_ {i} (A)}$${\ displaystyle i \ kertaa i}$ ${\ displaystyle d_ {0} (A): = 1}$

Algoritmi

Ensimmäinen tavoite on löytää käännettävät neliömatriisit ja sellaiset, että tuote on lävistäjä. Tämä on algoritmin vaikein osa. Kun diagonaalisuus on saavutettu, matriisin asettaminen Smithin normaalimuotoon on suhteellisen helppoa. Muotoiltu abstraktimmassa, tavoitteena on osoittaa, että ajattelu karttana (vapaa - moduuli listalla ) ja (vapaa - moduuli listalla ), on isomorfisuudella ja sellaiset, että on yksinkertainen muodoltaan matriisi . Matriisit ja löytyy aloittamassa identiteetti matriiseja sopivan kokoisia, ja muuttamalla joka kerran peräkkäin operaatio suoritetaan algoritmin vastaavalla pylvään toiminnan (esimerkiksi, jos rivi lisätään peräkkäin ja sitten sarake olisi vähennetään sarakkeesta , jotta tuotevariantti säilyy), ja samalla tavalla muunnetaan jokaiselle suoritetulle saraketoiminnalle. Koska rivitoiminnot ovat vasenkertaisia ​​ja saraketoiminnot ovat oikeakertoimia, tämä säilyttää invariantin, jossa merkitään nykyiset arvot ja alkuperäisen matriisin; lopulta tämän muuttujan matriiseista tulee diagonaalisia. Vain käännettävissä rivin ja sarakkeen toiminnot suoritetaan, mikä varmistaa sen, että ja edelleen käännettävissä matriiseja. ${\ displaystyle S}$${\ displaystyle T}$${\ displaystyle SAT}$${\ displaystyle A}$${\ displaystyle R ^ {n}}$${\ displaystyle R}$${\ displaystyle n}$${\ displaystyle R ^ {m}}$${\ displaystyle R}$${\ displaystyle m}$${\ displaystyle S: R ^ {m} \ - R ^ {m}}$${\ displaystyle T: R ^ {n} \ - R ^ {n}}$${\ displaystyle S \ cdot A \ cdot T}$${\ displaystyle S}$${\ displaystyle T}$${\ displaystyle S}$${\ displaystyle A}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle A}$${\ displaystyle j}$${\ displaystyle i}$${\ displaystyle S}$${\ displaystyle T}$${\ displaystyle A '= S' \ cdot A \ cdot T '}$${\ displaystyle A ', S', T '}$${\ displaystyle A}$${\ displaystyle S}$${\ displaystyle T}$

Sillä , kirjoita alkutekijöiden lukumäärälle (ne ovat olemassa ja ovat ainutlaatuisia, koska mikä tahansa PID on myös ainutlaatuinen tekijäalue ). Erityisesti se on myös Bézout-verkkotunnus , joten se on gcd-verkkotunnus ja minkä tahansa kahden elementin gcd täyttää Bézoutin identiteetin . ${\ displaystyle a \ sisään R \ setminus \ {0 \}}$${\ displaystyle \ delta (a)}$${\ displaystyle a}$${\ displaystyle R}$

Matriisin asettamiseksi Smithin normaalimuotoon voidaan käyttää toistuvasti seuraavaa, jossa silmukat ovat välillä 1 - ' . ${\ displaystyle t}$${\ displaystyle m}$

Vaihe I: Pivotin valinta

Valitse olla pienin sarakeindeksi, jossa ei ole nolla-merkintää. Aloita haku sarakehakemistosta, jos . ${\ displaystyle j_ {t}}$${\ displaystyle A}$${\ displaystyle j_ {t-1} +1}$${\ displaystyle t> 1}$

Haluamme saada ; jos näin on, tämä vaihe on valmis, muuten oletuksella on joitain kanssa , ja voimme vaihtaa rivejä ja siten saada . ${\ displaystyle a_ {t, j_ {t}} \ neq 0}$${\ displaystyle k}$${\ displaystyle a_ {k, j_ {t}} \ neq 0}$${\ displaystyle t}$${\ displaystyle k}$${\ displaystyle a_ {t, j_ {t}} \ neq 0}$

Valittu pivot on nyt paikallaan . ${\ displaystyle (t, j_ {t})}$

Vaihe II: Nivelen parantaminen

Jos kohdassa ( k , j _t ) on merkintä sellainen, että tällöin Bézout-ominaisuuden avulla tiedämme, että R: ssä on σ, τ siten , että ${\ displaystyle a_ {t, j_ {t}} \ nmid a_ {k, j_ {t}}}$${\ displaystyle \ beta = \ gcd \ vasen (a_ {t, j_ {t}}, a_ {k, j_ {t}} \ oikea)}$

${\ displaystyle a_ {t, j_ {t}} \ cdot \ sigma + a_ {k, j_ {t}} \ cdot \ tau = \ beta.}$

Kertomalla vasemmalle sopivalla käänteisellä matriisilla L voidaan saavuttaa, että matriisituotteen rivi t on summa σ kertaa alkuperäinen rivi t ja τ kertaa alkuperäinen rivi k , että tuotteen rivi k on toinen lineaarinen yhdistelmä alkuperäisistä riveistä ja että kaikki muut rivit ovat muuttumattomia. Jos σ ja τ täyttävät yllä olevan yhtälön, niin ja (mitkä jakaumat ovat mahdollisia β: n määritelmän mukaan) on ${\ displaystyle \ alpha = a_ {t, j_ {t}} / \ beta}$${\ displaystyle \ gamma = a_ {k, j_ {t}} / \ beta}$

${\ displaystyle \ sigma \ cdot \ alpha + \ tau \ cdot \ gamma = 1,}$

niin että matriisi

${\ displaystyle L_ {0} = {\ aloita {pmatrix} \ sigma & \ tau \\ - \ gamma & \ alfa \\\ end {pmatrix}}}$

on käänteinen, käänteinen

${\ displaystyle {\ begin {pmatrix} \ alpha & - \ tau \\\ gamma & \ sigma \\\ end {pmatrix}}.}$

Nyt L voidaan saada sovittamalla identiteettimatriisin riveihin ja sarakkeisiin t ja k . Rakentamalla matriisilla, joka saadaan vasemmalla kertomalla L: llä, on merkintä β asemassa ( t , j _t ) (ja valintamme α ja γ vuoksi sillä on myös merkintä 0 sijainnissa ( k , j _t ), mikä on hyödyllistä vaikkakaan ei välttämätöntä algoritmin kannalta). Tämä uusi merkintä β jakaa aiemmin siellä olleen merkinnän ja erityisesti ; siksi näiden vaiheiden toistamisen on lopulta lopetettava. Yksi päätyy matriisiin, jolla on merkintä kohdassa ( t , j _t ), joka jakaa kaikki sarakkeen j _t merkinnät . ${\ displaystyle L_ {0}}$${\ displaystyle a_ {t, j_ {t}}}$${\ displaystyle \ delta (\ beta) <\ delta (a_ {t, j_ {t}})}$

Vaihe III: Poistetaan merkinnät

Lopuksi, lisäämällä sopivia kerrannaisina rivi t , voidaan saavuttaa se, että kaikki merkinnät sarakkeen j _t , paitsi että kohdassa ( t , j _t ) ovat nolla. Tämä voidaan saavuttaa kertomalla vasemmalle sopivalla matriisilla. Jotta matriisi olisi täysin lävistäjä, meidän on kuitenkin poistettava myös nollasta poikkeavat merkinnät sijainnin rivillä ( t , j _t ). Tämä voidaan saavuttaa toistamalla vaiheen II vaiheet sarakkeille rivien sijaan ja käyttämällä kertolaskua oikealla saadun matriisin L transponoimalla . Yleensä tämä johtaa siihen, että vaiheen III aikaisemman sovelluksen nolla merkinnästä tulee jälleen nolla.

Huomaa kuitenkin, että jokaisen vaiheen II sovelluksen joko riveille tai sarakkeille on edelleen vähennettävä arvon arvoa , joten prosessin on lopulta lopetettava muutaman iteraation jälkeen, mikä johtaa matriisiin, jossa merkintä sijainnissa ( t , j _t ) on ainoa ei-nolla-merkintä sekä rivillä että sarakkeessa. ${\ displaystyle \ delta (a_ {t, j_ {t}})}$

Tässä vaiheessa vain A: n lohko ( t , j _t ): n oikeassa alakulmassa on diagonalisoitava, ja käsitteellisesti algoritmia voidaan soveltaa rekursiivisesti, käsittelemällä tätä lohkoa erillisenä matriisina. Toisin sanoen voimme lisätä t yksitellen ja palata vaiheeseen I.

Viimeinen vaihe

Soveltamalla yllä kuvattuja vaiheita tuloksena olevan matriisin jäljellä oleviin nollasta poikkeaviin sarakkeisiin (jos sellaisia ​​on) saadaan -matriisi, jossa on sarakeindeksit missä . Matriisimerkinnät eivät ole nollia, ja kaikki muut merkinnät ovat nollia. ${\ displaystyle m \ kertaa n}$${\ displaystyle j_ {1} <\ ldots <j_ {r}}$${\ displaystyle r \ leq \ min (m, n)}$${\ displaystyle (l, j_ {l})}$

Nyt voimme siirtyä nolla sarakkeita tämän matriisin oikealle, niin että nollasta poikkeava merkinnät ovat kantoja varten . Lyhyesti sanottuna, aseta elementti paikalleen . ${\ displaystyle (i, i)}$${\ displaystyle 1 \ leq i \ leq r}$${\ displaystyle \ alpha _ {i}}$${\ displaystyle (i, i)}$

Ehto diagonaalimerkintöjen jaettavuudesta ei välttämättä täyty. Kaikille hakemistoille , joiden osalta tämä puute voidaan korjata toimimalla riveillä ja sarakkeilla ja vain: lisää ensin sarake sarakkeeseen saadaksesi merkinnän sarakkeeseen i häiritsemättä sijainnin merkintää , ja tee sitten rivioperaatio merkinnän tekemiseen osoitteessa asema on yhtä suuri kuin vaiheessa II; jatka lopuksi kuten vaiheessa III, jotta matriisi olisi taas lävistäjä. Koska uusi merkintä sijainnissa on lineaarinen yhdistelmä alkuperäistä , se on jaollinen β: lla. ${\ displaystyle i <r}$${\ displaystyle \ alpha _ {i} \ nmid \ alpha _ {i + 1}}$${\ displaystyle i}$${\ displaystyle i + 1}$${\ displaystyle i + 1}$${\ displaystyle i}$${\ displaystyle \ alpha _ {i + 1}}$${\ displaystyle \ alpha _ {i}}$${\ displaystyle (i, i)}$${\ displaystyle (i, i)}$${\ displaystyle \ beta = \ gcd (\ alpha _ {i}, \ alpha _ {i + 1})}$${\ displaystyle (i + 1, i + 1)}$${\ displaystyle \ alpha _ {i}, \ alpha _ {i + 1}}$

Arvo ei muutu yllä mainitulla operaatiolla (se on δ ylemmän alimatriisin determinantista ), mistä operaatio pienenee (siirtämällä alkutekijöitä oikealle) arvon ${\ displaystyle \ delta (\ alpha _ {1}) + \ cdots + \ delta (\ alpha _ {r})}$${\ displaystyle r \ kertaa r}$

${\ displaystyle \ summa _ {j = 1} ^ {r} (rj) \ delta (\ alpha _ {j}).}$

Joten tämän toiminnon lopullisen monien sovellusten jälkeen uusi sovellus ei ole mahdollista, mikä tarkoittaa, että olemme saaneet toivomuksen mukaan. ${\ displaystyle \ alpha _ {1} \ mid \ alpha _ {2} \ mid \ cdots \ mid \ alpha _ {r}}$

Koska kaikki prosessiin liittyvät rivi- ja sarakekäsittelyt ovat käänteisiä, tämä osoittaa, että on olemassa käännettäviä ja -matriiseja S, T niin, että tuote SAT täyttää Smithin normaalin muodon määritelmän. Tämä osoittaa erityisesti, että Smithin normaali muoto on olemassa, mikä otettiin määritelmässä ilman todisteita. ${\ displaystyle m \ kertaa m}$${\ displaystyle n \ kertaa n}$

Sovellukset

Smithin normaali muoto on käyttökelpoinen ketjukompleksin homologian laskemiseksi, kun ketjukompleksin ketjumoduulit muodostetaan lopullisesti . Esimerkiksi topologiassa sitä voidaan käyttää yksinkertaisen kompleksin tai CW-kompleksin homologian laskemiseen kokonaislukujen yli, koska tällaisen kompleksin rajakartat ovat vain kokonaislukumatriiseja. Sitä voidaan käyttää myös määrittämään invarianttitekijät, jotka esiintyvät rakenteellisesti lauseessa lopullisesti generoiduille moduuleille pääideaalialueella , joka sisältää lopullisesti generoitujen abeliryhmien peruslauseen .

Smith normaali muoto on myös käytetään valvonta teoriassa laskea lähetyksen ja estää nollat on siirtofunktiomatriisin .

Esimerkki

Esimerkkinä löydämme seuraavan matriisin Smith-normaalimuodon kokonaislukujen yli.

${\ displaystyle {\ begin {pmatrix} 2 & 4 & 4 \\ - 6 & 6 & 12 \\ 10 & 4 & 16 \ end {pmatrix}}}$

Seuraavat matriisit ovat välivaiheita, kun algoritmia sovelletaan edellä olevaan matriisiin.

${\ displaystyle \ - {\ begin {pmatrix} 2 & 0 & 0 \\ - 6 & 18 & 24 \\ 10 & -16 & -4 \ end {pmatrix}} \ to {\ begin {pmatrix} 2 & 0 & 0 \\ 0 & 18 & 24 \\ 0 & -16 & -4 \ end {pmatrix}}}$

${\ displaystyle \ - {\ begin {pmatrix} 2 & 0 & 0 \\ 0 & 2 & 20 \\ 0 & -16 & -4 \ end {pmatrix}} \ to {\ begin {pmatrix} 2 & 0 & 0 \\ 0 & 2 & 20 \\ 0 & 0 & 156 \ end {pmatrix}}}$

${\ displaystyle \ - {\ begin {pmatrix} 2 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 156 \ end {pmatrix}}}$

Joten Smithin normaali muoto on

${\ displaystyle {\ begin {pmatrix} 2 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 156 \ end {pmatrix}}}$

ja muuttumattomat tekijät ovat 2, 2 ja 156.

Samankaltaisuus

Smithin normaalilla lomakkeella voidaan määrittää, ovatko matriisit, joissa on yhteisen kentän merkintöjä, samanlaisia . Erityisesti matriisien ja B ovat samanlaisia, jos ja vain jos ominaisuus matriisit ja on sama Smith normaali muoto. ${\ displaystyle xI-A}$${\ displaystyle xI-B}$

Esimerkiksi

${\ displaystyle {\ begin {aligned} A & {} = {\ begin {bmatrix} 1 & 2 \\ 0 & 1 \ end {bmatrix}}, && {\ mbox {SNF}} (xI-A) = {\ begin {bmatrix} 1 & 0 \\ 0 & (x-1) ^ {2} \ end {bmatrix}} \\ B & {} = {\ begin {bmatrix} 3 & -4 \\ 1 & -1 \ end {bmatrix}}, && {\ mbox {SNF}} (xI-B) = {\ aloita {bmatrix} 1 & 0 \\ 0 & (x-1) ^ {2} \ end {bmatrix}} \\ C & {} = {\ begin {bmatrix} 1 & 0 \\ 1 & 2 \ end {bmatrix}}, && {\ mbox {SNF}} (xI-C) = {\ begin {bmatrix} 1 & 0 \\ 0 & (x-1) (x-2) \ end {bmatrix}}. \ loppu {tasattu}}}$

A ja B ovat samanlaisia, koska niiden ominaismatriisien Smithin normaalimuoto täsmää, mutta eivät ole samankaltaisia ​​kuin C, koska karakterististen matriisien Smithin normaali muoto ei täsmää.

Katso myös

• Kanoninen muoto
• Alkeisjakajat
• Frobeniuksen normaalimuoto (kutsutaan myös rationaaliseksi kanoniseksi muodoksi)
• Hermiitin normaali muoto
• Muuttumaton tekijä
• Rakennelause lopullisesti generoiduille moduuleille pääidealueella

Huomautuksia

Viitteet

• Smith, Henry J.Stephen (1861). "Lineaaristen määrittelemättömien yhtälöiden ja yhtymien järjestelmistä". Phil. Trans. R. Soc. Lond. 151 (1): 293–326. doi : 10.1098 / rstl.1861.0016 . JSTOR   108738 . Uusintapainos (s. 367–409 ) julkaisussa The Collected Mathematical Papers of Henry John Stephen Smith , voi. Minä , toimittaja JWL Glaisher . Oxford: Clarendon Press (1894), xcv +603 ss.
• Smith normaalia muodossa osoitteessa PlanetMath .
• Esimerkiksi Smith normaali muoto on PlanetMath .
• KR Matthews, Smithin normaali muoto . MP274: Lineaarinen algebra, Luennot, Queenslandin yliopisto, 1991.

Ulkoiset linkit

• Animaatioesimerkki Smithin normaalimuodon laskemisesta .