Stół Cayleya

Tablica Cayleya, nazwana na cześć XIX-wiecznego brytyjskiego matematyka Arthura Cayleya , opisuje strukturę skończonej grupy poprzez ułożenie wszystkich możliwych iloczynów wszystkich elementów grupy w kwadratowej tabeli przypominającej tabliczkę dodawania lub mnożenia . Wiele właściwości grupy - takich jak to, czy jest abelowa , które elementy są odwrotnościami których elementów oraz rozmiar i zawartość środka grupy - można odkryć z jej tablicy Cayleya.

Prostym przykładem tabeli Cayleya jest tabela dla grupy {1, −1} przy zwykłym mnożeniu :

× 1 −1
1 1 −1
−1 −1 1

Historia

Tabele Cayleya zostały po raz pierwszy przedstawione w artykule Cayleya z 1854 r. „O teorii grup, jako zależnej od równania symbolicznego θ   n = 1”. W tym artykule były one określane po prostu jako tabele i miały jedynie charakter ilustracyjny - później zaczęto je nazywać stołami Cayleya, na cześć ich twórcy.

Struktura i układ

Ponieważ wiele tablic Cayleya opisuje grupy, które nie są abelowe , nie ma gwarancji, że iloczyn ab w odniesieniu do operacji binarnej grupy będzie równy iloczynowi ba dla wszystkich aib w grupie. Aby uniknąć nieporozumień, konwencja jest taka, że ​​​​czynnik oznaczający wiersz (nazywany czynnikiem bliższym ) jest pierwszy, a czynnik oznaczający kolumnę (lub dalszy czynnik ) jest drugi. Na przykład punkt przecięcia wiersza a i kolumny b to ab , a nie ba , jak w poniższym przykładzie:

* A B C
A 2 _ Ab ak
B ba b2 _ pne
C ok cb c 2

Właściwości i zastosowania

Przemienność

Tabela Cayleya mówi nam, czy grupa jest abelowa . Ponieważ operacja grupowa grupy abelowej jest przemienna , grupa jest abelowa wtedy i tylko wtedy, gdy wartości jej tabeli Cayleya są symetryczne wzdłuż jej przekątnej. Grupa {1, −1} powyżej i grupa cykliczna rzędu 3 przy zwykłym mnożeniu są przykładami grup abelowych, a sprawdzenie symetrii ich tablic Cayleya to potwierdza. Natomiast najmniejsza grupa nieabelowa, grupa dwuścienna rzędu 6 , nie ma symetrycznej tablicy Cayleya.

Asocjatywność

Ponieważ asocjatywność jest traktowana jako aksjomat w przypadku grup, często przyjmuje się ją za pewnik w przypadku tabel Cayleya. Jednak tablice Cayleya można również wykorzystać do scharakteryzowania działania quasigrupy , która nie zakłada asocjatywności jako aksjomatu (w rzeczywistości tablice Cayleya można wykorzystać do scharakteryzowania działania dowolnej skończonej magmy ). Niestety, generalnie nie jest możliwe określenie, czy operacja jest asocjacyjna, po prostu rzucając okiem na jej tablicę Cayleya, tak jak ma to miejsce w przypadku przemienności. równania 3-członowego tabela Cayleya pokazuje Jednak test asocjatywności Lighta może określić asocjatywność przy mniejszym wysiłku niż brutalna siła.

Permutacje

Ponieważ właściwość anulowania dotyczy grup (a nawet quasi-grup), żaden wiersz ani kolumna tabeli Cayleya nie może zawierać dwukrotnie tego samego elementu. Zatem każdy wiersz i kolumna tabeli jest permutacją wszystkich elementów w grupie. To znacznie ogranicza, które tablice Cayleya mogłyby definiować prawidłową operację grupową.

