Singular (0,1) matrices with constant row and column sums
type: Item
instance of: scholarly article
title: Singular (0,1) matrices with constant row and column sums
zbMATH Open document ID: 0658.15013
DOI: 10.1016/0024-3795(88)90028-6
author: Norman J. Pullman
author: Miriam Stanford
published in: Linear Algebra and its Applications
publication date: 1988-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 15B36
Mathematics Subject Classification ID: 05B20
Mathematics Subject Classification ID: 15B57
zbMATH DE Number: 4075285
zbMATH Keywords: matrices with constant row and column sums
zbMATH Keywords: (0,1) matrices with constant line sum
zbMATH Keywords: ranks
reviewed by: Veselin Perić
MaRDI profile type: Publication
full work available at URL: 0024-3795(88)90028-6
OpenAlex ID: W1998534430
cites work: Matrices of zeros and ones with fixed row and column sum vectors
cites work: On the minimum rank of regular classes of matrices of zeros and ones
cites work: Biclique coverings of regular bigraphs and minimum semiring ranks of regular matrices
cites work: Q3758977
cites work: Non-singular 0-1 matrices with constant row and column sums
cites work: Q5331504
cites work: Combinatorial Matrices with Small Determinants
cites work: Q3789613
description: scientific article; zbMATH DE number 4075285