Finite Geometry Notes   | Home | Site Map | Author |

Duality and Symmetry

by Steven H. Cullinane

The following problem was posted by the author to the alt.sci.math.combinatorics forum on January 16, 2001.

PROBLEM: Let M be an nxn square (0,1) matrix with exactly k 1's in each row and exactly k 1's in each column. What conditions on n, k, and the arrangement of the 1's in the matrix are necessary and sufficient for there to exist permutations of rows and/or columns that make M a symmetric matrix?

The problem was suggested by point-line duality in a finite projective plane. The problem was also suggested by Weyl's remarks in his classic book Symmetry and by the aesthetics of the following quotations:

"Contrary to John Keats's First and Second Laws of Aesthetics ('Beauty is truth, truth beauty') truth and beauty are poles apart. Keats's ode itself, while denying this by precept, bears it out by example. Truth occupies the alethic pole of the intellectual sphere and beauty the aesthetic pole. Each is admirable in its way. The alethic pole exerts the main pull on science, in the broad sense: Wissenschaft, comprising mathematics, history, and all the hard and soft sciences in between. The aesthetic pole is the focus of belles lettres, music, art for art's sake."
-- W. V. Quine in Quiddities, Harvard University Press, 1987.

John Keats's Laws of Aesthetics

"The beauty we find is from
the comparison we make....
Beauty therefore is a relation,
and the apprehension of it
a comparison."
-- Gerard Manley Hopkins,
"On the Origin of Beauty."
"Truth, or reality, in other words,
is to be found in what James called
'the relations perceived' between facts--
not in the facts themselves."
-- Andrew Delbanco,
New York Times Book Review,
January 29, 1995.

For a more precise formulation of the problem, see the following HTML transcription of a typed query sent to various mathematicians in 1986.

Duality and Symmetry. Query. Dec. 29, 1986.

Entities are not to be needlessly multiplied. -- William of Ockham (?)

Given disjoint n-sets A and B, and an integer k with 1 LE k LE n, there exists at least one duality
relation R:A-->2^B such that
(1) for each x in A there are exactly k y's in B such that xRy, and
(2) for each y in B there are exactly k x's in A such that xRy.

(Example: point-line incidence in a projective plane, for certain values of n and k. See also Ryser (3), and consider cyclic Latin squares.)

Let C = {1, 2, ..., n} and let a:C-->A, b:C-->B be bijections. For c in C, let

 cR = {y in C: a(c)Rb(y)},
Rc = {x in C: a(x)Rb(c)}.

If there exist a and b such that cR = Rc for all c in C, then with respect to R the sets A and B differ only nominally, and may be replaced by the single set C. In this case we can say the duality R is symmetric. (See Coxeter (1), which cites Hall (2).)

QUERY -- What references exist for the following problem: Which dualities are symmetric?

Update of May 31, 2004:

Clearly I should have thought harder about the problem, since Douglas West yesterday easily supplied the following example.  He says,  

"The matrix below is not symmetrizable, because it has two identical rows but does not have two identical columns. It is easy to construct such examples, and I don't think that avoiding identical rows and columns (or disjoint rows and columns) is sufficient."

1 1 0 1 0 0
1 0 1 0 1 0
1 1 0 1 0 0
0 0 1 1 0 1
0 1 0 0 1 1
0 0 1 0 1 1

Update of July 23, 2005:

From Igor V. Dolgachev's "Abstract Configurations in Algebraic Geometry" (pdf),
published in Proceedings of the Fano Conference (Torino, Italy, 29 Sept.-5 Oct. 2002), A. Conte, A. Collino, and M. Marchisio, eds., Univ. Torino 2004, pp. 423-462:

"ABSTRACT. An abstract (vk, br)-configuration is a pair of finite sets of cardinalities v and b with a relation on the product of the sets such that each element of the first set is related to the same number k of elements from the second set and, conversely, each element of the second set is related to the same number r of elements in the first set. An example of an abstract configuration is a finite geometry. In this paper we discuss some examples of abstract configurations and, in particular, finite geometries, which one encounters in algebraic geometry."

Dolgachev discusses what he calls symmetric configurations, those in which v=b and k=r.

This seems to be the proper context for the above problem.


(1) Coxeter, H.S.M., Projective Geometry,
second edition, 1974, University of Toronto Press, p. 93.
(2) Hall, Marshall, "Cyclic Projective Planes,"
Duke Math. J. 14 (1947), pp. 1079 - 1090.
(3) Ryser, H.J., Combinatorial Mathematics,
M.A.A., 1963, pp. 57-58. 77.

Page last modified March 25, 2007.
Created January 16, 2001.