Premium
Defining Sets and Critical Sets in (0,1)‐Matrices
Author(s) -
Cavenagh Nicholas J.
Publication year - 2013
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.21326
Subject(s) - mathematics , combinatorics , column (typography) , complement (music) , matrix (chemical analysis) , set (abstract data type) , order (exchange) , square (algebra) , property (philosophy) , square matrix , discrete mathematics , symmetric matrix , eigenvalues and eigenvectors , computer science , geometry , philosophy , materials science , chemistry , composite material , biochemistry , epistemology , quantum mechanics , programming language , physics , finance , connection (principal bundle) , complementation , economics , gene , phenotype
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 . If the removal of any entry of D destroys this property (i.e. at least two completions become possible), we say that D is a critical set for M . In this note, we show that the complement of a critical set for a (0, 1)‐matrix M is a defining set for M . We also study the possible sizes (number of filled‐in cells) of defining sets for square matrices M with uniform row and column sums, which are also frequency squares. In particular, we show that when the matrix is of even order 2 m and the row and column sums are all equal to m , the smallest possible size of a critical set is precisely m 2 . We give the exact structure of critical sets with this property. © 2012 Wiley Periodicals, Inc. J. Combin. Designs 21: 253–266, 2013
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom