|
Finite Geometry Notes
|
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.
"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.
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(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).)
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
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.
REFERENCES