Pictură tânără

Young tableaux sunt obiecte combinatorie joacă un rol important în teoria reprezentărilor grupurilor și în teoria funcțiilor simetrice . Ei fac posibilă , în special , pentru a construi reprezentările ireductibile ale grupului de simetrie , precum și cele ale grupării liniare generale pe domeniul de complecși . Tabelele lui Young au fost introduse de Alfred Young , matematician la Universitatea Cambridge , în 1900. Au fost aplicate studiului grupului simetric de către Georg Frobenius în 1903. Teoria lor a fost dezvoltată de mulți matematicieni, printre care Percy MacMahon , WVD Hodge , G . de B. Robinson , Gian-Carlo Rota , Alain Lascoux , Marcel-Paul Schützenberger și Richard P. Stanley .

Definiție

Diagrama lui Young

O diagramă Young (denumită și diagramă Ferrers) este o colecție finită de cutii sau celule, organizate în linii aliniate la stânga, cu proprietatea că lungimile liniilor cresc larg (fiecare linie este la fel de lungă sau mai lungă decât precedenta) . Secvența lungimilor liniilor oferă o partiție a întregului care este numărul total de celule ale diagramei. Imaginea din dreapta prezintă diagrama asociată scorului . Partiția se numește forma diagramei. Includerea unei diagrame Young în alta definește o structură de zăbrele cunoscută sub numele de zăbrele lui Young . Dacă enumerăm numărul de celule dintr-o diagramă de coloane, vom obține o altă partiție, numită partiția conjugată sau transpusă a . λ{\ displaystyle \ lambda}nu{\ displaystyle n}(5,4,1){\ displaystyle (5,4,1)}λ{\ displaystyle \ lambda}λ{\ displaystyle \ lambda}

Celulele unei diagrame Young sunt, în general, indexate de perechi de numere întregi, primul index indicând rândul, al doilea coloana. Cu toate acestea, există două convenții pentru reprezentarea acestor diagrame, prima care plasează fiecare rând sub precedentul, al doilea care îl plasează deasupra. Prima convenție este utilizată în principal de anglofoni , a doua este adesea preferată de francofoni  ; de aceea aceste notații se numesc notație engleză și notație franceză . Notarea în limba engleză corespunde matricelor, notația franceză la coordonatele carteziene.

Pictură tânără

Pentru un număr natural , denotăm setul de numere întregi de la la . Un tabel al lui Young se obține prin umplerea celulelor unei diagrame a lui Young cu numere întregi. Inițial, intrările erau variabile ; acum folosim numere întregi. În aplicația lor originală pentru reprezentări ale grupului simetric , matricile lui Young au intrări separate, asociate în mod arbitrar cu celulele matrice. O matrice a lui Young este standard atunci când valorile intrărilor sunt două câte două distincte și sunt numere întregi de la 1 la numărul total de celule și astfel încât intrările cresc strict în rânduri și coloane. O matrice este semi-standard atunci când rândurile cresc în sens larg și coloanele cresc în sens strict și când sunt prezente toate numerele întregi de la 1 la valoarea maximă. m{\ displaystyle m}[m]{\ displaystyle [m]}1{\ displaystyle 1}m{\ displaystyle m}X1,X2,X3,...{\ displaystyle x_ {1}, x_ {2}, x_ {3}, \ ldots}nu{\ displaystyle n}

Greutatea unei matrice este o secvență care, pentru fiecare valoare prezentă în matrice a lui Young, indică numărul de ori apare acolo. Astfel, o matrice Young semi-standard este o matrice standard atunci când greutatea sa este . (1,1,...,1){\ displaystyle (1,1, \ ldots, 1)}

Tânăra stânga la masă

