Singular (0,1) matrices with constant row and column sums
Let B(n,k) denote the set of all \(n\times n\) (0,1) matrices with constant line sum k, and let S(n,k) be the set of all possible ranks of matrices in B(n,k). It is known that max S(n,k)\(=n\) for all (n,k) except for (4,2), where it is 3 [cf. \textit{M. Newman}, Canad. J. Math. 30, 756-762 (1978; Zbl 0388.15012) and \textit{D. J. Houck} and \textit{M. E. Paul}, Linear Algebra Appl. 22, 263-266 (1978; Zbl 0396.15006)]. Moreover, for max S(n,k)\(=n\) a matrix of rank n in B(n,k) can be constructed (loc. cit.). The exact value r(n,k) of min S(n,k) is known for all n when \(k\leq 3\), for all \(n\equiv k/2(mod k)\) when k is even, and for all \(n\equiv 0(mod k)\) when k is arbitrary [cf. \textit{R. A. Brualdi}, \textit{R. Manber} and \textit{J. H. Ross}, J. Comb. Theory Ser. A 41, 32-49 (1986; Zbl 0583.05019)]. The authors address here the problem of constructing a matrix in B(n,k) for each possible rank \(r<n\). N. J. Ryser observed that S(n,k) is a set of consecutive integers [cf. \textit{R. A. Brualdi}, Linear Algebra Appl. 33. 159-231 (1980; Zbl 0448.05047)]. The main result of this paper is a construction providing a matrix in B(n,k) of rank r for every \(n>3k\) and every \(r<n\) except for (at most) the first 2k-4 possible ranks. The authors solve the problem above also for all possible \(r<n\) when (1) \(k\leq 3\) for all n, (2) \(n\equiv 0(mod k)\) for all k, and (3) \(n\equiv k/2(mod k)\) for all even k.
matrices with constant row and column sums
scientific article; zbMATH DE number 4075285