Constructing Disjunct (Separable) Matrices And Studying The Properties

Firstly we discuss some new links among(d,r)-disjunct,(d;r)-separable,((?): r)-separable,and d^r-disjunct matrices;we give out the lower bound of the minimum number of rows required for a d-disjunct matrix with n columns,and the counterpart for d-separable matrix.Next we construct two types of disjunct matrices with errorcorrecting capability.The first construction is the matrix M which is obtained on the basis of the given matrix A and B.The rows of M are indexed by the direct product of the row indices in A and B;the columns of M are indexed by the direct product of the column indices in A and B;the entry of M are obtained by conjuncting the elements of A and B.The second construction is a diagonal matrix M^* which is made by the special partial matrix of a binary matrix M.We study the disjunct and separable properties of M^*,and identify the upper bound of the number of column of M_m1×n1which is a submatrix of M^*.Finally,we define the matrices M(d,k,n, (?),r)and M(L.P)over finite geometry,and prove that M(d,k,n,(?),r)and M(L,P) are disjunct matrices;and discuss their detecting and correcting abilities.The following is our main results:Theorem 2.1.1.Let M denote a t×n binary matrix.For 1≤d≤k≤n-r, and 1≤s≤r≤n-d,if M is(k,s)-disjunct,then M is(d,r)-disjunct.Theorem 2.1.2.d^r-1-disjunct implies(d;2r)-separable.Theorem 2.1.3.Let M denote a(d;r)-separable matrix containing the 0-column. Then M¹is obtained from M by deleting the 0-column.Moreover,M¹is(d-1)^{r 1}-disjunct.Theorem 2.1.6.Let M be a(2d;r)-separable matrix without 0-column.Then we can obtain a((?);r)-scparablc matrix by adding at most r rows to M.Theorem 2.1.7.Let M³be a matrix obtained from d^r-1-disjunct matrix M by deleting any r rows.Then M³is(d;r)-separable.Theorem 2.2.1.Let t(d,n)denote the minimum number of rows required for a d-disjunct matrix with n columns.Then we haveTheorem 2.2.2.Let t_s((?),n)denote the minimum number of rows required for a(?)-separable matrix with n columns.Then we have where t_d=max{t_D||D|=d},where to denotes the number of positive pools (rows).Theorem 3.1.3.Let A=(a_ij)_m,nbe the d₁^e₁-disjunct matrix and let B= (b_ij)_{m′,n′}be the d₂^e₂-disjunct matrix.Then according to Definition 3.1.1,the provided matrix M on the basis of A and B is d^e-disjunct,where d=min{d₁,d₂}, e=(e₁+1)(e₂+1)-1.Theorem 3.1.4.Let A=(a_ij)_m,nbe the((?);r¹)-separable matrix and let B=(b_{ijm′,n′}be the((?);r₂)-separable matrix.Then according to Definition 3.1.1,the provided matrix M on the basis of A and B is((?);r)-separable,where d=min{d₁,d₂},r=r₁r₂.Theorem 3.2.2.Let M_m1×n1and M_m2×n2denote binary matrices without 0-column. We define M^*=((?)).Then we have that:(â…°)Let M_m1×n1be a d₁^r₁-1-disjunct matrix,and M_m2×n2be a d₂^r₂-1-disjunct matrix.Then M^* is d^r-1-disjunct,where d=min{d₁,d₂},r=min{r₁,r₂}.(â…±)Let M_m1×n1be a((?);r₁)-separable matrix,and M_m2×n2be a((?);r₂)-separable matrix.Then M^* is((?);r)-separable,where d=min{d₁,d₂},r=min{r₁,r₂}.(â…²)Let M_m1×n1be a(d₁;r₁)-separable matrix,and M_m2×n2be a(d₂;r₂)-separable matrix.Then M^* is(d;r)-separable,where d=min{d₁,d₂},r=min{r₁,r₂}.(â…³)Let M_m1×n1be a(d₁,r₁)-disjunct matrix,and M_m2×n2be a(d₂,r₂)-disjunct matrix.Then M^* is(d,r)-disjunct,where d=min{d₁,d₂},r=r₁+r₂.Theorem 3.2.3.M^* is(d;r)-separable(or(d;r)-separable or d^r-disjunct),if and only if M_m1×n1and M_m2×n2are(d;r)-separable(or((?);r)-separable or d^r-disjunct).Theorem 3.2.4.Suppose that there exists a set D={D₁,D₃,……,D_d} of d columns in M_m1×n1such that the union of D intersects all rows in M_m1×n1.Let N₁ denote the set of columns in M_m1×n1.Define D_i^*=D_i\(?)D_j,for 1≤i≤d. Then for all C,C'∈N₁\D and 1≤i≤d.Theorem 3.2.5.Let M be a t×n((?);r)-separable matrix.Let p denote the actual (unknown)number of positive objects.Let T₁ and T₂ denote the sets of positive pools and negative pools,respectively,with |T₁|=m₁,|T₂|=m₂,m₁+m₂=t. Let H denote the subset of columns in M such that the rows in T₂ has 0-entry at each column of H.Let M_m1×n1be the m₁×n₁ submatrix of M such that the rows are T₁ and the columns are H,where n₁ is the number of columns in the subset M_m1×n1 which is in M^*(see Difinition 3.2.1).For M_m1×n1,If p≤d-1,then n₁=p;if p=d,then n₁≤d+((?))2^[m₁/d]-r-1.Theorem 4.1.6.For 1≤d≤k≤n,and 1≤r≤k,let(?)be a subset of (?)(k,n)(see Difinition 1.1.12),with dim(K₁∩K₂)≤k-r for K₁,K₂∈(?),and K₁≠K₂.We define a binary matrix M(d,k,n,(?),r)by letting its rows and columns be respectively indexed by the members of(?)(d,n)and(?).The matrix M(d,k,n,(?), r)has a 1 in cell(i,j)if and only if the ith d-dimensional subspace is contained in the jth k-dimensional subspace.Let and for 1≤s≤p,let e=[(?)]_q-[(?)]_q-(s-1)([(?)]_q-[(?)]_q)-1.Then for 1≤s≤p,we have that M(d,k,n,(?),r)is s^e-disjunct.Theorem 4.2.2.We define a k(q-k/2+3/2)×k binary matrix M(L,P)by letting its rows be indexed by tangents and secants of a k-arc in PG(2,F_q),and its columns be indexed by the points on the k-arc(k satisfies an additional constraint that k is an odd integer).The matrix M(L,P)has a 1 in cell(L_i,P_j)if and only if the point P_j is contained in the line L_i.Then for d=1.2,…,k-1,we have that M(L,P)is d^q-d-disjunct.