Forma normal de Smith

En matemàtiques, la forma normal de Smith és una forma normal que es pot definir per a qualsevol matriu (no necessàriament quadrada) a entrades en un domini d'ideals principals (DIP). La forma normal de Smith d'una matriu és diagonal, i es pot obtenir a partir de la matriu original mitjançant multiplicació a l'esquerra i a la dreta per matrius quadrades invertibles. En particular, el conjunt dels enters formen un DIP, de tal forma que sempre es pot calcular la forma normal de Smith d'una matriu a entrades enteres. La forma normal de Smith és útil per treballar amb mòduls finitament generats sobre un DIP, i en particular per trobar l'estructura d'un quocient d'un mòdul lliure. Rep el seu nom en honor del matemàtic britànic Henry John Stephen Smith (1826-1883).

Definició

Sigui A una matriu m×n no nul·la sobre un domini d'ideals principals R. Llavors existeixen matrius invertibles S (de mida $m\times m$) i T (de mida $n\times n$) tals que el producte S A T és

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

i els elements de la diagonal $\alpha _{i}$ satisfan $\alpha _{i}\mid \alpha _{i+1}\;\forall \;1\leq i<r$. Aquesta és la forma normal de Smith de la matriu A. Els elements $\alpha _{i}$ són únics llevat de multiplicació per una unitat, i s'anomenen divisors elementals, invariants o factors invariants. Es poden calcular (llevat de multiplicació per una unitat) com

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

