|
Finite Geometry Notes
|
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.
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:
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.