Aby zrozumieć, dlaczego wiersz lub kolumna nie mogą zawierać tego samego elementu więcej niż raz, niech a , x i y będą elementami grupy, przy czym x i y będą różne. Wtedy w wierszu reprezentującym element a kolumna odpowiadająca x zawiera iloczyn ax i podobnie kolumna odpowiadająca y zawiera iloczyn ay . Gdyby te dwa iloczyny były równe – to znaczy wiersz a zawierał dwa razy ten sam element, nasza hipoteza – to ax równałoby się ay . Ale ponieważ obowiązuje prawo anulowania, możemy wywnioskować, że jeśli ax = ay , to x = y , sprzeczność . Dlatego nasza hipoteza jest błędna, a wiersz nie może zawierać dwa razy tego samego elementu. Dokładnie ten sam argument wystarczy, aby udowodnić przypadek kolumny, a więc dochodzimy do wniosku, że każdy wiersz i kolumna nie zawiera żadnego elementu więcej niż raz. Ponieważ grupa jest skończona, zasada przegródek gwarantuje, że każdy element grupy będzie reprezentowany w każdym rzędzie iw każdej kolumnie dokładnie raz.

Tak więc tabela grupy Cayleya jest przykładem kwadratu łacińskiego .

Inny, być może prostszy dowód: właściwość anulowania implikuje, że dla każdego x w grupie funkcja jednej zmiennej yf(x,y)= xy musi być odwzorowaniem jeden do jednego. A odwzorowania jeden do jednego na skończonych zbiorach to permutacje.

Konstruowanie tablic Cayleya

Ze względu na strukturę grup bardzo często można „uzupełnić” tablice Cayleya, w których brakuje elementów, nawet bez pełnej charakterystyki danej operacji grupowej. Na przykład, ponieważ każdy wiersz i kolumna muszą zawierać każdy element w grupie, jeśli wszystkie elementy są uwzględnione z wyjątkiem jednego i jest jedno puste miejsce, nie wiedząc nic więcej o grupie, można stwierdzić, że element nieuwzględniony musi zająć pozostałe puste miejsce. Okazuje się, że ta i inne obserwacje dotyczące grup w ogóle pozwalają nam konstruować tablice Cayleya grup, wiedząc bardzo niewiele o danej grupie. Należy jednak zauważyć, że tabela Cayleya zbudowana przy użyciu poniższej metody może nie spełniać wymogu asocjatywności grupy, a zatem reprezentować quasigrupę.

„Szkielet tożsamości” skończonej grupy

Odwrotności są identyfikowane przez elementy tożsamości w tabeli. Ponieważ w dowolnej grupie, nawet w grupie nieabelowej, każdy element komutuje się z własną odwrotnością, wynika z tego, że rozkład elementów tożsamości na stole Cayleya będzie symetryczny na przekątnej stołu. Te, które leżą na przekątnej, są swoją własną, unikalną odwrotnością.

Ponieważ kolejność wierszy i kolumn tabeli Cayleya jest w rzeczywistości dowolna, wygodnie jest uporządkować je w następujący sposób: zaczynając od elementu tożsamości grupy, który jest zawsze jego własną odwrotnością, wymień najpierw wszystkie elementy, które są ich własną odwrotność, po której następują pary odwrotności wymienionych obok siebie.

Następnie, dla skończonej grupy określonego rzędu, łatwo jest scharakteryzować jej „szkielet tożsamości”, nazwany tak, ponieważ elementy tożsamości na stole Cayleya skonstruowane w sposób opisany w poprzednim akapicie są skupione wokół głównej przekątnej - albo leżą bezpośrednio na nim lub są od niego odsunięci.

Stosunkowo trywialne jest udowodnienie, że grupy o różnych szkieletach tożsamościowych nie mogą być izomorficzne , chociaż sytuacja odwrotna nie jest prawdziwa (na przykład grupa cykliczna C8 . i grupa kwaternionów Q nie są izomorficzne, ale mają ten sam szkielet tożsamościowy)

Rozważ sześcioelementową grupę z elementami e , a , b , c , d i f . Zgodnie z konwencją e jest elementem tożsamości grupy. Ponieważ element tożsamości jest zawsze swoją własną odwrotnością, a odwrotności są unikalne, fakt, że w tej grupie jest 6 elementów, oznacza, że ​​przynajmniej jeden element inny niż e musi być swoją własną odwrotnością. Mamy więc następujące możliwe szkielety:

  1. wszystkie elementy są swoimi odwrotnościami,
  2. wszystkie elementy z wyjątkiem d i f są swoimi własnymi odwrotnościami, przy czym każdy z tych dwóch ostatnich jest odwrotnością drugiego,
  3. a jest swoją własną odwrotnością, b i c są odwrotnościami, a d i f są odwrotnościami.

