Angel \”Java\” Lopez on Blog

January 5, 2011

Abstract Elements in AjGroups

Filed under: .NET, AjGroups, C Sharp, Open Source Projects — ajlopez @ 10:40 am

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

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: