A Tour of AbstractAlgebra

An abbreviated tour through this notebook was given at the Worldwide Mathematica Conference held in Chicago, June, 1998.

Al Hibbard (Central College - hibbarda@central.edu)
Ken Levasseur (UMass-Lowell - Kenneth_Levasseur@uml.edu)
http://www.central.edu/eaam.html

Startup

First, we load the Master package, which will load in all of the names that are used in the AbstractAlgebra packages.

Needs["AbstractAlgebra`Master`"]

Since we will first consider groups, we switch the structure to Group.

SwitchStructureTo[Group]

The Basic Structures

There are three basic Mathematica data structures used in AbstractAlgebra: the Groupoid, Ringoid, and Morphoid. These are generalizations of groups, rings and morphisms. We will use groupoid, ringoid and function when we refer to the mathematical counterparts to the corresponding Mathematica data structures.

Groupoids

A Groupoid consists of a set of elements and a "binary" operation (two inputs from the space whose images do not need to belong to this space). One means of creating one of these is with the FormGroupoid option.

G = FormGroupoid[{0, 2, 1, 4, 6}, Times, GroupoidName -> "ex.1"]

We can easily extract the operation and elements of any groupoid.

Operation[G]Elements[G]

We are often interested in whether a groupoid has an identity element or not.

HasIdentityQ[G]

Many functions can take on additional Modes, such as Textual or Visual.

HasIdentityQ[G,  Mode  ->  Textual]

HasIdentityQ[G,  Mode  ->  Visual]

Another group axiom to consider is whether all the elements have inverses.

HasInversesQ[G,  Mode  -> Textual]

Closure is another required property of being a group. Here is the Visual mode of this Boolean function.

ClosedQ[G,  Mode ->  Visual]

Finally, the last required property is associativity. This visualization chooses a random triple and pursues whether these three elements obey this property.

AssociativeQ[G,  Mode -> Visual]

The GroupInfo function returns all the information learned about a groupoid from tests that have been performed.

GroupInfo[G]

Instead of testing the axiomatic properties individually, we can also test these together with one function.

GroupQ[G]

The Cayley table is a tool that can reveal a number of interesting properties regarding a group.

CayleyTable[G,  Mode  ->  Visual]

Ringoids

Since we now wish to consider rings, we switch our structure.

SwitchStructureTo[Ring]

FormRingoid works in a fashion analogous to FormGroupoid. The required parameters are the list of elements, the addition operation and the multiplication operation. Options can be added afterwards.

R = FormRingoid[{0, 2, 1, 4, 6}, Plus, Times, FormatOperator -> False, FormatElements -> True]

RingQ is similar to GroupQ; upon the first failure, it returns False.

RingQ[R]

Similarly, RingInfo is similar to GroupInfo.

RingInfo[R]

Since there are two operations, we need to view the Cayley tables of both operations.

CayleyTables[R,  Mode  ->  Visual]

Here we form the extension ring of polynomials over the Boolean ring on {1, 2, 3} and choose a random polynomial of degree 2 that is monic (leading coefficient is the unity).

RandomElement[PolynomialsOver[BooleanRing[3]], 2, Monic -> True]

