×

Geometric matrices and an inequality for (0,1)-matrices. (English) Zbl 0725.05024

Author’s abstract: “Let be an \(m\times n\) (0,1)-matrix with row vectors \(R_ 1,...,R_ m\) and column vectors \(C_ 1,...,C_ n\). If there exist integers \(\alpha\),\(\beta\) such hat \(R_ iR_ j=\alpha\) whenever \(R_ i\neq R_ j\) and \(C_ iC_ j=\beta\) whenever \(C_ i\neq C_ j\), then A will be called geometric. \((R_ iR_ j\), \(C_ iC_ j\) are the usual dot products of the vectors involved.) The geometric matrices are classified, and it is shown that (apart from certain trivialities) every geometric matrix is based on a symmetric balanced incomplete block design. Assume that each column of A has a zero entry and that \(C_ i\neq C_ j\) for some i and j. Under these assumptions it is shown that \(m\cdot \min \{R_ iR_ j:R_ i\neq R_ j\}\leq n\cdot \max \{C_ iC_ j:C_ i\neq C_ j\},\) and that equality occurs if and only if A is geometric. The results generalize a theorem of de Bruijn and Erdős concerning combinatorial designs.”

MSC:

05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.)
Full Text: DOI

References:

[1] Bouten, B.; De Witte, P., A new proof of an inequality of Szekeres, de Bruijn and Erdös, Bull. Soc Math. Belg., 17, 475-483 (1965) · Zbl 0156.19605
[2] Bruck, R. H.; Ryser, H. J., The nonexistence of certain finite projective planes, Can. J. Math., 1, 88-93 (1949) · Zbl 0037.37502
[3] De Bruijn, N. G.; Erdős, P., On a combinatorial problem, Indag. Math., 10, 421-423 (1948)
[4] Chowla, S.; Ryser, H. J., Combinatorial problems, Can. J. Math., 2, 93-99 (1950) · Zbl 0037.00603
[5] Hanani, H., On the number of lines and planes determined by \(d\) points, (Sci. Pub., Technion, 6 (1954-1955), Isr. Inst. Tech: Isr. Inst. Tech Haifa), 58-63 · Zbl 0066.39102
[6] Isbell, J. R., An inequality for incidence matrices, Proc. Am. Math. Soc., 10, 216-218 (1959) · Zbl 0094.33701
[7] Kelly, L. M.; Moser, W. O.J., On the number of ordinary lines determined by \(n\) points, Can. J. Math., 10, 210-219 (1958) · Zbl 0081.15103
[8] Majumdar, K. N., On some theorems in combinatorics relating to incomplete block designs, Ann. Math. Stat., 24, 377-389 (1953) · Zbl 0051.10802
[9] Ryser, H. J., An extension of a theorem of de Bruijn and Erdös on combinatorial designs, J. of Algebra, 10, 246-261 (1968) · Zbl 0167.28001
[10] Ryser, H. J., Subsets of finite sets that intersect each other in at most one element, J. of Comb. Theory (A), 17, 59-77 (1974) · Zbl 0285.05003
[11] de Witte, P., Combinatorial properties of finite linear spaces I, Bull. Soc. Math. Belg., 18, 133-141 (1966) · Zbl 0145.16901
[12] de Witte, P., A new property of non-trivial finite linear spaces, Bull. Soc. Math. Belg., 18, 430-438 (1966) · Zbl 0158.19403
[13] de Witte, P., Combinatorial properties of finite linear spaces II, Bull. Soc. Math. Belg., 27, 115-155 (1975) · Zbl 0384.05020
[14] Woodall, D. R., Square λ-linked designs, Proc. London Math. Soc., 20, 3, 669-687 (1970) · Zbl 0194.32401
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.