...

La forma normale di Smith di una matrice

by user

on
Category: Documents
7

views

Report

Comments

Transcript

La forma normale di Smith di una matrice
La forma normale di Smith di una matrice
Sia A un anello commutativo con unità e sia Ms,t (A) l’anello delle matrici con s righe
e t colonne con elementi in A.
Def. 1 Siano H, K ∈ Ms,t (A). H si dice equivalente a K se esistono due matrici
invertibili M e N (di ordini opportuni) tali che H = M KN .
In questo modo viene introdotta nell’anello di matrici una relazione di equivalenza.
La forma normale di Smith di H è una sorta di rappresentante canonico della classe
di equivalenza a cui H appartiene.
Indichiamo con diag (d1 , . . . , dn ) la matrice che ha gli elementi d1 , . . . , dn nei posti
(1, 1), (2, 2), . . . , (n, n) dove n = min(s, t), e ha zero in tutti gli altri posti.
Teor. 2 Se l’anello A è un PID, allora ogni matrice non nulla M ∈ Ms,t (A) è equivalente a una matrice diag (d1 , . . . , dn ) tale che
d1 | d2 | d3 | . . . | dn .
Una matrice siffatta è detta forma normale di Smith di M .
Dim. 1◦ : sia A dominio euclideo rispetto a una funzione ϕ.
Useremo due operazioni elementari sulle righe e sulle colonne di M :
1) scambiare due righe o due colonne,
2) sommare a una riga (colonna) un’altra riga (colonna) moltiplicata per r ∈ A.
Entrambe le operazioni si effettuano moltiplicando M a sinistra (o destra) per matrici
invertibili, cosı̀ che M viene trasformata in una matrice equivalente.
Cerchiamo di trasformare M in una matrice equivalente C ∈ Ms,t (A) del tipo

d1
 0
C=
 ...
0
...
0
C∗




(∗ )
0
dove d1 divide ogni elemento di C∗ ∈ Ms−1,t−1 (A).
Descriviamo una sequenza finita di operazioni elementari che, applicata alla M , o
porta alla (∗ ) o porta a una matrice B ∈ Ms,t (A) tale che
ϕ(b11 ) < ϕ(m11 ).
(∗∗ )
Nel caso (∗∗ ) riapplichiamo la sequenza ottenendo (∗ ) o ancora (∗∗ ). Dopo un
numero finito di applicazioni otterremo (∗ ) perché in caso contrario esisterebbe una
sequenza infinita . . . < ϕ(k11 ) < . . . < ϕ(b11 ) < ϕ(m11 ) contro il fatto che ϕ è una
funzione a valori interi inferiormente limitata.
Posso supporre che sia m11 6= 0, in caso contrario con uno scambio di righe e di
colonne porto un elemento non nullo di M (che esiste perché M 6= [0]) nel posto
(1, 1).
1◦ caso. Esiste un elemento m1j della prima riga di M non divisibile per m11 . Essendo A un dominio euclideo risulta
m1j = qm11 + r con ϕ(r) < ϕ(m11 ).
Allora si sottrae alla j-esima colonna la prima moltiplicata per q per poi scambiarle
tra loro. In tal modo il nuovo m11 è r e siamo nel caso (∗∗ ).
2◦ caso. Esiste un elemento mi1 della prima colonna di M non divisibile per m11 . Si
lavora come nel 1◦ caso agendo sulle righe invece che sulle colonne.
3◦ caso. m11 divide ogni elemento della prima riga e della prima colonna. Allora
sottraendo opportuni multipli della prima riga alle altre e opportuni multipli della
prima colonna alle altre si ottiene una matrice del tipo

m11
 0
D=
 ...
0
...
D∗
0


.

