Stół Cayley - Cayley table

Nazwana na cześć XIX-wiecznego brytyjskiego matematyka Arthura Cayleya , tablica Cayleya opisuje strukturę skończonej grupy poprzez ułożenie wszystkich możliwych iloczynów wszystkich elementów grupy w kwadratowej tablicy przypominającej tabliczkę dodawania lub mnożenia . Wiele właściwości grupy - takie jak, czy jest czy nie jest abelowa , które elementy są odwrotne , które elementy i wielkość i zawartość grupy centrum  - mogą być odkryte ze swojej tablicy Cayley.

Prostym przykładem tabeli Cayley jest ta 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 pracy Cayleya z 1854 r. „O teorii grup, w zależności od symbolicznego równania θ n = 1”. W tym artykule nazywano je po prostu stołami i były jedynie ilustracją – później stały się znane jako stoły Cayley, na cześć ich twórcy.  

Struktura i układ

Ponieważ wiele tabele Cayley określenia grup, które nie są abelowa produkt AB w stosunku do grupy operacji binarnego nie gwarantuje się iloczyn ba dla wszystkich A i B w grupie. Aby uniknąć nieporozumień, konwencja jest taka, że ​​czynnik, który oznacza wiersz (określany przez Cayley jako bliższy czynnik ) jest pierwszy, a czynnik, który oznacza kolumnę (lub dalszy czynnik ) jest drugi. Na przykład przecięcie wiersza a i kolumny b to ab , a nie ba , jak w poniższym przykładzie:

* a b C
a 2 ab AC
b ba b 2 pne
C może 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 tablicy Cayleya są symetryczne wzdłuż jej osi przekątnej. Grupa cykliczna rzędu 3 powyżej i {1, -1} pod zwykłym mnożeniem, również powyżej, są przykładami grup abelowych, a sprawdzenie symetrii ich tablic Cayley weryfikuje to. W przeciwieństwie do tego najmniejsza grupa nieabelowa, grupa dwuścienna rzędu 6 , nie ma symetrycznej tablicy Cayleya.

Łączność

Ponieważ asocjatywność jest traktowana jako aksjomat, gdy mamy do czynienia z grupami, często jest to oczywiste, gdy mamy do czynienia z tabelami Cayley. 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 spoglądając na tabelę Cayleya, jak to ma miejsce w przypadku przemienności. Dzieje się tak dlatego, że asocjatywność zależy od równania 3-członowego , podczas gdy tabela Cayleya pokazuje iloczyny 2-członowe. Jednak test asocjacji Lighta może określić asocjatywność przy mniejszym wysiłku niż brutalna siła.

Permutacje

Ponieważ właściwość anulowania dotyczy grup (a nawet quasigrup), żaden wiersz ani kolumna tabeli Cayley nie może zawierać dwa razy tego samego elementu. W ten sposób każdy wiersz i kolumna tabeli jest permutacją wszystkich elementów w grupie. To znacznie ogranicza, które tabele Cayley mogą ewentualnie definiować prawidłową operację grupową.

Aby zobaczyć, dlaczego wiersz lub kolumna nie może zawierać tego samego elementu więcej niż raz, niech wszystkie a , x i y będą elementami grupy, przy czym x i y są różne. Następnie 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 byłoby równe 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 dwukrotnie zawierać tego samego elementu. Dokładnie ten sam argument wystarcza do udowodnienia przypadku w kolumnie, 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 szufladki 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 Cayley 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 mapy jeden do jednego na zbiorach skończonych to permutacje.

Konstruowanie stołów Cayley

Ze względu na strukturę grup bardzo często można „wypełnić” tabele Cayleya, w których brakuje elementów, nawet nie posiadając pełnej charakterystyki rozpatrywanego działania grupowego. Na przykład, ponieważ każdy wiersz i kolumna musi zawierać każdy element w grupie, jeśli wszystkie elementy są uwzględnione, zapisz jeden, a jest jedno puste miejsce, nie wiedząc nic więcej o grupie, można wywnioskować, że element nieuwzględniony musi zajmują pozostałą pustą przestrzeń. Okazuje się, że ta i inne obserwacje dotyczące grup w ogóle pozwalają nam skonstruować tabele Cayleya grup niewiele wiedzących o danej grupie.

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