O formă din stânga este o pereche de partiții astfel încât diagrama Young a partiției conține diagrama Young a partiției ; asta înseamnă că dacă și , atunci pentru orice . O formă din stânga este notată sau . Diagrama din stânga a unei forme din stânga este diferența setată a diagramelor Young ale și ale  : conține casetele care sunt în diagrama și nu în diagrama lui . Un tabel al lui Young stânga este obținut prin completarea casetelor din diagrama din stânga corespunzătoare. Din nou, un tabel este semi-standard dacă intrările cresc strict în coloană și cresc în linii mari. Dacă în plus, toate numerele întregi de la 1 la numărul de celule apar exact o dată, tabelul este standard. (λ,μ){\ displaystyle (\ lambda, \ mu)}λ{\ displaystyle \ lambda}μ{\ displaystyle \ mu}λ=(λ1,λ2,...){\ displaystyle \ lambda = (\ lambda _ {1}, \ lambda _ {2}, \ ldots)}μ=(μ1,μ2,...){\ displaystyle \ mu = (\ mu _ {1}, \ mu _ {2}, \ ldots)}λeu≥μeu{\ displaystyle \ lambda _ {i} \ geq \ mu _ {i}}eu{\ displaystyle i}λ/μ{\ displaystyle \ lambda / \ mu}λ∖μ{\ displaystyle \ lambda \ setminus \ mu}λ{\ displaystyle \ lambda}μ{\ displaystyle \ mu}λ{\ displaystyle \ lambda}μ{\ displaystyle \ mu}

Forma stângă a unei diagrame Young stânga nu poate fi întotdeauna determinată din setul de celule din diagramă. De exemplu, dacă și , diagrama de formă din stânga constă dintr-o singură celulă în poziție . Dar această celulă poate fi obținută într-un număr infinit de alte moduri, de exemplu prin prelungirea primei linii a celor două forme sau prin adăugarea altor linii identice. De asemenea, dacă o diagramă este alcătuită din mai multe părți fără legătură, aceasta poate fi obținută din mai multe forme diferite. λ=(5,4,2,1){\ displaystyle \ lambda = (5,4,2,1)}μ=(5,3,2,1){\ displaystyle \ mu = (5,3,2,1)}λ/μ{\ displaystyle \ lambda / \ mu}(2,4){\ displaystyle (2,4)}

Toată forma stângă a tabelului semi-standard cu intrări pozitive determină o succesiune de scoruri (sau diagrame Young) după cum urmează: începem cu ; în pasul -th, îl luăm ca partiție pe a cărui diagramă se obține prin adăugarea tuturor celulelor a căror valoare conține ; scorul final este scorul . Orice pereche consecutivă de diagrame din această secvență definește o formă din stânga a cărei diagramă conține cel mult o intrare în fiecare coloană (deoarece intrările cresc în coloană). Astfel de forme se numesc dungi orizontale ( dungi orizontale în engleză). Această serie de partiții determină în întregime . T{\ displaystyle T}λ/μ{\ displaystyle \ lambda / \ mu}μ{\ displaystyle \ mu}eu{\ displaystyle i}μ{\ displaystyle \ mu}T{\ displaystyle T}≤eu{\ displaystyle \ leq i}λ{\ displaystyle \ lambda}T{\ displaystyle T}

Extensie

În loc să luăm valorile matricei lui Young în numere întregi, le luăm în orice alfabet , complet ordonat. Când citim succesiv rândurile unui tabel Young semi-standard, obținem o succesiune de cuvinte în creștere în sensul larg al acestui alfabet. Fiecare cuvânt din această secvență domină următorul în sensul că și mai mult pentru . Pentru diagrama Young a scorului (3,3,1), cuvintele liniilor sunt și fiecare domină următoarea. Produsul cuvintelor rând este în sine denumit uneori un tablou. În exemplul nostru, acesta este cuvântul . Corespondența dintre cuvinte și tabelul semi-standard este unu-la-unu: pentru a decoda cuvântul, este suficient de fiecare dată să se ia cel mai lung prefix care crește în sens larg. În tabelul de formulare opus , tabelul de cuvinte este descompus în rânduri, fiecare dintre ele dominând următorul. X=X1⋯Xr{\ displaystyle x = x_ {1} \ cdots x_ {r}}y=y1⋯ys{\ displaystyle y = y_ {1} \ cdots y_ {s}}r≤s{\ displaystyle r \ leq s}Xeu<yeu{\ displaystyle x_ {i} <y_ {i}}1≤eu≤r{\ displaystyle 1 \ leq i \ leq r}4234122{\ displaystyle 4 \, 234 \, 122}4234122{\ displaystyle 4234122}(7,6,4,2){\ displaystyle (7,6,4,2)}684556223357111444{\ displaystyle 684556223357111444}

