Діаграма Янга

Перенаправити на:

• Діаграма Юнга

Діаграми Юнга — комбінаторний об'єкт, що широко використовують, окрім комбінаторики, також у теорії представлень скінченних груп, зокрема для опису представлень симетричних і загальних лінійних груп і вивчення їх властивостей. Діаграми Юнга було введено Альфредом Юнгом^[en], математиком з Кембриджського університету, 1900 року [1][2]. Згодом 1903 року їх було використано Георгом Фробеніусом для вивчення симетричних груп.

Означення

Примітка: в цій статті для діаграм і таблиць використовується спосіб запису, прийнятий в англомовних країнах .

Діаграми

Діаграма Юнга форми (5, 4, 1), Англійська нотація

Діаграма Юнга форми (5, 4, 1), Французька нотація

Діаграма Юнга (також називається діаграмою Ферре у випадках, коли замість клітинок використовують точки [3] ) — скінченний набір клітинок, вирівняних по лівій стороні, в якому довжини рядків утворюють незростаючу послідовність (кожен рядок такої ж довжини, як попередній, або коротший). Набір чисел, що складається з довжин рядків, задає розбиття λ невід'ємного цілого числа n, яке дорівнює загальній кількості клітинок діаграми. Аналогічно, про конкретно взяте розбиття λ кажуть, що воно задає форму відповідної діаграми Юнга.

Включення однієї діаграми Юнга в іншу вводить частковий порядок на множині всіх розбиттів, що задає структуру, яка називається решіткою Юнга.

Розбиття, що задається транспонованою діаграмою Юнга, називається розбиттям, пов'язаним або транспонованим до λ.

Загальноприйнято позначати клітини, використовуючи пару цілих чисел, перше з яких позначає номер рядка в діаграмі, а друге — номер стовпця у цьому рядку. Проте, існують два різних поширених варіанти того, як діаграми зображати: або розташовувати наступний рядок під попереднім, або навпаки. Перше зазвичай використовується у англомовних країнах, тоді як другий — серед франкомовних, тому ці варіанти називаються англійською нотацією і французькою нотацією відповідно .

Англійська нотація відповідає загальноприйнятій нумерації елементів матриць, а французька ближче до традиційного позначення декартових координат (хоча для діаграм Юнга вертикальна координата все ж перша). Малюнок справа в англійській нотації зображує діаграму Юнга розбиття (5, 4, 1). Пов'язане розбиття, що вимірює висоти стовпців, рівне (3, 2, 2, 2, 1).

Таблиці

Стандартна таблиця Юнга форми (5, 4, 1)

Таблицею Юнга називається діаграма Юнга, клітини якої заповнені символами з якого-небудь алфавіту, який зазвичай вважається цілком упорядкованою множиною. Найчастіше використовуються натуральні числа. В класичному застосуванні у теорії представлень симетричних груп, таблиці Юнга заповнені n різними числами, довільно вписаними в клітини діаграми. Таблиця називається стандартною, якщо числа зростають в кожному рядку і в кожному стовпці.

Кількість різних стандартних таблиць Юнга з n елементами описується числом інволюцій в симетричній групі порядку n :

1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, ... (послідовність A000085 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).

В деяких застосуваннях таблиць Юнга використовується різновид, для якого дозволяється повторення деяких чисел (а якісь не використовуються зовсім). Таблиця називається напівстандартною, якщо числа не зменшуються по горизонталі і зростають по вертикалі. Виписуючи, скільки разів кожне число з'явилося в таблиці, ми отримуємо послідовність, що називається вагою таблиці. Зокрема стандартні таблиці Юнга збігаються з напівстандартними таблицями ваги (1,1, ..., 1).

Варіації

Існують варіації означення таблиці: наприклад коли у таблиці числа строго зростають уздовж рядків, і не спадають уздовж стовпців. Таблиці зі спадаючими числами розглядаються в теорії плоских розбиттів. Існують і інші узагальнення, де клітини можуть об'єднуватися до того, як їм призначають числа.

Косі таблиці Юнга

Коса таблиця форми (5, 4, 2, 2) / (2, 1), англійська нотація

Коса форма — це пара розбиття (λ, μ), така що діаграма Юнга для λ містить діаграму для μ; для цього використовується позначення: λ/μ. Якщо λ = (λ₁, λ₂, ...) і μ = (μ₁, μ₂, ...), то вкладення діаграм означає, що μ_i ≤ λ_i для всіх i.

Коса діаграма косої форми λ/μ — теоретико-множинна різниця діаграм для λ і для μ: множина клітин, що належать діаграмі для λ але не належать діаграмі для μ. Коса таблиця форми λ/μ одержується за допомогою заповнення клітин відповідної косої діаграми; така таблиця називається напівстандартною, якщо числа не зменшуються по рядках і зростають по стовпцях; напівстандартна таблиця називається стандартною, якщо кожне число від одиниці до кількості клітин зустрічається рівно один раз.