Next we consider a random 3 by 3 matrix whose elements come from the lattice ring on the divisors of 12 (with operation LCM/GCD for the addition and GCD for the multiplication.

RandomElement[MatricesOver[LatticeRing[12], 3]] // MatrixForm

The third type of ring extension is the ring of functions over a ring; here we use (Subscript[ℤ, 12]).

RandomElement[FunctionsOver[ZR[12]]]

As a last example here, we form the Galois field of order 9.

GF[9]

Morphoids

To form a Morphoid, the parameters are a (pure) function and then either two groupoids or two ringoids. (The function has the first structure as the domain and the second as the codomain.)

f = FormMorphoid[Mod[#, 6]&, Z[12], Z[6]]

The MorphismQ function determines if this is a (ring) homomorphism.

MorphismQ[f]

To see visually why the operation is preserved for the pair (3, 5), try the following.

PreservesQ[f,  {3, 5},  Mode  ->  Visual]

We now switch back to groups.

SwitchStructureTo[Group]

At this point, we now build a group homomorphism.

g = FormMorphoid[Mod[#, 6]&, Z[12], Z[6]]

We see different results now that we are working with groups.

PreservesQ[g,  {3, 5},  Mode  ->  Visual]

Sometimes morphisms are more easily set up by matching how we want the elements to line up.

FormMorphoidSetup[D[4],  Z[8]];

We want to send the first element in the domain to the first element in the codomain, the second element in the domain to the third element in the codomain, the third to the fifth etc.

h  = FormMorphoid[{1, 3, 5, 7, 2, 4, 6, 8}, D[4],  Z[8]]

Here we see that this is not a homomorphism on the whole group, but note that we can see a homormorphism from the rotational subgroup to the set {0, 2, 4, 6}.

MorphismQ[h,  Mode  ->  Visual]

Help Browser

We have implemented full documentation into the Help Browser. Before using, you need to download and install from http://www.central.edu/eaam.html, choose Rebuild Help Index from the Help menu and then access it from the AddOns button.

Exploring Abstract Algebra with Mathematica

description

The packages in AbstractAlgebra form the foundation for a series of 14 group labs and 13 ring labs designed to help students conceptualize abstract algebra. These are combined with documentation for AbstractAlgebra in a book entitled Exploring Abstract Algebra with Mathematica (EAAM) published by TELOS/Springer-Verlag (fall/winter 1998).

group labs

Group Lab 1. Using symmetry to uncover a group -- This lab explores the underlying definitions of a group by looking at the symmetries of an equilateral triangle.

Group Lab 2. Determining the symmetry group of a given figure -- The focus of this lab is to determine the symmetry group of a figure chosen randomly from a list of regular polygons and "cyclic" objects.

Group Lab 3. Is this a group? -- This lab randomly presents a Cayley table of one of 20 "possible groups." The goal is to determine which of the defining properties of a group are reflected in the Cayley table to see if it represents a group.

Group Lab 4. Let's get these orders straight! -- This lab looks at the order of an element and its inverse, the distribution of the orders of the elements in (Subscript[ℤ, n]), investigates the probability that an element in (Subscript[ℤ, n]) has order n and also explores the group (Subscript[U, n]) (the units in (Subscript[ℤ, n])).

Group Lab 5. Subversively grouping our elements -- This lab explores the notion of a subgroup, including looking at the subgroups of (Subscript[ℤ, n]) and (Subscript[U, n]), calculating the probability that a random subset of (Subscript[ℤ, n]) is a subgroup and determining what elements in a subset are necessary so that the closure yields the whole group.

Group Lab 6. Cycling through the groups -- Here we focus on the notion of a cyclic group and its subgroup structure. We also look at the determining when the direct sum of (Subscript[ℤ, m]) and (Subscript[ℤ, n]) yields a cyclic group.

Group Lab 7. Permutations -- This lab looks at the definition of a permutation, how to perform computations and explore properties. We also look at some applications of permutations.

Group Lab 8. Isomorphisms -- Here we look at the definition of an isomorphism and then use various visual mechanisms to try to determine when two groups are or are not isomorphic.

Group Lab 9. Automorphisms -- In this lab, we look at the group of automorphisms of (Subscript[ℤ, n]) and also look at inner automorphisms.

Group Lab 10. Direct Products -- The notion of direct products (sums) are introduced and we determine the order of elements in a direct product. We also try to determine when the direct product of cyclic groups is still cyclic. We also look for isomorphisms between some (Subscript[U, n]) groups.

Group Lab 11. Cosets -- This lab explores the definition and properties of cosets.

Group Lab 12. Normality and Factor groups -- A normal group is defined and explored and then used to define and explore factor groups.

Group Lab 13. Homomorphisms -- This lab explores group homomorphisms.

Group Lab 14: Rotational groups of regular polyhedra -- Here we look at how to generate the rotational groups of several polyhedra.

ring labs

Ring Lab 1. An Introduction to Ringoids and Rings -- This introduces some of the definitions and properties of rings.

Ring Lab 2. An Introduction to Rings: part two -- Guess what this is about!

Ring Lab 3. An ideal part of rings -- This explores the notion of an ideal and properties related to it.

Ring Lab 4. What does \(TraditionalForm
      \`ℤ[i]/
        ⟨a + b\ i⟩\) look like? -- This lab focuses on the Gaussian integers mod an ideal generated by some Gaussian integer.

Ring Lab 5. Ring homomorphisms -- This lab looks at ring homomorphisms, the First Isomorphism Theorem, and the Chinese Remainder Theorem.

Ring Lab 6. Polynomial rings -- Some basic properties of polynomial rings are introduced and explored.

Ring Lab 7. Factoring and irreducibility -- What does it mean to factor a polynomial? Various definitions and techniques are introduced. 

Ring Lab 8. Roots of unity -- This lab focuses on the polynomial (x^n) - 1 and explores graphically the zeros of this polynomial, in particular seeing how the zeros are related to the factors and how the group (Subscript[U, n]) springs out of this.

Ring Lab 9. Cyclotomic polynomials -- This lab focuses on cyclotomic polynomials and the many properties related to them.

Ring Lab 10. Quotient rings of polynomials -- The notion of a quotient ring over a polynomial is introduced in this lab.

Ring Lab 11. Quadratic field extensions -- This lab continues the last by looking more closely at quotient rings modulo a quadratic polynomial where the result is a field.

Ring Lab 12. Factoring in ℤ[(Sqrt[d])] -- This lab focuses on the rings ℤ[(Sqrt[d])] and pursues the notion of divisibility and factoring in such rings. Several rings are illustrated as failing being a UFD.

Ring Lab 13. Finite Fields -- This lab continues the ideas formulated in lab 11 by looking at Galois fields and properties related to them.

GroupCalculator

See our web page for a group calculator to download it. (For now, start with a clean kernel, clearing out any previous AbstractAlgebra definitions.)

More Groupoids

There are a number of options for controlling how groupoids, ringoids and morphoids are formed.

Options[FormGroupoid]

We can form the permutation group on any set of elements.

H = PermutationGroup[{α, β, γ}]

Here is the Cayley table of the group just formed, using a Key since the elements are too wide for the table.

CayleyTable[H,  Mode ->  Visual,  
      KeyForm  ->  StandardForm];

We form a list of some groups, to be used below.

someGroups  =  {Z[5],  Dihedral[4],  Symmetric[3],  U[15]}

Most functions can take a list of arguments, as shown here with CayleyTable.

CayleyTable[someGroups,  Mode  ->  Visual];

Here is a visualization of why the following groups are or are not cyclic.

CyclicQ[someGroups,  Mode  ->  Visual]

Loops indicate self-inversive elements, while lines connect other inverses.

Inverses[U[15],  Mode  ->  Visual]

We can form the direct product of any number of groupoids.

G = DirectProduct[Z[5], U[4]]

Here we choose 2 random elements from this group, each of which are pairs.

{g, h}  =  RandomElements[G,  2]

We can apply the group operation to these elements as follows.

Operation[G][g,h]

Here is a nonsense groupoid formed by specifying the "group" table.

H  =  
      FormGroupoidByTable[{b, a, a**b, 
          (a^b)}, {{a, a**b, b, (a^b)}, {b, a, (a^b), a**b}, {a**b, (a^b), b, 
            a}, {(a^b), a**b, a, b}}, "*", WideElements -> True]

The CayleyTable function has a large number of options, as well as the ability to take Graphics options.

CayleyTable[H, Mode -> Visual,  ShowName  ->  False,  
      VarToUse  ->  "hi",  KeyForm  ->  FullForm,  
      Background ->  Cyan, CayleyForm  ->  Characters,  
      Epilog  -> {RGBColor[1, 0, 0], Thickness[0.02], 
          Line[{{-1, 0}, {5, 6}}]}]

Each groupoid in CayleyTable can receive different options.

CayleyTable[{G, 
        H}, {{ShowBodyText -> False}, {ShowKey -> False}}, 
      Mode -> Visual];

We can work with Gaussian integers reduced some modulus.

Z[4, I]

The TwistedZ is an interesting groupoid that is sometimes a group.

SubgroupQ[ {0,  2 ,  8}, TwistedZ[13]]

The SubgroupQ function takes multiple requests in the following fashion.

SubgroupQ[{{ {0, 3}, Z[5]},  { {1, 4}, U[9]}},  
      Mode  ->  Visual]

Given the set {1,4} of the group (Subscript[ℤ, 9]), the following shows how the closure of this set is built up in three iterations.

Closure[Z[9],  {1,  4},  ReportIterations  ->  True]

One may want the elements to be canonically sorted.

Closure[Z[9],  {1,  4},  Sort  ->  True]

Here is a animation indicating the subgroup generated by 6 in the group (Subscript[ℤ, 8]).

SubgroupGenerated[Z[8],  6,  Mode  ->  Visual]

Here is the same but using a GraphicsArray for its display.

SubgroupGenerated[Z[8],  6,  Mode  ->  Visual,  
      Output  ->  GraphicsArray]

We can find all cyclic subgroups of any group.

CyclicSubgroups[D[4]]

Here is a visualization showing the left coset 7 + {0, 4} in the group (Subscript[ℤ, 8]).

LeftCoset[Z[8],  {0,  4},  7,  Mode  ->  Visual]

This illustrates how an operation makes sense on the following right cosets. This also shows a quotient group.

gr1  =  
      RightCosets[Z[8],  {0,  4},  Mode  ->  Visual,  
        Output  ->  Graphics];

By specifying Output -> Graphics, we indicate that we want the graphic as the output, not the actual Cayley table.

gr2  =  
      CayleyTable[Z[4],  Mode  ->  Visual,  
        Output  ->  Graphics];

Putting the two side-by-side makes it clear to what group this quotient group (Subscript[ℤ, 8])/{0, 4} is isomorphic.

Show[GraphicsArray[{gr1,  gr2}]];

The following indicates that \(TraditionalForm
      \`⟨{3, 2, 1}⟩\) in (Subscript[S, 3]) is not normal.

NormalQ[H  =  SubgroupGenerated[Symmetric[3],  {3,  2,  1}], 
      Symmetric[3]]

Because of this lack of normality, the product of cosets is not a well-defined operation, as illustrated here by the failure of having square blocks for products.

LeftCosets[Symmetric[3],   H,  Mode  ->  Visual];

Since {0, 4} is normal in (Subscript[ℤ, 8]), we can form the quotient group.

QuotientGroup[Z[8],  {0,  4}]

Here is a Cayley table of this group, using a different form and set of representatives for the representation of the elements.

CayleyTable[
      QuotientGroup[Z[8],  {0,  4},  Form  ->  Representatives,  
        Representatives  ->  {4, 1, 6,  3}],  
      Mode  ->  Visual]

The same group is shown here using a coset list for each element.

CayleyTable[
      QuotientGroup[Z[8],  {0,  4},  Form  ->  CosetLists],  
      Mode  ->  Visual]

This visulalization shows that 4 is the group exponent for the group (Subscript[U, 15]).

GroupExponent[U[15],  Mode  ->  Visual]

GenerateGroupoid is another means of forming a groupoid.

G  =  
      GenerateGroupoid[{{{2, 1}, {1, 1}}},  Mod[#1 . #2,  3]&,  
        WideElements  ->  True]

More Ringoids

Before working with rings, we switch our dominant structure.

SwitchStructureTo[Ring]

Here we see which rings (Subscript[ℤ, n]) are fields.

Map[{#, FieldQ[Z[#]]}&, Range[3, 9]]

This shows that this quotient ring is also a field.

FieldQ[QuotientRing[Z[3], Poly[Z[3], (x^2) + x + 2]]]

This gives us a list of powers of the element (3, 6) in the direct product \(TraditionalForm
      \`ℤ\_6×ℤ\_9\).

\(TableForm[
      Map[{#, ElementToPower[DirectProduct[Z[6], Z[9]], {3, 6}, #]}&, 
        Range[\(-1\), 4]], \ 
      TableHeadings\  -> 
        \ {None, \ {"n", \*""(3,6\!\(\()\^n\)\)\n""}}, \ 
      TableDepth\  -> \ 2]\)

Here we have a simple polynomial.

p = Poly[Z[5], (t^2) + 2 t + 3]

We can also form a polynomial by giving the list of coefficients.

q = Poly[Z[5], 4, 3, 2, 1]

Since the list of coefficients have an ordering, we can specify how this should be interpreted if we don't want to assume we are working from left to right.

Poly[Z[5], 4, 3, 2, 1, PowersIncrease -> RightToLeft]

When we are over (Subscript[ℤ, n]), we have more flexibility is the choices of our coefficients in that they do not have to strictly be in the prescribed set, but are reduced first.

Poly[Z[5], (x^2) - x + 11]

In this case, we choose 8 polynomials of degree 2, but allow lower degrees as well (LowerDegreeOK->True). We allow any type of polynmial (SelectFrom -> Any), but we do not want repeats (Replacement -> False).

RandomElements[PolynomialsOver[Z[2]], 2, 8, LowerDegreeOK -> True, 
       SelectFrom  ->  Any,  Replacement  ->  False]

Here is a basic polynomial.

q  =  Poly[Z[12],  (x^2) - 3  x  +  8]

We can ask for the zeros of this polynomial.

Zeros[q]

Finding zeros is equivalent to finding out when the polynomial is equal to the zero; the Solve command generalizes this (as an extension of the built-in Solve command).

Solve[q  ==  6]

We can verify that these are indeed solutions.

q /. %

The polynomials formed with Poly may look like ordinary polynomials, but they are not.

p  =  Poly[Z[7], (x^2) - 8  x  +  44]

In most cases, they can be converted to standard polynomials, although there is rarely a need for this since there are standard polynomial functions to work with the Poly-type form.

ToOrdinaryPolynomial[p]

In this example, we form a 5-by-5 matrix with elements from (Subscript[ℤ, 3]), but restricted to using only the nonzero elements.

RandomElement[MatricesOver[Z[3], 5], 
        SelectBaseElementsFrom -> NonZero] // MatrixForm

We can specify a number of different types of matrices when we want a random matrix.

Map[TraditionalForm, 
      examples = 
        Map[RandomMatrix[Z[5], 3, MatrixType -> #]&, { GL,  SL,  
            Diag,  UT,  LT,  UTD,   LTD , All}]]

We can calculate the determinant of any of these as follows.

Map[Det[Z[5], #]&, examples]

Any of these matrix extensions (if not too large) can be converted to a groupoid.

ToGroupoid[GL[Z[3], 2]]

Here is the Galois field of order 16.

GF[16]

It has a fourth degree extension.

ExtensionDegree[GF[16]]

This gives us a table to compare the multiplicative form using the generator x, against the additive form.

TableOfPowers[GF[2, 4]] // MatrixForm

Instead of using the table, we can use the following function to make conversions (and another one to go the other direction).

AdditiveToMultiplicative[GF[16],1+(x^2)+(x^3)]

More Morphoids

We mostly work with groups here.

SwitchStructureTo[Group]

This gives an animation of the maps from (Subscript[ℤ, 12]) to (Subscript[ℤ, k]) from k = 2 to k = 13.

Do[VisualizeMorphoid[ZMap[12,   k]], {k, 2, 13}]

This is a simple example showing that two cyclic groups of order 5 are indeed isomorphic.

Clear[g]f  = 
      FormMorphoid[g  ->  3,  Cyclic[5,  Generator  ->  g], 
        ZG[5],  Mode  ->  Visual]

We can calculate the kernel and image of any Morphoid.

Kernel[f]Image[f]

We can also test for an isomorphism.

IsomorphismQ[f]

The automorphism group of any cyclic group is readily available.

AutomorphismGroup[Z[8]]

Similarly, the inner automorphism group for any group can be obtained.

InnerAutomorphismGroup[Dihedral[5]]

Since the elements were suppressed, we use the Elements function to reveal them.

Elements[%]

And other stuff

Here is a random permutation.

q =  RandomPermutation[8]

Here is another permutation.

p  =  {1, 6, 2, 4, 7, 3, 5, 8, 9}

We can multiply the permutations in either directions, depending on your convention.

MultiplyPermutations[p, q]MultiplyPermutations[p, q, ProductOrder  ->  LeftToRight]

Any permutation is readily converted to cycles.

ToCycles[p]

And back.

FromCycles[%]

If you like the form found in the standard packages, this is available, although not as clear.

ToCycles[p,  CycleAs  ->  List]

Cycles can be multiplied.

MultiplyCycles[Cycle[3, 6, 4], Cycle[1, 6, 5, 3]]

The product is not commutative unless they are disjoint, so the following function can be used to test this.

DisjointCyclesQ[Cycle[3, 6, 4], Cycle[1, 6, 5, 3]]

Transpositions are just two-cycles and one can find a representation in terms of these.

ToTranspositions[p]

It is the number of transpositions that is important (determining if the permutation is odd or even).

Parity[p]OddPermutationQ[p]

Here we form a groupoid from a list of cycles or products of cycles (using @ as an infix operator for this).

\(G\  = \ 
      FormGroupoidFromCycles[{Cycle[1], \ 
          Cycle[1, 3, 2]\ @\ \(Cycle[4, 6, 5]\ @\ Cycle[7, 8]\), 

          Cycle[1, 3, 2]\ @\ Cycle[4, 6, 5]\ , 

          Cycle[1, 2, 3]\ @\ Cycle[4, 5, 6]\ , 

          Cycle[1, 2, 3]\ @\ \(Cycle[4, 5, 6]\ @\ Cycle[7, 8]\), 

          Cycle[7, 8]}]\)

Given this group, we can find the orbit of the element 4.

Orbit[G,  Range[8],  4]

Which of the following are units over ℤ[(Sqrt[2])]?

Map[ZdUnitQ[2, #]&,  {1 + (Sqrt[2]), -1,  2 + (Sqrt[2]), 1  -  (Sqrt[2])}]

Not satisfied? Some More!

This gives the commutators for (Subscript[D, 3]).

Commutators[Dihedral[3],  Mode  ->  Visual]

G  =  Z[16,  Structure  ->  Group]H  =  SubgroupGenerated[G,  4]

A quotient group is evident here.

SubgroupQ[H,  G,  Mode  ->  Visual2]

This gives us the order of all elements.

U[10] // OrderOfAllElements

Using the above, we can rearrange the elements when making the table, if we so desire. Compare this to the above table.

CayleyTable[U[10],  TheSet  ->  {1, 3, 9, 7},  Mode  ->  Visual, 
       Output  ->  Graphics]

The conjugacy class of elements in various groups can be found.

ConjugacyClass[Symmetric[3],  {2, 3, 1}]

Here are the generators of (Subscript[U, 25]).

CyclicGenerators[U[25]]

This gives us the center of a group.

GroupCenter[Dihedral[4]]