Symetrické polynomy
Buď M[xi, X2,..., xn] okruh všech polynomů n proměnných xi, X2,..., xn s koeficienty, jimiž jsou libovolné prvky tělesa IR. všech reálných čísel. Buď p G M[xi,X2,... ,xn] libovolný takový polynom. Přejeme-li si zde zdůraznit, že p je polynom v proměnných xi, X2,..., xn, píšeme obšírněji p(xi, X2,..., xn) místo pouhého p. Do takového polynomu můžeme dále dosadit libovolné polynomy <7i, <725 • • • 5 Qn z okruhu M[xi, X2,..., xn] za jednotlivé proměnné xi, X2,..., xn. Výsledkem takového dosazení je potom polynom z okruhu M[xi,X2,... ,xn], který zaznamenáváme zápisem p(gi, 92, • • • 3 Qn)- Řekneme, že polynom p z okruhu M[xi,X2,... ,xn] je symetrický, jestliže pro každou permutaci a množiny čísel {1,2,..., n} platí rovnost p(xfj(1), x^),... ,xfj(A?)) = p(xi,x2,... ,x„). Příklady symetrických polynomů jsou sumy Sk = x^ + x^ + • • • + x^ mocnin jednotlivých proměnných pro libovolná kladná celá čísla k. Je-li p(xi,X2,..., xn) libovolný polynom z okruhu M[xi, X2,..., xn] a jsou-li qi, q2,..., qn libovolné symetrické polynomy z tohoto okruhu, pak polynom p(qi, 92, • • • 3 <7n) vzniklý dosazením je symetrický polynom z tohoto okruhu.
Člen v proměnných xi,x2,... ,x„ je libovolný součin mocnin proměnných tvaru x^x^2 • • • x^n, kde ai,     • • • 5    jsou libovolná nezáporná celá čísla. Stupněm člene x^x^2 • • • x„n pak rozumíme součet ql\ + «2 + • • • + otn exponentů u všech jeho proměnných. Každý polynom p z okruhu M[xi,x2,... ,x„] je pak součtem několika členů opatřených koeficienty, jimiž jsou nějaké prvky tělesa IR. vyjma nuly. Stupněm nenulového polynomu p pak rozumíme největší ze stupňů jeho jednotlivých členů. Řekneme, že nenulový polynom p z okruhu M[xi,x2,..., x„] je homogenní, jestliže všechny jeho členy mají tentýž stupeň. Stupněm homogenního polynomu je pak ovšem stupeň kteréhokoliv z jeho jednotlivých členů. Je vidět, že každý polynom p z okruhu M[xi,x2,..., x„] je pak součtem několika homogenních polynomů různých stupňů. Je-li tento polynom p symetrický, pak jednotlivé homogenní polynomy různých stupňů, které v součtu dají tento symetrický polynom p, jsou samy o sobě rovněž symetrickými polynomy. Dostáváme se tak k pojmu homogenních symetrických polynomů. Pro každé kladné celé číslo k označme symbolem A^[xi,x2,... ,x„] množinu všech homogenních symetrických polynomů stupně k s koeficienty, jimiž jsou libovolné prvky tělesa M. Pak množina A^[xi, x2,..., xn] tvoří vektorový pod prostor ve vektorovém prostoru ^[*i5*25 • • • ,xn] nad tělesem M všech reálných čísel. Uvidíme, že A^[xi,x2,... ,x„] je vektorový prostor nad tělesem M konečné dimenze, a najdeme jeho bázi.
2/14
Rozkladem A nezáporného celého čísla k rozumíme libovolnou posloupnost A = (Ai, A2,..., As) kladných celých čísel takovou, že Ai ^ A2 ^ • • • ^ As a Xi + A2 + • —h As = k. Délkou rozkladu A rozumíme počet s jeho kladných složek a značíme ji symbolem £(X). Někdy připouštíme, aby složkami rozkladu A byly i nuly, a náš původní rozklad A = (Ai, A2,..., As) pak ztotožňujeme s každou posloupností tvaru (Ai, A2,..., As, 0, 0,..., 0). Značíme symbolem Par(/c) množinu všech rozkladů čísla k. Jestliže A G Par(/c), píšeme také A h k. Ještě pro každé / G {1, 2,..., k} označme symbolem m; = at7;(A) počet těch složek rozkladu A, které jsou rovny /. Pak ovšem platí mi + rri2 + • • • +     = £(X) a + 2/772 + • • • + krrik = k.
Pro každé nezáporné celé číslo k definujeme částečné uspořádání ^ na množině rozkladů Par(/c), nazývané uspořádání dominancí, následujícím způsobem. Jsou-li [i = (/ii, /i2, • • •, Mr) a A = (Ai, A2,..., As) dva rozklady čísla /c, pak klademe [i ^ A, jestliže platí
Mi + M2 + • • • +    ^ Ai + A2 + • • • + Xj      pro všechna j ^ 1. Dostáváme tak částečně uspořádanou množinu (Par(/c),
Budeme dále potřebovat nějaké lineární uspořádání množiny Par(/c), které by bylo kompatibilní s tímto právě definovaným uspořádáním dominancí. Příkladem takového lineárního uspořádání je lexikografické uspořádání, které budeme značit symbolem ^. Toto uspořádání je definováno následovně. Jestliže ji = (/ii, /i2, • • •, Mr) a A = (Ai, A2,..., As) jsou dva rozklady čísla k, pak klademe ji ^ A, jestliže buďto ji = A, anebo pro nějaké j ^ 1 platí
Dostáváme tak lineárně uspořádanou množinu (Par(/c), ^). Je snadné se přesvědčit, že takto definované lexikografické uspořádání ^ je skutečně kompatibilní s částečným uspořádáním dominancí ^, totiž že pro libovolné dva rozklady n a A čísla k splňující n ^ A platí n ^ A.
Je-li A = (Ai, A2,..., As) rozklad čísla k a je-li splněno £(X) ^ a?, definujeme homogenní symetrický polynom at7a(xi,X2, ... , xn) stupně k v proměnných xi, X2,..., xn předpisem
kde suma běží přes všechny vzájemně různé permutace a = (ai, «2,..., an) složek posloupnosti A = (Ai, A2,..., As, 0, 0,..., 0), kterou bereme jako posloupnost délky n. Polynom at7a(xi, X2,..., xn) nazýváme monomiální symetrický polynom.
jl\ — Ai, 112 — A2
/iy_l   - Ay_l
QL
Je-li nyní f libovolný homogenní symetrický polynom stupně k v proměnných xi,x2,... , xn, takže polynom f je prvkem vektorového podprostoru A^[xi, x2,..., x^], a je-li navíc splněno k ^ n, pak f je očividně lineární kombinací monomiálních symetrických polynomů m\(xi,X2,..., xn), kde A probíhá všechny rozklady čísla k, přičemž koeficienty jsou nějaké prvky tělesa M. Navíc takové vyjádření polynomu f ve tvaru lineární kombinace monomiálních symetrických polynomů je jediné. Odtud plyne, že množina monomiálních symetrických polynomů {m\(xi,X2,..., x„) : A h k} tvoří bázi vektorového prostoru A^[xi,x2,..., x„]. Je tedy dimenze tohoto vektorového prostoru rovna počtu prvků množiny Par(/c) všech rozkladů čísla k.
Definujme teď ještě jinou množinu homogenních symetrických polynomů, značme je p\(xi,X2,..., x„), kde A probíhá množinu Par(/c) všech rozkladů čísla k, následujícím způsobem. Předpokládáme i nadále, že je splněno k ^ n. Začneme tím, že připomeneme, že pro každé kladné celé číslo h jsme definovali sumu mocnin proměnných s/,, anebo podrobněji s/,(xi,x2,...,x„), předpisem
sh=xf + x!l + -'+xj;.
Pak pro každý rozklad A = (Ai, A2,..., A^) daného čísla k, kde ^ = Í{X) je délka rozkladu A, klademe
Pa(xi,x2, ... ,xn) — S\1S\2 • • • S\q.
Směřujeme nyní k tomu ukázat, že pak množina symetrických polynomů {Pa(xi,X2, ... ,xn) : A h k} tvoří jinou bázi našeho vektorového prostoru
Ar[*i,x2, • • • ,x„].
Buď M neprázdná konečná množina. Uspořádaným rozkladem této množiny M rozumíme každou posloupnost tt = (61, 62,..., B^) neprázdných vzájemně disjunktních podmnožin množiny M, jejichž sjednocením je celá množina M, takže pak soubor podmnožin {61, 62,..., B^} tvoří obvyklý rozklad množiny M. Podmnožiny 61, 62,..., B^ nazýváme bloky uspořádaného rozkladu tt.
Tvrzení.
Necht A = (Ai, A2,..., Xq) je rozklad čísla k, kde <; = Í{X) je délka tohoto rozkladu. Poněvadž množina polynomů {mfJ : jjl h k} tvoří bázi vektorového prostoru A^,[xi,X2,... ,xn], existují jednoznačně určená reálná čísla r\^f kde n probíhá všechny rozklady čísla k, taková, že platí
m
Buď fi = (/ii, /i2, • • •, Hx) kterýkoliv z těchto rozkladů čísla k, kde k = l(n) je délka tohoto rozkladu. Pak číslo     je rovno počtu všech těch uspořádaných rozkladů tt = (61, 62,..., B^) množiny čísel {1,2,...,     pro něž platí
lij = ^2 Pro všechna j = 1, 2.
ieBj
Důkaz
Připomeňme, že podle našeho předpokladu je k ^ n. Pak ovšem máme £(/i) ^ a?, čili k ^ n. Je jasné, že pak číslo      je koeficientem člene x^xtf2 .. • x^
sA<_, to jest v součinu (Ex^2) ''' (Z)***)-
v rozvoji tohoto součinu, vybereme pro každé
v součinu p\ = s\1s\2 • Abychom dostali člen x^xtf2
1,2
7=
C sčítanec x^J z činitele J2X^J takovým způsobem, aby bylo splněno
Y[.;Xj.J = x^x^2 ...      . Pro každé t = 1, 2,..., k pak položme Bt = {j £ {1, 2, ...,<;} : /) = ŕ}. Potom 7r = (Bi, 62,..., B^) bude uspořádaným rozkladem množiny čísel {1,2,..., ^} splňujícím poslední výše uvedenou podmínku. Naopak zase každý takový uspořádaný rozklad tt dá popsaným
způsobem vzniknout členu x^x^2
□
Věta.
Necht X = (Ai, A2,..., A^) je rozklad čísla k, kde <; = Í{X) je délka tohoto rozkladu. Pak, jak už bylo řečeno výše, existují jednoznačně určená reálná čísla r\^, kde n probíhá všechny rozklady čísla k, taková, že platí
Px = rx^
m
Pak platí r\^ = O s případnou výjimkou těch rozkladů n čísla k, pro něž je A ^ fi. Naproti tomu máme
r\\ = A77i(A)! A772(A)! • • • A77/c(A)!,
kde pro každé i E {1,2,..., k} je at7;(A) počet těch složek rozkladu X, které jsou rovny i. Odtud plyne, že množina polynomů {p\ : A h k} tvoří bázi vektorového prostoru A^[xi,...,xn\.
Jestliže [i = (/ii, /i2, • • •, Hx) je rozklad čísla k takový, že r\^ 7^ 0, pak podle předchozího tvrzení existuje alespoň jeden uspořádaný rozklad 7T = (61, 62,..., B^) množiny čísel {1,2,..., ^} takový, že platí fij = J2ieBj ^' pro všechna j = 1, 2,..., >c. Vezměme kterékoliv číslo t £ {1, 2,..., <;}.
Nechť B/:L,..., B;u jsou všechny ty vzájemně různé bloky uspořádaného rozkladu
7T, které obsahují alespoň jedno z čidel 1, 2,..., £. Z poslední podmínky uvedené
výše v tomto důkazu plyne, že     + • • • +     ^ Ai + A2 + • • • + Ař. Kromě toho
z faktu, že £ ^ z/ a /ii ^ /i2 ^ ■ ■ ■ ^      zřejmě plyne, že
Mi + M2 + • • • + Mí ^ M/i + ''' + Hiv ■ Dohromady tedy dostáváme, že
Mi + M2 + • • • +    ^ ^1 + ^2 + • • • + Ař. Poněvadž £ bylo libovolné číslo
z množiny {1,2,...,     celkem to dává, že A ^ ijl v uspořádání dominancí.
Pokud jde o hodnotu r\A, pak v úvahách z předchozího odstavce pro případ, že [i = A, zřejmě musí být všechny bloky Bi, 62,..., B^ uspořádaného rozkladu 7r jednoprvkovými množinami (poznamenejme zde, že pak totiž >c = ^). Navíc pro každé j G {1, 2,..., x} má platit, že fij = A/, kde / G {1,2,..., ^} je to číslo, pro něž Bj = {/}. Poněvadž nyní n = A a navíc máme Ai ^ A2 ^ • • • ^ A^, plyne odtud, že uspořádaný rozklad tt = (Bi, 62,..., B^) množiny čísel {1,2,..., ^} se od uspořádaného souboru množin ({1}, {2},..., {<;}) může lišit nanejvýš nějakou permutací prvních mk(X) položek tvaru {/}, pro něž A/ = /c, potom nějakou permutací následujících A7i/c_i(A) položek tvaru {/}, pro něž A/ = k — 1, atd., až nakonec nějakou permutací posledních at7i(A) položek tvaru {/}, pro něž A/ = 1. Celkem to dává at7i(A)! at72(A)! • • • ati/c(A)! možností, jak může vypadat uspořádaný rozklad 7r, a tomuto počtu je pak také rovno číslo r\\.
Konečně uvažme matici R = (r\/z)A AiGpar(/c)- Indexy řádků a sloupců v této matici
nechť jsou lineárně uspořádány lexikografickým uspořádáním ^ množiny rozkladů
Par(/c). Viděli jsme dříve, že toto uspořádání je zúplněním částečného uspořádání
^ dominancí na této množině Par(/c). Z prvního odstavce tohoto důkazu tak
plyne, že R je horní trojúhelníková matice. Z druhého odstavce tohoto důkazu pak
plyne, že všechny prvky na hlavní diagonále matice R jsou nenulové. Dohromady
to ukazuje, že R je regulární matice. Z definice prvků      matice R je patrno, že
matice R je maticí přechodu od soustavy polynomů {p\ : A h k} k soustavě
polynomů {m\ : A h k}. Ale, jak jsme už dříve viděli, množina polynomů
{m\ : A h k} tvoří bázi vektorového prostoru A^[xi,x2,... ,xn]. Z tohoto důvodu
také množina polynomů {p\ : A h k} tvoří bázi vektorového prostoru
A^[xi,x2,... ,x„]. □
Z právě uvedené věty odvodíme ještě následující důsledek. Připomeňme, že až dosud jsme předpokládali, že k ^ n. Nyní ale budeme pracovat se silnějším předpokladem. Budeme žádat, aby platilo k2 ^ n. Pak obdržíme následující fakt.
Ke každému symetrickému polynomu f z okruhu polynomů M[xi, X2,..., xn] stupně nejvýše k existuje jediný polynom q v okruhu polynomů M[xi, X2,..., x^] stupně nejvýše k takový, že platí f = g(si, S2,..., Sk).
Důkaz.
Již jsme viděli, že symetrický polynom /"je součtem konečného počtu homogenních symetrických polynomů různých stupňů, které nepřevyšují hodnotu k. Pokud dokážeme, že uvedený důsledek platí pro všechny sčítance v tomto součtu, budeme mít tento důsledek dokázán i pro samotný symetrický polynom f. Můžeme tedy dále předpokládat, že /"je homogenní symetrický polynom stupně /?, kde h ^ k. Kvůli jednoduchosti provedeme důkaz pouze v případě, kdy h = k. Pro menší hodnoty h by se důkaz vedl obdobně. Je tedy nyní f prvkem vektorového prostoru A^[xi,X2,..., x„].
Podle předchozí věty je množina polynomů {p\ : A h k} bází vektorového prostoru A^[xi, X2,..., x„]. Existují tedy jednoznačně určené prvky c\ tělesa M, kde A probíhá všechny rozklady čísla k, takové, že platí
Xhk
—/
11/14
Ovšem polynomy p\ jsou podle definice rovny polynomům
Pa — s\xs\2 • • • s\q,
kde A = (Ai, A2,..., A^) a ^ = £(X) je délka rozkladu A. Poněvadž A je rozklad
čísla k, máme Ai ^ /c, A2 ^ /c, ..., A^ ^ k. Vznikne tedy polynom S\1S\2 • • • sa?
dosazením polynomů si, S2,..., Sk za proměnné xi, X2,..., Xk do člene
xaiXa2 • • -x^. Tento poslední člen je ovšem prvkem okruhu polynomů
I^[xi,X2,... ,Xk] stupně nejvýše k. Celkem to tedy znamená, že samotný polynom
f vznikne dosazením polynomů Si,S2, ...,s^ za proměnné xi,X2,..., x/<- do
polynomu
Ah/c
což je ale prvek okruhu polynomů M[xi,X2,... ,Xk] stupně nejvýše k. Zbývá ozřejmit, že tento polynom q je určen jednoznačně.
Buď tedy q libovolný polynom z okruhu M[xi,X2,..., x/J stupně nejvýše k takový, že platí f = q(si,S2,..., S/J. Uvažme libovolný člen x^x^2 • • • x£k tohoto polynomu; tento člen je ovšem stupně nejvýše k. Dosaďme do tohoto člene polynomy si, S2,..., Sk za proměnné xi, X2,..., x^. Tak obdržíme polynom
sľls22 "'skk stLJPně nejvýše k2.
Pro každé celé číslo / G {0,1,2,..., k2} označme symbolem r-, polynom, který vznikne tím způsobem, že z polynomu q vybereme sumu všech těch jeho členů x^x^2 • • • x^k i s jejich koeficienty, pro něž stupeň polynomu s^s^2 • • • s^k je roven právě /. Pak jistě platí q = rg + r\ + ^ + • • • + rk2. Poněvadž f = q(si, S2,..., s/c) je homogenní symetrický polynom stupně /c, plyne odtud, že pro každé / G {0,1, 2,..., k — 1, k + 1,..., /c2} platí r,(si, S2,..., S/c) = 0, zatímco Oc(si, ^2,.. •, s/c) =    Uvažme znovu kterýkoliv člen x^x^2 • • • x£k jednoho z polynomů r,- pro / G {0,1, 2,..., /c2}. Pak dostáváme
kde [i = (/ii, /i2, • • •,      je ten rozklad čísla /, v němž prvních ak složek je rovno /c, dalších ak-i složek je rovno k — 1, atd., až posledních a\ složek je rovno 1. To znamená, že s^s^2 • • • s^k je polynom pM z vektorového prostoru Ajjxi, X2,..., xn\. Je tedy polynom r,(si, S2,..., sk) lineární kombinací polynomů pM pro nějaké rozklady ijl čísla /. Přitom koeficienty v této lineární kombinaci jsou koeficienty odpovídajících členů x^lx^2 • • • x^k ve vyjádření polynomu r,. Ovšem poněvadž / ^ a?, podle předchozí věty množina polynomů {pM : /i h /} tvoří bázi vektorového prostoru AjJxi,X2,... ,xn]. Je-li tedy / 7^ /c, takže n{si, ^2,..., s/c) = 0, musí všechny koeficienty v dotyčné lineární kombinaci být nulové. To ale znamená, že všechny koeficienty v polynomu r, jsou nulové, takže r, je nulový polynom pro všechna / G {0,1, 2,..., k — 1, k + 1,..., /c2}.
Zbývá tak už jenom polynom />, pro nějž platí /^(si, S2,..., S/J = Analogická úvaha jako předtím ukazuje, že pak polynom /^(si^,... , S/c) je nějakou lineární kombinací polynomů p\ pro některé rozklady A čísla k. Přitom koeficienty v této lineární kombinaci jsou koeficienty odpovídajících členů x^x^2 • • • x^k ve vyjádření polynomu />. Podle předchozí věty ale množina polynomů {p\ : A h k} tvoří bázi vektorového prostoru A^[xi,X2,...,x„]. To znamená, že dotyčné koeficienty ve zmíněné lineární kombinaci jsou určeny jednoznačně. Připomeňme znovu, že máme /^(si^,... , s/c) = f. Vrátíme-li se nyní k úvahám provedeným v předchozím odstavci tohoto důkazu, vidíme, že tam jsme polynom f vyjádřili jako lineární kombinaci zmíněných polynomů p\ s jistými koeficienty c\, které jsme následně použili v definici polynomu q. Ted' z toho, že jsou tyto koeficienty určeny jednoznačně, plyne rovnost polynomů    = q. Celkem to nakonec dává potřebnou rovnost polynomů q = q. □
í