Disjunct matrix
In mathematics, a logical matrix may be described as d-disjunct and/or d-separable.
≈ 6 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In mathematics, a logical matrix may be described as d-disjunct and/or d-separable. These concepts play a pivotal role in the mathematical area of non-adaptive group testing. In the mathematical literature, d-disjunct matrices may also be called superimposed codes or d-cover-free families.
According to Chen and Hwang (2006), * A matrix is said to be d-separable if no two sets of d columns have the same boolean sum. * A matrix is said to be \overline{d} -separable (that's d with an overline) if no two sets of d-or-fewer columns have the same boolean sum. * A matrix is said to be d-disjunct if no set of d columns has a boolean sum which is a superset of any other single column. The following relationships are "well-known": * Every \overline{d+1} -separable matrix is also d -disjunct. * Every d -disjunct matrix is also \overline{d} -separable. * Every \overline{d} -separable matrix is also d -separable (by definition).
In mathematics, a logical matrix may be described as d-disjunct and/or d-separable. These concepts play a pivotal role in the mathematical area of non-adaptive group testing. In the mathematical literature, d-disjunct matrices may also be called superimposed codes or d-cover-free families.
According to Chen and Hwang (2006), A matrix is said to be d-separable if no two sets of d columns have the same boolean sum. A matrix is said to be \overline{d} -separable (that's d with an overline) if no two sets of d-or-fewer columns have the same boolean sum. A matrix is said to be d-disjunct if no set of d columns has a boolean sum which is a superset of any other single column.
The following relationships are "well-known": Every \overline{d+1} -separable matrix is also d -disjunct. Every d -disjunct matrix is also \overline{d} -separable. Every \overline{d} -separable matrix is also d -separable (by definition).
Concrete examples
The following 6\times 8 matrix is 2-separable, because each pair of columns has a distinct sum. For example, the boolean sum (that is, the bitwise OR) of the first two columns is 110000\or 001100 = 111100 ; that sum is not attainable as the sum of any other pair of columns in the matrix.
However, this matrix is not 3-separable, because the sum of columns 1, 2, and 3 (namely 111111 ) equals the sum of columns 1, 4, and 5. This matrix is also not \overline{2} -separable, because the sum of columns 1 and 8 (namely 110000 ) equals the sum of column 1 alone.
In fact, no matrix with an all-zero column can possibly be \overline{d} -separable for any d\ge 1 . \quad\left[ \begin{array}{cccccccc} 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 \\ \end{array} \right] The following 6\times 4 matrix is \overline{3} -separable (and thus 2-disjunct) but not 3-disjunct. \quad\left[ \begin{array}{cccc} 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{array} \right] There are 15 possible ways to choose 3-or-fewer columns from this matrix, and each choice leads to a different boolean sum: However, the sum of columns 2, 3, and 4 (namely 111111 ) is a superset of column 1 (namely 110000 ), which means that this matrix is not 3-disjunct.
Application of d-separability to group testing
The non-adaptive group testing problem postulates that we have a test which can tell us, for any set of items, whether that set contains a defective item. We are asked to come up with a series of groupings that can exactly identify all the defective items in a batch of n total items, some d of which are defective.
A d -separable matrix with t rows and n columns concisely describes how to use t tests to find the defective items in a batch of n, where the number of defective items is known to be exactly d. A d -disjunct matrix (or, more generally, any \overline{d} -separable matrix) with t rows and n columns concisely describes how to use t tests to find the defective items in a batch of n, where the number of defective items is known to be no more than d.
Practical concerns and published results
For a given n and d, the number of rows t in the smallest d-separable t\times n matrix may (according to current knowledge) be smaller than the number of rows t in the smallest d-disjunct t\times n matrix, but in asymptotically they are within a constant factor of each other. Additionally, if the matrix is to be used for practical testing, some algorithm is needed that can "decode" a test result (that is, a boolean sum such as 111100 ) into the indices of the defective items (that is, the unique set of columns that produce that boolean sum).
For arbitrary d-disjunct matrices, polynomial-time decoding algorithms are known; the naïve algorithm is O(nt) . For arbitrary d-separable but non-d-disjunct matrices, the best known decoding algorithms are exponential-time. Porat and Rothschild (2008) present a deterministic O(nt) -time algorithm for constructing a d-disjoint matrix with n columns and \Theta(d^2\ln n) rows.
See also
Group testing Concatenated code Compressed sensing
Further reading
Essential Coding Theory, Chapter 20 Dýachkov, A. G., & Rykov, V. V. (1982). Bounds on the length of disjunctive codes. Problemy Peredachi Informatsii [Problems of Information Transmission], 18(3), 7–13.
Dýachkov, A. G., Rashad, A. M., & Rykov, V. V. (1989). Superimposed distance codes. Problemy Upravlenija i Teorii Informacii [Problems of Control and Information Theory], 18(4), 237–250.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1310515518 under CC BY-SA 4.0; modifications have been made.