W naszym konkretnym przykładzie nie istnieje grupa pierwszego szkieletu rzędu 6; w rzeczywistości sam fakt, że można sobie wyobrazić określony szkielet tożsamości, nie oznacza ogólnie, że istnieje grupa, która do niego pasuje.

Każda grupa, w której każdy element jest swoją własną odwrotnością, jest abelowa: niech a i b będą elementami grupy, to ab = ( ab ) −1 = b −1 a −1 = ba .

Wypełnienie szkieletu tożsamości

Po ustaleniu konkretnego szkieletu tożsamości można przystąpić do wypełniania tabeli Cayleya. Weźmy na przykład szkielet tożsamości grupy rzędu 6 drugiego szkieletu opisanego powyżej:

mi A B C D F
mi mi
A mi
B mi
C mi
D mi
F mi

Oczywiście e -wiersz i e -kolumnę można wypełnić od razu.

mi A B C D F
mi mi A B C D F
A A mi
B B mi
C C mi
D D mi
F F mi

Po wykonaniu tej czynności istnieje kilka możliwych opcji postępowania. Skupimy się na wartości ab . Zgodnie z właściwością Latin square jedynymi możliwymi prawidłowymi wartościami ab c , d lub f . Widzimy jednak, że zamiana dwóch elementów d i f skutkowałaby dokładnie taką samą tabelą, jaką już mamy, z wyjątkiem dowolnie wybranych etykiet. Oczekiwalibyśmy zatem, że obie te opcje dadzą ten sam wynik, aż do izomorfizmu, więc musimy rozważyć tylko jedną z nich.

Należy również zauważyć, że jedna lub kilka wartości może (i tak się dzieje w naszym przypadku) później prowadzić do sprzeczności – co oznacza po prostu, że w rzeczywistości nie były to wartości prawidłowe.

ab = c

Mnożąc naprzemiennie po lewej i po prawej stronie, możliwe jest rozszerzenie jednego równania w pętlę równań, w której każde implikuje wszystkie pozostałe:

  • Mnożenie ab = c po lewej stronie przez a daje b = ac
  • Mnożenie b = ac po prawej stronie przez c daje bc = a
  • Mnożenie bc = a po lewej stronie przez b daje c = ba
  • Mnożenie c = ba po prawej stronie przez a daje ca = b
  • Mnożenie ca = b po lewej stronie przez c daje a = cb
  • Mnożenie a = cb po prawej stronie przez b daje ab = c

Po wypełnieniu wszystkich tych produktów tabela Cayley wygląda teraz tak (nowe elementy na czerwono):

mi A B C D F
mi mi A B C D F
A A mi C B
B B C mi A
C C B A mi
D D mi
F F mi

Ponieważ tablica Cayleya jest kwadratem łacińskim, jedyną poprawną wartością ad jest f i podobnie jedyną możliwą wartością af jest d .

Po wypełnieniu tych wartości tabela Cayleya wygląda teraz tak (nowe elementy na niebiesko):

mi A B C D F
mi mi A B C D F
A A mi C B F D
B B C mi A
C C B A mi
D D mi
F F mi

Niestety, wszystkie elementy grupy są już obecne w tabeli powyżej lub na lewo od bd , więc nie ma wartości bd , która spełniałaby właściwość kwadratu łacińskiego.

Oznacza to, że wybrana przez nas opcja będzie ( ab = c ) doprowadziła nas do punktu, w którym nie można przypisać bd żadnej wartości bez powodowania sprzeczności. Pokazaliśmy zatem, że ab c .

Jeśli w podobny sposób wykażemy, że wszystkie opcje prowadzą do sprzeczności, to musimy stwierdzić, że nie istnieje żadna grupa rzędu 6 ze szkieletem identyczności, od którego zaczęliśmy.

ab = re

Mnożąc naprzemiennie po lewej i po prawej stronie, możliwe jest rozszerzenie jednego równania w pętlę równań, w której każde implikuje wszystkie pozostałe:

  • Mnożenie ab = d po lewej stronie przez a daje b = ad
  • Mnożenie b = ad po prawej stronie przez f daje bf = a
  • Mnożenie bf = a po lewej stronie przez b daje f = ba
  • Mnożenie f = ba po prawej stronie przez a daje fa = b
  • Mnożenie fa = b po lewej stronie przez d daje a = db
  • Mnożenie a = db po prawej stronie przez b daje ab = d

