Singular (0,1) matrices with constant row and column sums

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Matrices of integers (15B36) Hermitian, skew-Hermitian, and related matrices (15B57)

Review text

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.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: Singular (0,1) matrices with constant row and column sums

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1111651)