Cayleyův stůl

Cayleyova  tabulka je tabulka, která popisuje strukturu konečných algebraických systémů uspořádáním výsledků operace do tabulky připomínající násobilku. Pojmenován po anglickém matematikovi Arthuru Cayleym . Tablo je důležité v diskrétní matematice , zejména v teorii grup . Tabulka umožňuje zjistit některé vlastnosti skupiny, například zda je skupina abelian , najít střed skupiny a inverzní prvky prvků skupiny.

Ve vyšší algebře mohou být Cayleyovy tabulky také použity k definování binárních operací na polích , prstencích a jiných algebraických strukturách.

Jednoduchý příklad Cayleyovy tabulky pro grupu {1, −1} s normálním násobením :

Historie

Cayleyovy tabulky se poprvé objevily v Cayleyho práci „O teorii skupin, jak závisí na symbolické rovnici θ n = 1“ v roce 1854. V tomto článku to byly pouze tabulky použité pro ilustraci. Později byly na počest svého tvůrce nazývány Cayley tables.  

Struktura

Protože mnoho Cayleyových tabulek popisuje skupiny, které nejsou abelovské , součin ab se nemusí nutně rovnat součinu ba pro všechna aab ve skupině. Aby nedošlo k záměně, předpokládá se, že násobitel odpovídající řádkům je na prvním místě a násobitel odpovídající sloupcům je na druhém místě. Například průsečík řádku a a sloupce b  je ab , nikoli ba , jak ukazuje následující příklad:

Cayley ve své práci umístil neutrální prvek do prvního řádku a prvního sloupce, což mu umožnilo nevyčlenit samostatné řádky a sloupce označující prvky, jak je vidět na příkladu výše. Například stejná tabulka byla prezentována jako:

V tomto příkladu cyklické skupiny Z 3 je prvek a neutrálním prvkem a objevuje se v levém horním rohu tabulky. Je snadné vidět například, že b 2 = c a že cb = a . Na rozdíl od toho většina moderních textů, včetně tohoto článku, obsahuje řádek záhlaví a sloupec pro větší přehlednost.

Vlastnosti a použití

Komutativnost

Tabulka Cayley nám říká, zda je skupina abelianská . Protože operace skupiny na abelovské grupě je komutativní , grupa je abelovská právě tehdy, když je její Cayleyho tablo symetrické (vzhledem k diagonále). Cyklická grupa 3. řádu výše, stejně jako {1, −1} obyčejným násobením, jsou oba příklady Abelových grup a symetrie jejich Cayleyových tabulek to dokazuje. Ale nejmenší neabelovská dihedrální skupina šestého řádu nemá v tabulce žádnou symetrii.

Asociativita

Vzhledem k tomu , že asociativita je přítomna ve skupinách z definice, často se předpokládá i v Cayleyových tabulkách. Cayleyho tabulky však lze použít k popisu operací v kvazigrupách , kde se asociativita nevyžaduje (navíc Cayleyovy tabulky lze použít k popisu operace v jakémkoli konečném magmatu ). Bohužel obecně je nemožné určit, zda je operace asociativní nebo ne, pouhým pohledem na tabulku, na rozdíl od komutativnosti. To proto, že asociativita závisí na třech prvcích v rovnosti, zatímco Cayleyova tabulka ukazuje součin dvou prvků. Lightův test asociativity však může určit asociativitu s menším úsilím než hrubou silou.

Permutace

Vzhledem k tomu, že zkratka platí pro skupiny (opravdu i pro kvazigrupy), žádný řádek ani sloupec Cayleyovy tabulky nemůže obsahovat stejný prvek dvakrát. Každý řádek a sloupec tabulky je tedy permutací prvků skupiny.

Chcete-li zjistit, proč řádky a sloupce nemohou obsahovat stejné prvky, nechť a , x a y  jsou prvky skupiny a x a y jsou různé. Nyní bude řádek odpovídající prvku a a sloupec odpovídající prvku x obsahovat součin ax . Podobně sloupec odpovídající y bude obsahovat ay . Nechť jsou dva součiny stejné, to znamená, že řetězec a obsahuje prvek dvakrát. Pomocí redukčního pravidla můžeme z ax = ay usuzovat , že x = y , což je v rozporu s volbou x ​​a y . Úplně stejná úvaha platí pro sloupce. S ohledem na konečnost grupy podle Dirichletova principu bude každý prvek grupy uveden právě jednou v každém řádku a v každém sloupci.