Proprietăți combinatorii

Algoritmul Schensted

Schensted Algoritmul este un algoritm care permite de a insera un întreg într - o matrice semi-standard , sau standard, astfel încât să se obțină o nouă matrice de același tip. Acest algoritm permite:

• să furnizeze tuturor tabelelor o lege de compoziție internă , prin inserarea succesivă a elementelor unui tabel în altul.
• pentru a stabili o bijecție între permutări și, mai general, secvențe de numere întregi pozitive și perechi de matrice standard (resp. semi-standard) tinere de aceeași formă, cunoscute sub numele de corespondență Robinson-Schensted-Knuth .(P,Î){\ displaystyle (P, Q)}
• pentru a induce o relație de echivalență pe mulțimea secvențelor finite ale numerelor întregi pozitive. Două cuvinte sunt echivalente dacă în corespondența Robinson-Schensted au chiar tabelul P.

Viennot a dat o construcție geometrică a corespondenței Robinson-Schensted între permutații și perechi de tabele standard Young de aceeași formă.

Relațiile Knuth

Din studiul acestei relații de echivalență pe cuvinte de lungime 3, Donald Knuth a definit reguli de rescriere pentru setul de cuvinte de pe . Aceste reguli de rescriere induc, de asemenea, o relație de echivalență, iar Knuth a arătat că coincide cu relația Schensted. O consecință importantă a acestei teoreme este că legea compoziției care rezultă din algoritmul Schensted are toate proprietățile necesare pentru a da un set de matrice o monoid structură  : monoid plaxic . [m]{\ displaystyle [m]}

Formula pătratelor

Cele Formula paranteze ( formula cârlig lungime în limba engleză) este o formulă pentru a calcula numărul de formular standard de tableaux dat. Acest număr este important, deoarece numărul matricilor standard Young de formă dată este egal cu dimensiunea reprezentării ireductibile a grupului simetric corespunzător unei partiții de . λ{\ displaystyle \ lambda}Snu{\ displaystyle S_ {n}}λ{\ displaystyle \ lambda}nu{\ displaystyle n}

Pătratul set asociat cu o celulă de forma diagramei Ferrers este compus din această celulă și din toate celulele din dreapta și de dedesubt (în notație engleză), respectiv în dreapta și deasupra (în notație franceză) a celulei . Lungimea pătrat (în limba engleză cu cârlig lungime ) este numărul de celule care compun pătrat. În exemplul de partiție , celula din stânga sus are 5 celule pe același rând și 3 pe aceeași coloană. Prin urmare, lungimea pătratului este de 7. X{\ displaystyle x}Da(λ){\ displaystyle Y (\ lambda)}λ{\ displaystyle \ lambda}X{\ displaystyle x} h(X){\ displaystyle h (x)}λ=(5,4,1){\ displaystyle \ lambda = (5,4,1)}

Notăm numărul de matrice standard de formă Young , pentru o partiție de . fλ{\ displaystyle f ^ {\ lambda}}λ{\ displaystyle \ lambda}nu{\ displaystyle n}

Formula pătratelor  -  Fie numărul de matrice standard de formă Young pentru o partiție de . Deci avem fλ{\ displaystyle f ^ {\ lambda}}λ{\ displaystyle \ lambda}nu{\ displaystyle n}

fλ=nu!∏X∈Da(λ)h(X){\ displaystyle f ^ {\ lambda} = {\ frac {n!} {\ prod _ {x \ în Y (\ lambda)} h (x)}}}.

