Error-correcting D-disjunct Matrix Construction

Firstly we discuss the disjunct properties ofδ^c(n,d,k),the complement matrix ofδ(n,d,k),and prove that it is(n-d)-disjunct if k=n-1．Next we discuss thedisjunct properties and detecting and correcting abilities of matrices which act as thecomplement matrices of those obtained by the inclusion relations in simple complexesand subspaces．Define a new matrixδ^**(n,d,k)as that which results by row augment-ing the matrixδ(n,d,k)withδ^c(n,α,k)(1≤α≤m+1(α∈Z))．We prove that ifk-d≥m(m≥3),then H(B_d(δ^**(n,d,k)))≥4 andδ^**(n,d,k)can detect and correcterrors．In particular,if k=n-1,then its ability for detecting and correcting errors isthe largest．The following is our main results:Theorem 3．1 Letδ^c(n,d,n-1)be the complement matrix ofδ(n,d,n-1)．Thenδ^c(n,d,n-1)is an(n-d)-disjunct matrix．Theorem 3．3 Letδ^c(n,d,k)be the complement matrix ofδ(n,d,k)．If kc(n,d,k)is a 1-disjunct matrix．Theorem 3．4 For 1≤d≤n-1,let△denote simplicial complex in a set[n]．De-fine the binary matrix M(△,d,n-1)by letting its rows and columns be respectivelyindexed by all the members of d-plane,say A₁,A₂,…A_t and all the(n-1)-plane,say B₁,B₂,…B_m．The matrix M(△,d,n-1) has a 1 in its(A_i,B_j)^th entry if and onlyif A_i(?)B_j．Let M^c(△,d,n-1)be the complement matrix of M(△,d,n-1)．ThenM^c(△,d,n-1)is an(n-d)-disjunct matrix． Theorem 3．5 For 1≤d≤k≤n,let△denote simplicial complex in a set[n]．Definethe binary matrix M(△,d,k)by letting its rows and columns be respectively indexed byall the members of d-plane,say A₁,A₂,…A_t and all the k-plane,say B₁,B₂,…B_l．Thematrix M(△,d,k)has a 1 in its(A_i,B_j)^th entry if and only if A_i(?)B_j．Let M^c(△,d,k)be the complement matrix of M(△,d,k)．If kc(△,d,k)is a 1-disjunctmatrix．Theorem 3．6 For 1≤d≤k≤n and let q be a prime power and let(?)_q denotethe family of k dimensional subspaces of F_q⁽ⁿ⁾．Define the binary matrixγ(n,d,k)byletting its rows and columns be respectively indexed by the members of(?)_q and (?)_q．For D∈(?)_q and K∈(?)_q,the matrixγ(n,d,k)has a 1 in its(D,K)^th entry if andonly if D is a subset of K．Letγ^c(n,d,k)be the complement matrix ofγ(n,d,k)．Thenγ^c(n,d,k)is a 1-disjunct matrix．Theorem 3.7 For 1≤d≤k≤n and q≥1,let((?))[q]^k denote the set of all q-aryvectors of length n and weight k．Define the binary matrixπ(q,n,d,k)by letting itsrows and columns be respectively indexed by the members of((?))[q]^d and((?))[q]^k．Forα∈((?))[q]^d and (?)∈((?))[q]^k,the matrixπ(q,n,d,k)has a 1 in its(α,(?))^th entry if andonly ifα(?)(?)．Letπ^c(q,n,d,k)be the complement matrix ofπ(q,n,d,k)．If kc(q,n,d,k)is a 1-disjunct matrix．Theorem 4．2 Ifδ^**(n,d,k)is the matrix which results by row augmenting the matrixδ(n,d,k)withδ^c(n,2,k)and k-d≥3,then H(B_d(δ^**(n,d,k)))≥4．Theorem 4．3 Ifδ^**(n,d,k)is the matrix which results by row augmenting the ma-trixδ(n,d,k)withδ^c(n,α,k)(1≤α≤m+1(α∈Z))and k-d≥m(m≥3),thenH(B_d(δ^**(n,d,k)))≥4． Theorem 4．4 For 2≤d≤n-2,we haveH(δ^**(n,d,n-1))≥2n-2d,and H(B_d(δ^**(n,d,n-1)))≥n-d．...