0
Se m11 divide ogni elemento di D∗ ∈ Ms−1,t−1 (A), abbiamo raggiunto il caso (∗ ).
Altrimenti esiste dij ∈ D∗ non divisibile per m11 ; in tal caso sommo la riga i-esima
alla prima e ricomincio da capo col 1◦ caso.
Ogni passaggio fa sı̀ che il valore di ϕ sul primo elemento della matrice diminuisca,
quindi dopo un numero finito di passi il procedimento porta alla matrice C.
Ora si applica il medesimo algoritmo su C∗ e cosı̀ via fino ad ottenere una matrice
in cui aij = 0 se i 6= j.
Si noti che le operazioni elementari su C∗ corrispondono ad operazioni elementari
su C che non alterano la prima riga e la prima colonna, e inoltre danno una nuova
matrice i cui elementi sono combinazione lineare dei vecchi. Quindi tutti i nuovi
elementi saranno ancora divisibili per d1 . Perciò la matrice finale diag (d1 , d2 , . . . , dn )
avrà la proprietà d1 | d2 | . . . | dn , come richiesto.
2◦ : sia A un PID non euclideo.
Il procedimento è analogo al precedente, ma occorre trovare una funzione che giochi
il ruolo della ϕ.
Essendo A un PID, è anche un UFD, quindi ogni r ∈ A∗ = A − {0} ha una sola
espressione del tipo:
r = up1 p2 . . . pn con n ≥ 0
dove u è unitario e i pi sono primi in A (in tutto o in parte coincidenti). L’intero n
è univocamente individuato da r, quindi è ben definita una funzione
λ : A∗ → N data da λ(r) = n.
(A volte λ è chiamata lunghezza di r.)
Ovviamente si ha λ(r) ≥ 0 per ogni r ∈ A∗ e λ(r) = 0 se e solo se r è invertibile.
Inoltre si ha
λ(rr0 ) = λ(r) + λ(r0 ) per ogni r, r0 ∈ A.
Trasformiamo M in una matrice equivalente C ∈ Ms,t (A) del tipo

d1
 0
C=
 ...
0
...
0
C∗


,

(∗ )
0
dove d1 divide ogni elemento di C∗ ∈ Ms−1,t−1 (A), passando attraverso matrici
B ∈ Ms,t (A) tali che
λ(b11 ) < λ(m11 ).
(∗∗ )
Rispetto alla dimostrazione precedente basta modificare il 1◦ e il 2◦ caso.
1◦ caso. Sia m11 6= 0 e m1j non divisibile per m11 per un j ∈ (1, 2, . . . t]. Pongo per
comodità j = 2.
Sia d = M CD(m11 , m12 ), da cui
m11 = dy1 e m12 = dy2
dove y1 non è unitario, altrimenti m11 | m12 . Perciò λ(y1 ) ≥ 1, da cui
λ(m11 ) = λ(dy1 ) = λ(d) + λ(y1 ) > λ(d).
Per l’identità di Bézout si ha
d = x1 m11 + x2 m12
con x1 , x2 ∈ A
da cui
d = x1 dy1 + x2 dy2 = d(x1 y1 + x2 y2 ).
Essendo A un dominio ciò implica che x1 y1 + x2 y2 = 1, per cui, indicata con It−2
la matrice identica di ordine t − 2, la matrice


x1 −y2 0 . . . 0
 x2 y1 0 . . . 0 


 ∈ Mt,t (A)
0
0
S=
 .

.
 ..

..
It−2
0
0
è invertibile in A in quanto det S = 1.
Ne segue che la matrice M S è equivalente a M e presenta d nel posto (1,1). Quindi
M S cade nel caso (∗ ) o nel caso (∗∗ ).
2◦ caso. Sia m11 6= 0 e mj1 non divisibile per m11 per un j ∈ (1, 2, . . . s]. Posto per
comodità j = 2, si procede come nel 1◦ caso ottenendo una matrice invertibile


x1 x2 0 . . . 0
 −y2 y1 0 . . . 0 


 ∈ Ms,s (A).
0
0
T =
 .

.
 ..

