Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5772924 | Linear Algebra and its Applications | 2018 | 10 Pages |
Abstract
If D is a partially filled-in (0,1)-matrix with a unique completion to a (0,1)-matrix M (with prescribed row and column sums), we say that D is a defining set for M. Let A2m,m be the set of (0,1)-matrices of dimensions 2mÃ2m with uniform row and column sum m. It is shown in Cavenagh (2013) [3] that the smallest possible size for a defining set of an element of A2m,m is precisely m2. In this note when m is a power of two we construct an element of A2m,m which has no defining set of size less than 2m2âo(m2). Given that it is easy to show any A2m,m has a defining set of size at most 2m2, this construction is asymptotically optimal. Our construction is based on a array, defined using linear algebra, in which any subarray has asymptotically the same number of 0's and 1's.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Algebra and Number Theory
Authors
Nicholas J. Cavenagh, Reshma Ramadurai,