Po wypełnieniu wszystkich tych produktów tabela Cayley wygląda teraz tak (nowe elementy na czerwono):

mi A B C D F
mi mi A B C D F
A A mi D B
B B F mi A
C C mi
D D A mi
F F B mi

Pozostałe iloczyny a, pokazane na niebiesko, można teraz wprowadzić za pomocą właściwości kwadratu łacińskiego. Na przykład brakuje c w wierszu a i nie może wystąpić dwa razy w kolumnie c , stąd ac = f .

mi A B C D F
mi mi A B C D F
A A mi D F B C
B B F mi A
C C D mi
D D C A mi
F F B mi

Podobnie można wprowadzić pozostałe iloczyny b, pokazane na zielono:

mi A B C D F
mi mi A B C D F
A A mi D F B C
B B F mi D C A
C C D F mi A
D D C A mi
F F B C A mi

Pozostałe produkty, z których każdy jest jedyną brakującą wartością w wierszu lub kolumnie, można teraz wypełnić za pomocą właściwości kwadratu łacińskiego, pokazanej na pomarańczowo:

mi A B C D F
mi mi A B C D F
A A mi D F B C
B B F mi D C A
C C D F mi A B
D D C A B F mi
F F B C A mi D

Ponieważ udało nam się wypełnić całą tabelę bez uzyskania sprzeczności, znaleźliśmy grupę rzędu 6, a inspekcja wykazała, że ​​jest ona nieabelowa. Ta grupa jest w rzeczywistości najmniejszą grupą nieabelową, grupą dwuścienną D 3

Przykład quasigrupy skonstruowanej powyższą metodą

Poniższą tabelę Cayleya można skonstruować, wprowadzając szkielet tożsamości, wypełniając pierwszy wiersz i kolumnę, a następnie postulując, że ab = c . Alternatywne założenie ab = d skutkuje homomorfizmem. Reszta tabeli ma postać kwadratu łacińskiego. Jednak w odniesieniu do tabeli (ac)b = db = a , podczas gdy a(cb) = ad = b . Dlatego zawodzi aksjomat asocjatywności i reprezentuje raczej quasigrupę niż grupę.

mi A B C D
mi mi A B C D
A A mi C D B
B B D mi A C
C C B D mi A
D D C A B mi

Generowanie macierzy permutacji

Standardowa postać tabeli Cayleya ma kolejność elementów w wierszach taką samą jak kolejność w kolumnach. Inną formą jest takie ułożenie elementów kolumn, aby n- ta kolumna odpowiadała odwrotności elementu w n- tym rzędzie. W naszym przykładzie D 3 wystarczy zamienić tylko dwie ostatnie kolumny, ponieważ f i d są jedynymi elementami, które nie są swoimi odwrotnościami, ale odwrotnościami siebie nawzajem.

mi A B C f=d −1 d=f −1
mi mi A B C F D
A A mi D F C B
B B F mi D A C
C C D F mi B A
D D C A B mi F
F F B C A D mi

Ten konkretny przykład pozwala nam stworzyć sześć macierzy permutacji (wszystkie elementy 1 lub 0, dokładnie jedna 1 w każdym wierszu i kolumnie). Macierz 6x6 reprezentująca element będzie miała 1 na każdej pozycji, która ma literę elementu w tabeli Cayleya i zero na każdej innej pozycji, delta Kroneckera dla tego symbolu. (Zauważ, że e znajduje się na każdej pozycji wzdłuż głównej przekątnej, co w tym przypadku daje nam macierz identyczności dla macierzy 6x6, jak byśmy się tego spodziewali.) Oto macierz reprezentująca nasz element a , na przykład.

mi A B C F D
mi 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

bezpośrednio , że dowolna grupa rzędu n jest podgrupą grupy permutacji Sn , rzędu n !.

Uogólnienia

Powyższe właściwości zależą od pewnych aksjomatów obowiązujących dla grup. Naturalne jest rozważenie tablic Cayleya dla innych struktur algebraicznych, takich jak półgrupy , quasigrupy i magmy , ale niektóre z powyższych właściwości nie są spełnione.

Zobacz też