On Kramer-Mesner matrix partitioning conjecture

Abstract

In 1977, Ganter and Teirlinck proved that any 2t times 2tmatrix with 2t nonzero elements can be partitioned into foursubmatrices of order t of which at most two contain nonzeroelements. In 1978, Kramer and Mesner conjectured that any mttimes nt matrix with kt nonzero elements can be partitionedinto mn submatrices of order t of which at most k containnonzero elements. In 1995, Brualdi et al. showed that thisconjecture is true if m = 2, k leq 3 or k geq mn-2. Theyalso found a counterexample of this conjecture when m=4, n=4,k=6 and t=2. When t=2, we show that this conjecture is true