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