FooGroup Algebra is a little ‘algebra’ that I created while trying to solve a problem. It seemed sufficiently interesting to describe by itself. I would have liked to call it group algebra, but it seemd like the name would already have been taken, and it also seemed like that’s too nice a name to dedicate to something like this :)

FooGroup Algebra

A term in this algebra consists of one or more symbols enclosed in [] or (). An expression is a set of terms. The enclosing [] or () are called the type of the term. The symbols the enclose are called base of the term. The ordering of symbols inside a term is of no significance. The ordering of terms in an expression is of no significance.

Here are some expressions:

(a b c)[c d]

(a b)(c d)(a d)

An expression is said to be solved, if all the terms in the expression have only one symbol. The following is a solved expression:

(a)[b](c)(d)

The value of each symbol is the type of the term that it is held.

An expression is invalid or is a contradiction is there atleast two terms of different type but same base. The following expressions are contradictions:

(a b)[a b]

(a)(b c d)[a]

Term Reduction and Solving: One can solve and expression by reducing each term in the expression until every terms contains only one symbol. Terms can be reduced as follows –

(X Y) => (X)[Y] and [X](Y)

[X Y] => [X][Y] and (X)(Y)

Where X and Y are any set of terms.

Since a term can be reduced in two ways, there maybe more that one solution for a given expression. A valid solution cannot have a contradiction. Here are some example reductions –

(a b c)[c d]

(a)[b c][c d]

(a)(b)(c)(d)

This is another solution for the same –

(a b c)[c d]

(a)[b c][c d]

(a)[b][c][d]

This is another solution for the same –

(a b c)[c d]

[a](b c)[c d]

[a](b)[c][d]

This is another solution for the same –

(a b c)[c d]

[a](b c)[c d]

[a](b)[c][d]

Independent Variables: When reducing a term we select one variable and assign it both type values. The values of other symbols/variables might be get fixed as a consequence of this. Such variables are referred to as independent variables. In the general case, the maximum number of solutions than an expression can generate is 2^n where n is the number of independent variables. Since one or both choices of type assignment may result in a contradiction the number of actual solutions maybe lesser than this.

In the above example, there were two independent variables a and b. c and d values were fixed by the selection of values for a and b. Hence there were 4 solutions.

Ex:

(a b)(b c)(c a)

(a)[b](c)[a] <-- contradiction

[a](b)[c](a) <-- contradiction

This expression has no solutions.

(a b)(a c)(a d)[b c d]

(a)[b][c][d] <-- this is one solution

[a](b)(c)(d) <-- this is a contradiction.

The above expression has only one solution

End.

That’s it. That’s all I know about this thing. I would like to create a method to predict how many solutions an expression may have. I don’t know how to do that.

I also would like to explore extensions to the algebra in terms of adding more types to the algebra.

Adding More Types: Right now I have only two types () and []. One can think of the relation between these as that of the relation between –ve and +ve, or as odd and even.

()() = [] or odd odd = even or - - = +

()[] = () or odd even = odd or - + = -

One can consider adding three types (), [] and {} such that

() = []{} and {}[]

[] = (){} and {}()

{} = []() and ()[]

I don’t know what sorts of types map to.

One can consider +, -, +i and –i as four types as well and so on.

What is this useful for?

I was working on solving another problem and the search space for that was too large. I was looking for a way of reducing the search space and for compactly representing this search operation when I realized that I could express the problem like this.

The original problem was that I had a matrix like the one below. I could assign and + or negative sign to any variable such that the matrix when multiplied by its transpose would generate the identity matrix. (The transpose of a matrix is the matrix you get when you flip it along its diagonal).

a b c d

b a d c

c d a b

d c b a

Then I had to solve the problem for the larger 8x8 version of the same matrix –

a b c d e f g h

b a d c f e h g

c d a b g h e f

d c b a h g f e

e f g h a b c d

f e h g b a d c

g h e f c d a b

h g f e d c b a

These matrices are generated as a consequence of simple XOR order, that can be easily expressed by the following ruby program –

syms = %w(a b c d e f g h i j k l m n o p q r s t)

v = 8

v.times{|m|

      v.times{|n|

            printf("%s ", syms[n^m])

      }

      puts ""

}

The fact is that I had to solve the problem for matrices of any dimension that is a power of two and I couldn’t see any pattern that would help me automagically generate the signs for matrices of higher dimensions.

So I though about how to search the space of all possible sign assignment and then realised that I can group elements into groups of four such that each group would have 4 variables and would be of type (). As an example here is the expression in FooGroup algebra which when solved would give all the solutions possible.

(r1c0,r1c1,r0c0,r0c1)(r1c2,r1c3,r0c2,r0c3)(r2c0,r2c2,r0c0,r0c2)(r2c1,r2c3,r0c1,r0c3)(r2c0,r2c3,r1c0,r1c3)(r2c1,r2c2,r1c1,r1c2)(r3c0,r3c3,r0c0,r0c3)(r3c1,r3c2,r0c1,r0c2)(r3c0,r3c2,r1c0,r1c2)(r3c1,r3c3,r1c1,r1c3)(r3c0,r3c1,r2c0,r2c1)(r3c2,r3c3,r2c2,r2c3)

