These examples illustrate how to develop a moderately complex software system by using features of the Maple module system. Generic programming is at the heart of the design. Only a fraction of the complete system from which the examples are taken is shown.

A system for computing with finite groups comprises the examples that follow. Recall that a group is a set of objects together with an associative binary operation, for which there is a unique two-sided identity element and every element has a unique inverse within the underlying set. Examples of groups include:

Systems of numbers, using addition

Closed sets of invertible matrices (all of the same size, with a common ground field), using multiplication (linear groups)

Closed sets of permutations (bijective mappings on a set), using composition (permutation groups)

Groups of points on elliptic curves

Only finite groups are discussed.

First, you must decide how to represent the generic group interface. This is determined by the proposed use of the group objects. Once again, the design takes a group to be a repository of data and computational services that you can query or invoke.

The Group signature used in the examples describes a computational model of abstract groups that supports the methods in the following table.

`type/GroupType` := '`module`(
    id, `.`, mul, inv,
    eq, member,
    gens,
    order, elements
)':

A corresponding constructor for groups is easily written using the Record constructor introduced earlier. For the examples in this section, no default methods are introduced.

Group := proc()
    Record( op( `type/GroupType` ) );
end proc:

This constructor does very little work on its own. It relies on more specialized constructors to establish useful values or defaults for the methods exported.

You can write generic algorithms using this interface immediately. A few simple examples are these routines for computing conjugates and commutators of group elements. The conjugate of a group member $a$ by a group member $b$ is $b^{\mathrm{-1}}ab$. This routine computes the conjugate of an element a by an element b in a group G.

Conjugate := proc( G, a, b )
    description "compute the conjugate of a "
                "group element by another";
    use `/` = G:-inv, `.` = G:-`.` in
       b^(-1) . a . b;
    end use;
end proc:

Since the group operations `.` and inv in a generic group remain unassigned, the following computation is done symbolically.

Conjugate( Group(), 'x', 'y' );

$\mathrm{`.`}\left(\mathrm{inv}\left(y\right)\,x\,y\right)$

Similarly, you can compute the commutator $\left[a\,b\right]=a^{\mathrm{-1}}{b}^{\mathrm{-1}}ab$, generically, as follows.

Commutator := proc( G, a, b )
    description "compute the commutator of "
                "two group elements";
    use `/` = G:-inv, mul = G:-mul in
        mul( inv( a ), inv( b ), a, b );
    end use;
end proc:

Again, this computation is done symbolically, so the group operations return unevaluated.

Commutator( Group(), 'x', 'y' );

$\mathrm{mul}\left(\mathrm{inv}\left(x\right)\,\mathrm{inv}\left(y\right)\,x\,y\right)$

The ability to write generic algorithms over a given interface is important for the management of large software projects involving many developers. One developer can be assigned the task of implementing particular group constructors along with the attendant arithmetic, while another developer can begin coding generic routines. The two developers can work independently, provided each ensures that the work conforms to some agreed-upon interface and semantics.

Before attempting to develop any complicated algorithms, it is helpful to have a few constructors for specific kinds of groups. These can then be used to validate generic algorithms in specific instances. For this reason, we will develop a straightforward implementation of permutation groups.

Permutations are represented using Maple lists. For example, the list [2,1,3] represents the permutation that maps 1 -> 2, maps 2 -> 1, and leaves 3 fixed. (In cycle notation, this is written as the transposition (12).) The constructor takes a positive integer as its first argument, indicating the degree of the permutation group. The remaining arguments are expected to be permutations (represented as lists) of the stated degree. These are used to form the generating set of the group returned by the constructor.

PermutationGroup := proc( deg::posint )
    description "permutation group constructor";
    local G, gens;
    gens := { args[ 2 .. -1 ] };
    G := Group();
    G:-id := [ $ 1 .. deg ];
    G:-`.` := proc( a, b )
        local i;
        [ seq( b[ i ], i = a ) ];
    end proc;
    G:-mul := () -> foldl( G:-`.`, G:-id, args );
    G:-inv := proc( g )
        local i, a;
        a := array( 1 .. deg );
        for i from 1 to deg do
            a[ g[ i ] ] := i;
        end do;
        [ seq( a[ i ], i = 1 .. deg ) ];
    end proc;
    G:-member := proc( g, S, pos::name )
        if nargs = 1 then
            type( g, 'list( posint )' )
              and { op( g ) } = { $ 1 .. deg };
        else
            :-member( args );
        end if;
    end proc;
    G:-eq := ( a, b ) -> evalb( a = b );
    G:-gens := gens;
    eval( G, 1 );
end proc:

For example, to construct the group $⟨\left(12\right),\left(123\right)⟩$ in the symmetric group $S_4$, use the PermutationGroup constructor as follows.

G := PermutationGroup( 4, { [2,1,3,4], [2,3,1,4] } );

$G≔\mathrm{Record}\left(\mathrm{id}=\left[1\,2\,3\,4\right]\,\mathrm{`.`}=\mathbf{proc}\left(a\,b\right)\mathbf{local}i\;\left[\mathrm{seq}\left(b\[i\]\,i\=a\right)\right]\mathbf{end\; proc}\,\mathrm{mul}=\left(\left(\right)\mapsto \mathrm{foldl}\left(G:-\mathrm{`.`}\,G:-\mathrm{id}\,\mathrm{args}\right)\right)\,\mathrm{inv}=\mathbf{proc}\left(g\right)\mathbf{local}i\,a\;a:=\mathrm{array}\left(1..4\right)\;\mathbf{for}i\mathbf{to}4\mathbf{do}a\[g\[i\]\]:=i\mathbf{end\; do}\;\left[\mathrm{seq}\left(a\[i\]\,i\=1..4\right)\right]\mathbf{end\; proc}\,\mathrm{eq}=\left(\left(a\,b\right)\mapsto \mathrm{evalb}\left(a=b\right)\right)\,\mathrm{member}=\mathbf{proc}\left(g\,S\,\mathrm{pos}::\mathrm{name}\right)\mathbf{if}\mathrm{nargs}\=1\mathbf{then}\mathrm{type}\left(g\,\'\mathrm{list}\left(\mathrm{posint}\right)\'\right)\mathbf{and}\left\{\mathrm{op}\left(g\right)\right\}\=\left\{\mathrm{`\$`}\left(1..4\right)\right\}\mathbf{else}:-\mathrm{member}\left(\mathrm{args}\right)\mathbf{end\; if}\mathbf{end\; proc}\,\mathrm{gens}=\left\{\left\{\left[2\,1\,3\,4\right]\,\left[2\,3\,1\,4\right]\right\}\right\}\,\mathrm{order}\,\mathrm{elements}\right)$

To compute with its elements, use the methods exported by the instantiated group G.

use G in
    inv( [ 2,1,3,4 ] ) . [2,3,1,4];
end use;

$\left[3\,2\,1\,4\right]$

It is useful to provide more specialized permutation group constructors for special kinds of groups. Using the general constructor PermutationGroup, and overriding some of the exported methods, you can define several of these specialized constructors as follows.

The full symmetric group $S_n$ on the n points { 1, 2, 3, ... , n } is produced by specifying a particular set of generators for a given degree (which must be specified as an argument to the constructor).

Symmetric := proc( n::posint )
    description "symmetric group constructor";
    if n < 2 then
        error "argument must be an integer larger than 1";
    elif n = 2 then
        PermutationGroup( 2, [ 2, 1 ] );
    else
        PermutationGroup( n, [ 2, 1, $ 3 .. n ], [ $ 2 .. n, 1 ] );
    end if;
end proc:

This uses the fact that $S_n$ is the two-generator group

for any integer $3\le n$.

A second special case is the class of dihedral groups. Think of these as the groups of symmetries of regular plane polygons. The symmetry group of the regular $n$-gon is the dihedral group of degree $n$ and order $2n$; it is denoted by ${\mathrm{D}}_n$.

Use the following utility for reversing the order of a list.

lreverse := proc( L::list )
    description "reverse a list";
    option inline;
    [ seq( L[ -i ], i = 1 .. nops( L ) ) ];
end proc:

Dihedral := proc( n::posint )
    description "dihedral group constructor";
    local a, b, D;
    if n = 2 or n = 3 then
        return Symmetric( n );
    end if;
    a := [ $ 2 .. n, 1 ];
    b := [ 1, op( lreverse( [ $ 2 .. n ] ) ) ];
    D := PermutationGroup( n, { a, b } );
    D:-order := () -> 2*n;
    eval( D, 1 );
end proc:

Use the fact that the alternating group $A_n$ of degree $3\le n$ is generated by the set$\left\{\left(123\right),\left(234\right),\left(345\right),\dots ,\left(n-2,n-1,n\right)\right\}$ of 3-cycles to write a constructor Alternating for this class of groups.

Dimino's algorithm is used to compute a complete enumeration of the elements of a finite group, given a generating set for the group. Suppose that you are given a generating set $\left\{g_1,g_2,\dots ,g_n\right\}$ for a finite group G. The idea behind Dimino's algorithm is to enumerate, successively, the elements of each of the subgroups

of G, which form a chain

These elements can be enumerated by forming products of the generators $g_1$, $g_2$, ... , $g_n$ in all possible ways, until all the elements of G have been found. Dimino's algorithm does this in a careful way, avoiding unnecessary product computations.

Use the following utility routine to determine the entries assigned to a table. It can be used when you are certain no entry is a non-NULL expression sequence. Since it is sufficiently simple, it is defined with option inline;.

Entries := proc( T )
    description "return a set of simple table entries";
    option inline;
    map( op, { entries( T ) } );
end proc:

Here is the code for Dimino's algorithm.

Dimino := proc( G::GroupType )
    description "enumerate the elements of a finite group";
    local s, g, ord, elements, i, j, prev_ord, rep_pos,
          elt, addElt, gens;

    if nargs > 1 then
        gens := args[ 2 ];
    else
        gens := G:-gens;
    end if;

    if not type( gens, '{ set, list }' ) then
        error "no generating set specified";
    end if;

    if nops( gens ) = 0 then
        # trivial group
        return { G:-id };
    end if;

    addElt := proc( h )
        ord := 1 + ord;
        elements[ ord ] := h;
    end proc;

    elements := table();
    ord := 0;
    addElt( G:-id );

    # Handle the first cyclic subgroup
    s := gens[ 1 ];
    g := s;
    while not G:-eq( g, G:-id ) do
        addElt( g );
        g := G:-`.`( g, s );
    end do;
    userinfo( 1, 'Dimino', "finished first cycle; order is:", ord );

    for i from 2 to nops( gens ) do
        userinfo( 1, 'Dimino', "Adding generator number:", i );
        s := gens[ i ];
        if not G:-member( s, Entries( elements ) ) then
            prev_ord := ord;
            addElt( s );
            for j from 2 to prev_ord do
                addElt( G:-`.`( elements[ j ], s ) );
            end do;
            rep_pos := 1 + prev_ord;
            do
                for s in gens[ 1 .. i ] do
                    elt := G:-mul( elements[ rep_pos ], s );
                    if not G:-member( elt, Entries( elements ) ) then
                        addElt( elt );
                        for j from 2 to prev_ord do
                            addElt( G:-`.`( elements[ j ], elt ) );
                        end do;
                    end if;
                end do;
                rep_pos := rep_pos + prev_ord;
                if rep_pos > ord then
                    break;
                end if;
            end do;
        end if;
    end do;
    Entries( elements );
end proc:

The coding of this algorithm is generic. The exported members of the group object G are used to effect computations within the procedure. Even comparisons of equality use the export eq instead of the built-in comparison operator `=`. (The need for this is illustrated below.)

Using the Symmetric constructor previously defined, you can compute the elements of the symmetric group $S_4$, using Dimino's algorithm, as follows.

G := Symmetric( 4 );

$G≔\mathrm{Record}\left(\mathrm{id}=\left[1\&comma;2\&comma;3\&comma;4\right]\&comma;\mathrm{`.`}=\mathbf{proc}\left(a\&comma;b\right)\mathbf{local}i\&semi;\left[\mathrm{seq}\left(b\&lsqb;i\&rsqb;\&comma;i\&equals;a\right)\right]\mathbf{end\; proc}\&comma;\mathrm{mul}=\left(\left(\right)\mapsto \mathrm{foldl}\left(G:-\mathrm{`.`}\&comma;G:-\mathrm{id}\&comma;\mathrm{args}\right)\right)\&comma;\mathrm{inv}=\mathbf{proc}\left(g\right)\mathbf{local}i\&comma;a\&semi;a:=\mathrm{array}\left(1..4\right)\&semi;\mathbf{for}i\mathbf{to}4\mathbf{do}a\&lsqb;g\&lsqb;i\&rsqb;\&rsqb;:=i\mathbf{end\; do}\&semi;\left[\mathrm{seq}\left(a\&lsqb;i\&rsqb;\&comma;i\&equals;1..4\right)\right]\mathbf{end\; proc}\&comma;\mathrm{eq}=\left(\left(a\&comma;b\right)\mapsto \mathrm{evalb}\left(a=b\right)\right)\&comma;\mathrm{member}=\mathbf{proc}\left(g\&comma;S\&comma;\mathrm{pos}::\mathrm{name}\right)\mathbf{if}\mathrm{nargs}\&equals;1\mathbf{then}\mathrm{type}\left(g\&comma;\&apos;\mathrm{list}\left(\mathrm{posint}\right)\&apos;\right)\mathbf{and}\left\{\mathrm{op}\left(g\right)\right\}\&equals;\left\{\mathrm{`\$`}\left(1..4\right)\right\}\mathbf{else}:-\mathrm{member}\left(\mathrm{args}\right)\mathbf{end\; if}\mathbf{end\; proc}\&comma;\mathrm{gens}=\left\{\left[2\&comma;1\&comma;3\&comma;4\right]\&comma;\left[2\&comma;3\&comma;4\&comma;1\right]\right\}\&comma;\mathrm{order}\&comma;\mathrm{elements}\right)$

Dimino( G );

$\left\{\left[1\&comma;2\&comma;3\&comma;4\right]\&comma;\left[1\&comma;2\&comma;4\&comma;3\right]\&comma;\left[1\&comma;3\&comma;2\&comma;4\right]\&comma;\left[1\&comma;3\&comma;4\&comma;2\right]\&comma;\left[1\&comma;4\&comma;2\&comma;3\right]\&comma;\left[1\&comma;4\&comma;3\&comma;2\right]\&comma;\left[2\&comma;1\&comma;3\&comma;4\right]\&comma;\left[2\&comma;1\&comma;4\&comma;3\right]\&comma;\left[2\&comma;3\&comma;1\&comma;4\right]\&comma;\left[2\&comma;3\&comma;4\&comma;1\right]\&comma;\left[2\&comma;4\&comma;1\&comma;3\right]\&comma;\left[2\&comma;4\&comma;3\&comma;1\right]\&comma;\left[3\&comma;1\&comma;2\&comma;4\right]\&comma;\left[3\&comma;1\&comma;4\&comma;2\right]\&comma;\left[3\&comma;2\&comma;1\&comma;4\right]\&comma;\left[3\&comma;2\&comma;4\&comma;1\right]\&comma;\left[3\&comma;4\&comma;1\&comma;2\right]\&comma;\left[3\&comma;4\&comma;2\&comma;1\right]\&comma;\left[4\&comma;1\&comma;2\&comma;3\right]\&comma;\left[4\&comma;1\&comma;3\&comma;2\right]\&comma;\left[4\&comma;2\&comma;1\&comma;3\right]\&comma;\left[4\&comma;2\&comma;3\&comma;1\right]\&comma;\left[4\&comma;3\&comma;1\&comma;2\right]\&comma;\left[4\&comma;3\&comma;2\&comma;1\right]\right\}$

Anticipating later developments, the procedure Dimino has been coded to accept a second, optional argument that specifies an alternate set of generators to use. Thus, you could compute the same set using the set$\left\{\left(12\right),\left(23\right),\dots ,(n-1,n)\right\}$ of transpositions instead.

Dimino( G, { [2,1,3,4], [1,3,2,4], [1,2,4,3] } );

$\left\{\left[1\&comma;2\&comma;3\&comma;4\right]\&comma;\left[1\&comma;2\&comma;4\&comma;3\right]\&comma;\left[1\&comma;3\&comma;2\&comma;4\right]\&comma;\left[1\&comma;3\&comma;4\&comma;2\right]\&comma;\left[1\&comma;4\&comma;2\&comma;3\right]\&comma;\left[1\&comma;4\&comma;3\&comma;2\right]\&comma;\left[2\&comma;1\&comma;3\&comma;4\right]\&comma;\left[2\&comma;1\&comma;4\&comma;3\right]\&comma;\left[2\&comma;3\&comma;1\&comma;4\right]\&comma;\left[2\&comma;3\&comma;4\&comma;1\right]\&comma;\left[2\&comma;4\&comma;1\&comma;3\right]\&comma;\left[2\&comma;4\&comma;3\&comma;1\right]\&comma;\left[3\&comma;1\&comma;2\&comma;4\right]\&comma;\left[3\&comma;1\&comma;4\&comma;2\right]\&comma;\left[3\&comma;2\&comma;1\&comma;4\right]\&comma;\left[3\&comma;2\&comma;4\&comma;1\right]\&comma;\left[3\&comma;4\&comma;1\&comma;2\right]\&comma;\left[3\&comma;4\&comma;2\&comma;1\right]\&comma;\left[4\&comma;1\&comma;2\&comma;3\right]\&comma;\left[4\&comma;1\&comma;3\&comma;2\right]\&comma;\left[4\&comma;2\&comma;1\&comma;3\right]\&comma;\left[4\&comma;2\&comma;3\&comma;1\right]\&comma;\left[4\&comma;3\&comma;1\&comma;2\right]\&comma;\left[4\&comma;3\&comma;2\&comma;1\right]\right\}$

You still need to pass the group object G for Dimino to access its operations.

Dimino's algorithm is a useful fallback algorithm, but many finite groups of interest can be enumerated more efficiently using specific knowledge of their structure. For small examples, the implementation presented here suffices, but a well-optimized implementation that takes advantage of fast arithmetic for group elements is required.

A subset of a group that forms a group for larger groups (using the operations inherited from the group, by restriction) is called a subgroup. For example, the 3-member set { (123), (132), (1) } is a subgroup of the full symmetric group $S_3$ of degree 3 (which has 6 members). There are many approaches for the representation of subgroups. One way is to represent a subgroup H of a known group G by specifying a generating set for H and copying the computational services from the representation of G to the representation of H. Thus, the Maple representations G and H of G and H would both be of type GroupType.

There is a different approach that is better suited to implicit representations of subgroups. This design can be extended to allow implicit representations of subgroups that you do not need to compute with directly. The idea is to represent a subgroup by a simpler structure that maintains a link to its parent group and an indication of how it is defined in terms of its parent group. Thus, a subgroup is represented by a module with an export parent that is assigned the group in which the subgroup is contained. A second export has a name depending upon the way in which the subgroup is defined. One way to define a subgroup in terms of its parent is to specify a generating set. Subgroups defined in this way are represented by a module having the export gens of type set. A second way to define a subgroup is by a property. For example, the center of a group is defined by the property that all its members commute with every element of the group (or, equivalently, that each member of the subgroup commutes with all the generators of the parent group). You can specify properties by using a procedure that tests for membership in the subgroup. Thus, subgroups can be described by either of the following interfaces.

Only one of the methods test and gens need be present. A Maple implementation of this interface is as follows.

`type/SubGroup` := '{
    `module`( parent::GroupType, gens::set ),
    `module`( parent::GroupType, test::procedure )
}':

The SubGroup constructor must dispatch on the type of its second argument to determine which kind of record to create to model the subgroup.

SubGroup := proc( G::{GroupType,SubGroup}, how::{set,procedure} )
    description "subgroup constructor";
    local S;
    if type( how, 'procedure' ) then
        S:= Record( 'parent', 'test' = eval( how, 1 ) );
    else
        S := Record( 'parent', 'gens' = how );
    end if;
    S:-parent := G;
    eval( S, 1 );
end proc:

For example, the center of the symmetric group $S_3$ can be defined as follows.

S3 := Symmetric( 3 ):
Z := SubGroup( S3, proc( z )
    local g;
    use S3 in
        for g in gens do
            if not eq( mul( inv( g ), inv( z ), g ), z ) then
                return false;
            end if;
        end do;
    end use;
    true;
end proc );

$Z≔\mathrm{Record}\left(\mathrm{parent}=\mathrm{S3}\&comma;\mathrm{test}=\mathbf{proc}\left(z\right)\mathbf{local}g\&semi;\mathbf{for}g\mathbf{in}\mathrm{S3}:-\mathrm{gens}\mathbf{do}\mathbf{if}\mathbf{not}\mathrm{S3}:-\mathrm{eq}\left(\mathrm{S3}:-\mathrm{mul}\left(\mathrm{S3}:-\mathrm{inv}\left(g\right)\&comma;\mathrm{S3}:-\mathrm{inv}\left(z\right)\&comma;g\right)\&comma;z\right)\mathbf{then}\mathbf{return}\mathrm{false}\mathbf{end\; if}\mathbf{end\; do}\&semi;\mathrm{true}\mathbf{end\; proc}\right)$

Z:-test( [2,1,3] );

$\mathrm{false}$

Z:-test( [2,3,1] );

$\mathrm{false}$

Z:-test( [1,2,3] );

$\mathrm{true}$

Similarly, you can write a constructor for the centralizer of an element in a group.

Centralizer := proc( G, g )
    SubGroup( G, proc( s )
                   use `.` = G:-`.`, `=` = G:-eq in
                       s . g = g . s;
                   end use; end proc );
end proc:

Dimino's algorithm is relatively slow. For many classes of groups, there are better alternatives for enumerating group elements. Use Dimino's algorithm only as a last resort. The advantage of Dimino's algorithm is that it works for any finite group. To provide a clean and uniform interface to the enumeration functionality, you can develop a front-end procedure, which hides the details, to choose the best available algorithm.

GroupElements := proc( G )
    description "enumerate the elements of a finite group";
    if type( G, 'GroupType' ) then
        if type( G:-elements, 'set' ) then
            G:-elements;
        elif type( G:-elements, 'procedure' ) then
            G:-procedure();
        else
            G:-elements := Dimino( G );
        end if;
    else
        'procname'( args );
    end if;
end proc:

Several elements of the design allow you to take advantage of structural knowledge to improve efficiency. This routine first checks whether the export elements of its input group is of type set. If it is, then it is taken to be a stored enumeration of the group elements and is simply returned. Otherwise, if the export elements is a procedure, then it is taken to be a (perhaps specialized) routine for computing the requested enumeration. Finally, Dimino's algorithm is used as a last resort if no better alternative is provided. As a simple optimization, the result of Dimino's algorithm is stored as a new value for the elements export so that it need only be computed once.

Providing the GroupElements interface shields the user from needing to know what the available alternatives are and how to use them. An additional benefit of the design is that it allows you to change the algorithm selection criteria at any time (to correct software faults, or make functional or performance improvements). Code using this interface need not be modified, provided that the routine continues to honor its contract.

Once the elements of the parent group are known, the members of the subgroup can be computed using a call to the built-in Maple command select:

select( C:-test, Dimino( G ) );

How best to enumerate the elements of a subgroup depends upon how it is defined and what is known about the parent group. The procedure SubGroupElements that follows takes a subgroup as argument and attempts to find the optimal way to compute the elements of the subgroup from among the available methods.

SubGroupElements := proc( S )
    description "enumerate the elements of "
                "a subgroup of a group";
    local P;
    P := S;
    while type( P, 'SubGroup' ) do
        P := P:-parent;
    end do;
    if type( P, 'GroupType' ) then
        if member( :-test, S ) then
            select( S:-test, GroupElements( P ) );
        else
            ASSERT( member( :-gens, S ) );
            Dimino( P, S:-gens );
        end if;
    else
        'procname'( args );
    end if;
end proc:

G := Symmetric( 4 );

$G≔\mathrm{Record}\left(\mathrm{id}=\left[1\&comma;2\&comma;3\&comma;4\right]\&comma;\mathrm{`.`}=\mathbf{proc}\left(a\&comma;b\right)\mathbf{local}i\&semi;\left[\mathrm{seq}\left(b\&lsqb;i\&rsqb;\&comma;i\&equals;a\right)\right]\mathbf{end\; proc}\&comma;\mathrm{mul}=\left(\left(\right)\mapsto \mathrm{foldl}\left(G:-\mathrm{`.`}\&comma;G:-\mathrm{id}\&comma;\mathrm{args}\right)\right)\&comma;\mathrm{inv}=\mathbf{proc}\left(g\right)\mathbf{local}i\&comma;a\&semi;a:=\mathrm{array}\left(1..4\right)\&semi;\mathbf{for}i\mathbf{to}4\mathbf{do}a\&lsqb;g\&lsqb;i\&rsqb;\&rsqb;:=i\mathbf{end\; do}\&semi;\left[\mathrm{seq}\left(a\&lsqb;i\&rsqb;\&comma;i\&equals;1..4\right)\right]\mathbf{end\; proc}\&comma;\mathrm{eq}=\left(\left(a\&comma;b\right)\mapsto \mathrm{evalb}\left(a=b\right)\right)\&comma;\mathrm{member}=\mathbf{proc}\left(g\&comma;S\&comma;\mathrm{pos}::\mathrm{name}\right)\mathbf{if}\mathrm{nargs}\&equals;1\mathbf{then}\mathrm{type}\left(g\&comma;\&apos;\mathrm{list}\left(\mathrm{posint}\right)\&apos;\right)\mathbf{and}\left\{\mathrm{op}\left(g\right)\right\}\&equals;\left\{\mathrm{`\$`}\left(1..4\right)\right\}\mathbf{else}:-\mathrm{member}\left(\mathrm{args}\right)\mathbf{end\; if}\mathbf{end\; proc}\&comma;\mathrm{gens}=\left\{\left[2\&comma;1\&comma;3\&comma;4\right]\&comma;\left[2\&comma;3\&comma;4\&comma;1\right]\right\}\&comma;\mathrm{order}\&comma;\mathrm{elements}\right)$

SubGroupElements( Centralizer( G, [ 1, 3, 2, 4 ] ) );

$\left\{\left[1\&comma;2\&comma;3\&comma;4\right]\&comma;\left[1\&comma;3\&comma;2\&comma;4\right]\&comma;\left[4\&comma;2\&comma;3\&comma;1\right]\&comma;\left[4\&comma;3\&comma;2\&comma;1\right]\right\}$

With SubGroupElements implemented, it is a good idea to extend GroupElements to accept subgroups also, thus providing a common interface.

GroupElements := proc( G )
    description "enumerate the elements of a "
                "group or subgroup";
    if type( G, 'SubGroup' ) then
        SubGroupElements( G );
    elif type( G, 'GroupType' ) then
        if type( G:-elements, 'set' ) then
            G:-elements;
        elif type( G:-elements, 'procedure' ) then
            G:-elements();
        else
            G:-elements := Dimino( G );
        end if;
    else
        'procname'( args );
    end if;
end proc:

As you can enumerate all of a group's elements, it is always possible to determine its order. (Note that this is rarely the best way to do this, however.) In many cases, it is possible to provide much better ways to compute the order of a group. For instance, the symmetric group of degree $n$ has order equal to $n!$, so its order export could be redefined to compute this number instead.

A generic interface to computing group orders, in the same spirit as GroupElements can be written as follows.

GroupOrder := proc( G )
    description "compute the order of a finite group";
    if type( G, 'SubGroup' ) then
        nops( GroupElements( G ) );
    elif type( G, 'GroupType' ) then
        if type( G:-order, 'posint' ) then
            G:-order;
        elif type( G:-elements, 'set' ) then
            G:-order := nops( G:-elements );
        elif type( G:-order, 'procedure' ) then
            G:-order();
        else
            nops( GroupElements( G ) );
        end if;
    else
        'procname'( args );
    end if;
end proc:

As with GroupElements, this routine checks the possible shortcuts that might be available for a group. It begins with those that are likely to involve the least computation and progresses through more costly alternatives. Only as a last resort does the procedure call GroupElements to compute a full enumeration of the group elements only to return their number.

G := Symmetric( 4 );

$G≔\mathrm{Record}\left(\mathrm{id}=\left[1\&comma;2\&comma;3\&comma;4\right]\&comma;\mathrm{`.`}=\mathbf{proc}\left(a\&comma;b\right)\mathbf{local}i\&semi;\left[\mathrm{seq}\left(b\&lsqb;i\&rsqb;\&comma;i\&equals;a\right)\right]\mathbf{end\; proc}\&comma;\mathrm{mul}=\left(\left(\right)\mapsto \mathrm{foldl}\left(G:-\mathrm{`.`}\&comma;G:-\mathrm{id}\&comma;\mathrm{args}\right)\right)\&comma;\mathrm{inv}=\mathbf{proc}\left(g\right)\mathbf{local}i\&comma;a\&semi;a:=\mathrm{array}\left(1..4\right)\&semi;\mathbf{for}i\mathbf{to}4\mathbf{do}a\&lsqb;g\&lsqb;i\&rsqb;\&rsqb;:=i\mathbf{end\; do}\&semi;\left[\mathrm{seq}\left(a\&lsqb;i\&rsqb;\&comma;i\&equals;1..4\right)\right]\mathbf{end\; proc}\&comma;\mathrm{eq}=\left(\left(a\&comma;b\right)\mapsto \mathrm{evalb}\left(a=b\right)\right)\&comma;\mathrm{member}=\mathbf{proc}\left(g\&comma;S\&comma;\mathrm{pos}::\mathrm{name}\right)\mathbf{if}\mathrm{nargs}\&equals;1\mathbf{then}\mathrm{type}\left(g\&comma;\&apos;\mathrm{list}\left(\mathrm{posint}\right)\&apos;\right)\mathbf{and}\left\{\mathrm{op}\left(g\right)\right\}\&equals;\left\{\mathrm{`\$`}\left(1..4\right)\right\}\mathbf{else}:-\mathrm{member}\left(\mathrm{args}\right)\mathbf{end\; if}\mathbf{end\; proc}\&comma;\mathrm{gens}=\left\{\left[2\&comma;1\&comma;3\&comma;4\right]\&comma;\left[2\&comma;3\&comma;4\&comma;1\right]\right\}\&comma;\mathrm{order}\&comma;\mathrm{elements}\right)$

C := Centralizer( G, [ 1, 3, 2, 4 ] );

$C≔\mathrm{Record}\left(\mathrm{parent}=G\&comma;\mathrm{test}=\mathbf{proc}\left(s\right)G:-\mathrm{eq}\left(G:-\mathrm{`.`}\left(s\&comma;\left[1\&comma;3\&comma;2\&comma;4\right]\right)\&comma;G:-\mathrm{`.`}\left(\left[1\&comma;3\&comma;2\&comma;4\right]\&comma;s\right)\right)\mathbf{end\; proc}\right)$

GroupOrder( G );

$24$

GroupOrder( C );

$4$

Note that, when the argument G is neither a group nor a subgroup, the procedure GroupElements returns unevaluated. This allows you to extend other Maple operations, such as expand, combine or simplify to be effective on algebraic expressions involving unevaluated calls to GroupOrder.

So far, all the groups have been permutation groups returned by one of the constructors previously presented. You must test the code on some other kinds of groups. A good source for examples of finite groups are the finite groups of exact matrices.

Because distinct matrices with equal entries compare differently using the Maple equality comparison operator `=`, it is necessary to implement a specialized test for membership in a set. For example, consider the matrices

A := Matrix( [[1,0],[0,1]] );

$A≔\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]$