Тоді як відображення з розбиття в їх діаграми Юнга є ін'єктивним, те ж твердження для відображення з косих форм в косі діаграми не є правильним. Наприклад, коса діаграма, що складається з єдиного квадрата в позиції (2,4) може бути отримана шляхом видалення піддіаграми μ ${\displaystyle =(5,3,2,1)}$ з діаграми μ${\displaystyle =(5,3,2,1)}$, або ще багатьма способами. Взагалі кажучи, будь-яка коса діаграма, для якої множина непустих рядків (або непустих стовпців) не є суцільною, або не містить першого рядка (або першого стовпця), одержується більш ніж з однієї косої форми. Хоча багато властивостей косих таблиць залежать тільки від заповнених квадратів, деякі можуть залежати і від косої форми. Таблиці Юнга можуть бути ототожнені з косими таблицями, для яких розбиття μ є порожнім (розбиття нуля).

Будь-яка коса напівстандартна таблиця T форми λ/μ, заповнена додатними цілими числами, породжує послідовність розбиттів (або послідовність діаграм Юнга): перший елемент — це μ, а i-й одержується додаванням усіх клітинок, що містять число, менше або рівне i; зрештою виходить діаграма λ. Будь-яка пара сусідніх форм у цій послідовності утворює косу форму, в кожному стовпці якої не більше однієї клітини; такі форми називаються горизонтальними смужками. Ця послідовність повністю визначає таблицю T, і іноді в літературі (наприклад, в книзі Макдональда) косі напівстандартні форми визначають як послідовності такого виду.

Застосування

Діаграми Юнга знаходять численні застосування в комбінаториці, теорії представлень і алгебричній геометрії. Були досліджені різні способи підрахунку числа діаграм, які привели до визначення і формул для многочленів Шура. Відомі алгоритми, що виконуються безпосередньо на діаграмах, такі як jeu de taquin («гра в квача») Шютценбергера і алгоритм Робінсона — Шенстеда. Ласку і Шютценбергер вивчили асоціативний добуток на множині напівстандартних діаграм Юнга, що приводить в підсумку до структури, відомої як плактичний моноїд.

У теорії представлень, стандартні таблиці Юнга розміру k описують базиси незвідних представлень симетричної групи S_k.

Стандартний мономіальний базис в скінченновимірному незвідному представленні загальної лінійної групи GL_n параметризується множиною напівстандартних таблиць Юнга фіксованої форми над алфавітом {1, 2, …, n}. З цього факту випливає кілька важливих наслідків для теорії інваріантів, починаючи з робіт Вільяма Ходжа по однорідним координатним кільцям грассманіанів, які були продовжені у працях Девіда Айзенбада і Джан-Карло Роти, Корадо де Кончіні, Клаудіо Процезі.

Правило Літтвуда — Річардсона, описуючи (серед іншого) розклад тензорного добутку незвідних представлень GL_n на незвідні компоненти, формулюється в термінах певних косих напівстандартних таблиць.

Застосування в алгебричній геометрії зосереджені навколо числення Шуберта на грасманіанах і многовидах прапорів.

Деякі важливі класи когомологій можуть бути представлені за допомогою многочленів Шуберта і описані в термінах діаграм Юнга.

Застосування в теорії представлень

Діаграми Юнга знаходяться у взаємно однозначній відповідності із незвідними представленнями симетричної групи (над комплексними числами). Вони надають зручний спосіб задання симетризаторів Юнга, на основі яких будується теорія представлень симетричної групи. Багато фактів про представлення можуть бути виведені з відповідних діаграм. Нижче наведено два приклади: визначення розмірності представлення і обмежені представлення.

Діаграми Юнга також параметризують незвідні поліноміальні представлення загальної лінійної групи GL_n (коли вони містять не більше n непустих рядків), а також незвідні представлення спеціальної лінійної групи SL_n (коли вони містять не більше n-1 непустих рядків) і незвідні комплексні представлення спеціальної унітарної групи SU_n (знову ж таки, коли вони містять не більше n-1 непустих рядків).

У цих випадках центральну роль відіграють напівстандартні таблиці з числами, що не є більшими за n (зокрема, їх кількість визначає розмірність представлень).

Формула гаків

Довжини гаків для клітинок розбиття 10 = 5 + 4 + 1' '

Розмірність незвідного представлення π_λ (що відповідає розбиттю λ числа n) симетричної групи S_n дорівнює кількості різних стандартних таблиць Юнга, відповідним діаграмі розбиття. Це число може бути пораховано за допомогою так званої формули гаків.

Довжиною гака hook(x) клітини x у діаграмі Y(λ) форми λ називається число клітин в тому ж рядку правіше плюс число клітин в тому ж стовпці нижче плюс один (сама клітина). За формулою гаків, розмірність незвідного представлення дорівнює n!, поділеному на добуток довжин всіх гаків діаграми:

${\displaystyle \dim \pi _{\lambda }={\frac {n!}{\prod _{x\in Y(\lambda )}\mathrm {hook} (x)}}.}$

Малюнок справа ілюструє довжини гаків для діаграми розбиття 10 = 5 + 4 + 1. Тому