Where r0c1 is the symbol for the sign that should be given to element at row 0 column 1. (I further go on to fix my first row to be all positive numbers. )

Finally, if you are interested I have a .Net library to solve expressions in the algebra. I also have a ruby program that generates C# programs which get the library to solve the above matrix problem.  The build command takes as parameter the dimensions of the matrix that you wish to solve (this should be a power of 2).

Download FooGroup Algebra and the Matrix Solver

Running the solver on a 4x4 matrix generates 16 solutions. 2048 solutions for a 8x8 matrix.

Solving :(r1c0 r1c1)(r1c2 r1c3)(r2c0 r2c2)(r2c1 r2c3)(r1c0 r1c3 r2c0 r2c3)(r1c1 r1c2 r2c1 r2c2)(r3c0 r3c3)(r3c1 r3c2)(r1c0 r1c2 r3c0 r3c2)(r1c1 r1c3 r3c1 r3c3)(r2c0 r2c1 r3c0 r3c1)(r2c2 r2c3 r3c2 r3c3)

Solution 1 : (r1c1)(r1c3)(r2c2)(r2c1)[r2c3](r2c1)(r3c3)[r3c1](r3c2)[r3c1][r3c1](r3c2)[r1c0][r1c2][r2c0][r3c0]

Solution 2 : (r1c1)(r1c3)(r2c2)(r2c1)[r2c3](r2c1)[r3c3](r3c1)[r3c2](r3c1)(r3c1)[r3c2][r1c0][r1c2][r2c0](r3c0)

Solution 3 : (r1c1)(r1c3)[r2c2][r2c1](r2c3)[r2c1](r3c3)[r3c1](r3c2)[r3c1][r3c1](r3c2)[r1c0][r1c2](r2c0)[r3c0]

Solution 4 : (r1c1)(r1c3)[r2c2][r2c1](r2c3)[r2c1][r3c3](r3c1)[r3c2](r3c1)(r3c1)[r3c2][r1c0][r1c2](r2c0)(r3c0)

Solution 5 : (r1c1)[r1c3](r2c2)[r2c1](r2c3)[r2c1](r3c3)(r3c1)[r3c2](r3c1)(r3c1)[r3c2][r1c0](r1c2)[r2c0][r3c0]

Solution 6 : (r1c1)[r1c3](r2c2)[r2c1](r2c3)[r2c1][r3c3][r3c1](r3c2)[r3c1][r3c1](r3c2)[r1c0](r1c2)[r2c0](r3c0)

Solution 7 : (r1c1)[r1c3][r2c2](r2c1)[r2c3](r2c1)(r3c3)(r3c1)[r3c2](r3c1)(r3c1)[r3c2][r1c0](r1c2)(r2c0)[r3c0]

Solution 8 : (r1c1)[r1c3][r2c2](r2c1)[r2c3](r2c1)[r3c3][r3c1](r3c2)[r3c1][r3c1](r3c2)[r1c0](r1c2)(r2c0)(r3c0)

Solution 9 : [r1c1](r1c3)(r2c2)[r2c1](r2c3)[r2c1](r3c3)(r3c1)[r3c2](r3c1)(r3c1)[r3c2](r1c0)[r1c2][r2c0][r3c0]

Solution 10 : [r1c1](r1c3)(r2c2)[r2c1](r2c3)[r2c1][r3c3][r3c1](r3c2)[r3c1][r3c1](r3c2)(r1c0)[r1c2][r2c0](r3c0)

Solution 11 : [r1c1](r1c3)[r2c2](r2c1)[r2c3](r2c1)(r3c3)(r3c1)[r3c2](r3c1)(r3c1)[r3c2](r1c0)[r1c2](r2c0)[r3c0]

Solution 12 : [r1c1](r1c3)[r2c2](r2c1)[r2c3](r2c1)[r3c3][r3c1](r3c2)[r3c1][r3c1](r3c2)(r1c0)[r1c2](r2c0)(r3c0)

Solution 13 : [r1c1][r1c3](r2c2)(r2c1)[r2c3](r2c1)(r3c3)[r3c1](r3c2)[r3c1][r3c1](r3c2)(r1c0)(r1c2)[r2c0][r3c0]

Solution 14 : [r1c1][r1c3](r2c2)(r2c1)[r2c3](r2c1)[r3c3](r3c1)[r3c2](r3c1)(r3c1)[r3c2](r1c0)(r1c2)[r2c0](r3c0)

Solution 15 : [r1c1][r1c3][r2c2][r2c1](r2c3)[r2c1](r3c3)[r3c1](r3c2)[r3c1][r3c1](r3c2)(r1c0)(r1c2)(r2c0)[r3c0]

Solution 16 : [r1c1][r1c3][r2c2][r2c1](r2c3)[r2c1][r3c3](r3c1)[r3c2](r3c1)(r3c1)[r3c2](r1c0)(r1c2)(r2c0)(r3c0)