Таблиці Келі — Вікіпедія
Таблиця Келі — таблиця, яка описує структуру скінченних алгебраїчних систем шляхом розміщення результатів операції в таблиці, яка нагадує таблицю множення. Названа в честь англійського математика Артура Келі. Таблиця має важливе значення в дискретній математиці, зокрема, в теорії груп. Таблиця дозволяє визначити деякі властивості групи, наприклад, чи є група абелевою, знайти центр групи і обернені (симетричні) елементи для елементів групи.
В вищій алгебрі таблиці Келі можуть також використовуватися для визначення бінарних операцій в полях, кільцях і інших алгебраїчних структурах.
Простий приклад таблиці Келі для групи {1, −1} з звичайним множенням:
× | 1 | −1 |
---|---|---|
1 | 1 | −1 |
−1 | −1 | 1 |
Історія[ред. | ред. код]
Таблиці Келі вперше з'явилися в статті Келі "On The Theory of Groups, as depending on the symbolic equation θ n = 1" в 1854 році. В цій статті це були просто таблиці, які використовувалися з ілюстративною метою. Називати таблицями Келі їх почали пізніше, в честь їх творця.
Структура[ред. | ред. код]
Оскільки чимало таблиць Келі описують групи, які не є абелевими, добуток ab не обов'язково рівний добутку ba для всіх a і b в групі. Щоб уникнути плутанини, приймається, що множник, який відповідає рядкам, йде першим, а множник, який відповідає стовпцям — другим. Наприклад, перетин рядка a і стовпця b — це ab, а не ba, що показано в наступному прикладі:
* | a | b | c |
---|---|---|---|
a | a2 | ab | ac |
b | ba | b2 | bc |
c | ca | cb | c2 |
Келі в своїй роботі в першому рядку і першому стовпці розміщував нейтральний елемент, що дозволяло йому не виділяти окремого рядка і стовпця з переліком елементів, як це видно в прикладі вище. Наприклад, ця ж таблиця виглядала так:
a | b | c |
b | c | a |
c | a | b |
В цьому прикладі циклічної групи Z3 елемент a є нейтральним елементом, тому він знаходиться в верхньому лівому куті таблиці. Легко побачити, наприклад, що b2 = c і що cb = a. Незважаючи на це, більшість сучасних текстів, включаючи і цю статтю, включає заголовний рядок і стовпець для більшої зрозумілості.
Властивості і використання[ред. | ред. код]
Комутативність[ред. | ред. код]
Таблиця Келі показує нам, чи є група абелевою. Оскільки групова операція в абелевій групі комутативна, група є абелевою в тому і тільки в тому випадку, коли її таблиця Келі є симетричною (відносно діагоналі). Циклічна група порядку 3 і вище, а також {1, −1} по звичайному множенню, обидві є прикладами абелевих груп, і симетрія їх таблиць Келі це доводить. А ось найменша неабелева діедральна група шостого порядку[en] не має симетрії в таблиці Келі.
Асоціативність[ред. | ред. код]
Оскільки асоціативність в групах наявна за визначенням, часто на неї розраховують і в таблицях Келі. Однак таблиці Келі можна використовувати для опису операцій в квазігрупах, в яких асоціативність не потрібна (більш того, таблиці Келі можна використовувати для опису операції в будь-якій скінченній магмі). На жаль, в загальному випадку неможливо простим оглядом таблиці визначити, асоціативна операція чи ні, на відміну від комутативності. Це обумовлено тим, що асоціативність залежить від трьох елементів в рівності, , а таблиця Келі показує добуток двох елементів. Тим не менш, тест асоціативності Лайта може дослідити асоціативність з меншими зусиллями, ніж повний перебір.
Перестановки[ред. | ред. код]
Оскільки скорочення для груп виконується (більш того, виконується навіть для квазігруп), ніякий рядок або стовпець таблиці Келі не може містити один елемент двічі. Таким чином, кожний рядок і стовпець таблиці є перестановкою елементів групи.
Щоб побачити, чому рядки і стовпці не можуть містити однакових елементів, припустимо, що a, x та y — елементи групи, причому x та y відрізняються. Тепер в рядку, який відповідає елементу a, і стовпці, який відповідає елементу x, буде знаходитися добуток ax. Аналогічно в стовпці, який відповідає y, буде знаходитись ay. Нехай два добутки рівні, тобто є рядок a, який містить два однакові елементи. За правилом скорочення ми з ax = ay можемо зробити висновок, що x = y, що суперечить вибору x і y. Для стовпців ці міркуванням також істинні. Оскільки група скінченна, за принципом Діріхле кожен елемент групи міститиметься в кожному рядку і в кожному стовпці тільки по одному разу.
Тобто таблиця Келі для групи є прикладом латинського квадрату.
Побудова таблиць Келі[ред. | ред. код]
Використовуючи структуру груп, часто можна "заповнити" таблиці Келі, які мають незаповнені поля, навіть не знаючи нічого про операції групи. Наприклад, оскільки кожен рядок і кожен стовпець повинен вміщати всі елементи групи, один відсутній елемент в рядку (або стовпці) можна заповнити, не знаючи абсолютно нічого про групу. Це показує, що ця властивість і деякі інші властивості груп дозволяють побудувати таблицю Келі, навіть якщо ми мало що знаємо про групу.
"Скелет нейтральних елементів" кінцевої групи[ред. | ред. код]
Оскільки в будь-якій групі, навіть в неабелевій, будь-який елемент взаємозамінний з оберненим до нього, розміщення нейтральних елементів в таблиці Келі є симетричним відносно діагоналі. Ті, що лежать на діагоналі, збігаються з оберненими до них.
Оскільки порядок рядків і стовпців в таблиці Келі довільні, зручно розміщувати їх наступним чином: починаємо з нейтрального елемента групи, який завжди збігається з оберненим до нього, потім перераховуємо всі елементи, які збігаються з оберненими до них, а потім виписуємо пари елементів (елемент і обернений до нього).
Тепер для кінцевої групи деякого порядку нескладно визначити "скелет нейтральних елементів", названий так у зв'язку з тим, що нейтральні елементи або лежать на головній діагоналі, або поблизу неї.
Відносно легко довести, що групи з різними скелетами не можуть бути ізоморфними, однак протилежне твердження - хибне (наприклад, циклічна група C8 і група кватерніонів Q не ізоморфні, хоча й мають однакові скелети).
Нехай ми маємо шість елементів групи e, a, b, c, d і f. Нехай e — нейтральний елемент. Оскільки нейтральний елемент збігається з оберненим до нього, а обернений елемент є унікальним, то повинен бути принаймні ще один елемент, який збігається з оберненим до нього. Таким чином, отримуємо наступні можливі скелети:
- все елементи збігаються з оберненими до них,
- все елементи, за винятком d і f, збігаються з оберненими до них, а ці два обернені один одному,
- a збігається з оберненим до нього, b і c обернені, d і f обернені.
В нашому випадку не існує групи першого типу порядку 6. Більш того, те, що скелет можливий, зовсім не означає, що існує група, у якої скелет збігається з ним.
Заслуговує уваги той факт (і його легко довести), що будь-яка група, в якій будь-який елемент збігається з оберненим до нього - абелева.
Заповнення таблиці за скелетом нейтральних елементів[ред. | ред. код]
Якщо заданий скелет нейтральних елементів, можна приступити до заповнення таблиці Келі. Наприклад, виберемо другий скелет групи порядку 6 із описаних вище:
e | a | b | c | d | f | |
---|---|---|---|---|---|---|
e | e | |||||
a | e | |||||
b | e | |||||
c | e | |||||
d | e | |||||
f | e |
Очевидно, що рядок e і стовпець e можуть бути заповнені одразу. Як тільки це зроблено, може виявитися необхідним (і це необхідно в нашому випадку) зробити припущення, яке може привести до суперечності, а це означатиме, що припущення є помилковим. Ми припустимо, що ab = c. Тоді:
e | a | b | c | d | f | |
---|---|---|---|---|---|---|
e | e | a | b | c | d | f |
a | a | e | c | |||
b | b | e | ||||
c | c | e | ||||
d | d | e | ||||
f | f | e |
Множачи ab = c зліва на a, отримаємо b = ac. Множення справа на c дає bc = a. Множення ab = c справа на b дає a = cb. Множення bc = a зліва на b дає c = ba, а множення справа на a дає ca = b. Після заповнення цих добутків в таблиці ми побачимо, що ad і af залишаються незаповненими в рядку a. Оскільки кожний елемент повинен з'являтися в рядку не більше одного разу, отримаємо, що ad повинен бути або d, або f. Однак цей елемент не може дорівнювати d, оскільки в протилежному випадку a був би рівним e, а нам відомо, що ці два елементи різняться. Таким чином, ad = f і af = d.
Тепер, оскільки елемент обернений до d - f, множення ad = f справа на f дає a = f2. Множення зліва на d дає da = f. Помноживши справа на a, ми отримаємо d = fa.
Після внесення всіх цих добутків таблиця Келі виглядатиме так:
e | a | b | c | d | f | |
---|---|---|---|---|---|---|
e | e | a | b | c | d | f |
a | a | e | c | b | f | d |
b | b | c | e | a | ||
c | c | b | a | e | ||
d | d | f | e | |||
f | f | d | e | a |
Оскільки кожний елемент групи повинен з'являтися в кожному рядку тільки один раз, легко помітити, що дві порожні комірки таблиці в рядку b повинні бути зайняті або d, або f. Однак в відповідних стовпцях вже присутні d і f . Таким чином, що би ми не поставили в ці поля, отримаємо повторення в стовпцях, що показує, що наше початкове припущення ab = c було хибним. Однак ми тепер знаємо, що ab ≠ c.
Залишилось два варіанти — або ab = d, або ab = f. Оскільки d і f обернені один одному і вибір букв довільний, варто очікувати, що результат буде однаковим з точністю до ізоморфізму. Без втрати загальності можна вважати, що ab = d. Якщо ми тепер отримаємо суперечність, нам прийдеться визнати, що для цього скелету немає відповідної групи.
Отримуємо нову таблицю Келі:
e | a | b | c | d | f | |
---|---|---|---|---|---|---|
e | e | a | b | c | d | f |
a | a | e | d | |||
b | b | e | ||||
c | c | e | ||||
d | d | e | ||||
f | f | e |
Перемножуючи ab = d зліва на a, ми отримуємо b = ad. Множення справа на f дає bf = a, а множення зліва на b дає f = ba. Після множення справа на a, ми отримаємо fa = b, а помноживши зліва на d, отримаємо a = db. Після внесення результатів в таблицю Келі, отримаємо (нові елементи виділено червоним):
e | a | b | c | d | f | |
---|---|---|---|---|---|---|
e | e | a | b | c | d | f |
a | a | e | d | b | ||
b | b | f | e | a | ||
c | c | e | ||||
d | d | a | e | |||
f | f | b | e |
В рядку a відсутні c і f, але оскільки af не може дорівнювати f (тоді a буде дорівнювати e), ми можемо зробити висновок, що af = c. Множення зліва на a дає f = ac, і це ми можемо помножити справа на c, що дає fc = a. Множення останнього на d зліва дає c = da, що ми можемо помножити справа на a і отримати ca = d. Аналогічно, після множення af = c справа на d, отримаємо a = cd. Оновимо таблицю (останні зміни виділено синім):
e | a | b | c | d | f | |
---|---|---|---|---|---|---|
e | e | a | b | c | d | f |
a | a | e | d | f | b | c |
b | b | f | e | a | ||
c | c | d | e | a | ||
d | d | c | a | e | ||
f | f | b | a | e |
Оскільки в рядку b відсутні c і d, а bc не може дорівнювати c, ми вираховуємо, що bc = d, внаслідок цього добуток bd повинен дорівнювати c. Множення справа на f дає нам b = cf, що можна перетворити в cb = f множенням на c зліва. Аналогічно, можна вирахувати, що c = fb і dc = b. Вносимо зміни до таблиці (внесені елементи виділено зеленим кольором):
e | a | b | c | d | f | |
---|---|---|---|---|---|---|
e | e | a | b | c | d | f |
a | a | e | d | f | b | c |
b | b | f | e | d | c | a |
c | c | d | f | e | a | b |
d | d | c | a | b | e | |
f | f | b | c | a | e |
В рядку d відсутній тільки f, тому d2 = f. Аналогічно отримуємо, що f2 = d. Ми заповнили всю таблицю і не отримали суперечності. Таким чином, ми знайшли групу порядку 6, відповідну скелету. перегляд таблиці показує, що вона не абелева. Фактично це найменша неабелева група, діедральна група D3:
* | e | a | b | c | d | f |
---|---|---|---|---|---|---|
e | e | a | b | c | d | f |
a | a | e | d | f | b | c |
b | b | f | e | d | c | a |
c | c | d | f | e | a | b |
d | d | c | a | b | f | e |
f | f | b | c | a | e | d |
Генерація матриці перестановок[ред. | ред. код]
В стандартній формі таблиці Келі порядок рядків і стовпців збігаються. Іншим методом впорядкування є розміщення стовпців таким чином, щоб n-ий стовпець відповідав оберненим елементам n-ого рядка. В нашому прикладі для D3 нам необхідно тільки переставити два останніх стовпця, оскільки тільки f і d не є оберненими до себе, зате є оберненими один до одного.
e | a | b | c | f=d−1 | d=f−1 | |
---|---|---|---|---|---|---|
e | e | a | b | c | f | d |
a | a | e | d | f | c | b |
b | b | f | e | d | a | c |
c | c | d | f | e | b | a |
d | d | c | a | b | e | f |
f | f | b | c | a | d | e |
В нашому прикладі можна створити шість матриць перестановки (всі елементи дорівнюють 1 або 0, по одній одиниці в кожному рядку і кожному стовпці). 6x6 матриця містить одиницю, якщо мітка стовпця збігається з міткою рядка, і нулі в усіх інших полях, символ Кронекера для мітки. (Зауважимо, що для рядка e отримаємо одиничну матрицю.) Наприклад, для a отримаємо таку матрицю перестановок:
e | a | b | c | f | d | |
---|---|---|---|---|---|---|
e | 0 | 1 | 0 | 0 | 0 | 0 |
a | 1 | 0 | 0 | 0 | 0 | 0 |
b | 0 | 0 | 0 | 0 | 1 | 0 |
c | 0 | 0 | 0 | 0 | 0 | 1 |
d | 0 | 0 | 1 | 0 | 0 | 0 |
f | 0 | 0 | 0 | 1 | 0 | 0 |
Це демонструє, що будь-яка група порядку n є підгрупою групи перестановок Sn порядку n!.
Узагальнення[ред. | ред. код]
Описані вище властивості залежать від деяких аксіом для груп. Таблиці Келі можна використовувати і для деяких інших алгебраїчних структур, таких як напівгрупи, квазігрупи і магми, але для них деякі вище вказані властивості не виконуватимуться.
Дивись також[ред. | ред. код]
Посилання[ред. | ред. код]
- Cayley, Arthur. "On the theory of groups, as depending on the symbolic equation θ n = 1", Philosophical Magazine, Vol. 7 (1854), pp. 40–47. Available on-line at Google Books as part of his collected works.
- Cayley, Arthur. "On the Theory of Groups", American Journal of Mathematics, Vol. 11, No. 2 (Jan 1889), pp. 139–157. Available at JSTOR.