B := Matrix( [[2,3],[3,4]] );

$B≔\left[\begin{array}{cc}2& 3\\ 3& 4\end{array}\right]$

C := Matrix( [[1,0],[0,1]] );

$C≔\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]$

Both A and C have the same entries, and represent mathematically identical objects. However, because matrices are mutable data structures (necessary for efficiency in matrix computations), they are distinct as Maple objects. Thus, for instance:

member( A, { B, C } );

$\mathrm{false}$

To deal with this property of these data structures, you must implement a generic version of the Maple command member. The gmember routine accepts arguments like those required by the member routine in addition to the first argument, which specifies an equality test. This utility is used in the following implementation of the matrix group constructor.

gmember := proc( test, g::anything, S::{set,list}, pos::name )
    description "a generic membership predicate";
    local i;
    if type( test, 'procedure' ) then
        for i from 1 to nops( S ) do
            if test( g, S[ i ] ) then
                if nargs > 3 then
                    pos := i;
                end if;
                return true;
            end if;
        end do;
        false;
    elif test = '`=`' then
        # use the standard membership test
        :-member( args[ 2 .. -1 ] );
    else
        'procname'( args );
    end if;
end proc:

The built-in procedure Equal in the LinearAlgebra package provides an equality predicate that is suitable for use with matrices.

