Finite Geometry Notes   | Home | Site Map | Author |

# Binary Coordinate Systems

### by Steven H. Cullinane

#### Mathematics Subject Classification (MSC2000) - Primary: 20B25, Finite automorphism groups of algebraic, geometric, or combinatorial structures. Secondary: 05B25, Finite geometries; 51E20, Combinatorial structures in finite projective spaces.

This article tells how to visualize some low-dimensional vector spaces over the finite field F2 as square or cubical arrays of points in Euclidean 3-space. Simple geometric operations on the point-arrays are shown to generate linear and affine groups over F2 of orders up to approximately 1.3 trillion. Some properties of these groups are sketched.
The typical example of a finite group is GL(n,q), the general linear group of n dimensions over the field with q elements. The student who is introduced to the subject with other examples is being completely misled. -- J. L. Alperin [AL]
Among the algebraic structures known as fields, clearly the most important for applications are the rationals, the reals, and the complex numbers, together with the fields of rational functions with coefficients in one of these number fields. What is the next most important field? Combinatorialists, coding theorists, and computer scientists would be likely to name the ridiculously simple structure F2, consisting of the elements 0 and 1, with 1 + 1 = 0.

One reason for the importance of this field is that the 1's in a vector in an n-space over F2 can be used to indicate membership in a subset of an n-set, with addition of vectors corresponding to taking the symmetric difference of sets. A family of subsets corresponds to a set of vectors, which in turn generate a vector subspace that may be easier to work with than the original subsets. Permutations on the parent n-set that leave the family of subsets invariant induce linear transformations on the corresponding subspaces. (J. H. Conway's analysis of M24, sketched below, exemplifies this approach to working with subsets.)

These considerations, and Alperin's remarks quoted above, indicate that linear and affine maps on vector spaces over F2 are reasonable things to study. Just as in linear algebra over the reals, the student working over F2 may be helped by seeing low-dimensional examples of how linear and affine maps actually move points throughout a vector space. (Over the reals, the student can visualize the global effects of such things as shears, dilations, rotations, and reflections.) We will describe how one can at least begin to visualize global actions of the linear and affine groups of 2, 3, 4, and 6 dimensions over F2, by constructing generators for these groups that have easily pictured actions on square and cubical arrays of points. (The awkward case of 5 dimensions we leave as an exercise.)

Before delving into the construction of these low-dimensional groups, we first show that their sizes are nontrivial, and then note that one of them, GL(4,2), has several nice properties that make it of particular interest to group theorists.

The notation GL(n,q) gives little idea of the size of these groups, which grow quite rapidly as n increases. As an aid to intuition, we list the orders of the first six general linear groups over F2, and of the corresponding affine groups AGL(n,2). Here AGL(n,2) is a semidirect product of the elementary abelian group V(n,2) of order 2n (the translation group) by GL(n,2). (In fact, AGL(n,q) is the holomorph of V(n,q). See [RO, pp. 136-139] and [CA, pp. 68, 112-113].)

Group Order of group
GL(1, 2) 1
AGL(1, 2) 2
GL(2, 2) (=S3) 6
AGL(2, 2) (=S4) 24
GL(3, 2) 168
AGL(3, 2) 1,344
GL(4, 2) 20,160
AGL(4, 2) 322,560
GL(5, 2) 9,999,360
AGL(5, 2) 319,979,520
GL(6, 2) 20,158,709,760
AGL(6, 2) 1,290,157,424,640

To verify these numbers, note that the order of GL(n,q) is
(qn - 1)(qn - q)(qn - q2)...(qn - qn-1),
which is the number of ways to choose successive images of basis vectors, and that
|AGL(n,q)| = qn|GL(n,q)|.

Among the groups above, GL(4,2) has several nice properties that make it of particular interest to students of group theory, combinatorics, or finite geometry.

1. GL(4, 2) is one of two nonisomorphic simple groups of the same order, the other being the projective unimodular group PSL(3, 4). (See AR, p. 171, or RO, p. 172.)
2. GL(4, 2) is isomorphic to A8, and this isomorphism plays a role (described below) in the structure of the quintuply transitive Mathieu group M24.
3. Underlying the isomorphism of GL(4, 2) with A8 is a structure that by itself is of interest in combinatorics and finite geometry. This structure is a correspondence J between the 35 partitions of an 8-set into two 4-sets and the 35 2-dimensional subspaces of V(4, 2) when the latter is regarded as a vector 4-space over F2. Under the correspondence J, two partitions into 4-sets have a common refinement as a partition into four 2-sets if and only if the corresponding 2-dimensional subspaces have a nontrivial intersection. (See HA or CA, p. 60.)
4. J. H. Conway [CO] has shown that M24 can be generated by combining three sorts of permutations, one sort being an action of GL(4, 2) on the 16 points of V(4, 2), combined with the corresponding action of A8 on a separate set E of 8 points, the second sort being a translation acting on V(4, 2), with all points of E fixed, and the third sort being an interchange of E with either of two halves of V(4, 2). Conway shows that a family of 8-element subsets (octads) is left invariant by the action of M24 on a 24-set, and also shows that the vectors over F2 corresponding to these subsets span a 12-dimensional space C over F2 that is known as the binary Golay code, in which each vector has 0, 8, 12, 16, or 24 1's. In a related paper, R. T. Curtis [CU] displays the correspondence J, described above, in his "miracle octad generator," which beautifully pictures the locations of octads within a 4x6 array.
5. GL(4, 2) is the collineation group of a finite projective geometry, PG(3, 2), that as the smallest projective space is a rich source of examples for geometers.

