Orthogonal block structures

If you google “commuting equivalence relations” you will find signs of a large and rich literature. I want to talk about one aspect, on the border of algebraic combinatorics and experimental design: orthogonal block structures.

Look up orthogonal block structures in Rosemary’s book on association schemes. One of these structures is a sublattice of the lattice of partitions of a finite set, ordered by refinement (so that P is below Q if each part of Q is a union of parts of P), containing the bottom element (the partition into singletons) and the top element (the partition with a single part), and having two further properties: first, the partitions should all be uniform (that is, have all parts of the same size); and a second condition which I will come to shortly.

The reason why statisticians might be interested in collections of partitions is essentially the inhomogeneity of the experimental material. If you do an agricultural experiment, using plots on farms in different parts of the country, there will be a (probably significant) systematic difference between plots on different farms, and you probably need to take this into account so that you can allow for it when you are testing the real differences between the seeds, fertilisers, or whatever that are the subject of your experiment. Partitions into farms in this case, and similar in other cases, are referred to as “factors”.

The reason you need a lattice (that is, closure under meet and join) has to do with the analysis of variance, for example testing for interactions. The meet of two partitions P and Qis straightforward to define; it is the partition whose parts are all non-empty intersections of a part of P and a part of Q. Joins are more difficult; the join of P and Q is the partition into connected components of the graph whose edges are all pairs within either a part of P or a part of Q.

The nicest situation for the analysis is when the partitions are “orthogonal”. This is defined in terms of the vector space of all functions from the set of all experimental units to the real numbers. With each partition is associated a subspace consisting of all functions which are constant on each part of the partition; and the requirement is that, modulo the subspace associated with their meet, the subspaces for the two partitions should be orthogonal with respect to the usual inner product.

But later in the chapter on orthogonal block structures it is mentioned, in a throwaway remark, that orthogonality is equivalent to the condition that the equivalence relations commute. That is, the possible results of a step within a part of P and a step within a part of Q is the same as if we took the steps in the other order.

Now if G is a transitive permutation group on a set Ω, then the G-invariant partitions of Ω satisfy all these conditions except possibly the last: the meet and join of invariant partitions are invariant; the two trivial partitions are invariant; and the invariant partitions are uniform. (These partitions are just the systems of imprimitivity for the group.)

I described earlier how Marina and I had been looking at the concept we called pre-primitivity of a transitive group: this is the property that every G-invariant partition is the orbit partition of a normal subgroup of G. Empirically it seems that a very large proportion of transitive groups have this property, including all the primitive ones. We noticed that the invariant partitions of a pre-primitive group commute pairwise, and so form an orthogonal block structure. So this condition, for reasons which I will come to we called the relatively permuting property, is weaker than pre-primitivity. For example, there are 1954 transitive groups of degree 16; 1833 of them are pre-primitive, but 1886 of them have the RP property.

So of course we looked for further connections.

The reason that orthogonal block structures are studied in a book on association schemes is that any such structure gives rise to an association scheme. Each partition in the OBS is defined by an equivalence relation, which is a set of pairs; if we remove from each such set the pairs in the equivalence relations strictly below the one we are considering, we might get the empty set, but the non-empty sets that arise in this way form an association scheme (a symmetric coherent configuration, in the other language used for these things).

A little more research led us to the AssociationSchemes package for GAP, written by John Bamberg, Akihide Hanaki, and Jesse Lansdown. This is not part of the official distribution; but it exists, and can be downloaded. One feature of it is that the library files amount to half a gigabyte, and dwarf all the rest of the distribution. Also, I couldn’t install it on my desktop machine, since I don’t have root access; but I put it on my laptop and ran it. Very quickly it discovered that the association schemes derived from the 1386 transitive groups on 16 points which have the RP property fall into just 37 isomorphism classes.

However, reading the manual for the package, I get the impression that it was not really designed with these highly imprimitive association schemes in mind; there is rather more concentration on things like Hamming and Johnson schemes.

So what?

Marina is taking her undergraduate exams this month, so she is temporarily off the case. So I am just playing round with it, not very seriously, while her attention is distracted.

One observation is that a lattice of partitions satisfying the OBS conditions is modular. (This observation doesn’t appear in the Association Schemes book, but when I asked Rosemary she had no difficulty coming up with the proof.) Now we can observe that the lattice of invariant partitions of a transitive group is isomorphic to the lattice of subgroups lying between the point stabiliser and the whole group. Moreover, the commuting equivalence relations imply that the subgroups containing the point stabiliser permute pairwise; that is, if H and K are two of these, then HK = KH. (Hence the name: RP stands for “relatively permuting”.) But modularity is not equivalent to the permuting property. The lattice of subgroups of the symmetric group S₃ is modular, but the three subgroups of order 2 do not permute pairwise. A little further thought showed that even distributivity of the lattice does not imply the RP property. Forming a chain, however, does.

It would be nice to think that we might come up with some novel orthogonal block structures which could be interesting to statisticians. But this is unlikely to happen. As my earlier remarks were meant to indicate, the OBS used in an experiment is dictated by the nature of the experimental material, rather than being chosen by the experimenter.

So what about RP as a property of permutation groups? When discussing pre-primitivity, I remarked that pre-primitivity and quasiprimitivity in conjunction were equivalent to primitivity. This is not the case for the RP property. There are quasiprimitive groups which have RP but are not primitive. As just stated, if the subgroups between the point stabiliser and the whole group form a chain, then RP holds, and there are examples of this, such as the symmetric and alternating groups of degree 5 in their actions on 15 points (having 5 blocks of size 3).

This is part of a general program to convince people that even highly imprimitive association schemes are interesting. I am hoping that John Bamberg and his co-writers of the AssociationSchemes package may be persuaded to add some functions for dealing with orthogonal block structures (and specialisations of them such as poset block structures and special orthogonal block structures). In a sense, an orthogonal block structure describes just the systems of imprimitivity for an association scheme, discarding any other structure it might have; so they are in a sense orthogonal to some of the more familiar types such as Hamming and Johnson schemes.