View Single Post
Old 2005-01-21, 12:50   #2
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13·89 Posts
Default

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 G-set 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 G-set 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 G-set 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 non-adjacent 'a' entries identical and non-adjacent '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 2005-01-21 at 13:01 Reason: fix mistakes
geoff is offline   Reply With Quote