Aplicaciones de la Forma Normal de Smith de una Matriz Entera · 2012-10-29 · una matriz...
Transcript of Aplicaciones de la Forma Normal de Smith de una Matriz Entera · 2012-10-29 · una matriz...
Forma normal de Smith Factores invariantes Sistemas de ecuaciones lineales diofanticas Grupos abelianos finitamente generados Grado de anillos afınes Grado de ideales binomiales asociados a lattices
Aplicaciones de la Forma Normal de Smith deuna Matriz Entera
Rafael Heraclio Villarreal Rodrıguez
Departmento de MatematicasCINVESTAV-IPN, Mexico D.F.
XLV Congreso Nacional Sociedad Matematica MexicanaUniversidad Autonoma de Queretaro
28 de octubre al 2 de noviembre de 2012
Forma normal de Smith Factores invariantes Sistemas de ecuaciones lineales diofanticas Grupos abelianos finitamente generados Grado de anillos afınes Grado de ideales binomiales asociados a lattices
Bosquejo
1 Forma normal de Smith
2 Factores invariantes
3 Sistemas de ecuaciones lineales diofanticas
4 Grupos abelianos finitamente generados
5 Grado de anillos afınes
6 Grado de ideales binomiales asociados a lattices
Forma normal de Smith Factores invariantes Sistemas de ecuaciones lineales diofanticas Grupos abelianos finitamente generados Grado de anillos afınes Grado de ideales binomiales asociados a lattices
Sea A una matriz no-cero de orden m × n con entradas en Z ysea r el rango de A. Esta matriz se escribe como:
A = (aij) =
a11 · · · a1n...
......
am1 · · · amn
Operaciones Elementales(I) Permutar filas (columnas).
(II) Multiplicar una fila (columna) por −1.(III) Multiplicar una fila (columna) por un entero y sumar a otra
fila (columna).
Forma normal de Smith Factores invariantes Sistemas de ecuaciones lineales diofanticas Grupos abelianos finitamente generados Grado de anillos afınes Grado de ideales binomiales asociados a lattices
Teorema (Forma normal de Smith)Usando operaciones elementales la matriz A se puede reducira una matriz diagonal:
D =
d1 0 0 · · · 0 0 · · · 00 d2 0 · · · 0 0 · · · 0...
......
......
......
...0 0 0 · · · dr 0 · · · 00 0 0 · · · 0 0 · · · 0...
......
......
... · · ·...
0 0 0 · · · 0 0 · · · 0
= diag{d1, . . . ,dr ,0, . . . ,0},
donde di > 0 y di divide a di+1 para toda i.
La matriz D es la forma normal de Smith de A y d1, . . . ,drson los factores invariantes de A.
Forma normal de Smith Factores invariantes Sistemas de ecuaciones lineales diofanticas Grupos abelianos finitamente generados Grado de anillos afınes Grado de ideales binomiales asociados a lattices
DemostracionSea δ(A) = min{|aij | : aij 6= 0, 1 ≤ i ≤ m, 1 ≤ j ≤ n}.
(1) Podemos suponer que a11 = δ(A).(2) Si a1k 6= 0 para algun k > 1, por algoritmo de la division
a1k = bka11 + b1k , donde 0 ≤ |b1k | < a11.(3) Multiplicando la primera columna de A por −bk y
sumandola a la columna k obtenemos:
B =
a11 · · · −bka11 + a1k = b1k · · · a1n...
......
......
am1 · · · −bkam1 + amk = bmk · · · amn
una matriz equivalente B = (bij) donde b1k = 0 o bienb1k 6= 0 y δ(B) ≤ |b1k | < a11 = δ(A). Si b1k = 0, repetimoseste paso con otro elemento no-cero de la primera fila. Sib1k 6= 0, regresamos al paso (1) con la matriz B.
Forma normal de Smith Factores invariantes Sistemas de ecuaciones lineales diofanticas Grupos abelianos finitamente generados Grado de anillos afınes Grado de ideales binomiales asociados a lattices
(4) Repitiendo este proceso tantas veces como sea necesarioy usando un proceso similar sobre la primera columnaobtenemos una matriz equivalente:
C =
c11 0 · · · 00 c22 · · · c2n...
......
0 cm2 · · · cmn
Forma normal de Smith Factores invariantes Sistemas de ecuaciones lineales diofanticas Grupos abelianos finitamente generados Grado de anillos afınes Grado de ideales binomiales asociados a lattices
(5) Si c11 no divide a algun cij , sumando la fila i a la fila 1obtenemos
C′ =
c11 ci2 · · · cin0 c22 · · · c2n...
......
0 cm2 · · · cmn
y regresamos al paso (1).
Forma normal de Smith Factores invariantes Sistemas de ecuaciones lineales diofanticas Grupos abelianos finitamente generados Grado de anillos afınes Grado de ideales binomiales asociados a lattices
(6) Aplicando pasos (1) a (5) repetidamente obtenemos:
E = (eij) =
e11 0 · · · 00 e22 · · · e2n...
......
0 em2 · · · emn
donde e11 divide a cualquier entrada eij .
(7) Definimos d1 := e11 y se regresa al paso (1) con la matriz:e22 · · · e2n...
...em2 · · · emn
2
Forma normal de Smith Factores invariantes Sistemas de ecuaciones lineales diofanticas Grupos abelianos finitamente generados Grado de anillos afınes Grado de ideales binomiales asociados a lattices
Ejemplo
A = (a11, . . . ,a1n) ∼ D = (mcd{a11, . . . ,a1n},0, . . . ,0)
Ejemplo
A = (12,−5) ∼ (−5,12) ∼ (5,12) ∼ (5,2) ∼ (2,5) ∼ (2,1)∼ (1,2) ∼ (1,0) = D.
I2 =
(1 00 1
)→(
0 11 0
)→(
0 1−1 0
)→ · · · →
(−2 5−5 12
)= Q
AQ = (12,−5)
(−2 5−5 12
)= (1,0) = D
Forma normal de Smith Factores invariantes Sistemas de ecuaciones lineales diofanticas Grupos abelianos finitamente generados Grado de anillos afınes Grado de ideales binomiales asociados a lattices
Ejemplo
A =
(5 0 11 −2 3
)∼(
1 2 35 0 1
)∼(
1 0 05 −10 −14
)∼(
1 0 00 −10 −14
)∼(
1 0 00 10 14
)∼(
1 0 00 10 4
)∼(
1 0 00 4 10
)∼(
1 0 00 4 2
)∼(
1 0 00 2 4
)∼(
1 0 00 2 0
)= D
I2 =
(1 00 1
)→(
0 11 0
)→ · · · →
(0 1−1 5
)= P
I3 =
1 0 00 1 00 0 1
→1 0 0
0 −1 00 0 1
→ · · · →1 0 −1
0 −3 70 −2 5
= Q
Forma normal de Smith Factores invariantes Sistemas de ecuaciones lineales diofanticas Grupos abelianos finitamente generados Grado de anillos afınes Grado de ideales binomiales asociados a lattices
Aop.elem. fila−→ B
⇒ B = EA
Inop.elem. fila−→ E
PAQ =
(0 1−1 5
)(5 0 11 −2 3
)1 0 −10 −3 70 −2 5
=
(1 0 00 2 0
)= D
CorolarioExisten matrices enteras invertibles P y Q tales que
PAQ = diag{d1, . . . ,dr ,0, . . . ,0},
di > 0 para 1 ≤ i ≤ r y di divide a di+1 para 1 ≤ i ≤ r − 1.
Forma normal de Smith Factores invariantes Sistemas de ecuaciones lineales diofanticas Grupos abelianos finitamente generados Grado de anillos afınes Grado de ideales binomiales asociados a lattices
Considere el sistema de ecuaciones lineales
Ax = b, (∗)
donde b = (b1, . . . ,bm)t es un vector entero y x = (x1, . . . , xn)t .
¿Como se determinan las soluciones enteras de este sistema?
Puesto que PAQ = D, el sistema Ax = b se re-escribe como
(P−1D)(Q−1x) = b ⇒ Dy = Pb, donde Q−1x = y
Por tanto para determinar las soluciones enteras del sistemaAx = b es suficiente resolver el sistema
Dy = Pb (∗∗)
y hacer x = Qy .
Forma normal de Smith Factores invariantes Sistemas de ecuaciones lineales diofanticas Grupos abelianos finitamente generados Grado de anillos afınes Grado de ideales binomiales asociados a lattices
EjemploDeterminar las soluciones enteras de la ecuacion
12x1 − 5x2 = 7
Este sistema se puede escribir como Ax = b, donde
A = (12, −5), x = (x1, x2)t , y b = (7)
Recordar que PAQ = D, donde
P = (1), Q =
(−2 5−5 12
), D = (1, 0).
Forma normal de Smith Factores invariantes Sistemas de ecuaciones lineales diofanticas Grupos abelianos finitamente generados Grado de anillos afınes Grado de ideales binomiales asociados a lattices
Dy = (1, 0)
(y1y2
)= Pb = (1)(7) = (7)
∴ y1 = 7, y2 ∈ Z. De la ecuacion
x =
(x1x2
)= Qy =
(−2 5−5 12
)(y1y2
)se obtiene que las soluciones enteras de la ecuacion lineal12x1 − 5x2 = 7 son:
x1 = −14 + 5y2
x2 = −35 + 12y2, y2 ∈ Z.
Comprobando: Si y2 = 0, se tiene
12(−14)− 5(−35) = −168 + 175 = 7.
Forma normal de Smith Factores invariantes Sistemas de ecuaciones lineales diofanticas Grupos abelianos finitamente generados Grado de anillos afınes Grado de ideales binomiales asociados a lattices
EjemploDeterminar las soluciones enteras del sistema
5x1 + x3 = 1x1 − 2x2 + 3x3 = −11
Este sistema se puede escribir como Ax = b, donde
A =
(5 0 11 −2 3
)y b =
(1−11
)Recordar que PAQ = D, donde
P =
(0 1−1 5
), Q =
1 0 −10 −3 70 −2 5
, D =
(1 0 00 2 0
)
Forma normal de Smith Factores invariantes Sistemas de ecuaciones lineales diofanticas Grupos abelianos finitamente generados Grado de anillos afınes Grado de ideales binomiales asociados a lattices
Dy =
(1 0 00 2 0
)y1y2y3
= Pb =
(0 1−1 5
)(1−11
)=
(−11−56
)
∴ y1 = −11, y2 = −28, y3 ∈ Z. De la ecuacion
x =
x1x2x3
= Qy =
1 0 −10 −3 70 −2 5
y1y2y3
se obtienen las soluciones enteras del sistema Ax = b:
x1 = −11− y3
x2 = 84 + 7y3
x3 = 56 + 5y3, y3 ∈ Z.
Forma normal de Smith Factores invariantes Sistemas de ecuaciones lineales diofanticas Grupos abelianos finitamente generados Grado de anillos afınes Grado de ideales binomiales asociados a lattices
∆r (A) = mcd de los r -menores de A.
Teorema (I. Heger)
Sea b ∈ Zm un vector columna tal que rango(A) = rango([A b]).Entonces, el sistema
Ax = b
tiene una solucion entera si y solo si ∆r (A) = ∆r ([A b]).
CorolarioLa ecuacion lineal Diofantina
a11x1 + · · ·+ a1nxn = b1
tiene solucion entera si y solo si mcd(a11, . . . ,a1n) divide a b1.
Forma normal de Smith Factores invariantes Sistemas de ecuaciones lineales diofanticas Grupos abelianos finitamente generados Grado de anillos afınes Grado de ideales binomiales asociados a lattices
Teorema (Grupos abelianos finitamente generados)
Sean a1, . . . ,am las filas de A y sean d1, . . . ,dr los factoresinvariantes de A. Entonces
Zn/〈a1, . . . ,am〉 ' Z/(d1)× · · · × Z/(dr )× Zn−r
' Zd1 × · · · × Zdr × Zn−r
DefinicionSean L = 〈a1, . . . ,am〉 y M = Zn/L.La parte de torsion de M es T (M) := Zd1 × · · · × Zdr .La parte libre de M es F (M) := Zn−r .
ObservacionT (M) = (0)⇔ di = 1 para todo i ⇔ M es libre.F (M) = 0⇔ rango(M) = n⇔ T (M) = M ⇔ M es grupo finito.
Forma normal de Smith Factores invariantes Sistemas de ecuaciones lineales diofanticas Grupos abelianos finitamente generados Grado de anillos afınes Grado de ideales binomiales asociados a lattices
Corolario
∆r (A) = |T (Zn/L)|.
Demostracion: |T (Zn/L)| = d1 · · · dr . Por otra parte PAQ = D ycomo ∆r (A) es invariante bajo operaciones elementales,obtenemos:
∆r (A) = ∆r (PAQ) = ∆r (D) = d1 · · · dr . 2
CorolarioSi n = m y det(A) 6= 0, entonces
|Zn/L| = |det(A)|.
Forma normal de Smith Factores invariantes Sistemas de ecuaciones lineales diofanticas Grupos abelianos finitamente generados Grado de anillos afınes Grado de ideales binomiales asociados a lattices
TeoremaSi a1, . . . ,am son linealmente independientes, entonces
(a) m!vol(conv(0,a1, . . . ,am)) = ∆m(A).
(b) Si n = m, entonces m!vol(conv(0,a1, . . . ,am)) = |det(A)|.
(c) Zn ∩ (R+a1 + · · ·+ R+am) = Na1 + · · ·+ Nam ⇔ ∆m(A) = 1.
Ejemplo
(Comprobando (b)): Sea A la matrix identidad, i.e., a1 = (1,0) ya2 = (0,1). Entonces conv(0,a1,a2) es un triangulo rectangulo conbase y altura 1 y con area/volumen igual a 1/2.
(Ilustrando (a) y (c)) Sea A = (12,−5) = (a1). Entonces conv(0,a1)es un segmento de linea en R2 (que tiene area 0) pero por (a) tenemos1!vol(conv(0,a1)) = ∆1(A) = 1 y por (c) tenemosZ2 ∩ R+(12,−5) = N(12,−5).
Forma normal de Smith Factores invariantes Sistemas de ecuaciones lineales diofanticas Grupos abelianos finitamente generados Grado de anillos afınes Grado de ideales binomiales asociados a lattices
Sea S = K [t1, . . . , tn] un anillo de polinomios con coeficientesen un campo K y sea I un ideal de S.
Sea ` ∈ N, sea S≤` el K -espacio vectorial de polinomios de Sde grado ≤ ` y sea I≤` = I ∩ S≤`. La funcion
HI(`) = dimK (S≤`/I≤`)
es llamada la funcion de Hilbert de S/I. Esta funcion es centralen algebra conmutativa y en geometrıa algebraica.
TeoremaExiste un unico polinomio
hI(x) = λdxd + · · ·+ λ1x + λ0
con λi ∈ Q para todo i tal que hI(`) = HI(`) para `� 0.
Forma normal de Smith Factores invariantes Sistemas de ecuaciones lineales diofanticas Grupos abelianos finitamente generados Grado de anillos afınes Grado de ideales binomiales asociados a lattices
DefinicionEl entero positivo (d !)λd es el grado de S/I y d es la dimension deKrull de S/I.
Ejemplo
Sea S = Q[t1] y sea I = (0). Entonces:
Q[t1]≤i = Q⊕Qt1 ⊕ · · · ⊕Qt i1⇒ HI(i) = i + 1 ∀ i ⇒
grado(S/I) = grado(S) = 1.
Como ejercicio probar que grado(Q[t1, . . . , tn]) = 1.
Forma normal de Smith Factores invariantes Sistemas de ecuaciones lineales diofanticas Grupos abelianos finitamente generados Grado de anillos afınes Grado de ideales binomiales asociados a lattices
Ejemplo
Sea S = Q[t1] y sea I = (td1 + · · ·+ t1 + 1).
Denotamos las clase de t i1 en S/I por t i
1.
td1 + · · ·+ t1 + 1 = 0⇒ t i
1 ∈ Q1⊕Qt1⊕ · · ·⊕Qtd−11 para i ≥ d −1
Para i ≥ d − 1, se tiene Q[t1]≤i/I≤i = Q1⊕Qt1 ⊕ · · · ⊕Qtd−11
Por tanto dimQ(Q[t1]≤i/I≤i) = d para i ≥ d − 1⇒ grado(S/I) = d .
Forma normal de Smith Factores invariantes Sistemas de ecuaciones lineales diofanticas Grupos abelianos finitamente generados Grado de anillos afınes Grado de ideales binomiales asociados a lattices
Un binomio de S es un polinomio de la forma tb − tc , dondeb, c ∈ Nn, y donde, si b = (b1, . . . ,bn) ∈ Nn, definimos
tb = tb11 · · · t
bnn ∈ S.
Un ideal binomial es un ideal generado por binomios.
Dado c = (ci) ∈ Nn, podemos escribir c = c+ − c−, donde c+ yc− son vectores no-negativos.
DefinicionUn subgrupo L de Zn es llamado un lattice (enrejado). Un ideallattice es un ideal de la forma
I(L) = ({tc+ − tc− | c ∈ L}) ⊂ S
para algun lattice L ⊂ Zn.
Forma normal de Smith Factores invariantes Sistemas de ecuaciones lineales diofanticas Grupos abelianos finitamente generados Grado de anillos afınes Grado de ideales binomiales asociados a lattices
TeoremaSi D = kerZ(A) y v1, . . . , vn son las columnas de A, entonces
|T (Zm/〈v1, . . . , vn〉)| grado(S/I(D))
= (rango(A)!)vol(conv(0, v2 − v1, . . . , vn − v1,−v1)).
Ejemplo
Sea A =
(5 0 11 −2 3
). Las soluciones enteras del sistema Ax = 0
son de la forma y3(−1,7,5) con y3 ∈ Z⇒
D = kerZ(A) = 〈(−1,7,5)〉 y I(D) = (t1 − t72 t5
3 )
Como D = diag(1, 2), tenemos
|T (Z2/〈v1, v2, v3〉| = |Z2/〈(5,1), (0,−2), (1,3)〉| = 2.
Forma normal de Smith Factores invariantes Sistemas de ecuaciones lineales diofanticas Grupos abelianos finitamente generados Grado de anillos afınes Grado de ideales binomiales asociados a lattices
Usando el programa Normaliz obtenemos:
(rango(A)!)vol(conv(0, v2 − v1, . . . , vn − v1,−v1)) =
2!vol(conv((0,0), (−5,−3), (−4,2), (−5,−1))) = 24.
Por el teorema anterior obtenemos
grado(S/I(D)) = 12.
Lo cual es consistente con la nocion intuitiva de grado pues elpolinomio t1 − t7
2 t53 tiene grado 12.
Forma normal de Smith Factores invariantes Sistemas de ecuaciones lineales diofanticas Grupos abelianos finitamente generados Grado de anillos afınes Grado de ideales binomiales asociados a lattices
TeoremaSea L un lattice en Zn.
1 Si rango(L) = n y K = Q, entonces
grado(S/I(L)) = |Zn/L|.
2 Si rango(L) = n − 1 y c1 + · · ·+ cn = 0 para todo(c1, . . . , cn) ∈ L, entonces
grado(S/I(L)) = |T (Zn/L)|.
Forma normal de Smith Factores invariantes Sistemas de ecuaciones lineales diofanticas Grupos abelianos finitamente generados Grado de anillos afınes Grado de ideales binomiales asociados a lattices
FIN