Figura opusă oferă lungimile parantezelor pentru partiție . Noi obținem λ=(5,4,1){\ displaystyle \ lambda = (5,4,1)}

fλ=10!7⋅5⋅4⋅3⋅1⋅5⋅3⋅2⋅1⋅1=288.{\ displaystyle f ^ {\ lambda} = {\ frac {10!} {7 \ cdot 5 \ cdot 4 \ cdot 3 \ cdot 1 \ cdot 5 \ cdot 3 \ cdot 2 \ cdot 1 \ cdot 1}} = 288 .}

Prin urmare, există 288 tabele Young standard ale acestei forme și există tot atâtea reprezentări ireductibile ale grupului simetric S 10 corespunzător acestei partiții.

Formula pătrată este numită și teorema Frame-Robinson-Thrall conform autorilor unei dovezi. Dovada combinatorie, folosind jocul de tachinare al lui Schützenberger, a fost dată de Novelli, Pak și Stoyanovskii. De fapt, s-au dat multe dovezi, printre care și alte dovezi prin bijecție. Dovada lui Novelli, Pak și Stoyanovskii este considerată de Krattenthaler ca fiind cea mai naturală: „  Bijecția prezentată în lucrarea examinată trebuie considerată ca bijecția cârligului natural  ”. Cărțile de referință, cum ar fi Sagan 2001 sau Fulton 1997 , conțin dovezi. O demonstrație de bază și detaliată, realizată de Jason Bandlow, există online.

Formula sumei de pătrate

O formulă apropiată de formula pătrată este următoarea:

Suma pătratelor  -  Fie un număr întreg. Avem : nu{\ displaystyle n}

∑λ(fλ)2=nu!{\ displaystyle \ sum _ {\ lambda} (f ^ {\ lambda}) ^ {2} = n \,!},

în cazul în care suma este de peste toate partițiile de , și este numărul de tineri matrice standard de formă . λ{\ displaystyle \ lambda}nu{\ displaystyle n}fλ{\ displaystyle f ^ {\ lambda}}λ{\ displaystyle \ lambda}

De exemplu, pentru partițiile (3), (2,1) și (1,1,1) ale întregului număr 3, există respectiv 1, 2 și 1 matrice standard (x) Young a acestei forme, d 'unde total 1 + 4 + 1 = 6 = 3!. O dovadă a acestei formule este bine realizată prin intermediul rețelelor lui Young .

Prezentare generală a aplicațiilor

Tablourile lui Young au multe aplicații în combinatorică , teoria reprezentării și geometria algebrică . Au fost explorate diferite moduri de numărare a matricelor tinere și au condus la definirea și identitățile polinoamelor Schur . Au fost dezvoltați mulți algoritmi, inclusiv jocul teaser Schützenberger , corespondența Robinson-Schensted-Knuth sau construcția geometrică Viennot . Lascoux și Schützenberger au introdus un produs asociativ pe setul de matrice Young semi-standard care au înzestrat acest set cu o structură monoidică , numită monoid plaxic .

În teoria reprezentării, tabelele standard de dimensiuni Young descriu bazele reprezentărilor ireductibile ale grupului simetric pe litere. Bazele monomiale standard ale unei reprezentări ireductibile a dimensiunii finite a grupului liniar general sunt parametrizate de setul de tabele Young semi-standard de formă fixate pe alfabet . Acest lucru are consecințe importante în teoria invariantă . Regula Littlewood-Richardson , care descrie, printre altele, descompunerea produsului tensorial reprezentărilor ireductibile în componente ireductibile este formulată în termeni de tabele Young ramase. k{\ displaystyle k}k{\ displaystyle k} GLnu{\ displaystyle {\ text {GL}} _ {n}}{1,2,...,nu}{\ displaystyle \ {1,2, \ ldots, n \}}GLnu{\ displaystyle {\ text {GL}} _ {n}}

Aplicațiile în geometria algebrică se concentrează pe calculul lui Schubert , Grassmannianii și varietățile de steaguri . Unele clase de cohomologie importante pot fi reprezentate de polinoame Schubert  (în) și descrise în termeni de tablouri Young.