We now describe how to generate eight of the groups on our list above, of orders 6 through approximately 1.3 trillion, by letting the symmetric groups S3 (for linear groups) or S4 (for affine groups) permute natural subdivisions of square or cubical arrays.

We first recall that a permutation group acting on spatially located objects has isomorphic "alias" and "alibi" interpretations, depending on whether the cycle (ab...) means that object a is replaced by object b, etc. ("alias"), or whether it means that the object in location a is replaced by the object in location b, etc. ("alibi"). To avoid confusion we will use the alibi approach throughout, and will apply labels (numbers or (0,1)-vectors) only to locations within square or cubical arrays, and not to the objects permuted, which are "points" represented by unlabeled square or cubical unit cells. (The reader may, of course, label these cells as he pleases.)

Our groups will act on the following arrays of unit cells: a 2x2 square, a 2x2x2 cube, a 4x4 square, and a 4x4x4 cube. In each case, the same mathod of labeling locations is used:

• First, think of the locations in a square array, or in the top layer of a cubical array, as labeled by the integers 0, 1, 2, ... in normal reading order (left to right, top to bottom); for a cubical array, continue this process on lower layers, with the numbers increasing as the layers get lower.
• Now change the numbers to binary notation.
• Finally, regard the string of 0's and 1's labeling a given location as a vector over F2, rather than a binary number.

By a standard result of linear algebra [AR, ch. IV] the group of all unimodular linear transformations on an n-space over a field, i.e. the group of all nxn matrices with determinant 1, is generated by transvections, i.e. by the matrices Bij(t) obtained from the identity matrix by substituting the scalar t for one of the 0's. Since we are working over F2, every nonsingular linear transformation is unimodular, so the transvections Bij are the only generators for GL(n, 2) we need examine.

A quick check shows that for the 2x2 array as labeled above, the Bij for GL(2, 2) generate the action of S3 on the three unit cells not located at the origin (0, 0).

Given this S3action, clearly AGL(2, 2) acts as S4, since any nonzero translation moves the cell at the origin into the S3 orbit.

For the 2x2x2 array, the transvections of GL(3, 2) are easily seen to generate copies of the S3 action on the top, left, and back of the cube, with this action being extended through adjacent layers. In other words, GL(3, 2) is generated by S3 acting in each of 3 sets of 4 parallel 1x1x2 sections of the cube, with the fourth section in each set being fixed under S3's action on that set, since the fourth section contains the cell located at the origin. By the same argument as above, AGL(3, 2) is generated by S4 acting on each of the 3 sets of 4 parallel 1x1x2 sections.

For the 4x4 array, 6 of the Bij generate all 12 transvections, and also generate the action of S3 on the 3 rows, the 3 columns, and the 3 2x2 quadrants of cells that do not contain the cell located at the origin. Again, it is clear that AGL(4, 2) is generated by the action of S4 on rows, on columns, and on quadrants.

For GL(6, 2) acting on the 4x4x4 cube, consider the three 4x4 submatrices of the 6x6 identity matrix that correspond to the 3 sets of parallel 1x4x4 layers of the cube such that 4 of the 6 coordinates are identical throughout the four layers in a set. Together, these three submatrices cover all possible locations for a 1 located outside the diagonal in a 6x6 transvection matrix. It follows that the actions of GL(6 2) on the 4x4x4 cube are generated by S3 permuting any 3 parallel 1x4x4 layers not containing a cell at the origin and by S3 permuting any 3 parallel 2x2x4 sections not containing a cell at the origin. Naturally, AGL(6, 2) is generated by arbitrary permutations of parallel layers and of parallel 2x2x4 sections.

We conclude by mentioning an application to symmetries of ornamental patterns. Consider a cubic cell that is colored white around each of two opposite corners, in an area bounded by diagonals of the faces surrounding these corners, and black elsewhere, so that a band of black running around the cube separates the two white "caps," which are images of one another under a reflection in the center of the cube. If the reader arranges such cubes into a diamond pattern within any of the arrays we have discussed, he is likely to find that the resulting pattern has either an ordinary or a color-interchange symmetry under some rigid motion (rotation, reflection, or inversion) of the entire array. That such symmetry always occurs, given the right sort of starting pattern, is due to the Euclidean symmetries of partitions by affine hyperplanes.

For a summary of these results, see Affine groups on small binary spaces.

For a look at AGL(4, 2) in action, see The Diamond 16 Puzzle.

### References:

AL.... J. L. Alperin, book review,
Bulletin (New Series) of the American Mathematical Society 10 (1984) 121.
AR.... E. Artin, Geometric Algebra,
Interscience, New York, 1957.
CA.... P. J. Cameron, Parallelisms of Complete Designs,
Cambridge University Presss, Cambridge, 1976.
CO.... J. H. Conway, "Three lectures on exceptional groups,"
in Finite Simple Groups, edited by M. B. Powelll and G. Higman,