polinomios de schur y soluciones básicas de las recurrencias...
TRANSCRIPT
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Polinomios de Schury soluciones basicas de las recurrencias lineales
Egor Maximenko, Mario Alberto Moctezuma Salazar
Instituto Politecnico Nacional, ESFM, Mexico
50o Congreso Nacionalde la Sociedad Matematica Mexicana
UNAM, Ciudad de Mexico25 de octubre de 2017
1 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Ejemplo de recurrencia lineal: contamos los ritmosFijamos una unidad de tiempo T (por ejemplo, un segundo).Rn := el numero de los ritmos de longitud nT que consistende sonidos de dos tipos: cortos (T ) y muy largos (3T ).
R1 = 1:
R2 = 1:R3 = 2: ,R4 = 3: , ,R5 = 4: , , ,R6 = 6: , , , , ,
Recurrencia lineal:
Rn = Rn−1 +Rn−3.
Condiciones iniciales: R0 = 1, R1 = 1, R2 = 1.
2 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Ejemplo de recurrencia lineal: contamos los ritmosFijamos una unidad de tiempo T (por ejemplo, un segundo).Rn := el numero de los ritmos de longitud nT que consistende sonidos de dos tipos: cortos (T ) y muy largos (3T ).
R1 = 1:R2 = 1:
R3 = 2: ,R4 = 3: , ,R5 = 4: , , ,R6 = 6: , , , , ,
Recurrencia lineal:
Rn = Rn−1 +Rn−3.
Condiciones iniciales: R0 = 1, R1 = 1, R2 = 1.
2 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Ejemplo de recurrencia lineal: contamos los ritmosFijamos una unidad de tiempo T (por ejemplo, un segundo).Rn := el numero de los ritmos de longitud nT que consistende sonidos de dos tipos: cortos (T ) y muy largos (3T ).
R1 = 1:R2 = 1:R3 = 2: ,
R4 = 3: , ,R5 = 4: , , ,R6 = 6: , , , , ,
Recurrencia lineal:
Rn = Rn−1 +Rn−3.
Condiciones iniciales: R0 = 1, R1 = 1, R2 = 1.
2 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Ejemplo de recurrencia lineal: contamos los ritmosFijamos una unidad de tiempo T (por ejemplo, un segundo).Rn := el numero de los ritmos de longitud nT que consistende sonidos de dos tipos: cortos (T ) y muy largos (3T ).
R1 = 1:R2 = 1:R3 = 2: ,R4 = 3: , ,
R5 = 4: , , ,R6 = 6: , , , , ,
Recurrencia lineal:
Rn = Rn−1 +Rn−3.
Condiciones iniciales: R0 = 1, R1 = 1, R2 = 1.
2 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Ejemplo de recurrencia lineal: contamos los ritmosFijamos una unidad de tiempo T (por ejemplo, un segundo).Rn := el numero de los ritmos de longitud nT que consistende sonidos de dos tipos: cortos (T ) y muy largos (3T ).
R1 = 1:R2 = 1:R3 = 2: ,R4 = 3: , ,R5 = 4: , , ,
R6 = 6: , , , , ,
Recurrencia lineal:
Rn = Rn−1 +Rn−3.
Condiciones iniciales: R0 = 1, R1 = 1, R2 = 1.
2 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Ejemplo de recurrencia lineal: contamos los ritmosFijamos una unidad de tiempo T (por ejemplo, un segundo).Rn := el numero de los ritmos de longitud nT que consistende sonidos de dos tipos: cortos (T ) y muy largos (3T ).
R1 = 1:R2 = 1:R3 = 2: ,R4 = 3: , ,R5 = 4: , , ,R6 = 6: , , , , ,
Recurrencia lineal:
Rn = Rn−1 +Rn−3.
Condiciones iniciales: R0 = 1, R1 = 1, R2 = 1.
2 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Ejemplo de recurrencia lineal: contamos los ritmosFijamos una unidad de tiempo T (por ejemplo, un segundo).Rn := el numero de los ritmos de longitud nT que consistende sonidos de dos tipos: cortos (T ) y muy largos (3T ).
R1 = 1:R2 = 1:R3 = 2: ,R4 = 3: , ,R5 = 4: , , ,R6 = 6: , , , , ,
Recurrencia lineal:
Rn = Rn−1 +Rn−3.
Condiciones iniciales: R0 = 1, R1 = 1, R2 = 1.2 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Sucesion de Fibonacci (Leonardo de Pisa)
F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
Fn = Fn−1 + Fn−2, F0 = 0, F1 = 1.
3 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Sucesion de Fibonacci (Leonardo de Pisa)
F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
Fn = Fn−1 + Fn−2, F0 = 0, F1 = 1.
3 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Sucesion de Fibonacci (Leonardo de Pisa)
F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
Fn = Fn−1 + Fn−2, F0 = 0, F1 = 1.
3 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Sucesion de Fibonacci (Leonardo de Pisa)
F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
Fn = Fn−1 + Fn−2, F0 = 0, F1 = 1.
3 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Sucesion de Fibonacci (Leonardo de Pisa)
F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
Fn = Fn−1 + Fn−2, F0 = 0, F1 = 1.
3 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Sucesion de Fibonacci (Leonardo de Pisa)
F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
Fn = Fn−1 + Fn−2, F0 = 0, F1 = 1.
3 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Recurrencia lineal homogenea de orden dcon coeficientes constantes
Para cada n ≥ d,
a0︸︷︷︸1
fn + a1fn−1 + a2fn−2 + · · ·+ adfn−d = 0. (RecLin)
Definicion (polinomio caracterıstico)
a(t) = a0td + a1t
d−1 + · · ·+ adt0.
Definicion (conjunto solucion)La := el conjunto de las sucesiones complejas f = (fk)∞k=0
que satisfacen (RecLin) para cada n ≥ d.
L es un espacio vectorial.
4 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Recurrencia lineal homogenea de orden dcon coeficientes constantes
Para cada n ≥ d,
a0︸︷︷︸1
fn + a1fn−1 + a2fn−2 + · · ·+ adfn−d = 0. (RecLin)
Definicion (polinomio caracterıstico)
a(t) = a0td + a1t
d−1 + · · ·+ adt0.
Definicion (conjunto solucion)La := el conjunto de las sucesiones complejas f = (fk)∞k=0
que satisfacen (RecLin) para cada n ≥ d.
L es un espacio vectorial.
4 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Recurrencia lineal homogenea de orden dcon coeficientes constantes
Para cada n ≥ d,
a0︸︷︷︸1
fn + a1fn−1 + a2fn−2 + · · ·+ adfn−d = 0. (RecLin)
Definicion (polinomio caracterıstico)
a(t) = a0td + a1t
d−1 + · · ·+ adt0.
Definicion (conjunto solucion)La := el conjunto de las sucesiones complejas f = (fk)∞k=0
que satisfacen (RecLin) para cada n ≥ d.
L es un espacio vectorial.
4 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Recurrencia lineal homogenea de orden dcon coeficientes constantes
Para cada n ≥ d,
a0︸︷︷︸1
fn + a1fn−1 + a2fn−2 + · · ·+ adfn−d = 0. (RecLin)
Definicion (polinomio caracterıstico)
a(t) = a0td + a1t
d−1 + · · ·+ adt0.
Definicion (conjunto solucion)La := el conjunto de las sucesiones complejas f = (fk)∞k=0
que satisfacen (RecLin) para cada n ≥ d.
L es un espacio vectorial.
4 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Recurrencia lineal homogenea de orden dcon coeficientes constantes
Para cada n ≥ d,
a0︸︷︷︸1
fn + a1fn−1 + a2fn−2 + · · ·+ adfn−d = 0. (RecLin)
Definicion (polinomio caracterıstico)
a(t) = a0td + a1t
d−1 + · · ·+ adt0.
Definicion (conjunto solucion)La := el conjunto de las sucesiones complejas f = (fk)∞k=0
que satisfacen (RecLin) para cada n ≥ d.
L es un espacio vectorial.4 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Condiciones inicialesRecurrencia lineal de orden 2 con dos valores iniciales v0 y v1:
f0 = v0,
f1 = v1,
f2 + a1f1 + a2f0 = 0,
f3 + a1f2 + a2f1 = 0,
f4 + a1f3 + a2f2 = 0,
. . .
Proposicion (existencia y unicidad de solucion de rec. lin.)Sean a0 = 1, a1, . . . , ad ∈ C y v0, v1, . . . , vn−1 ∈ C.Entonces existe una unica sucesion f en La tal que
f0 = v0, f1 = v1, . . . , fd−1 = vd−1.
5 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Metodo clasico de solucion, para d = 2Consideramos la recurrencia lineal de segundo orden:
fn + a1fn−1 + a2fn−2 = 0 (n ≥ 2).
Denotamos por x1 y x2 a las raıces del polinomio caracterıstico:
a(t) = t2 + a1t+ a2 = (t− x1)(t− x2).
Las progresiones geometricas
(xk1)∞k=0, (xk2)∞k=0
son soluciones de la recurrencia lineal:
xn1 + a1xn−11 + a2x
n−21 = xn−2
1 (x21 + a1x1 + a2) = 0.
Consideramos el caso x1 6= x2.Entonces (xn1 )∞n=0 y (xn2 )∞n=0 forman una base de La.
6 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Metodo clasico de solucion, para d = 2
Consideramos el caso x1 6= x2. La solucion general es
fn = αxn1 + βxn2 .
Los coeficientes se determinan por las condiciones iniciales:
n = 0: αx01 + βx0
2 = v0,
n = 1: αx11 + βx1
2 = v1.
En forma matricial,[x0
1 x02
x11 x1
2
] [α
β
]=[v0
v1
].
Como x1 6= x2, el determinante de Vandermonde es no nulo,y el sistema tiene una unica solucion.
7 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Metodo clasico para d = 3
Para d = 3, si x1, x2, x3 son diferentes a pares, entonces
fn = αxn1 + βxn2 + γxn3 ,
donde los coeficientes α, β, γ se determinan del sistemax0
1 x02 x0
3x1
1 x12 x1
3x2
1 x22 x2
3
α
β
γ
=
v0
v1
v2
.Un defecto de esta forma de la solucion:
las condiciones iniciales v0, . . . , vd−1no aparecen de manera simple en la respuesta.
8 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Busquemos soluciones basicas
Denotemos por b(0), . . . , b(d−1) a las sucesiones de clase Laque se determinan por los siguientes valores iniciales:
b(0) = (d︷ ︸︸ ︷
1, 0, . . . , 0, ?, ?, . . .),b(1) = ( 0, 1, . . . , 0, ?, ?, . . . ),· · ·
b(d−1) = ( 0, 0, . . . , 1, ?, ?, . . . ).
Formalmente,b(j)k = δj,k (0 ≤ k < j).
9 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Solucion general en terminos de las soluciones basicas
Proposicion
Sea f ∈ La. Entonces f =d−1∑j=0
fjb(j).
¡Los coeficientes son los valores iniciales!
Demostracion.La sucesion g :=
∑d−1j=0 fjb
(j) es de clase La.Ademas, tiene los mismos valores iniciales que la sucesion f .En efecto, si k < d, entonces
gk =d−1∑j=0
fjδj,k = fk.
10 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Soluciones basicas para d = 2
t2 + a1t+ a2 = (t− x1)(t− x2) = t2 + (−x1 − x2)︸ ︷︷ ︸a1
t1 + x1x2︸ ︷︷ ︸a0
t0.
Si f ∈ La, entonces para cada n ≥ 2
fn = −a1fn−1 − a2fn−2 = (x1 + x2)fn−1 − x1x2fn−2.
Las soluciones basicas empiezan con las siguientes componentes:
b(0) =(1, 0, −x1x2, −(x2
1x2 + x1x22), . . .
),
b(1) =(0, 1, x1 + x2, x
21 + x1x2 + x2
2, . . .).
¡Las componentes son polinomios simetricos homogeneos!
11 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Soluciones basicas para d = 2
t2 + a1t+ a2 = (t− x1)(t− x2) = t2 + (−x1 − x2)︸ ︷︷ ︸a1
t1 + x1x2︸ ︷︷ ︸a0
t0.
Si f ∈ La, entonces para cada n ≥ 2
fn = −a1fn−1 − a2fn−2 = (x1 + x2)fn−1 − x1x2fn−2.
Las soluciones basicas empiezan con las siguientes componentes:
b(0) =(1, 0, −x1x2, −(x2
1x2 + x1x22), . . .
),
b(1) =(0, 1, x1 + x2, x
21 + x1x2 + x2
2, . . .).
¡Las componentes son polinomios simetricos homogeneos!
11 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Algunas familias de polinomios simetricos
Macdonald (1995): Symmetric functions and Hall polynomials.Stanley (1999): Enumerative combinatorics, vol. 2.
Polinomiossimetricos
completos
elementales Schur
Schursesgados
generan al algebra
generan al algebra base del espacio vectorial
12 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Polinomios simetricos completos
h1(x1, x2, x3) = x1 + x2 + x3,
h2(x1, x2, x3) = x21 + x2
2 + x23 + x1x2 + x1x3 + x2x3,
h3(x1, x2, x3) = x31 + x3
2 + x33 + x2
1x2 + x21x3 + x2
2x1 + x22x3
+ x23x1 + x2
3x2 + x1x2x3.
DefinicionEl polinomio simetrico completo de orden k en n variableses la suma de todos los monomios de grado total k:
hk(x1, . . . , xn) =∑
p1,...,pn≥0p1+p2+···+pn=k
xp11 · · ·x
pnn .
13 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Polinomios simetricos elementales
e1(x1, x2, x3, x4) = x1 + x2 + x3 + x4,
e2(x1, x2, x3, x4) = x1x2 + x1x3 + x1x4 + x2x3 + x2x4 + x3x4,
e3(x1, x2, x3, x4) = x1x2x3 + x1x2x4 + x1x3x4 + x2x3x4,
e4(x1, x2, x3, x4) = x1x2x3x4.
DefinicionEl polinomio simetrico elemental de grado k en n variableses la suma de todos los productos de k variables diferentes:
ek(x1, . . . , xn) =∑
1≤j1<j2<···<jk≤nxj1xj2 · · ·xjk .
14 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Formula de Vieta (Francois Viete, 1540–1603)
ProposicionLos coeficientes del polinomio monico
a(t) = td + a1td−1 + · · ·+ ad−1t+ ad =
d∏j=1
(t− xj)
son polinomios elementales de sus raıces, con signos alternados:
ak = (−1)kek(x1, . . . , xd).
a(t) = t2 + a1t+ a2 = (t− x1)(t− x2),
a0 = 1 = e0(x1, x2),a1 = −(x1 + x2) = −e1(x1, x2),a2 = x1x2 = e2(x1, x2).
15 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Recurrencia lineal en terminos de los pol. elementales
La recurrencia lineal
fn + a1fn−1 + a2fn−2 + · · ·+ adfn−d = 0 (RecLin)
se escribe comod∑
k=0(−1)kek(x1, . . . , xd)fn−k = 0 (n ≥ d).
Otra forma equivalente:
d∑k=0
(−1)ked−k(x1, . . . , xd)fn+k = 0 (n ≥ 0).
16 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Particiones enteras y sus diagramas de YoungParticiones enteras son listas finitas debilmente decrecientes denumeros enteros no negativos.
λ = (3, 2, 2, 1).
Cada particion entera se identifica con su diagrama:
λ = .
La particion conjugada corresponde al diagrama transpuesto:
λ′ = = (4, 3, 1).
17 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Varias definiciones equivalentes de polinomios de Schur
Dada una particion entera λ = (λ1, . . . , λn),el polinomio de Schur sλ(x1, . . . , xn) es cierto polinomiosimetrico homogeneo de grado λ1 + · · ·+ λn.
Hay varias definiciones equivalentes de sλ(x1, . . . , xn):por la formula de Jacobi–Trudi, en terminos de hk,por la formula dual de Jacobi–Trudi, en terminos de ek,usando determinantes generalizados de Vandermonde,por medio de tablas semiestandares de Young, etc.
Los polinomios de Schur forman una base del espacio vectorialde los polinomios simetricos.
18 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Definicion de polinomios de Schurpor la formula de Jacobi–Trudi
La formula de Jacobi–Trudi expresa los polinomios de Schuren terminos de polinomios simetricos homogeneos completos.
Definicion
sλ = det[hλj−j+k]nj,k=1.
Si λ = (λ1, λ2, λ3, λ4), entonces
sλ =
∣∣∣∣∣∣∣∣∣hλ1 hλ1+1 hλ1+2 hλ1+3hλ2−1 hλ2 hλ2+1 hλ2+2hλ3−2 hλ3−1 hλ3 hλ3+1hλ4−3 hλ4−2 hλ4−1 hλ4
∣∣∣∣∣∣∣∣∣ .
19 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
La formula dual de Jacobi–Trudi(la identidad de Nagelsbach–Kostka)
Expresa polinomios de Schur en terminos de polinomiossimetricos elementales, usando la particion conjugada.
Proposicion
sλ = det[eλ′j−j+k]λ1j,k=1.
Si λ′ = (λ′1, λ′2, λ′3), entonces
sλ =
∣∣∣∣∣∣∣eλ′1 eλ′1+1 eλ′1+2eλ′2−1 eλ′2 eλ′2+1eλ′3−2 eλ′3−1 eλ′3
∣∣∣∣∣∣∣ .
20 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Pol. de Schur y det. generalizados de Vandermonde
Proposicion
sλ(x1, . . . , xn) =det[xλj+n−jk
]nj,k=1
det[xn−jk
]nj,k=1
.
s(λ1,λ2,λ3)(x1, x2, x3) =
∣∣∣∣∣∣∣∣∣xλ1+2
1 xλ1+22 xλ1+2
3
xλ2+11 xλ2+1
2 xλ2+13
xλ31 xλ3
2 xλ33
∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣x2
1 x22 x2
3
x11 x1
2 x13
x01 x0
2 x03
∣∣∣∣∣∣∣∣∣
.
21 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Polinomios de Schur y tablas de Young
Las tablas semiestandares del diagrama λ = (2, 2, 1, 1) son
1 12 234
,
1 12 334
,
1 22 334
,
1 12 434
,
1 22 434
,
1 32 434
.
El correspondiente polinomio de Schur s(3,2,2,1)(x1, x2, x3, x4) es
x21x
22x3x4 + x2
1x2x23x4 + x1x
22x
23x4
+ x21x2x3x
24 + x1x
22x3x
24 + x1x2x
23x
24.
22 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Polinomios de Schur y tablas de Young
Las tablas semiestandares del diagrama λ = (2, 2, 1, 1) son
1 12 234
,
1 12 334
,
1 22 334
,
1 12 434
,
1 22 434
,
1 32 434
.
El correspondiente polinomio de Schur s(3,2,2,1)(x1, x2, x3, x4) es
x21x
22x3x4 + x2
1x2x23x4 + x1x
22x
23x4
+ x21x2x3x
24 + x1x
22x3x
24 + x1x2x
23x
24.
22 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Polinomios de Schur y tablas de Young
Las tablas semiestandares del diagrama λ = (2, 2, 1, 1) son
1 12 234
,
1 12 334
,
1 22 334
,
1 12 434
,
1 22 434
,
1 32 434
.
El correspondiente polinomio de Schur s(3,2,2,1)(x1, x2, x3, x4) es
x21x
22x3x4 + x2
1x2x23x4 + x1x
22x
23x4
+ x21x2x3x
24 + x1x
22x3x
24 + x1x2x
23x
24.
22 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Ejemplo: calculemos s(3,1)(x1, x2)
I. Empecemos con la formula de Jacobi–Trudi:
s(3,1)(x1, x2) =∣∣∣∣∣ h3 h4h0 h1
∣∣∣∣∣ = h3h1 − h4h0
= (x31 + x2
1x2 + x1x22 + x3
2)(x1 + x2)
− (x41 + x3
1x2 + x21x
22 + x1x
32 + x4
2)
= x31x2 + x2
1x22 + x1x
32.
23 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Ejemplo: calculemos s(3,1)(x1, x2)II. Calculamos el diagrama conjugado:
λ = (3, 1) = , λ′ = = (2, 1, 1),
y aplicamos la formula dual de Jacobi–Trudi:
s(3,1)(x1, x2) =
∣∣∣∣∣∣∣e2 e3 e4e0 e1 e2e−1 e0 e1
∣∣∣∣∣∣∣ =
∣∣∣∣∣∣∣e2 0 0e0 e1 e20 e0 e1
∣∣∣∣∣∣∣= e2(e2
1 − e2)
= x1x2((x1 + x2)2 − x1x2)
= x31x2 + x2
1x22 + x1x
32.
24 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Ejemplo: calculemos s(3,1)(x1, x2)
III. Usamos determinantes de Vandermonde generalizados:
s(3,1)(x1, x2) =
∣∣∣∣∣ x41 x4
2x1 x2
∣∣∣∣∣∣∣∣∣∣ x11 x1
2x0
1 x02
∣∣∣∣∣= x4
1x2 − x1x42
x1 − x2= x1x2(x3
1 − x32)
x1 − x2
= x1x2(x21 + x1x2 + x2
2)
= x31x2 + x2
1x22 + x1x
32.
25 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Ejemplo: calculemos s(3,1)(x1, x2)
IV. Finalmente, hallamos todas las tablas de Youngsemiestandares:
1 1 12 , 1 1 2
2 , 1 2 22 ,
y las convertimos en monomios:
s(3,1)(x1, x2) = x31x2 + x2
1x22 + x1x
32.
26 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Elementales y completos como polinomios de Schur
Proposicion
ek = s(1k), hk = s(k).
e2(x1, x2, x3) = s(1,1)(x1, x2, x3)
= 12 + 1
3 + 23
= x1x2 + x1x3 + x2x3;
h2(x1, x2, x3) = s(2)(x1, x2, x3)
= 1 1 + 1 2 + 1 3 + 2 2 + 2 3 + 3 3
= x21 + x1x2 + x1x3 + x2
2 + x2x3 + x23.
27 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Elementales y completos como polinomios de Schur
Proposicion
ek = s(1k), hk = s(k).
e2(x1, x2, x3) = s(1,1)(x1, x2, x3)
= 12 + 1
3 + 23
= x1x2 + x1x3 + x2x3;
h2(x1, x2, x3) = s(2)(x1, x2, x3)
= 1 1 + 1 2 + 1 3 + 2 2 + 2 3 + 3 3
= x21 + x1x2 + x1x3 + x2
2 + x2x3 + x23.
27 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Elementales y completos como polinomios de Schur
Proposicion
ek = s(1k), hk = s(k).
e2(x1, x2, x3) = s(1,1)(x1, x2, x3)
= 12 + 1
3 + 23
= x1x2 + x1x3 + x2x3;
h2(x1, x2, x3) = s(2)(x1, x2, x3)
= 1 1 + 1 2 + 1 3 + 2 2 + 2 3 + 3 3
= x21 + x1x2 + x1x3 + x2
2 + x2x3 + x23.
27 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Particiones sesgadas y sus diagramas
Los diagramas de las particiones λ = (3, 2, 2, 1) y µ = (2, 1) son
λ = , µ = .
La particion sesgada λ/µ = (3, 2, 2, 1)/(2, 1) tiene diagrama
.
28 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Jacobi–Trudi para polinomios de Schur sesgados
Definicion
sλ/µ = det[hλj−µk−j+k]nj,k=1.
s(λ1,λ2,λ3)/(µ1,µ2) =
∣∣∣∣∣∣∣hλ1−µ1 hλ1−µ2+1 hλ1−µ3+2hλ2−µ1−1 hλ2−µ2 hλ2−µ3+1hλ3−µ1−2 hλ3−µ2−1 hλ3−µ3
∣∣∣∣∣∣∣ .
Proposicion
sλ/µ = det[eλ′j−µ′k−j+k]λ1j,k=1.
29 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Jacobi–Trudi para polinomios de Schur sesgados
Definicion
sλ/µ = det[hλj−µk−j+k]nj,k=1.
s(λ1,λ2,λ3)/(µ1,µ2) =
∣∣∣∣∣∣∣hλ1−µ1 hλ1−µ2+1 hλ1−µ3+2hλ2−µ1−1 hλ2−µ2 hλ2−µ3+1hλ3−µ1−2 hλ3−µ2−1 hλ3−µ3
∣∣∣∣∣∣∣ .
Proposicion
sλ/µ = det[eλ′j−µ′k−j+k]λ1j,k=1.
29 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Tablas sesgadas y polinomios sesgados de Schur
Calculemos s(4,3,2)/(3,1)(x1, x2) usando tablas de Young:
11 1
1 2
, 11 1
2 2
, 11 2
1 2
, 21 1
1 2
,
11 2
2 2
, 21 2
1 2
, 21 1
2 2
, 21 2
2 2
.
Cada tabla se convierte en un monomio:
s(4,3,2)/(3,1)(x1, x2) = x41x2 + 3x3
1x22 + 3x2
1x32 + x1x
42.
30 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Dos operaciones de concatenacion de diagramas
D1 = (3, 3, 2)/(2, 1) = , D2 = (4, 2)/(1) = .
D1 ↑ D2 = = ,
D1 ← D2 = = .
31 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Producto de polinomios de Schur sesgados
ProposicionSean D1 y D2 diagramas sesgados. Entonces
sD1sD2 = sD1↑D2 + sD1←D2 .
· = + .
En otra notacion,
s(3,3,2)/(2,1)s(4,2)/(1) = s(6,4,3,3,2)/(3,2,2,1) + s(7,5,3,2)/(4,2,1).
32 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Productos de ganchos por elementales
· =
+ ,
· = + ,
· = + .
Sumamos estas igualdades alternando los signos:e3s(5,12) − e2s(6,12) + e1s(7,12) − e0s(8,12) = s(54,12)/(43).
33 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Productos de ganchos por elementales
· = + ,
· = + ,
· = + .
Sumamos estas igualdades alternando los signos:e3s(5,12) − e2s(6,12) + e1s(7,12) − e0s(8,12) = s(54,12)/(43).
33 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Productos de ganchos por elementales
· = + ,
· = + ,
· = + .
Sumamos estas igualdades alternando los signos:e3s(5,12) − e2s(6,12) + e1s(7,12) − e0s(8,12) = s(54,12)/(43).
33 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Productos de ganchos por elementales
· = + ,
· = + ,
· = + .
Sumamos estas igualdades alternando los signos:e3s(5,12) − e2s(6,12) + e1s(7,12) − e0s(8,12) = s(54,12)/(43).
33 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Productos de ganchos por elementales
· = + ,
· = + ,
· = + .
Sumamos estas igualdades alternando los signos:e3s(5,12) − e2s(6,12) + e1s(7,12) − e0s(8,12) = s(54,12)/(43).
33 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Identidades tipo Newton para polinomios de Schur
ProposicionSean d ≥ 0, p ≥ 1, q ≥ 0. Entonces
d∑k=0
(−1)ked−ks(p+k,1q) = s(pd+1,1q)/((p−1)d).
Si el numero de variables es d, entonces el lado derecho es cero:
d∑k=0
(−1)ked−k(x1, . . . , xd)s(p+k,1q)(x1, . . . , xd) = 0.
34 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Identidades tipo Newton para polinomios de Schur
ProposicionSean d ≥ 0, p ≥ 1, q ≥ 0. Entonces
d∑k=0
(−1)ked−ks(p+k,1q) = s(pd+1,1q)/((p−1)d).
Si el numero de variables es d, entonces el lado derecho es cero:
d∑k=0
(−1)ked−k(x1, . . . , xd)s(p+k,1q)(x1, . . . , xd) = 0.
34 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Identidades tipo Newton para polinomios de Schur
Una version mas general de la formula anterior:
ProposicionSean d ≥ 0, λ1 ≥ λ2 ≥ · · · ≥ λn > 0. Entonces
d∑k=0
(−1)ked−ks(λ1+k,λ2,...,λn) = s(λd+11 ,λ2,...,λn)/((λ1−1)d).
35 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Soluciones basicas en terminos de polinomios de Schur
TeoremaSea 0 ≤ j < d. La solucion de (RecLin) con condiciones iniciales
b(j)k = δj,k (0 ≤ k < d).
esta dada por
b(j)k = (−1)d−j−1s(k+1−d,1d−j−1).
Otras demostraciones de este resultado:
William F. Trench (1985), doi:10.1137/0606054
Alain Lascoux (2009), http://lipn.univ-paris13.fr/˜duchamp/Books&more/Lascoux/RecurSeq.pdf
36 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Soluciones basicas en terminos de polinomios de Schur
TeoremaSea 0 ≤ j < d. La solucion de (RecLin) con condiciones iniciales
b(j)k = δj,k (0 ≤ k < d).
esta dada por
b(j)k = (−1)d−j−1s(k+1−d,1d−j−1).
Otras demostraciones de este resultado:
William F. Trench (1985), doi:10.1137/0606054
Alain Lascoux (2009), http://lipn.univ-paris13.fr/˜duchamp/Books&more/Lascoux/RecurSeq.pdf
36 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Ejemplo: solucion basica b(0) para d = 2
b(0)k = −s(k−1,1)(x1, x2).
b(0)0 = s(−1,1)(x1, x2) = 1,
b(0)1 = s(0,1)(x1, x2) = 0,
b(0)2 = −s(1,1) = − 1
1= −x1x2,
b(0)3 = −s(2,1) = −
(2 11
+ 2 21
)= −
(x2
1x2 + x1x22).
b(0)k = −x1x2(xk−1
1 − xk−12 )
x1 − x2.
Si x1 = x2, entonces b(0)k = −(k − 1)xk1.
37 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Ejemplo: solucion basica b(1) para d = 2
b(1)k = s(k−1)(x1, x2).
b(1)0 = s(−1) = 0,
b(1)1 = s(0) = 1,
b(1)2 = s(1) = 1 + 2 = x1 + x2,
b(1)3 = s(2) = 1 1 + 1 2 + 2 2 = x2
1 + x1x2 + x22.
b(1)k = xk1 − xk2
x1 − x2.
Si x1 = x2, entoncesb(1)k = kxk−1
1 .
38 / 39
Recurrencias lineales Polinomios de Schur Polinomios de Schur sesgados Soluciones basicas
Ejemplo: la sucesion de Fibonacci
Consideramos la recurrencia lineal asociada al polinomio
a(t) = t2 − t− 1 = (t− φ)(t+ φ−1), donde φ = 1 +√
52 ,
con condiciones iniciales F0 = 0 y F1 = 1.
La solucion de este problema es la solucion basica b(1):
Fk = b(1)k = s(k−1)(x1, x2) = xk1 − xk2
x1 − x2= φk − (−φ)−k√
5.
Hemos llegado a la formula de Binet.
39 / 39