Smith normal form

Inom matematik är Smiths normalform (ibland förkortad SNF ) en normalform som kan definieras för vilken matris som helst (inte nödvändigtvis kvadratisk) med poster i en principiell idealdomän (PID). Smith normala formen av en matris är diagonal och kan erhållas från den ursprungliga matrisen genom att multiplicera till vänster och höger med inverterbara kvadratiska matriser. I synnerhet är heltalen ett PID, så man kan alltid beräkna Smiths normala form av en heltalsmatris. Smith normalform är mycket användbar för att arbeta med ändligt genererade moduler över en PID, och i synnerhet för att härleda strukturen för en kvot av en fri modul . Den är uppkallad efter den irländska matematikern Henry John Stephen Smith .

Definition

Låt A vara en icke-noll m × n matris över en principiell idealdomän R . Det finns inverterbara $m\times m$ och $n\times n$ -matriser S, T (med koefficienter i R ) så att produkten SAT är

${\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}}.$

och de diagonala elementen $\alpha _{i}$ uppfyller $\alpha _{i}\mid \alpha _{i+1}$ för alla $1\leq i<r$ . Detta är Smiths normala form av matrisen A . Elementen $\alpha _{i}$ är unika upp till multiplikation med en enhet och kallas elementära divisorer , invarianter eller invarianta faktorer . De kan beräknas (upp till multiplikation med en enhet) som

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

där $d_{i}(A)$ (kallad i -th determinant divisor ) är lika med den största gemensamma divisorn av determinanterna av alla $i\times i$ moll i matrisen A och $d_{0}(A):=1$ .

Algoritm

Det första målet är att hitta inverterbara kvadratiska matriser $S$ och $T$ så att produkten $SAT$ är diagonal. Detta är den svåraste delen av algoritmen. När diagonalitet väl har uppnåtts blir det relativt lätt att sätta matrisen i Smith normal form. Mer abstrakt formulerat är målet att visa att om man tänker på $A$ som en karta från $R^{n}$ (den fria $R$ - modul av rang ${\ displaystyle n}$ ) till $R^{m}$ (den fria $R$ - modulen av rang $m$ ), det finns isomorfismer $S:R^{m}\to R^{m}$ och $T:R^{n}\to R^{n}$ så att ${\ displaystyle S\cdot A\cdot T}$ har den enkla formen av en diagonal matris . Matriserna $S$ och $T$ kan hittas genom att börja med identitetsmatriser av lämplig storlek och ändra $S$ varje gång en radoperation utförs på $A$ i algoritmen av motsvarande kolumnoperation (till exempel om rad $i$ läggs till rad $j$ i ${\displaystyle A} , då$ ska kolumn ${\displaystyle j} subtraheras$ från kolumn $i$ av $S$ för att behålla produktens invariant), och på liknande sätt modifiera $T$ för varje kolumnoperation som utförs. Eftersom radoperationer är vänstermultiplikationer och kolumnoperationer är högermultiplikationer, bevarar detta invarianten $A'=S'\cdot A\cdot T'$ där $A',S',T'$ betecknar aktuella värden och $A$ betecknar den ursprungliga matrisen; så småningom blir matriserna i denna invariant diagonala. Endast inverterbara rad- och kolumnoperationer utförs, vilket säkerställer att $S$ och $T$ förblir inverterbara matriser.

För $a\in R\setminus \{0\}$ , skriv $\delta (a)$ för antalet primtalsfaktorer för $a$ (dessa finns och är unika eftersom alla PID också är en unik faktoriseringsdomän ). Speciellt $R$ också en Bézout-domän , så det är en gcd-domän och gcd för alla två element uppfyller en Bézouts identitet .

För att sätta en matris i Smiths normalform kan man upprepade gånger tillämpa följande, där $t$ går från 1 till $m$ .

Steg I: Välja en pivot

Välj $j_{t}$ för att vara det minsta kolumnindexet för $A$ med en post som inte är noll, starta sökningen på kolumnindex $j_{t- 1}+1$ om $t>1$ .

Vi vill ha $a_{t,j_{t}}\neq 0$ ; om så är fallet är detta steg komplett, annars finns det enligt antagandet några $k$ med $a_{k,j_{t}}\neq 0$ , och vi kan byta raderna $t$ och $k$ , och erhåller därmed $a_{t,j_{t}}\neq 0$ .

