Таблиці Келі
Таблиця Келі — таблиця, яка описує структуру скінченних алгебраїчних систем шляхом розміщення результатів операції в таблиці, яка нагадує таблицю множення. Названа в честь англійського математика Артура Келі. Таблиця має важливе значення в дискретній математиці, зокрема, в теорії груп. Таблиця дозволяє визначити деякі властивості групи, наприклад, чи є група абелевою, знайти центр групи і обернені (симетричні) елементи для елементів групи.
В вищій алгебрі таблиці Келі можуть також використовуватися для визначення бінарних операцій в полях, кільцях і інших алгебраїчних структурах.
Простий приклад таблиці Келі для групи {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.