Aplicații pentru gruparea reprezentărilor

Reprezentări ale grupului simetric

Reprezentarea GL ( E )

Dacă E este un spațiu vector-vectorial de dimensiune m și λ o partiție, definim modulul Schur E λ ca fiind spațiul ℂ-vector a cărui bază este formată din setul de matrice Young de formă λ și cu valoare în [ m ]. Știind că este posibil să se identifice o matrice Young cu valori în [ m ] la un polinom de of [ X i, j | 1≤ i, j≤m ], există o acțiune naturală a GL ( E ) asupra lui Young matrici prin multiplicare matricială simplă. Modulii lui Schur sunt deci reprezentări ale GL ( E ). Putem arăta că orice reprezentare polinomială ireductibilă a GL ( E ) este izomorfă pentru un modul Schur unic.

Funcții simetrice

Cele Caracterele de moduli Schur lui (ca reprezentări ale GL ( E )) sunt simetrice polinoame numite polinoame Schur , după matematicianul rus ISSAI Schur . Tablourile lui Young oferă o modalitate elegantă de a exprima aceste polinoame. În plus, există o regulă pur combinatorie care folosește tabelele lui Young și care face posibilă descompunerea produsului a două polinoame Schur. Acest lucru implică în special faptul că tabelele permit descompunerea produsului tensor al a două reprezentări ireductibile ale GL ( E ) într-o sumă directă de reprezentări ireductibile.

Note și referințe

1. (în) Ian G. Macdonald , Funcții simetrice și polinoame Hall , OUP , al.  „Monografii matematice Oxford”,1979( ISBN  0-19-853530-9 ) recomandă cititorilor care preferă notația franceză să citească această carte „de jos în sus în oglindă”.
2. Și matricile semi-standard stânga pot fi definite ca astfel de secvențe; așa procedează Macdonald în 1979 , p.  4.
3. (în) Alain Lascoux Bernard Leclerc și Jean-Yves Thibon, "Monoidul plactic" , în M. Lothaire , Algebraic Combinatorics on Words , UPC , al.  "Enciclopedia matematicii și a aplicațiilor sale" ( nr .  90)2002( ISBN  978-0-521-81220-7 , citit online ) , p.  164-196.
4. Lascoux, Leclerc și Thibon 2002 , p.  166.
5. (în) JS Frame, Gilbert B. Robinson și Robert M. Thrall, „  Graficele cu cârlig ale grupurilor simetrice  ” , Canadian Journal of Mathematics , vol.  6,1954, p.  316-324.
6. .
7. Recenzie a articolului de Novelli, Pak și Stoyanovskii în MathSciNet . Acces limitat.
8. (în) Jason Bandlow, „  O dovadă elementară a formulei cârligului  ” , The Electronic Journal for Combinatorics , vol.  15,2008( citește online ).

Bibliografie

• (ro) William Fulton , Young tableaux , Cambridge University Press , col.  „London Mathematical Society Texts Student” ( nr .  35)1997( ISBN  978-0-521-56144-0 și 978-0-521-56724-4 , Recenzii matematice  1464693 )
• (în) Donald E. Knuth , „  Permutări, matrice și tablouri tinere generalizate  ” , Pacific Journal of Mathematics , vol.  34,1970, p.  709–727 ( ISSN  0030-8730 , Math Reviews  0272654 , citiți online )
• (ro) Donald E. Knuth , The Art of Computer Programming , vol.  3: Sortare și căutare ,1998, A 2 -a  ed. [ detaliul ediției ]
• (ro) Bruce E. Sagan  (ro) , The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions , New York / Berlin / Heidelberg etc., Springer, col.  „  GTM  ” ( nr .  203)2001, A 2 -a  ed. , 238  p. ( ISBN  0-387-95067-2 )
• (ro) Richard P. Stanley , Enumerative Combinatorics , vol.  2 [ detaliu ediții ] ( prezentare online )

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">