To znamená, že Cayleyho tablo pro skupinu je příkladem latinského čtverce .

Konstrukce Cayleyových tabulek pro skupiny

Pomocí skupinové struktury je často možné „vyplnit“ Cayleyovy tabulky, které mají prázdná pole, aniž byste vůbec věděli cokoli o skupinovém provozu. Například, protože každý řádek a každý sloupec musí obsahovat všechny prvky skupiny, jeden chybějící prvek v řádku (nebo sloupci) lze vyplnit, aniž byste o skupině vůbec něco věděli. To ukazuje, že tato vlastnost a některé další vlastnosti grup umožňují konstruovat Cayleyho tabulky, i když o skupině víme jen málo.

"Kostra neutrálních prvků" konečné grupy

Protože v jakékoli skupině, dokonce ani v abelovské, jakýkoli prvek komutuje se svou inverzí, je rozložení neutrálních prvků v Cayleyově tablo symetrické vzhledem k diagonále. Neutrální prvky ležící na diagonále odpovídají prvkům, které se shodují s jejich inverzemi.

Vzhledem k tomu, že pořadí řádků a sloupců v Cayleyově tabulce je libovolné, je vhodné je uspořádat v následujícím pořadí: začneme neutrálním prvkem skupiny, který se vždy shoduje se svou inverzní, pak vypíšeme všechny prvky, které se shodují s jejich převrácenými hodnotami a poté vypište dvojice prvků (prvek a inverzní k němu).

Nyní, pro konečnou skupinu určitého řádu, je snadné definovat "kostru neutrálních prvků", pojmenovanou tak, protože neutrální prvky buď leží na hlavní diagonále nebo blízko ní.

Je poměrně snadné dokázat, že skupiny s různými kostrami nemohou být izomorfní , ale obráceně to neplatí (například cyklická grupa C 8 a kvaternionová grupa Q nejsou izomorfní, ačkoli mají stejné kostry).

Nechť existuje šest prvků skupiny e , a , b , c , daf . Nechť e  je neutrální prvek. Protože neutrální prvek je stejný jako jeho inverzní prvek a inverzní prvek je jedinečný, musí existovat alespoň jeden další prvek, který je stejný jako jeho inverzní. Získáme tedy následující možné kostry:

• všechny prvky se shodují se svými převrácenými hodnotami,
• všechny prvky kromě d a f jsou stejné jako jejich převrácené hodnoty a tyto dva jsou navzájem převrácené,
• a je jeho inverzní, b a c jsou inverzní, d a f jsou inverzní.

V našem případě neexistuje skupina prvního typu řádu 6. Navíc skutečnost, že je kostra možná, vůbec neznamená, že existuje skupina, jejíž kostra s ní splývají.

Pozoruhodný je fakt (a lze jej snadno dokázat), že každá skupina, ve které se jakýkoli prvek shoduje se svou inverzí, je abelovská.

Doplnění tabulky podle kostry neutrálních prvků

Pokud je uvedena kostra neutrálních prvků, můžete začít vyplňovat Cayleyho tabulku. Vyberme například druhou kostru skupiny řádu 6 z výše popsaných:

Je zřejmé, že řádek e a sloupec e lze vyplnit okamžitě. Jakmile se tak stane, může být nutné (a v našem případě je to nutné) vytvořit předpoklad, což může následně vést k rozporu, což bude znamenat, že předpoklad je nesprávný. Budeme předpokládat, že ab = c . Pak:

Vynásobením ab = c zleva a dostaneme b = ac . Pravé násobení c dá bc = a . Vynásobením ab = c zprava číslem b vznikne a = cb . Vynásobením bc = a zleva b dostaneme c = ba a vynásobením zprava a dostaneme ca = b . Po vyplnění těchto produktů v tabulce zjistíme, že ad a af zůstávají prázdné v řádku a . Protože se každý prvek musí objevit právě jednou za sebou, dostaneme, že reklama musí být buď d nebo f . Tento prvek se však nemůže rovnat d , protože jinak by a bylo rovno e ​​, přičemž víme, že oba prvky jsou různé. Tedy ad = f a af = d .

Protože inverzní k d je f , vynásobením ad = f zprava f dostaneme a = f 2 . Vynásobení levým d dává da = f . Vynásobením vpravo a , dostaneme d = fa .

Po zadání všech těchto prací bude mít Cayleyova tabulka tvar:

Protože se každý prvek skupiny musí v každém řádku objevit právě jednou, je snadné vidět, že dvě prázdné buňky tabulky v řádku b musí být obsazeny buď d nebo f . Avšak d a f jsou již přítomny v odpovídajících sloupcích . Cokoli tedy vložíme do těchto polí, dostaneme do sloupců opakování, což ukazuje, že náš původní odhad ab = c byl špatný. Nyní však víme, že ab ≠ c .

Zbývají dvě možnosti - buď ab = d nebo ab = f . Protože d a f jsou vzájemně inverzní a výběr písmen je libovolný, měli bychom očekávat, že výsledek bude stejný až do izomorfismu. Bez ztráty obecnosti můžeme předpokládat, že ab = d . Pokud nyní dostaneme rozpor, musíme uznat, že pro tuto kostru neexistuje žádná odpovídající skupina.

Dostáváme nový Cayleyův stůl:

Vynásobením ab = d vlevo a a dostaneme b = ad . Pravé násobení f dává bf = a a levé násobení b dává f = ba . Vynásobením vpravo a dostaneme fa = b a vynásobením vlevo d dostaneme a = db . Zadáním výsledků do Cayley tabulky získáme (nové prvky jsou zvýrazněny červeně):

Řetězec a chybí c a f , ale protože af se nemůže rovnat f (jinak by a bylo rovno e ​​), můžeme dojít k závěru, že af = c . Vynásobením nalevo a dostaneme f = ac , a to můžeme vynásobit napravo c , což dostane fc = a . Vynásobením d na levé straně dostaneme c = da , které můžeme vynásobit napravo číslem a , abychom dostali ca = d . Stejným způsobem vynásobením af = c zprava d dostaneme a = cd . Aktualizujte tabulku (nejnovější změny jsou zvýrazněny modře):

Protože řetězec b neobsahuje c a d a bc se nemůže rovnat c , odvodíme, že bc = d , takže součin bd se musí rovnat c . Vynásobením vpravo f dostaneme b = cf , které lze převést na cb = f vynásobením c vlevo. Argumentujeme-li podobně, můžeme odvodit, že c = fb a dc = b . Provádíme změny v tabulce (zavedené prvky jsou zvýrazněny zeleně):

V řádku d chybí pouze f , takže d 2 = f . Stejným způsobem získáme, že f 2 = d . Vyplnili jsme celou tabulku a nedošli jsme k rozporu. Našli jsme tedy skupinu řádu 6 odpovídající kostře. Pohled na tabulku ukazuje, že to není abelian. Ve skutečnosti se jedná o nejmenší neabelovskou skupinu, dihedrální skupinu D 3 :

Generování permutační matice

Ve standardní podobě Cayley tabulky je pořadí řádků a sloupců stejné. Dalším způsobem řazení je uspořádání sloupců tak, aby n -tý sloupec odpovídal obráceným prvkům n -tého řádku. V našem příkladu pro D 3 potřebujeme pouze prohodit poslední dva sloupce, protože pouze f a d nejsou inverzní k sobě, ale jsou inverzní k sobě navzájem.

V našem příkladu lze vytvořit šest permutačních matic (všechny prvky jsou 1 nebo 0, jedna 1 v každém řádku a každém sloupci). Matice 6x6 obsahuje jedničku, pokud štítek sloupce odpovídá štítku řádku, a nuly ve všech ostatních polích, symbol Kronecker pro štítek. (Všimněte si, že pro řádek e dostaneme matici identity.) Například pro a dostaneme permutační matici.

To ukazuje , že jakákoli skupina řádu n je podgrupou permutační grupy Sn řádu n !.

Zobecnění

Vlastnosti popsané výše závisí na některých axiomech pro skupiny. Je přirozené rozšířit Cayleyovy obrázky na některé další algebraické struktury, jako jsou pologrupy , kvazigrupy a magmata , ale některé z výše uvedených vlastností pro ně nebudou platit.

Viz také

• Násobilka
• latinský čtverec

Odkazy

• Cayley, Arthur . “O teorii grup, jak závisí na symbolické rovnici θ n = 1”, Philosophical Magazine , Vol. 7 (1854), str. 40-47. Dostupné online na Google Books jako součást jeho sebraných děl. 
• Cayley, Arthur . "O teorii skupin", American Journal of Mathematics , sv. 11, č. 2 (leden 1889), str. 139-157. K dispozici na JSTOR.