Vår valda pivot är nu i position $(t,j_{t})$ .

Steg II: Förbättra pivoten

Om det finns en post vid position ( k , j _t ) så att $a_{t,j_{t}}\nmid a_{k,j_{t}}$ , sedan låter $\beta =\gcd \left(a_{t,j_{t}},a_{k,j_{t}} \right)$ , vi vet genom Bézout-egenskapen att det finns σ, τ i R så att

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

Genom vänstermultiplikation med en lämplig inverterbar matris L kan det uppnås att raden t i matrisprodukten är summan av σ gånger den ursprungliga raden t och τ gånger den ursprungliga raden k , den raden k i produkten är en annan linjär kombination av dessa ursprungliga rader och att alla andra rader är oförändrade. Explicit, om σ och τ uppfyller ovanstående ekvation, då för $\alpha =a_{t,j_{t}}/\beta$ och $\gamma =a_{k,j_{t}}/\beta$ (vilka divisioner är möjliga enligt definitionen av β) har man

$\sigma \cdot \alpha +\tau \cdot \gamma =1,$

så att matrisen

$L_{0}={\begin{pmatrix}\sigma &\tau \\-\gamma &\alpha \\\end{pmatrix}}$

är inverterbar, med invers

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

Nu kan L erhållas genom att anpassa $L_{0}$ i rader och kolumner t och k i identitetsmatrisen. Genom konstruktion har matrisen som erhålls efter vänstermultiplicering med L ingången β vid position ( t , j t ₎ (och på grund av vårt val av α och γ har den också en ingång 0 vid position ( k , j _t ), vilket är användbart men inte nödvändigt för algoritmen). Denna nya post β delar posten $a_{t,j_{t}}$ som fanns där tidigare, och så i synnerhet $\delta (\beta )<\delta (a_{t,j_{t}})$ ; därför måste upprepandet av dessa steg så småningom avslutas. Man slutar med en matris som har en post vid position ( t , j _t ) som delar upp alla poster i kolumn j _t .

Steg III: Eliminera poster

_genom att lägga till lämpliga multiplar av rad _t , kan det uppnås att alla poster i kolumn jt förutom den vid position ( t , jt ) är noll. Detta kan uppnås genom vänstermultiplikation med en lämplig matris. _{göra matrisen helt diagonal måste vi} också eliminera poster som inte är noll på positionsraden ( t , jt ). Detta kan uppnås genom att upprepa stegen i steg II för kolumner istället för rader och använda multiplikation till höger genom att transponera den erhållna matrisen L . I allmänhet kommer detta att resultera i att nollposterna från den tidigare tillämpningen av steg III blir olik noll igen.

Observera dock att varje tillämpning av steg II för antingen rader eller kolumner måste fortsätta att minska värdet på ${\displaystyle \delta (a_{t,j_{t}})} ,$ och så processen måste så småningom stoppa efter ett antal iterationer, vilket _leder till en matris där posten vid position ( t , jt ) är den enda posten som inte är noll i både dess rad och kolumn.

behöver bara blocket av A längst ned till höger om ( t , j _{t ) diagonaliseras, och konceptuellt kan algoritmen tillämpas rekursivt och behandla detta block som en separat matris.} Med andra ord kan vi öka t med ett och gå tillbaka till steg I.

Sista steget

Genom att tillämpa stegen som beskrivs ovan på de återstående kolumnerna som inte är noll i den resulterande matrisen (om någon), får vi en $m\times n$ -matris med kolumnindex $j_{1}<\ldots <j_{r}$ där $r\leq \min(m,n)$ . Matrisposterna $(l,j_{l})$ är icke-noll, och varannan post är noll.

Nu kan vi flytta nollkolumnerna i denna matris till höger, så att posterna som inte är noll är på positioner $(i,i)$ för $1\leq i\ leq r$ . Kort sagt, ställ in $\alpha _{i}$ för elementet i position ( $\displaystyle (i,i)}$ .

Villkoret för delbarhet för diagonala poster kanske inte är uppfyllt. För alla index $i<r$ för vilka ${\displaystyle \alpha _{i}\nmid \alpha _{i+1}},$ kan man reparera denna brist genom operationer endast på rader och kolumner $i$ och $i+1$ : lägg först till kolumn $i+1$ till kolumn $i$ för att få en post $\alpha _{i+1}$ i kolumn i utan att störa inmatningen $\alpha _{i}$ vid position $(i,i)$ , och använd sedan en radoperation för att göra inmatningen vid position $(i,i)$ lika med $\beta =\gcd(\ alfa _{i},\alpha _{i+1})$ som i steg II; fortsätt slutligen som i steg III för att göra matrisen diagonal igen. Eftersom den nya posten vid position $(i+1,i+1)$ är en linjär kombination av den ursprungliga $\alpha _{i },\alpha _{i+1}$ , den är delbar med β.

Värdet $\delta (\alpha _{1})+\cdots +\delta (\alpha _{r})$ ändras inte av ovanstående operation (det är δ för determinanten för den övre $r\times r$ submatrisen), varav den operationen minskar (genom att flytta primtalsfaktorer åt höger) värdet på

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

Så efter ändligt många tillämpningar av denna operation är ingen ytterligare tillämpning möjlig, vilket betyder att vi har erhållit $\alpha _{1}\mid \alpha _{2}\mid \ cdots \mid \alpha _{r}$ efter önskemål.

Eftersom alla rad- och kolumnmanipulationer som är involverade i processen är inverterbara, visar detta att det finns inverterbara $m\times m$ och $n\times n$ -matriser S, T så att produkt SAT uppfyller definitionen av en Smith normal form. Detta visar i synnerhet att Smiths normalform existerar, vilket antogs utan bevis i definitionen.

Ansökningar

Smiths normala form är användbar för att beräkna homologin för ett kedjekomplex när kedjemodulerna i kedjekomplexet genereras ändligt . Till exempel, i topologi , kan den användas för att beräkna homologin för ett ändligt förenklat komplex eller CW-komplex över heltal, eftersom gränskartorna i ett sådant komplex bara är heltalsmatriser. Den kan också användas för att bestämma de invarianta faktorerna som förekommer i struktursatsen för ändligt genererade moduler över en principiell idealdomän, som inkluderar grundsatsen för ändligt genererade abelska grupper .

Smiths normalform används också i styrteori för att beräkna överförings- och blockeringsnollor i en överföringsfunktionsmatris .

Exempel

Som ett exempel hittar vi Smith-normalformen av följande matris över heltalen.

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

Följande matriser är de mellanliggande stegen när algoritmen tillämpas på matrisen ovan.

${\displaystyle \to {\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}}} → ( 2 2$

$to {\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}}}$

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