gmember( LinearAlgebra:-Equal, A, { B, C } );

$\mathrm{true}$

Except for the member export, most of the exported methods for matrix groups simply delegate to the appropriate routine in the LinearAlgebra package. The MatrixGroup constructor takes the degree n of the matrix group as its first argument and, if given more than one argument, takes the remaining ones to be matrices that form a set of generators for the group.

MatrixGroup := proc( n::posint )
    description "matrix group constructor";
    local matgens, G;
    use LinearAlgebra in
        matgens := { args[ 2 .. -1 ] };
        G := Record(
            'id' = Matrix( n, n, ( i, j ) -> `if`( i = j, 1, 0 ) ),
            '`.`' = ( ( a, b ) -> MatrixMatrixMultiply( a, b ) ),
            'mul' = ( () -> foldl( G:-`.`, G:-id, args ) ),
            'inv' = ( m -> MatrixInverse( m ) ),
            'gens' = matgens,
            'eq' = ( ( a, b ) -> Equal( a, b ) ),
            'member' = proc( g, S, pos::name )
                local i, s;
                if nargs = 1 then
                    if type( g, 'Matrix( square )' ) then
                        evalb( Determinant( g ) <> 0 );
                    else
                        false;
                    end if;
                else
                    gmember( G:-eq, args );
                end if;
            end proc,
            'order', 'elements' );

        if nargs = 1 then
            G:-order := 1;
            G:-elements := { G:-id };
        end if;
    end use;
    eval( G, 1 );