..
Is−2
0
0
Ne segue che T M è equivalente a M e ha d nel posto (1,1).
3◦ caso. È del tutto analogo alla dimostrazione fatta per A euclideo. Si raggiunge
una matrice del tipo D e si conclude la dimostrazione come nel caso euclideo.
ESEMPIO 1. Troviamo la forma
 normale
−4 −6

M= 2
2
6
6
di Smith
della matrice

7
4  ∈ M3,3 (Z).
15
Conviene iniziare portando nel posto (1,1) l’elemento della prima riga o colonna
avente valore assolutominimo.  

0 1 0
−4 −6 7
1 0 0 2
2
4 
0 0 1
6
6 15




1 −1 −2
2
2
4
1 0 0
 2 1 0   −4 −6 7   0 1
0 
0 0
1
6
6 15
−3 0 1



2 0
0
1 0 1
 0 1 0   0 −2 15 
0 0
3
0 0 1



1 0 −1
2 0
3
 0 −2 15   0 1 0 
0 0
3
0 0 1



0 0 1
2 0
1
 0 −2 15   0 1 0 
1 0 0
0 0
3




1
0 0
1
0 2
1 0 −2
 −15 1 0   15 −2 0   0 1 0 
−3 0 1
3
0 0
0 0 1



1 0
0
1 0
0
 0 −2 −30   0 1 −15 
0 0
−6
0 0
1



1 0
0
1 0
0
 0 −2 0   0 −1 0 
0 0 −6
0 0 −1


1 0 0
 0 2 0  = M0
0 0 6
NOTE. 1) La moltiplicazione indicata nella terza riga si rende necessaria perché m11
non divide m33 .
2) Il cambio di segni indicato nella penultima riga non è contenuto nel teor. 2, però
è consuetudine (e sempre possibile in Z) considerare i numeri di positivi.
3) Può essere necessario calcolare le matrici che producono l’equivalenza tra M e M 0 .
In tal caso, chiamate S1 , . . . S4 le matrici che dall’alto in basso operano sulle righe e
D1 , . . . D6 le matrici che operano dall’alto in basso sulle colonne, si ha


0 −2
1
X = S4 · S3 · S2 · S1 =  1 32 −15 ,
0 3
−2

e
−3

Y = D1 · D2 · D3 · D4 · D5 · D6 =
0
1
1
−1
0

−22
15 
2
XM Y = M 0 .
4) Come si vede i conti possono essere complicati. Un controllo (non decisivo) di
esattezza per le matrici ad elementi interi si ha osservando che deve essere det M 0 =
± det M (perché?).
5) Se un elemento della matrice M è uguale a ±1, conviene, come prima operazione,
portarlo nel posto (1,1).
ESEMPIO 2. Troviamo la 
forma normale di Smith
della matrice

x
0
0
M = 0 1−x
0  ∈ M3,3 (IR[x]).
0
0
1 − x2






1
x
0
x 1−x
0
x
1
0
0 
0  −→  1 − x 0
M −→  0 1 − x
0  −→  0 1 − x
2
2
0 1 − x2 
0
1−x 
0
0
1−x 
0
0

1
0
0
1
0
0
1
0
0
0  −→  0 x2 − x 1 − x2 
0  −→  0 x2 − x
→  1 − x x2 − x
2
2
2
0
1−x
0
1−x
0
1−x


 0

 0
 0
1
0
0
1
0
0
1
0
0
0 
−→  0 x2 − x 1 − x  −→  0 1 − x x2 − x  −→  0 1 − x
2
2
2
0 1 − x x − x3
0 
0
1 − x
 0 1−x
0
1
0
0
1
0
0



−→ 0 x − 1
0  = M0
−→ 0 1 − x
0
0
0
x3 − x
0
0
x − x3
L’ultimo passaggio è motivato dal fatto che in K[x] gli elementi di sono polinomi che
si usa prendere sempre monici.
Fly UP