Cayley bord

Cayley-  tabellen är en tabell som beskriver strukturen hos finita algebraiska system genom att ordna resultatet av en operation i en tabell som liknar en multiplikationstabell. Uppkallad efter den engelske matematikern Arthur Cayley . Tabellen är viktig i diskret matematik , särskilt i gruppteorin . Tabellen låter dig ta reda på några egenskaper hos gruppen, till exempel om gruppen är abelisk , hitta gruppens mittpunkt och de omvända elementen i gruppens element.

I högre algebra kan Cayley-tabeller också användas för att definiera binära operationer på fält , ringar och andra algebraiska strukturer.

Ett enkelt exempel på en Cayley-tabell för gruppen {1, −1} med normal multiplikation :

× ett −1
ett ett −1
−1 −1 ett

Historik

Cayley-tabeller dök upp först i Cayleys artikel "On The Theory of Groups, beroende på den symboliska ekvationen θ n = 1" 1854. I den här artikeln var det bara tabeller som användes i illustrativt syfte. De kallades senare för Cayley-bord för att hedra sin skapare.  

Struktur

Eftersom många Cayley-tabeller beskriver grupper som inte är abelska , är produkten ab inte nödvändigtvis lika med produkten ba för alla a och b i gruppen. För att undvika förvirring antas det att multiplikatorn som motsvarar raderna kommer först och multiplikatorn som motsvarar kolumnerna kommer på andra plats. Till exempel är skärningspunkten mellan rad  a och kolumn b ab , inte ba , som visas i följande exempel:

* a b c
a en 2 ab ac
b ba b 2 före Kristus
c ca cb c 2

Cayley placerade i sitt arbete ett neutralt element i den första raden och den första kolumnen, vilket gjorde att han inte kunde peka ut separata rader och kolumner som indikerar elementen, vilket kan ses i exemplet ovan. Till exempel presenterades samma tabell som:

a b c
b c a
c a b

I detta exempel på en cyklisk grupp Z 3 är elementet a det neutrala elementet, och det visas i tabellens övre vänstra hörn. Det är lätt att till exempel se att b 2 = c och att cb = a . I motsats till detta innehåller de flesta moderna texter, inklusive denna artikel, en rubrikrad och kolumn för större tydlighet.

Egenskaper och användningsområden

Kommutativitet

Cayley-tabellen talar om för oss om en grupp är abelisk . Eftersom gruppoperationen på en Abelisk grupp är kommutativ , är en grupp Abelian om och endast om dess Cayley-tablå är symmetrisk (med avseende på diagonalen). Den cykliska gruppen av ordning 3 ovan, såväl som {1, −1} med vanlig multiplikation, är båda exempel på Abeliska grupper, och symmetrin i deras Cayley-tabeller bevisar detta. Men den minsta icke-abeliska dihedriska gruppen av sjätte ordningen har ingen symmetri i Cayley-tabellen.

Associativitet

Eftersom associativitet per definition förekommer i grupper, antas det ofta även i Cayley-tabeller. Emellertid kan Cayley-tabeller användas för att beskriva operationer i kvasigrupper , där associativitet inte krävs (desutom kan Cayley-tabeller användas för att beskriva en operation i vilken finit magma som helst ). Tyvärr är det i allmänhet omöjligt att avgöra om en operation är associativ eller inte genom att bara titta på en tabell, i motsats till kommutativitet. Detta beror på att associativitet beror på de tre elementen i jämlikhet, medan Cayley-tabellen visar produkten av två element. Lights associativitetstest kan dock bestämma associativitet med mindre ansträngning än brute force.

Permutationer

Eftersom förkortningen gäller för grupper (i själva verket även för kvasigrupper), kan ingen rad eller kolumn i Cayley-tabellen innehålla samma element två gånger. Således är varje rad och kolumn i tabellen en permutation av elementen i gruppen.

För att se varför rader och kolumner inte kan innehålla samma element, låt a , x och y  vara element i en grupp och x och y är olika. Nu kommer raden som motsvarar element a och kolumnen som motsvarar element x att innehålla produkten ax . På liknande sätt kommer kolumnen som motsvarar y att innehålla ay . Låt två produkter vara lika, det vill säga strängen a innehåller elementet två gånger. Genom reduktionsregeln kan vi från ax = ay dra slutsatsen att x = y , vilket motsäger valet av x och y . Exakt samma resonemang gäller för kolumner. Med tanke på gruppens ändlighet enligt Dirichlet-principen kommer varje element i gruppen att presenteras exakt en gång i varje rad och i varje kolumn.

Det vill säga, Cayleys tablå för gruppen är ett exempel på en latinsk kvadrat .

Konstruktion av Cayley-bord för grupper

Med hjälp av gruppstrukturen är det ofta möjligt att "fylla i" Cayley-tabeller som har tomma fält utan att ens veta något om gruppoperationen. Till exempel, eftersom varje rad och varje kolumn måste innehålla alla element i en grupp, kan ett saknat element i en rad (eller kolumn) fyllas i utan att veta något om gruppen alls. Detta visar att denna egenskap och vissa andra egenskaper hos grupper gör det möjligt att konstruera Cayley-tabeller även om vi vet lite om gruppen.

"Skelett av neutrala element" i en finit grupp

Eftersom i vilken grupp som helst, inte ens i en abelisk, vilket element som helst pendlar med sin invers, är fördelningen av neutrala element i Cayley-tabellen symmetrisk med avseende på diagonalen. Neutrala element som ligger på diagonalen motsvarar element som sammanfaller med deras inverser.

Eftersom ordningen på raderna och kolumnerna i Cayley-tabellen är godtycklig, är det bekvämt att ordna dem i följande ordning: vi börjar med det neutrala elementet i gruppen, som alltid sammanfaller med dess invers, listar sedan alla element som sammanfaller med sina inverser, och skriv sedan ut par av element (element och invers till honom).

Nu, för en ändlig grupp av någon ordning, är det lätt att definiera ett "skelett av neutrala element", så kallat eftersom de neutrala elementen antingen ligger på eller nära huvuddiagonalen.

Det är relativt lätt att bevisa att grupper med olika skelett inte kan vara isomorfa , men det omvända är inte sant (till exempel är den cykliska gruppen C 8 och quaterniongruppen Q inte isomorfa, även om de har samma skelett).

Låt det finnas sex gruppelement e , a , b , c , d och f . Låt e  vara ett neutralt element. Eftersom det neutrala elementet är detsamma som dess invers, och inversen är unik, måste det finnas minst ett annat element som är samma som dess invers. Således får vi följande möjliga skelett:

I vårt fall finns det ingen grupp av den första typen av ordning 6. Det faktum att ett skelett är möjligt innebär inte alls att det finns en grupp vars skelett sammanfaller med det.

Anmärkningsvärt är det faktum (och det är lätt att bevisa) att varje grupp där något element sammanfaller med dess invers är abelian.

Komplettera tabellen enligt skelettet av neutrala element

Om skelettet av neutrala element anges kan du börja fylla i Cayley-tabellen. Låt oss till exempel välja det andra skelettet i gruppen av ordning 6 från de som beskrivs ovan:

e a b c d f
e e
a e
b e
c e
d e
f e

Uppenbarligen kan rad e och kolumn e fyllas direkt. När detta är gjort kan det bli nödvändigt (och det är nödvändigt i vårt fall) att göra ett antagande, vilket i efterhand kan leda till en motsägelse, vilket kommer att innebära att antagandet är felaktigt. Vi antar att ab = c . Sedan:

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

Multiplicerar vi ab = c från vänster med a , får vi b = ac . Rätt multiplikation med c ger bc = a . Att multiplicera ab = c från höger med b ger a = cb . Multiplicera bc = a från vänster med b ger c = ba och multiplicera från höger med a ger ca = b . Efter att ha fyllt i dessa produkter i tabellen ser vi att ad och af förblir tomma i rad a . Eftersom varje element måste visas exakt en gång i rad får vi att annonsen måste vara antingen d eller f . Detta element kan dock inte vara lika med d , eftersom a annars skulle vara lika med e , medan vi vet att de två elementen är olika. Således ad = f och af = d .

Nu, eftersom inversen av d är f , multiplicering av ad = f från höger med f ger a = f 2 . Vänstermultiplikation med d ger da = f . Multiplicerar vi till höger med a får vi d = fa .