end proc:

Here, the matrix group constructor is used to generate a dihedral matrix group of order 12.

theta := Pi / 3;

$\mathrm{\theta }≔\frac{\mathrm{\pi }}{3}$

a := Matrix( 2, 2, [[ 0, 1 ], [ 1, 0 ]] );
b := Matrix( 2, 2,
      [[cos(theta),sin(theta)],
       [-sin(theta),cos(theta)]] );

$a≔\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]$

$b≔\left[\begin{array}{cc}\frac{1}{2}& \frac{\sqrt{3}}{2}\\ -\frac{\sqrt{3}}{2}& \frac{1}{2}\end{array}\right]$

B := MatrixGroup( 2, a, b );

$B≔\mathrm{Record}\left(\mathrm{id}=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]\&comma;\mathrm{`.`}=\left(\left(a\&comma;b\right)\mapsto \mathrm{LinearAlgebra}:-\mathrm{MatrixMatrixMultiply}\left(a\&comma;b\right)\right)\&comma;\mathrm{mul}=\left(\left(\right)\mapsto \mathrm{foldl}\left(G:-\mathrm{`.`}\&comma;G:-\mathrm{id}\&comma;\mathrm{args}\right)\right)\&comma;\mathrm{inv}=\left(m\mapsto \mathrm{LinearAlgebra}:-\mathrm{MatrixInverse}\left(m\right)\right)\&comma;\mathrm{gens}=\left\{\left[\begin{array}{cc}\frac{1}{2}& \frac{\sqrt{3}}{2}\\ -\frac{\sqrt{3}}{2}& \frac{1}{2}\end{array}\right]\&comma;\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]\right\}\&comma;\mathrm{eq}=\left(\left(a\&comma;b\right)\mapsto \mathrm{LinearAlgebra}:-\mathrm{Equal}\left(a\&comma;b\right)\right)\&comma;\mathrm{member}=\mathbf{proc}\left(g\&comma;S\&comma;\mathrm{pos}::\mathrm{name}\right)\mathbf{local}i\&comma;s\&semi;\mathbf{if}\mathrm{nargs}\&equals;1\mathbf{then}\mathbf{if}\mathrm{type}\left(g\&comma;\&apos;\mathrm{Matrix}\left(\mathrm{square}\right)\&apos;\right)\mathbf{then}\mathrm{evalb}\left(\mathrm{LinearAlgebra}:-\mathrm{Determinant}\left(g\right)<>0\right)\mathbf{else}\mathrm{false}\mathbf{end\; if}\mathbf{else}\mathrm{gmember}\left(G:-\mathrm{eq}\&comma;\mathrm{args}\right)\mathbf{end\; if}\mathbf{end\; proc}\&comma;\mathrm{order}\&comma;\mathrm{elements}\right)$