Ponieważ w każdej grupie, nawet nieabelowej, każdy element komutuje 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żą po przekątnej, są swoją własną, unikalną odwrotnością.

Ponieważ kolejność wierszy i kolumn w tabeli Cayley 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 zawsze jest swoją odwrotnością, wypisz najpierw wszystkie elementy, które są ich własna odwrotność, po której następują obok siebie pary odwrotności.

Wtedy, dla skończonej grupy określonego rzędu, łatwo scharakteryzować jej „szkielet tożsamości”, nazwany tak, ponieważ elementy tożsamości na stole Cayleya są skupione wokół głównej przekątnej – albo leżą bezpośrednio na niej, albo są jednym usunięte z niego.

Jest to stosunkowo trywialne udowodnić, że grupy o różnych szkieletów tożsamość nie może być izomorficzne , że odwrotna jest prawdą (na przykład, cykliczną grupę C 8 a grupa kwaternion P są nieizomorficznych, ale mają ten sam szkielet osobistego).

Rozważmy 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 ​​co najmniej 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 oprócz d i f są swoimi własnymi odwrotnościami, każdy z tych dwóch ostatnich jest odwrotnością drugiego,
  3. a jest jego odwrotnością, b i c są odwrotnościami, a d i f są odwrotnościami.

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

Każda grupa, w której każdy element jest jego własny odwrotna jest abelowa niech i b są elementy grupy, wtedy AB = ( ab ) -1 = b -1 o -1 = BA .

Wypełnianie szkieletu tożsamości

Po ustaleniu konkretnego szkieletu tożsamości można rozpocząć wypełnianie tabeli Cayley. Na przykład weźmy szkielet tożsamości grupy rzędu 6 drugiego typu opisanego powyżej:

mi a b C D F
mi mi
a mi
b mi
C mi
D mi
F mi

Oczywiście, e -row i e -column mogą być wypełnione natychmiast.

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

Gdy to zrobisz, istnieje kilka możliwych opcji postępowania. Skupimy się na wartości ab . Ponieważ każdy element grupy musi pojawić się raz i tylko raz w każdym wierszu i raz i tylko raz w każdej kolumnie, jedynymi poprawnymi wartościami ab są c , d lub f . Widzimy jednak, że zamiana dwóch elementów d i f dałaby dokładnie taką samą tabelę, jaką już mamy, z wyjątkiem arbitralnie wybranych etykiet. Dlatego spodziewalibyśmy się, że obie te dwie opcje dadzą ten sam wynik, aż do izomorfizmu, a zatem musimy rozważyć tylko jedną z nich.

Ważne jest również, aby pamiętać, że jedna lub kilka wartości może (i prowadzi w naszym przypadku) później prowadzić do sprzeczności – co oznacza po prostu, że w rzeczywistości nie były one wcale ważnymi wartościami.

ab = c

Mnożąc naprzemiennie z lewej i prawej strony, można rozszerzyć jedno równanie w pętlę równań, w której jedno implikuje wszystkie inne:

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

Wypełniając wszystkie te produkty, stół Cayley wygląda teraz tak (nowe elementy w kolorze czerwonym):

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

Skupimy się teraz na wartości reklamy . Ponieważ każdy element grupy musi pojawić się raz i tylko raz w każdym wierszu oraz raz i tylko raz w każdej kolumnie, jedyną możliwą poprawną wartością ad jest f .

Mnożąc naprzemiennie z lewej i prawej strony, można rozszerzyć jedno równanie w pętlę równań, w której jedno implikuje wszystkie inne:

  • Mnożąc ad = f po lewej przez a daje d = af
  • Mnożenie d = af po prawej przez d daje d 2 = a
  • Mnożenie d 2 = a po lewej przez f daje d = fa
  • Mnożenie d = fa po prawej przez a daje da = f
  • Mnożenie da = f po lewej przez f daje a = f 2
  • Pomnożenie a = f 2 po prawej przez d daje ad = f

Wypełniając wszystkie te produkty, stół Cayley wygląda teraz tak (nowe elementy w kolorze niebieskim):

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 F a mi
F F D mi a

Skupimy się teraz na wartości bd . Niestety, ponieważ każdy element grupy musi pojawić się raz i tylko raz w każdym wierszu i raz i tylko raz w każdej kolumnie, nie ma poprawnych wartości bd .

