Theorem: (Fisher's Inequality, 1940) If a (v,b,r,k,λ) – BIBD exists with 2 kv, then b v .
Proof: Assume (V, B) is a (v,k,λ) – BIBD and construct the
v bincidencematrix of the design.
A =
Then A AT =
We compute the determinant of AAT, det(AAT).
det(AAT) = det
= det
= (r + (v – 1)) (r –)v – 1 = rk(r – ) v – 1 0.
So AAT is nonsingular, and thus AAT has rank v.
Since rank(A) rank(AAT) = v
And since b rank(A) (A has only b rows)
We get that b v.
In the extremal case of b = v, the design is called a symmetric design.
In a symmetric (v,k,λ) – BIBD every pair of blocks intersects in points. So the dual of a symmetric design (exchanging the roles of blocks and points) is also a design (but not necessarily the same as the original).
Hadamard designs and matrices
A square n n matrix Hall of whose entries are 1 is called a
Hadamard matrix of order n if HHT = nI.
This says that the inner product of any two rows is 0, i.e. any two rows are orthogonal as n – dimensional vectors.
Examples:
n = 2n = 4
Some properties of Hadamard matrices:
- The columns are also pairwise orthogonal
- Of all n n matrices with entries |aij| 1, a Hadamard matrix of order n has the maximum determinant.
- If a Hadamard matrix of order n exists then n = 2, or n = 4m for some m. (homework)
The existence of a Hadamard matrix of order 4m is equivalent to the existence of a (symmetric) design with parameters
(4m – 1, 2m – 1, m – 1). This design is called a Hadamard design .
Construction: Take a normalized Hadamard matrix of order 4m,
delete the first row and change all –1's to 0's. The result is the incidence matrix of a (4m – 1, 2m – 1, m – 1) design.
(This process can be reversed to get the matrix from the design)
Product construction for Hadamard matrices:
If there exists Hadamard matrices of order m and n, then there exists a Hadamard matrix of order mn.
Proof: Use the Kroneker product of the two matrices.
Example:
M = and N =
Then M N =
is a Hadamard matrix of order 8.
A direct construction for Hadamard designs:
Let q = 4m – 1 be a prime power, Let b be the set of all non-zero squares in GF(q). A Hadamard design with parameters
(4m – 1, 2m – 1, m – 1) can constructed from this blocks plus all its translates in GF(q).
Example:
Let q = 11 (so m = 3). The non-zero squares mod 11 are
b = 1, 4, 9, 5, 3
then b, b + 1= 2, 5, 10, 6, 4 , b + 2, b +3, …., b + 10
are the blocks of a Hadamard design of order 11, (an (11,5,2) – BIBD).
Why??
The Hadamard conjecture: for every n 1, there exists a Hadamard matrix of order 4n.
State of the art: The smallest unknown case is order 4 107 = 428.
The Hadamard table:
Some applications of BIBD's
- Resolvable BIBD's with block size 2 are equivalent to round-robin tournaments. (Lecture 4)
- BIBD's are intimately connected to error correcting codes, erasure codes and optical orthogonal codes used in the transmission of digital information.
- BIBD's are used in the design of experiments.
- BIBD's have applications to parts of cryptography such as visual cryptography and to the construction of threshold schemes.
- BIBD's can be used in the construction of quorum systems, these are used for redundancy in distributed disk storage systems.
- BIBD's are used in bioinformatics to construct so called Oligo arrays. These are micro-arrays of DNA strands used in gene sequencing.
- BIBD's are used to test for defective items in a population by testing groups of items at a time. (Called group testing)
- BIBD's and their generalizations are used in constructing lottery wheels (systems for buying multiple tickets for lotteries with the aim of increasing the expected yield).
Lotteries
We desire to buy the minimum number of lottery tickets necessary to insure that whatever numbers are chosen by the lottery that at least one of our tickets contains k of these numbers.
Example:
A lottery wheel for Lotto 6/44 that guarantees at least a 3-match.
There are firms that sell solutions to this problem using 355 tickets, we give a solution using 154 tickets.
Partition the set of 44numbers into two sets A, and B where
A = 1, …, 22 and B = 23, …, 44 .
On each of A and B, purchase 77 tickets corresponding to the blocks of the block design with parameters 3 (22,6,1).
Holding these 154 tickets, one must obtain a 3-match at least, unless the six winning numbers contain at most two from A, and at most two from B. Clearly this can't happen.
So these 154 tickets cover every possible 3 subset of the numbers from 1 to 44.
Error correcting codes
The aim is to send encode signals so that if they are sent hrough a noisy channel, the receiver is able to correct any errors that may be induced in transmission.
Example: (used for photos from the Mariner and Voyager space probes that visited Mars and Venus in the 1970's).
Photos are made by using three black-and-white pictures taken, in
turn, through red, green and blue filters. Each picture is then considered as a 1000 1000 matrix of black and white pixels. Each pixel is graded on a scale of 1 to 16, according to its greyness (so white is 1, black is 16). These grades are then used to choose a codeword in an eight error correcting code based on a Hadamard matrix of order 32. The codeword are transmitted to earth, error corrected, the three black-and-white pictures are reconstructed, and then combined to obtain the colored picture.
Example:
The matrix G = has rank 4.
So there 24 = 16 vectors that are linear combinations of the rows of G (all arithmetic done modulo 2).
It can be checked that any two of these 16 vectors must differ in at least three positions. Assume we have 16 messages written as
4-tuples of 0's and 1's. For our codeword corresponding to this message we send the 7-tuple (from the row span of G) that begins with our4-tuple message.
So for example if we wish to send the message 0110, we send the codeword 0110100. To send 1001 we send 1001011.
If one error occurs in transmission, it can be corrected by decoding to the nearest codeword.
G is called the generator matrix of a binary [7,4,3] code.
(7 is the length of the codewords, 24 is the number of messages and
3 is the minumun distance between any two codewords)
Codes and designs are closely related. In this case we have that the set of all codewords of weight 3 form the incidence matrix of the (7,3,1) – design (the fano plane again).
Lots more …..
Group testing
When testing a large number of samples for a rare attribute, it is efficient (faster and less expensive) to test large groups of these samples together for the attribute. It is desirable to then use the results of these pooled tests to deduce which of the samples had the attribute. Note that a negative result ensures that none of the samples were positive, while a positive result reveals only that at least one of the samples was positive.
The theory of group testing arose via testing millions of World War II military draftees for syphilis and it is very relevant to schemes for large-scale blood testing for viruses such as HIV.
Group testing also arises in connection with the mapping of genomes. Here, we have a long list of molecular sequences, form a library of subsequences (clones), and test whether or not a particular sequence (a probe) appears in the library by testing to see which clones it appears in. Because clone libraries can be huge, this is done by pooling the clones into groups.
Group testing is also relevant to the identification of defective products and has found application in satellite communications.
When the sequence of tests is predetermined this is called a nonadaptive group testing algorithm.
We can model a nonadaptive group testing algorithm as a design.
Let X be a set of m elements called samples.
Let A = {b1, b2, … bn} be a set of n subsets of X called tests .
Let U X be the set of positive samples.
Now construct a binary vector of length n calledthe result vector of U or R(U)as follows:
The ithcomponant R(U) is 1 if U bi ;
0 otherwise
Then (X, A) is (m,n)-NAGTA with thresholds if R(U) R(V) whenever U, V X, with |U| s, |V| s, and UV.
Example:
Let X = {1,2,3,4,5,6} and A= {{1,2,3}, {1,4,5}, {2,4,6}, {3,5,6}}.
The result vectors of the (6,4)-NAGTA (X, A) for all possible positive subsets U with |U| 2:
U R(U) U R(U)
0000 {1,6} 1111
{1} 1100 {2,3} 1011
{2} 1010 {2,4} 1110
{3} 1001 {2,5} 1111
{4} 0110 {2,6} 1011
{5} 0101 {3,4} 1111
{6} 0011 {3,5} 1101
{1,2} 1110 {3,6} 1011
{1,3} 1101 {4,5} 0111
{1,4} 1110 {4,6} 0111
{1,5} 1101 {5,6} 0111
We see that (X, A) has (maximum) threshold s 1 since the seven vectors R(U), where |U | 1, are distinct.
However, for sets of cardinality 2, the result vectors are not always different (for example, R(1,3) = R(1,5)). So s = 1.
So we can use this scheme to test 6 items using 4 tests
The connection to designs:
Theorem: If there exists a (v,b,r,k,1)- BIBD, then there exists a
(b, v)- NAGTA with threshold k – 1.