on $d_{i}(A)$ (anomenat l'i-sim divisor determinant) és igual al màxim comú divisor de tots els menors $i\times i$ de la matriu A.

Algorisme

El primer objectiu és trobar dues matrius quadrades invertibles S i T tals que el producte S A T sigui diagonal. Aquesta és la part més difícil de l'algorisme; un cop ho hàgim aconseguit, és relativament fàcil trobar la forma normal de Smith de la matiru original. Més formalment, l'objectiu és demostrar que, si pensem que A és una aplicació de $R^{n}$ (el R-mòdul lliure de rang n) a $R^{m}$ (el R-mòdul lliure de rang m), llavors existeixen isomorfismes $S:R^{m}\to R^{m}$ i $T:R^{n}\to R^{n}$ tals que $S\cdot A\cdot T$ té forma de matriu diagonal. Hom pot trobar les matrius S i T començant per matrius identitat de la mida apropiada, i modificant les files de S cada cop que s'efectua una operació sobre les files de A, i de manera semblant a T per les operacions sobre columnes. Com que les operacions sobre files són multiplicacions per l'esquerra, i les operacions sobre columnes són multiplicacions per la dreta, això preserva l'invariant $A'=S'\cdot A\cdot T'$, on $A',S',T'$ denota els valors actuals, i A denota la matriu original; en un moment donat, les matrius d'aquest invariant esdevenen diagonals. Com que només es realitzen operacions invertibles sobre files i columnes, això ens assegura que les matrius S i T són invertibles durant tot el procés.

Donat a en R \ {0}, escrivim δ(a) el nombre de factors primers de a (que existeixen i són únics perquè un DIP és també un domini de factorització única). En particular, R és també un domini de Bézout, i el màxim comú divisor de dos elements qualssevol satisfà la identitat de Bézout.

Per transformar una matriu en la seva forma normal de Smith, hom pot aplicar els següents passos de forma iterativa, on t va des de 1 fins a m.

Pas 1: Escollir un pivot

Escollim j_t el més petit índex columna de A amb una entrada no-nul·la, començant a comptar des de l'índex columna j_t-1+1 si t > 1.

Volem que $a_{t,j_{t}}\neq 0$; si ja és així, aquest pas està complet. Altrament, per hipòtesi existeix algun k tal que $a_{k,j_{t}}\neq 0$, i podem intercanviar les files $t$ i $k$, d'on obtenim $a_{t,j_{t}}\neq 0$.

El pivot que hem escollit està a la posició (t, j_t).

Pas 2: Millorar el pivot

Si existeix una entrada a la posició (k,j_t) tal que $a_{t,j_{t}}\nmid a_{k,j_{t}}$, llavors, posant $\beta =\mathrm {mcd} \left(a_{t,j_{t}},a_{k,j_{t}}\right)$, sabem que per la propietat de Bézout existeixen σ, τ de R tals que

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

Multiplicant per l'esquerra amb una matriu invertible L adient, podem aconseguir que la fila t del producte de matrius sigui la suma de σ cops la fila original t i τ cops la fila original k. És a dir, aquesta fila k del producte és combinació lineal de les files originals, i totes les altres files romanen sense canvis. Més explícitament, si σ i τ satisfan l'equació anterior, llavors per $\alpha =a_{t,j_{t}}/\beta$ i $\gamma =a_{k,j_{t}}/\beta$ (aquestes divisions són possibles per la definició de β) tenim:

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

de tal manera que la matriu

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

és invertible, i la seva inversa és

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

Ara, podem obtenir L col·locant $L_{0}$ en les files t i k de la matriu identitat. Per construcció, la matriu obtinguda després de multiplicar per l'esquerra per L té l'entrada β a la posició (t,j_t) (i pel fet d'haver escollit α i γ de la manera anterior, també té una entrada 0 a la posició (k,j_t), la qual cosa és útil però no essencial per l'algorisme). Aquesta nova entrada β divideix l'entrada $a_{t,j_{t}}$ que apareixia abans, i per tant en particular $\delta (\beta )<\delta (a_{t,j_{t}})$; així doncs, si repetim aquests passos acabarem en algun moment. Hom finalitza amb una matriu que té una entrada en la posició (t,j_t) que divideix totes les entrades de la columna j_t.

Pas 3: Eliminar entrades

Finalment, afeegint múltiples adients de la fila t, podem aconseguir que totes les entrades de la columna j_t siguin zero, llevat de la posició (t,j_t). Això es pot aconseguir multiplicant per l'esquerra per una matriu adient. Tot i això, per fer que la matriu resultant sigui completament diagonal, també hem d'eliminar les entrades no-nul·les en la fila de la posició (t,j_t). Això ho podem aconseguir tot repetint el procediment de Pas 2 per columnes en lloc de per files, i usant la multiplicació per la dreta. En general, això causa que les entrades a 0 de l'aplicació del pas 3 esdevinguin de nou no-nul·les.

Tot i això, notem que l'ideal generat pels elements de la posició (t,j_t) formen una cadena ascendent, perquè les entrades d'un pas posterior sempre divideixen les entrades d'un pas anterior. Per tant, com que R és un anell noetherià (ja que és un DIP), arribarà un punt en què els ideals de la cadena esdevindran estacionaris i no canviaran. Això significa que, en algun moment després d'haver aplicat el Pas 2, l'entrada de la posició (t,j_t) dividirà totes les entrades no-nul·les de la fila i de la columna, abans d'avançar en el Pas 2. Per tant, podem eliminar les entrades de la fila o de la columna amb valors no-nuls, mentre es preserven els zeros en la fila o columna que ja és 0. En aquest punt, només cal diagonalitzar el bloc de A a sota i a la dreta de la posició (t,j_t), i conceptualment hom pot aplicar l'algorisme de forma recursiva, perquè hom pot tractar aquest bloc com una matriu separada. En altres paraules, podem incrementar t en 1, i tornar al Pas 1.

Pas final

Un cop hem aplicat els passos anteriors a les columnes no-nul·les restants de la matriu resultant (si n'hi ha), obtenim una matriu $m\times n$ amb índexs columna $j_{1}<\ldots <j_{r}$, on $r\leq \min(m,n)$. Les entrades $(l,j_{l})$ són no-nul·les, i la resta són 0.

Ara podem moure les columnes 0 d'aquesta matriu a la dreta, de tal forma que les entrades no-nul·les estiguin en les posicions $(i,i)$ per $1\leq i\leq r$. Per simplicitat, diem $\alpha _{i}$ a l'element de la posició $(i,i)$.

Pot succeir que no se satisface la condició de divisibilitat de les entrades de la diagonal. Per a qualsevol índex $i<r$ tal que $\alpha _{i}\nmid \alpha _{i+1}$, podem esmenar-ho mitjançant únicament operacions sobre files i columnes $i$ i $i+1$: primer afegim la columna $i+1$ a la columna $i$ per obtenir una entrada $\alpha _{i+1}$ a la columna i sense perturbar l'entrada $\alpha _{i}$ de la posició $(i,i)$, i després apliquem una operació fila per fer que l'entrada de la posició $(i,i)$ sigui igual a $\beta =\mathrm {mcd} (\alpha _{i},\alpha _{i+1})$ com en el Pas 2; finalment, procedim con en el Pas 3 per obtenir de nou una matriu diagonal. Com que la nova entrada de la posició $(i+1,i+1)$ és una combinació lineal de l'original $\alpha _{i},\alpha _{i+1}$, és divisible per β.

El valor $\delta (\alpha _{1})+\cdots +\delta (\alpha _{r})$ no canvia per l'operació anterior (és el δ del determinant de la submatriu superior $r\times r$), on aquesta operació disminueix (movent factors primers a la dreta) el valor de

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

Per tant, després d'un nombre finit d'aplicacions d'aquesta operació, no es pot aplicar més cops, la qual cosa significa que hem obtingut $\alpha _{1}\mid \alpha _{2}\mid \cdots \mid \alpha _{r}$, com volíem.

Com que totes les manipulacions sobre files i columnes d'aquest procés són invertibles, això ens diu que existeixen matrius S i T $m\times m$ i $n\times n$ invertibles, tals que el producte S A T satisfà la definició de forma normal de Smith. En particular, això demostra que la forma normal de Smith existeix, cosa que s'havia suposat sense demostrar en la definició.

Aplicacions

La forma normal de Smith és útil per calcular l'homologia d'un complex de cadenes quan els mòduls de la cadena són mòduls finitament generats. Per exemple, en topologia, es pot usar per calcular l'homologia d'un complex simplicial o CW-complex sobre els enters, perquè les aplicacions que envien la frontera en aquest complex són simplement matrius enteres. També es pot utilitzar per demostrar el teorema d'estructura dels mòduls finitament generats sobre un domini d'ideals principals.

Exemple

A títol d'exemple, trobem la forma normal de Smith de la següent matriu sobre els enters:

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

Les següents matrius són els passos intermedis de l'algorisme que hem vist abans:

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

$\to {\begin{pmatrix}2&0&0\\0&18&24\\0&-6&-12\end{pmatrix}}\to {\begin{pmatrix}2&0&0\\0&6&12\\0&18&24\end{pmatrix}}$

$\to {\begin{pmatrix}2&0&0\\0&6&12\\0&0&-12\end{pmatrix}}\to {\begin{pmatrix}2&0&0\\0&6&0\\0&0&12\end{pmatrix}}$

Així, la forma normal de Smith és:

${\begin{pmatrix}2&0&0\\0&6&0\\0&0&12\end{pmatrix}}$

i els divisors elementals són 2, 6 i 12.

Semblança

La forma normal de Smith es pot utilitzar per determinar si dues matrius a entrades en un cos comú són semblants. En concret, dues matrius A i B són semblants si i només si les respectives matrius característiques $xI-A$ i $xI-B$ tenen la mateixa forma normal de Smith.

Per exemple, si tenim:

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

llavors A i B són semblants, perquè les formes normals de Smith de les seves respectives matrius característiques coincideixen, però no són semblants a C, perquè la forma normal de Smith de la matriu característica de C és diferent de les de A i B.

Bibliografia

• Smith, Henry J. Stephen «On Systems of Linear Indeterminate Equations and Congruences». Philosophical Transactions of the Royal Society of London, 151, 1, 01-01-1861, pàg. 293–326. DOI: 10.1098/rstl.1861.0016 [Consulta: 7 desembre 2013]. Reimpressió (pp. 367–409) a The Collected Mathematical Papers of Henry John Stephen Smith, Vol. I, editat per J. W. L. Glaisher. Oxford: Clarendon Press (1894), xcv+603 pp.
• Matthews, Keith R. «Smith normal form». Number Theory Web - MP274 Lecture Notes 1991. University of Queensland, 1991. [Consulta: 7 desembre 2013].

Vegeu també

• Forma canònica
• Divisor elemental
• Forma normal de Frobenius
• Forma normal d'Hermite
• Factor invariant
• Henry John Stephen Smith (1826–1883), epònim de la forma normal de Smith
• Teorema d'estructura dels mòduls finitament generats sobre un domini d'ideals principals

Enllaços externs

• Forma normal de Smith a PlanetMath
• Exemple de forma normal de Smith a PlanetMath