Abstract Elements in AjGroups

I wrote about my AjGroups finite groups library in my previos posts:

Presenting AjGroups: Finite Groups Library
Permutations in AjGroups

Now, I want to present the other internal implementation of a finite group in the solution: based, not in permutations, but in abstract elements.

An abstract element is identified by a name:

The names are letters: a, b, c, …. By convention, element e is the identity. Then

a * e = e * a

But, what is the result of a * b in a group? The results are stored in an OperationTable:

The OperationTable keeps a list of elements and a matrix. The cell of a matrix is the result of the multiplication of two elements:

public void SetValue(IElement left, IElement right, IElement value)
{
    this.SetValue(elements.IndexOf(left), elements.IndexOf(right), value);
}
public IElement GetValue(IElement left, IElement right)
{
    return this.GetValue(elements.IndexOf(left), elements.IndexOf(right));
}
internal void SetValue(int leftpos, int rightpos, IElement value)
{
    cells[leftpos, rightpos] = value;
}
internal IElement GetValue(int leftpost, int rightpos)
{
    return cells[leftpost, rightpos];
}
		
The OperationTable can be built using permutation elements. A test:
[TestMethod]
public void CalculateSymmetricGroupTable()
{
    IGroup group = new SymmetricGroup(3);
    OperationTable table = new OperationTable(group.Elements);
    table.Calculate();
    foreach (IElement left in group.Elements)
        foreach (IElement right in group.Elements)
            Assert.AreEqual(left.Multiply(right), table.GetValue(left, right));
}

But it is not the idea: I want to use OperationTable with named elements, and construct by hand or calculation the multiplication matrix.
The OperationTable has methods: .HasIdentity, .IsAssociative, .IsConmutative, to determine its properties. A test:
[TestMethod]
public void SymmetricGroupThreeOperationIsAssociative()
{
    OperationTable table = new OperationTable((new SymmetricGroup(3)).Elements);
    table.Calculate();
    Assert.IsTrue(table.IsAssociative);
}

Notably, the OperationTable can be incomplete: some cells can be still undefined. The method .IsClosed returns true if the multiplication matrix is completely defined: every result is know.
The OperationTable can be built by hand. The table:
 
is built and tested in:
[TestMethod]
public void CreateWithNamedIdentityAndOneElement()
{
    NamedElement identity = new NamedElement('e');
    NamedElement aelement = new NamedElement('a');
    OperationTable table = new OperationTable(new List<IElement>() { identity , aelement}, true);
    identity.OperationTable = table;
    aelement.OperationTable = table;
    table.SetValue(aelement, aelement, identity);
    Assert.IsTrue(table.HasIdentity);
    Assert.IsTrue(table.IsAssociative);
    Assert.IsTrue(table.IsClosed);
    Assert.IsTrue(table.IsCommutative);
    Assert.AreEqual(2, table.Elements.Count);
    Assert.AreEqual(identity, table.GetValue(identity, identity));
    Assert.AreEqual(aelement, table.GetValue(aelement, identity));
    Assert.AreEqual(aelement, table.GetValue(identity, aelement));
    Assert.AreEqual(identity, table.GetValue(aelement, aelement));
    Assert.AreEqual(1, identity.Order);
    Assert.AreEqual(2, aelement.Order);
}

But my preferred method in OperationTable is .GetSolutions(). From an incomplete OperationTable, it returns a list of complete OperationTables that are compatible with group axioms. Let this initial incomplete operation table:
 
Applying .GetSolutions() to this operation table returns the only one compatible group (the unique finite group of order 3):
 
Note: every row and column IS A permutation of the original elements. That rule resumes the group axioms.
A test:
[TestMethod]
public void GetGroupsOfOrderThree()
{
    NamedElement identity = new NamedElement('e');
    NamedElement aelement = new NamedElement('a');
    NamedElement belement = new NamedElement('b');
    OperationTable table = new OperationTable(new List<IElement>() { identity, aelement, belement }, true);
    IList<OperationTable> solutions = table.GetSolutions().ToList();
    Assert.IsNotNull(solutions);
    Assert.AreEqual(1, solutions.Count);
    Assert.IsTrue(solutions[0].IsClosed);
}

But OperationTable is not an IGroup. There is a TableGroup:
 
Its constructor receives an OperationTable: it clones the elements and OperationTable, to makes a new abstract group.
The tables returned by .GetSolutions() are not all different via isomorphism. I have a method, used internally by tests, to return all the essentially distinct groups of order n:
private static IList<IGroup> GetGroupsOfOrder(int order)
{
    IList<IElement> elements = new List<IElement>();
    for (int k = 0; k < order; k++)
        elements.Add(new NamedElement(k));
    OperationTable table = new OperationTable(elements, true);
    IList<OperationTable> solutions = table.GetSolutions().ToList();
    foreach (OperationTable solution in solutions)
    {
        Assert.IsTrue(solution.HasIdentity);
        Assert.IsTrue(solution.IsAssociative);
        Assert.IsTrue(solution.IsClosed);
    }
    IList<IGroup> groups = new List<IGroup>();
    foreach (OperationTable ot in solutions)
        groups.Add(new TableGroup(ot));
    IList<IGroup> dgroups = GroupUtilities.GetNonIsomorphic(groups);
    return dgroups;
}

The .GetSolutions() method heavily relies on method .GetCompatibleTable(a,b,c) that tries to add the equation:
a * b = c
to an OperationTable, without breaking group axioms. If a compatible table exists, it is returned; if not, null is the result.
All these features were constructed using TDD. Notably, the original design didn’t include named elements and operation tables: it was totally based in permutations. My next post: the way TDD saved my day, when I added named elements.
Keep tuned!
Angel “Java” Lopez

  
http://www.ajlopez.com 
http://twitter.com/ajlopez
					

Permutations in AjGroups

In my previous post I presented AjGroups, a class library written in C# that implements finite group concepts and operations. Source code at my AjCodeKata Google Project, under trunk/AjGroups.

In this post, I want to explain one of the implementations inside AjGroups: groups based on permutation.

A permutation is a bijective application of a set S over S. Say S is

S = { 0, 1, 2, 3, 4 }

Then, an permutation example is:

i(0)=0, i(1)=1, i(2)=2, i(3)=3, i(4)=4

It is the identity permutation. Other example:

s(0)=1, s(1)=0, s(2)=2, s(3)=3, s(4)=4

It is a swap, interchange of the first two elements. A rotation permutation:

r(0)=1, r(1)=2, r(2)=3, r(3)=4, r(4)=0

Permutations can be combined r*s:

(r*s)(n) = r(s(n))

The permutations of S are the elements of a group using the * operation. AjGroups implements a permutation using the Element class:

    public class Element : AjGroups.IElement
    {
        private byte[] values;
        public Element(params byte[] values)
        {
//....
    }
The permutation is represented in a byte array, where values[k] is the result of f(k), being f the permutation represented by the Element.
Element.Multiply(Element element) implements the multiplication:
 
Element.CreateIdentity generates an identity element, of size n:
       public Element Multiply(Element element)
        {
            int k;
            int length1 = this.values.Length;
            int length2 = element.values.Length;
            int newlength = Math.Max(length1, length2);
            byte[] newvalues = new byte[newlength];
            for (k = 0; k < newlength; k++)
            {
                if (k >= length2)
                {
                    newvalues[k] = this.values[k];
                }
                else if (element.values[k] >= length1)
                {
                    newvalues[k] = element.values[k];
                }
                else
                {
                    newvalues[k] = this.values[element.values[k]];
                }
            }
            return new Element(newvalues);
        }
Note that the method supports the multiplication of different size permutations.
Creating a swap of first two positions:
        public static Element CreateSwap(int size) 
        {
            Element element = CreateIdentity(size);
            element.values[0] = 1;
            element.values[1] = 0;
            return element;
        }

Creating a swap at position:
        public static Element CreateSwap(int size, int position)
        {
            Element element = CreateIdentity(size);
            element.values[position] = (byte) (position+1);
            element.values[position+1] = (byte) position;
            return element;
        }

Creating a rotation:
        public static Element CreateRotation(int size)
        {
            byte[] values = new byte[size];
            for (int k = 0; k < size; k++)
            {
                values[k] = (byte)(k == size - 1 ? 0 : k + 1);
            }
            return new Element(values);
        }

A CompleteGroup is a group with all its elements given in the constructor:
    public class CompleteGroup : BaseGroup
    {
        private List<IElement> elements;
        public CompleteGroup(List<IElement> elements)
        {
            this.elements = elements.Distinct().ToList();
        }
//...
    }
A GeneratedGroup is the result of combining a set of generator elements:
    public class GeneratedGroup : CompleteGroup
    {
        public GeneratedGroup(params IElement[] generators)
            : base(ElementUtilities.ElementsClosure(generators))
        {
        }
    }

ElementsUtilities.ElementsClosure generated by all the multiplication (a(a*b, b*a, a*b*b, a*c*b… ) generated by a set of initial elements (a, b, c, …)
Notably, the permutations of S are generated using a swap and a rotation:
    public class SymmetricGroup : GeneratedGroup
    {
        public SymmetricGroup(int size)
            : base(Element.CreateSwap(size), Element.CreateRotation(size))
        {
        }
    }

It can be proved that every finite group is a subgroup of a group generated by those two elements: a symmetric group of order n.
As I mentioned in my previous post, there is another implementation of finite groups in AjGroups: using abstract elements, not concrete permutations. That will be the topic for upcoming post.
Keep tuned!
Angel “Java” Lopez

  
http://www.ajlopez.com 
http://twitter.com/ajlopez
					

Presenting AjGroups: Finite Groups Library

I was writing a C# class library to manage finite groups. A group is a set G of elements with a defined binary operation *, where:

a * b  is in G    (closure)

a * (b * c) = (a * b) * c        (associative)

a * a’ = e     (inverse and identity)

a * e = e * a   (identity)

The solution code is in my AjCodeKata Google Project, under trunk/AjGroups:

The key interfaces are:

IElement has a method Multiply, that receives another IElement and returns the result IElement. IElement.Order is the number of elements to be multiplied to get the identity:

a * a * a ….. * a = e

IGroup.Elements is the collection of IElements that are the elements of the group. IGroup.Order is the count of elements.

There are two implementations of that interfaces: one based on permutations, another based on named elements (such “a”, “e”) and a table describing their multiplications.

There are methods to:

– Get the subgroups of a group
– Get the normal subgroups of a group
– Answer if two groups are isomorphic

I followed TDD ideas during development. All tests in green:

Good code coverage:

I should make some refactoring, but the project is taking form. I will write posts describing the permutation implementation, and the abstract elements implementation.

Keep tuned!

Angel “Java” Lopez
http://www.ajlopez.com
http://twitter.com/ajlopez