×

Zero-sum square matrices. (English) Zbl 1020.15019

Let \(A\) be a matrix over the integers, and let \(p\) be a positive integer. A submatrix \(B\) of \(A\) is zero-sum \(\text{mod }p\) if the sum of earch row of \(B\) and the sum of each column of \(B\) is a multiple of \(p\). Let \(M(p,k)\) denote the least integer \(m\) for which every square matrix of order at least \(m\) has a square submatrix of order \(k\) which is zero-sum \(\text{mod }p\).
In this paper the authors determine several upper and lower bounds for \(M(p,k)\). They show that \(M(2,k)\) is linear in \(k\). They also show that \(M(3,k)\) is linear in \(k\) for infinitely many values of \(k\). In particular, they prove that \(\limsup M(2,k)/k\leq 4\), \(\liminf M(3,k)/k\leq 20\), and that \(M(p,k)\geq {k\sqrt{2}\over 2e} \exp(1/e)^{p/2}\). Some nontrivial explicit values are also computed.

MSC:

15B36 Matrices of integers
15A45 Miscellaneous inequalities involving matrices
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Alon, N.; Spencer, J. H., The Probabilistic Method (1991), John Wiley and Sons Inc: John Wiley and Sons Inc New York
[2] Enomoto, H.; Frankl, P.; Ito, N.; Nomura, N., Codes with given distances, Graphs Comb., 3 (1987) · Zbl 0629.94014
[3] Hattingh, J. H.; Henning, M. A., Bipartite Ramsey theory, Util. Math., 53, 217-230 (1998) · Zbl 0908.05064
[4] Olson, J. E., A combinatorial problem on finite Abelian groups, I, II, Number Theory, 1, 8.10, 195, 199 (1969) · Zbl 0167.28004
[5] Thomason, A., On finite Ramsey numbers, Europ. J. Combinatorics, 3, 262-272 (1982)
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.