Hi, I think the application of group theory you are alluding to is group action on a set, where the group in this case is the symmetries of a square, and the set is all nxn binary matrices. I studied this topic (but not this particular problem) in an algebra paper last year, but I failed the paper so you should check everything below for yourself. :)
By Burnside's theorem, if X is a finite Gset then the number of distinguishable elements in X under the action of finite group G is the sum
Sigma X_g/G
where X_g is the subset of X fixed by the action g in G. (A Gset X is one where ex = x for all x in X, and where (gh)x = g(hx) for all g,h in G and all x in X. I think it is clear that the set of nxn binary matrices is a Gset when G is the symmetries of a square).
To work out the 3x3 case (where X = 2^9) I label the positions in the matrix:
aba
bcb
aba
Every matrix is fixed by the identity rotation, so X_1 = 2^9;
The matrices fixed by a 90 degree rotation in either direction are those which have all 'a' entries identical and all 'b' entries identical, so X_2 = X_3 = 2^3;
The matrices fixed by a 180 degree rotation are those which have nonadjacent 'a' entries identical and nonadjacent 'b' entries identical, so X_4 = 2^5;
The matrices fixed by a horizontal (vertical) reflection are those which have identical first and third rows (columns), so X_5 = X_6 = 2^6;
The diagonal reflections are similar, so X_7 = X_8 = 2^6;
Then the number of distinguishable 3x3 matrices is [2^9 + 2(2^3) + 2^5 + 2(2^6) + 2(2^6)] / 8 = 102
I think you could get a general formula for the nth term by using a similar method, perhaps by considering odd and even cases separately.
Last fiddled with by geoff on 20050121 at 13:01
Reason: fix mistakes