Efter att ha angett alla dessa verk kommer Cayley-bordet att ha formen:

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

Eftersom varje element i gruppen måste förekomma exakt en gång i varje rad, är det lätt att se att de två tomma tabellcellerna i rad b måste vara upptagna av antingen d eller f . Men d och f finns redan i motsvarande kolumner . Alltså, vad vi än lägger i dessa fält kommer vi att få upprepning i kolumnerna, vilket visar att vår initiala gissning ab = c var fel. Men nu vet vi att ab ≠ c .

Det finns två möjligheter kvar - antingen ab = d eller ab = f . Eftersom d och f är ömsesidigt inversa och valet av bokstäver är godtyckligt, bör vi förvänta oss att resultatet blir detsamma fram till isomorfism. Utan förlust av generalitet kan vi anta att ab = d . Om vi ​​nu får en motsägelse måste vi erkänna att det inte finns någon motsvarande grupp för detta skelett.

Vi får ett nytt Cayley-bord:

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

Om vi ​​multiplicerar ab = d till vänster med a får vi b = ad . Höger multiplikation med f ger bf = a , och vänster multiplikation med b ger f = ba . Multiplicerar vi till höger med a får vi fa = b , och multiplicerar vi till vänster med d får vi a = db . När vi anger resultaten i Cayley-tabellen får vi (nya element är markerade i rött):

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

Strängen a saknar c och f , men eftersom af inte kan vara lika med f (annars skulle a vara lika med e ), kan vi dra slutsatsen att af = c . Multiplicera till vänster med a ger f = ac , och detta kan vi multiplicera till höger med c , vilket ger fc = a . Att multiplicera det senare med d till vänster ger c = da , som vi kan multiplicera till höger med a för att få ca = d . På samma sätt, multiplicerar vi af = c från höger med d , får vi a = cd . Uppdatera tabellen (de senaste ändringarna är markerade i blått):

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

Eftersom strängen b inte innehåller c och d , och bc inte kan vara lika med c , härleder vi att bc = d , så produkten av bd måste vara lika med c . Att multiplicera till höger med f ger oss b = cf , som kan omvandlas till cb = f genom att multiplicera med c till vänster. På liknande sätt kan vi härleda att c = fb och dc = b . Vi gör ändringar i tabellen (de introducerade elementen är markerade i grönt):

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

Endast f saknas på rad d , så d 2 = f . På samma sätt får vi att f 2 = d . Vi har fyllt i hela tabellen och har inte kommit fram till någon motsägelse. Således har vi hittat en grupp av ordning 6 som motsvarar skelettet. En titt på tabellen visar att den inte är abelsk. I själva verket är detta den minsta icke-abelska gruppen, den dihedriska gruppen D 3 :

* 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

Permutationsmatrisgenerering

I standardformen för Cayley-tabellen är ordningen på rader och kolumner densamma. Ett annat sätt att ordna är att ordna kolumner på ett sådant sätt att den n -te kolumnen motsvarar de omvända elementen i den n -te raden. I vårt exempel för D 3 behöver vi bara byta de två sista kolumnerna, eftersom endast f och d inte är inversa till sig själva, utan är inversa till varandra.

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

I vårt exempel kan sex permutationsmatriser skapas (alla element är 1 eller 0, en 1 i varje rad och varje kolumn). 6x6-matrisen innehåller en etta om kolumnetiketten matchar radetiketten och nollor i alla andra fält, Kronecker-symbolen för etiketten. (Observera att för raden e får vi identitetsmatrisen.) Till exempel för a får vi permutationsmatrisen.

e a b c f d
e 0 ett 0 0 0 0
a ett 0 0 0 0 0
b 0 0 0 0 ett 0
c 0 0 0 0 0 ett
d 0 0 ett 0 0 0
f 0 0 0 ett 0 0

Detta visar att varje grupp av ordningen n är en undergrupp till permutationsgruppen Sn av ordningen n !.

Generaliseringar

De egenskaper som beskrivs ovan beror på vissa axiom för grupper. Det är naturligt att utöka Cayley-tablåerna till några andra algebraiska strukturer som semigrupper , kvasigrupper och magma , men några av ovanstående egenskaper kommer inte att hålla för dem.

Se även

Länkar