GroupElements( B );

$\left\{\left[\begin{array}{cc}-\frac{1}{2}& \frac{\sqrt{3}}{2}\\ -\frac{\sqrt{3}}{2}& -\frac{1}{2}\end{array}\right]\&comma;\left[\begin{array}{cc}\mathrm{-1}& 0\\ 0& \mathrm{-1}\end{array}\right]\&comma;\left[\begin{array}{cc}-\frac{1}{2}& -\frac{\sqrt{3}}{2}\\ \frac{\sqrt{3}}{2}& -\frac{1}{2}\end{array}\right]\&comma;\left[\begin{array}{cc}\frac{1}{2}& -\frac{\sqrt{3}}{2}\\ \frac{\sqrt{3}}{2}& \frac{1}{2}\end{array}\right]\&comma;\left[\begin{array}{cc}\frac{\sqrt{3}}{2}& \frac{1}{2}\\ \frac{1}{2}& -\frac{\sqrt{3}}{2}\end{array}\right]\&comma;\left[\begin{array}{cc}\frac{\sqrt{3}}{2}& -\frac{1}{2}\\ -\frac{1}{2}& -\frac{\sqrt{3}}{2}\end{array}\right]\&comma;\left[\begin{array}{cc}0& \mathrm{-1}\\ \mathrm{-1}& 0\end{array}\right]\&comma;\left[\begin{array}{cc}-\frac{\sqrt{3}}{2}& -\frac{1}{2}\\ -\frac{1}{2}& \frac{\sqrt{3}}{2}\end{array}\right]\&comma;\left[\begin{array}{cc}-\frac{\sqrt{3}}{2}& \frac{1}{2}\\ \frac{1}{2}& \frac{\sqrt{3}}{2}\end{array}\right]\&comma;\left[\begin{array}{cc}\frac{1}{2}& \frac{\sqrt{3}}{2}\\ -\frac{\sqrt{3}}{2}& \frac{1}{2}\end{array}\right]\&comma;\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]\&comma;\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]\right\}$