Oznacza to, że wybrana przez nas opcja ( ab = c ) doprowadziła nas do punktu, w którym żadna wartość nie może być przypisana do bd bez powodowania sprzeczności. Wykazaliśmy zatem, że ab ≠ c .

Jeśli w podobny sposób pokażemy, że wszystkie opcje prowadzą do sprzeczności, to musimy dojść do wniosku, że nie istnieje grupa porządku 6 ze szkieletem tożsamości, od którego zaczęliśmy.

ab = d

Mnożąc naprzemiennie z lewej i prawej strony, można rozszerzyć jedno równanie w pętlę równań, w której jedno implikuje wszystkie inne:

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

Wypełniając wszystkie te produkty, stół Cayley wygląda teraz tak (nowe elementy w kolorze czerwonym):

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

Skupimy się teraz na wartości ac . Ponieważ każdy element grupy musi pojawić się raz i tylko raz w każdym wierszu oraz raz i tylko raz w każdej kolumnie, jedyną możliwą poprawną wartością ac jest f .

Mnożąc naprzemiennie z lewej i prawej strony, można rozszerzyć jedno równanie w pętlę równań, w której jedno implikuje wszystkie inne:

  • Mnożąc ac = f po lewej przez a daje c = af
  • Mnożenie c = af po prawej przez d daje cd = a
  • Mnożenie cd = a po lewej przez c daje d = ca
  • Mnożenie d = ca po prawej przez a daje da = c
  • Mnożenie da = c po lewej przez f daje a = fc
  • Pomnożenie a = fc po prawej przez c daje ac = f

Wypełniając wszystkie te produkty, stół Cayley wygląda teraz tak (nowe elementy w kolorze niebieskim):


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 a
D D C a mi
F F b a mi

Skupimy się teraz na wartości bc . Ponieważ każdy element grupy musi pojawić się raz i tylko raz w każdym wierszu i raz i tylko raz w każdej kolumnie, jedyną możliwą poprawną wartością bc jest d .

Mnożąc naprzemiennie z lewej i prawej strony, można rozszerzyć jedno równanie w pętlę równań, w której jedno implikuje wszystkie inne:

  • Mnożąc bc = d po lewej przez b daje c = bd
  • Mnożenie c = bd po prawej przez f daje cf = b
  • Mnożenie cf = b po lewej przez c daje f = cb
  • Mnożenie f = cb po prawej przez b daje fb = c
  • Mnożenie fb = c po lewej przez d daje b = dc
  • Mnożenie b = dc po prawej przez c daje bc = d

Wypełniając wszystkie te produkty, stół Cayley wygląda teraz tak (nowe elementy w kolorze zielonym):

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 mi
F F b C a mi

Wreszcie, ponieważ każdy element grupy musi pojawić się raz i tylko raz w każdym wierszu i raz i tylko raz w każdej kolumnie, jedyną możliwą poprawną wartością d 2 jest f , a jedyną możliwą możliwą wartością f 2 jest d .

Wypełniając te produkty, stół Cayley wygląda teraz tak (nowe elementy w kolorze pomarańczowym):

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 nieabelowa. Ta grupa jest w rzeczywistości najmniejszą grupą nieabelową, dwuścienną grupą D 3 :


Generowanie macierzy permutacji

W standardowej formie tabeli Cayley kolejność elementów w wierszach jest taka sama jak kolejność w kolumnach. Inną formą jest ułożenie elementów kolumn tak, aby n- ta kolumna odpowiadała odwrotności elementu w n- tym rzędzie. W naszym przykładzie D 3 , musimy zamienić tylko dwie ostatnie kolumny, ponieważ f i d są jedynymi elementami, które nie są swoimi odwrotnościami, lecz 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 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 Cayley i zero na każdej innej pozycji, funkcję delta Kroneckera dla tego symbolu. (Zauważ, że e znajduje się w każdej pozycji wzdłuż głównej przekątnej, co daje nam w tym przypadku macierz jednostkową dla macierzy 6x6, jak byśmy się spodziewali.) Oto macierz, która reprezentuje 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

To pokazuje nam bezpośrednio, że każda grupa rzędu n jest podgrupą grupy permutacyjnej S n , rzędu n !.

Uogólnienia

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

Zobacz też

Bibliografia