A counting problem

As the tagline for this blog says, I like counting things. Reading my Iran diary reminded me of a counting problem I solved then, of which I am quite proud. But like all good problems, it leaves a loose end, which you might like to try.

THe problem came from Charles Johnson, one offour pairs of my coauthhors with the same surname. He was interested in properties of a matrix which are at least partly controlled by its sign pattern, and wanted to count certain sign patterns.

So a sign pattern is an n×n matrix with entries +1 and −1 only. We are interested in symmetric sign patterns, and want to count them up to the equivalence relation generated by three kinds of transformation:

• Multiplying on left and right by the same diagonal matrix with diagonal entries +1 and −1.
• Permuting rows and columns by the same permutation.
• Replacing the matrix by its negative.

Charles had obsrved that, for example, if two sign patterns commute then their images under one of these transformations also commute.

Charles had counted the number of equivalence classes for the first few values of n. I recognised these as the numbers of n-vertex graphs up to isomorphism. So we set out to prove that these numbers must be equal, and succeeded. The paper, if you want to see it, is in Discrete Mathematics 306 (2006), 3074–3077, doi 10.1016/j.disc.2004.10.029.

The paper is not too long, only four pages, but such a simply-stated result should have a really short proof. Can you find one?