Så är Smiths normala form

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

och de invarianta faktorerna är 2, 2 och 156.

Likhet

Smith normalform kan användas för att avgöra om matriser med poster över ett gemensamt fält är lika eller inte . Specifikt två matriser A och B är lika om och endast om de karakteristiska matriserna $xI-A$ och $xI-B$ har samma Smith-normalform.

Till exempel med

${\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)={\begin{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}}.\ end{aligned}}$

A och B är lika eftersom Smiths normala form av deras karakteristiska matriser matchar, men liknar inte C eftersom Smiths normala form av de karakteristiska matriserna inte matchar.

Se även

• Kanonisk form
• Diofantisk ekvation
• Elementära divisorer
• Frobenius normalform (även kallad Rational canonical form)
• Hermit normal form
• Invariant faktor
• Struktursats för ändligt genererade moduler över en principiell idealdomän
• Singulärvärdesfaktorisering

Anteckningar

•    Smith, Henry J. Stephen (1861). "På system av linjära obestämda ekvationer och kongruenser". Phil. Trans. R. Soc. Lond. 151 (1): 293–326. doi : 10.1098/rstl.1861.0016 . JSTOR 108738 . S2CID 110730515 . Omtryckt (s. 367–409 ) i The Collected Mathematical Papers of Henry John Stephen Smith, Vol. I , redigerad av JWL Glaisher . Oxford: Clarendon Press (1894), xcv +603 s.
• Smith normal form på PlanetMath .
• Exempel på Smith normal form på PlanetMath .
• KR Matthews, Smith normal form . MP274: Linjär algebra, föreläsningsanteckningar, University of Queensland, 1991.

externa länkar

• Ett animerat exempel på beräkning av Smiths normalform .