To enrich the supply of example groups that you can use, develop a constructor for the direct product of (two) groups. (Extending the constructor to handle any finite number of groups is straightforward, but complicates the exposition unnecessarily.) Direct products are very important in the study of finite groups because all finitely generated abelian groups possess a unique factorization as a direct product of cyclic groups. (In the abelian theory, direct products are often referred to as direct sums.)

The direct product of two groups A and B is the group G whose elements are all pairs (a,b), with $a\in A$ and $b\in B$. The group product in G is defined by

The inverse of an element (a,b) is the pair $\left(a^{\mathrm{-1}}\&comma;b^{\mathrm{-1}}\right)$. All the operations are defined component-wise. Represent the elements (a,b) of the direct product by two-element lists. Here is the constructor DirectProduct.

DirectProduct := proc( A::GroupType, B::GroupType )
    description "direct product constructor";
    local G, a, b;
    if type( A, 'GroupType' ) and type( B, 'GroupType' ) then
        G := Group();
        G:-id := [ A:-id, B:-id ];
        G:-`.` := ( u, v ) -> [ A:-`.`( u[1], v[1] ),
                                B:-`.`( u[2], v[2] ) ];
        G:-mul := () -> foldl( G:-`.`, G:-id, args );
        G:-inv := v -> [ A:-inv( v[ 1 ] ),
                         B:-inv( v[ 2 ] ) ];
        G:-gens := [ seq( seq( [ a, b ],
                       a = A:-gens ), b = B:-gens ) ];
        G:-eq := ( u, v ) -> A:-eq( u[ 1 ], v[ 1 ] )
                         and B:-eq( u[ 2 ], v[ 2 ] );
        G:-order := () -> GroupOrder( A ) * GroupOrder( B );
        G:-member := proc( g, S, pos::name )
            if nargs = 1 then
                A:-member( g[ 1 ] )
                   and B:-member( g[ 2 ] );
            else
                gmember( G:-eq, args );
            end if;
        end proc;
        G:-elements := () -> [ seq( seq( [ a, b ],
           a = GroupElements( A ) ), b = GroupElements( B ) ) ];
        eval( G, 1 );
    else
        'procname'( args );
    end if;
