On the product of certain permutations (Q1820167)

Let P be a cyclic permutation and let Q be a fixed point involution on the same set. A pair of orbits \(\{\) a,aQ\(\}\), \(\{\) b,bQ\(\}\) are linked in P if a and aQ separate b and bQ. The link matrix, M(P,Q), over GF(2) has rows and columns indexed by the orbits of Q, with an entry 1 if the corresponding orbits are linked in P. The author gives a new proof of a result due to Cohn and Lempel, saying that the number of orbits in PQ is \(1+\) the nullity of M(P,Q). The proof involves restating the problem in terms of the genus of a pair of permutations, then reducing the link matrix to a canonical form while leaving the genus unchanged. This procedure can be viewed topologically as an embedding of a Hamiltonian cubic graph into an orientable surface. In this context the author's reduced form is similar to the canonical 'handles' form characterizing orientable surfaces, and his reduction procedures are similar to those used in the classification of these surfaces.