${\displaystyle \dim \pi _{\lambda }={\frac {10!}{7\cdot 5\cdot 4\cdot 3\cdot 1\cdot 5\cdot 3\cdot 2\cdot 1\cdot 1}}=288.}$

Аналогічно, розмірність незвідного представлення W(λ) групи GL_r, що відповідає розбиттю λ числа n ( на не більше ніж r доданків), дорівнює кількості напівстандартних таблиць форми λ (що містять тільки числа від 1 до r), яке дається формулою:

${\displaystyle \dim W(\lambda )=\prod _{(i,j)\in Y(\lambda )}{\frac {r+ji}{\mathrm {hook} (i,j)}},}$

де індекс i нумерує рядок, а індекс j нумерує стовпець клітини. [4] Наприклад, розбиття (5,4,1) породжує розмірність відповідного незвідного представлення групи GL ₇ (обхід клітин по рядках):

${\displaystyle \dim W(\lambda )={\frac {7\cdot 8\cdot 9\cdot 10\cdot 11\cdot 6\cdot 7\cdot 8\cdot 9\cdot 5}{7\cdot 5\cdot 4\cdot 3\cdot 1\cdot 5\cdot 3\cdot 2\cdot 1\cdot 1}}=66528.}$

Обмежені представлення

Представлення симетричної групи S_n на n елементах є також представленням симетричної групи на n-1 елементі, S_n-1. Однак незвідне представлення S_n не обов'язково є незвідним представленням S_n-1, а може бути прямою сумою кількох таких представлень. Ці представлення називаються факторами обмеженого представлення.

Задача визначення розкладу обмеженого представлення даного незвідного представлення S_n, що відповідає розбиттю λ числа n, може бути розв'язаною з використанням діаграм Юнга. Для цього розглядаються всі діаграми Юнга, які можна отримати з діаграми форми λ видаленням однієї клітини (яка повинна знаходитися в кінці свого рядка і свого стовпця). Обмежене представлення тоді розкладається в пряму суму незвідних представлень S_n-1, що відповідають діаграмам, отриманим при цьому, і до того ж кожне з них у сумі зустрічається рівно один раз.

Примітки

1. Кнут, Дональд Э. (2005), Искусство программирования, Том 3: Сортировка и поиск (вид. 2ое), Вильямс, Addison-Wesley, с. 66.
2. Young, A. (1900), On quantitative substitutional analysis, Proceedings of the London Mathematical Society, Ser. 1, 33 (1): 97—145, doi:10.1112/plms/s1-33.1.97.
3. Р. Стенли Перечислительная комбинаторика. М: Мир, 1990. с. 52.
4. Predrag Cvitanović (2008). Group Theory: Birdtracks, Lie's, and Exceptional Groups. Princeton University Press., ур. 9.28 и приложение B.4

Посилання

• Yong, Alexander. What is...a Young Tableau?. — Notices of the American Mathematical Society, 2007, 54 (2). — P. 240—241.

Література

• Буфетов А. И., Житлухин М. М., Н. Е. Козин Н. Е. Диаграммы Юнга. — М. : Изд-во МЦНМО, 2013. — ISBN 978-5-4439-0077-3.
• Пилипів В. М. Теорія представлень груп та її застосування(навчальний посібник). — Івано-Франківськ: ВДВ ЦІТ Прикарпатського національного університету імені Василя Стефаника, 2008. — 156 с.
• Смирнов Е. Ю. Диаграммы Юнга, плоские разбиения и знакочередующиеся матрицы. — М. : Изд-во МЦНМО, 2014. — ISBN 978-5-4439-0137-4.
• Cvitanovic, Predrag. Group Theory: Birdtracks, Lie’s, and Exceptional Groups. — Princeton : Princeton University Press, 2008.
• Fulton, William (1997), Young Tableaux, London Mathematical Society Student Texts, т. 35, Cambridge University Press, ISBN 978-0-521-56144-0, MR 1464693.
• Fulton, William; Harris, Joe. Representation theory. A first course. — New York : Springer-Verlag, 1991. — ISBN 978-0-387-97495-8. (Lecture 4)
• Macdonald I. G. Symmetric functions and Hall polynomials. — Oxford : The Clarendon Press, Oxford University Press, 1979. — viii + 180 p. — ISBN 0-19-853530-9. MR84g:05003
• Manivel, Laurent. Symmetric Functions, Schubert Polynomials, and Degeneracy Loci. — American Mathematical Society.
• Novelli, Jean-Christophe; Pak, Igor; Stoyanovkii, Alexander V. A direct bijective proof of the Hook-length formula. — Discrete Mathematics and Theoretical Computer Science, 1997, 1. — P. 53—67.
• Sagan, Bruce E. The Symmetric Group. — Springer, 2001. — ISBN 0-387-95067-2.
• Vinberg E. B. Hazewinkel, Michiel. Encyclopedia of Mathematics. — Springer, 2001. — ISBN 978-1-55608-010-4.