end proc:

Most of the group methods are straightforward, but use the known group structure to reduce the complexity of some computations such as those for the order and elements exports.

A := Symmetric( 3 ):

G := DirectProduct( A, B ):

GroupOrder( G );

$72$

nops( GroupElements( G ) );

$72$

In all algebraic theories, homomorphisms play a key role. A group homomorphism is a mapping from a group to another (possibly the same) group which commutes with the group operations. That is, a map $\mathrm{\phi }$ : A -> B of groups A and B is a homomorphism if $\mathrm{\phi }\left(\mathrm{ab}\right)=\mathrm{\phi }\left(a\right)\mathrm{\phi }\left(b\right)$, for all a and b in A. A homomorphism is determined uniquely by its effect on a generating set for its domain; therefore, to define a homomorphism, it is enough to specify the images of each among a set of generators for the domain.

Use the interface in the following table for homomorphisms.

This leads directly to a simple constructor for homomorphism objects.

`type/Homomorphism` := '`module`( domain, codomain, genmap )':
Homomorphism := proc( A::GroupType, B::GroupType, p::procedure )
   description "homomorphism constructor";
    Record( 'domain' = A, 'codomain' = B, 'genmap' = p );
end proc:

The image of a group homomorphism $\mathrm{\phi }$ : A -> B is the subset $\mathrm{\phi }\left(A\right)$ of B consisting of all elements of B having the form $\mathrm{\phi }\left(a\right)$, for some element a in A. It is a subgroup of B. These various design choices lead to a simple formulation for computing or representing images of homomorphisms.

HomImage := proc( hom::Homomorphism )
    description "compute the image of a homomorphism";
    SubGroup( hom:-codomain,
              map( hom:-genmap, hom:-domain:-gens ) );
end proc:

As an example computation, compute the image of a homomorphism from the symmetric group $S_4$ onto a two-element matrix group generated by the reflection

Matrix( [ [ 0, 1 ], [ 1, 0 ] ] );

$\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]$

First, define the groups.

A := Symmetric( 4 ):

B := MatrixGroup( 2, Matrix( [[0,1],[1,0]] ) ):

Define a mapping from the generators of A to the group B by inserting the images of the generators into a procedure's remember table.

h( [2,1,3,4] ) := Matrix( [[0,1],[1,0]] ):

h( [2,3,4,1] ) := Matrix( [[1,0],[0,1]] ):

This defines a Maple procedure h that performs the indicated mapping and returns unevaluated for any other arguments.

eval( h );

$\mathbf{proc}\left(\right)\mathbf{option}\mathrm{remember}\&semi;\&apos;\mathrm{procname}\left(\mathrm{args}\right)\&apos;\mathbf{end\; proc}$

Use A, B and h to construct the homomorphism object.

hom := Homomorphism( A, B, h );

$\mathrm{hom}≔\mathrm{Record}\left(\mathrm{domain}=A\&comma;\mathrm{codomain}=B\&comma;\mathrm{genmap}=h\right)$

type( hom, 'Homomorphism' );

$\mathrm{true}$

Use the machinery developed earlier in this example to compute the order of the image of this homomorphism.

GroupOrder( HomImage( hom ) );

$2$

Thus, the homomorphism is surjective (as expected). You can compute the elements explicitly.

GroupElements( B );

$\left\{\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]\&comma;\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]\right\}$

GroupElements( HomImage( hom ) );

$\left\{\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]\&comma;\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]\right\}$

An automorphism $\mathrm{\alpha }$ of a group G is called inner if there is an element a in G for which $\mathrm{\alpha }\left(g\right)=a^{\mathrm{-1}}ga$, for all g in G. Write a constructor for inner automorphisms of groups.

With generic programming you need only implement computation in quotient fields or groups once --- in the constructors and generic procedures. The functor QuotientField and the various generic group constructors and procedures are parameterized by the computational domains upon which their computed values depend. Rings, fields, groups, and subgroups are collections of computational capabilities, which you use to construct new instances with derived computational capabilities. Overriding default methods (which may not be efficient, but are always present) with  methods that take advantage of specific structural information allows for efficient computation without sacrificing generality. This leads to a powerful paradigm for software reuse, and is the principal motivation underlying the Maple module system.