Chapter 6 designs and codes Flashcards
blocks related to job allocation
Before, we had a set J of jobs and a set P of people, and for each job j ∈ J we had a subset C[j] ⊆ P
of people who are qualified to do that job. For each person p we can also consider the set Q[p] of jobs that
they are qualified to do. This can be expressed in symbols as Q[p] = {j ∈ J | p ∈ C[j]}
We will have a set B of “blocks” and a set V of “varieties”. For each block j ∈ B
we have a corresponding subset C[j] ⊆ V . For any variety p ∈ V we again define Q[p] = {j ∈ B | p ∈ C[j]}.
DEF 1: block designs
Consider numbers v, b, r, k, λ > 0 with k < v and r < b. A block design with parameters
(v, b, r, k, λ) is a matching problem as above, with the following properties:
(a) |V | = v
(b) |B| = b
(c) |Q[p]| = r for all p ∈ V
(d) |C[j]| = k for all j ∈ B
(e) |Q[p] ∩ Q[q]| = λ for all p, q ∈ V with p ≠ q.
there are v varieties and b blocks, every variety is in precisely r blocks, every block contains
precisely k varieties, every pair of distinct varieties is in precisely λ blocks
k,v , r relation remark
As C[j] ⊆ V and |C[j]| = k and |V | = v it is automatic that k ≤ v. If k were equal to v then
that would mean that C[j] = V for all j, which is like a job allocation problem in which every person is
qualified to do every job. However, we specified as part of the definition that k < v, so as to exclude this
uninteresting case. The condition r < b also has the same effect.
We will assume throughout our work on designs that 1 < k < v. (The cases k = 1 and k = v are trivial.)
Example 3:
Nine types of coffee are to be tested. Each of twelve families is asked to compare three of the types. Overall we want each pair from the nine to be
compared by the same number of families. (In fact, in this example, we’ll ask for
each to be compared by just one family).
Put B = {1, . . . , 12} and V = {1, . . . , 9} and Here is one way to do it
Family, block of varieties to be tested
C[1] = {1, 2, 3}
C[2] = {4, 5, 6}
C[3] = {7, 8, 9}
C[4] = {1, 4, 7}
C[5] = {1, 5, 9}
C[6] = {2, 5, 8}
C[7] = {3, 6, 9}
C[8] = {2, 6, 7}
C[9] = {3, 4, 8}
C[10] = {1, 6, 8}
C[11] = {2, 4, 9}
C[12] = {3, 5, 7}
The corresponding sets Q[p] are
Q[1] = {1, 4, 5, 10}
Q[2] = {1, 6, 8, 11}
Q[3] = {1, 7, 9, 12}
Q[4] = {2, 4, 9, 11}
Q[5] = {2, 5, 6, 12}
Q[6] = {2, 7, 8, 10}
Q[7] = {3, 4, 8, 12}
Q[8] = {3, 6, 9, 10}
Q[9] = {3, 5, 7, 11}.
It is now visible that
|V | = 9 and |B| = 12
and |C[j]| = 3 for all j
and |Q[p]| = 4 for all p.
We also have
Q[1] ∩ Q[2] = {1}
Q[3] ∩ Q[4] = {9}
Q[3] ∩ Q[6] = {7}
Q[4] ∩ Q[9] = {11}.
In fact, we have |Q[p] ∩ Q[q]| = 1 for all p ≠q, as we can see by a long but easy check of cases.
Thus, the
above sets give a (9, 12, 4, 3, 1) block design.
relation prop4: bk/v=12.3/9=4 and λ(v − 1)/(k-1) = 1.(9-1)/(3-1) =4,
proposition 4:
(v, b, r, k, λ)-block design
relations
If there is a (v, b, r, k, λ)-block design, then
bk = vr and
bk(k − 1) = λv(v − 1) and
r(k − 1) = λ(v − 1) and λ < r.
ie r=(bk/v)=λ(v − 1)/(k-1)
Not every collection of numbers satisfying the theorem necessarily corresponds to a design.
Proposition 5: (v, b, r, k, λ)-block design
relations
Suppose that we have a matching problem as before, and numbers v, b, k, λ > 0 with k < v.
Suppose that |V | = v and |B| = b and |C[j]| = k for all j and |Q[p] ∩ Q[q]| = λ for all p 6= q, so axioms (a),
(b), (d) and (e) from Definition 1 are satisfied. Then the number r = λ(v − 1)/(k − 1) is an integer and is
the same as bk/v. Moreover, we have |Q[p]| = r for all p, so axiom (c) is also satisfied, and we have a block
design.
definition 6 : quadratic residues
Let p be a prime number of the form p = 4n + 3, so
Z/p = {0, ±1, ±2, . . . , ±(2n + 1)}.
We put
R = {i ∈ Z/p | i = j
2
for some j ∈ Z/p with j 6= 0},
and call this the set of quadratic residues. We then have a matching problem with B = V = Z/p and
C[j] = j + R.Remark 7. We have m ∈ C[j] iff
Remark 7. We have m ∈ C[j] iff m ∈ j + R iff m − j ∈ R iff j ∈ m − R, so Q[m] = m − R
Example 8:
Take p = 7, so p = 4n + 3 with n = 1 and Z/p = {0, ±1, ±2, ±3}.
We have (±1)2 = 1 and
(±2)2 = 4 = −3 (mod 7) and (±3)2 = 9 = 2 (mod 7), so
R = {1, 2, −3}. This gives
C[0] = {1, 2, −3}
Q[0] = {−1, −2, 3}
C[1] = {2, 3, −2}
Q[1] = {0, −1, −3}
C[2] = {3, −3, −1}
Q[2] = {1, 0, −2}
C[3] = {−3, −2, 0}
Q[3] = {2, 1, −1}
C[−1] = {0, 1, 3}
Q[−1] = {−2, −3, 2}
C[−2] = {−1, 0, 2}
Q[−2] = {−3, 3, 1}
C[−3] = {−2, −1, 1}
Q[−3] = {3, 2, 0}.
One can check that |Q[l] ∩ Q[m]| = 1 whenever l ≠m, so this is a (7, 7, 3, 3, 1)-block design
Example 9:
We use arithmetic mod 11 to construct a design with 11 varieties
and 5 varieties per block, v = 11, k = 5. The blocks are listed below. Each one is
constructed from the previous one by adding one to the entries and working mod
11 (with the slight variation that we write 11 rather than 0).
block number; block
Take p = 11, so p = 4n + 3 with n = 2 and Z/p = {0, ±1, ±2, ±3, ±4, ±5}. We have (±1)2 = 1
and (±2)2 = 4 and (±3)2 = 9 = −2 (mod 11) and (±4)2 = 16 = 5 (mod 11) and (±5)2 = 25 = 3 (mod 11),
so
R = {1, −2, 3, 4, 5}.
I particular, we have |R| = 5 and so |C[j]| = 5 for all j and |Q[m]| = 5 for all m. We also have
Q[0] ∩ Q[1] = (−R) ∩ (1 − R) = {−1, 2, −3, −4, −5} ∩ {0, 3, −2, −3, −4} = {−3, −4},
so |Q[0]∩Q[1]| = 2. In fact we have |Q[l]∩Q[m]| = 2 for all l 6= m, so we have a (11, 11, 5, 5, 2)-block design.
This process only rarely works. For example, with 11 varieties, if you start with
the first block {1, 2, 3, 4, 5} then you will find that the pair (4, 5) appears in 4 blocks,
but the pair (1, 6) appears in none. So this is not a design.
quadratic residues answer this
lemma 10: for each i relation with R
Lemma 10. For each i ∈ {1, . . . , 2n + 1}, precisely one of i and −i is in R. Thus, |R| = 2n + 1.
This result is clearly visible in the cases p = 7 (where R = {1, 2, −3}) and p = 11 (where R =
{1, −2, 3, 4, 5}).
From Lemma 10 it is clear that |C[j]| = 2n + 1 for all j, and that |Q[m]| = 2n + 1 for all m. However, it
is not yet clear what we can say about |Q[l] ∩ Q[m]| when l 6= m. For this we need some more definitions.
DEF 11: size of D for
D = {(u, v) ∈ R × R | u ≠ v}
We put D = {(u, v) ∈ R × R | u ≠ v}, so |D| = |R|(|R| − 1). As |R| = 2n + 1, this gives
|D| = (4n + 2)n. Also, for x ∈ Z/p with x 6= 0 we put Dx = {(u, v) ∈ D | u − v = x}. We note that D is the
disjoint union of the subsets Dx, so |D| =
P
x
|Dx|.
Lemma 12: |D_x|
|D_x| = n for all x.
EXAMPLE: lemma 12 with p = 11 and so n = 2 and
R = {1, −2, 3, 4, 5}.
p = 11 and so n = 2 and
R = {1, −2, 3, 4, 5}. The table below shows the differences u − v for u, v ∈ R with u≠v
[u\v][ 1][-2][3 ][4 ][ 5] [ 1 ][ x][3 ][-2][-3][-4] [-2 ][-3][x ][-5][ 5][ 4] [ 3 ][2 ][5 ][ x ][-1][-2] [ 4 ][3 ][-5][ 1 ][ x][-1] [ 5 ][ 4][-4][ 2 ][ 1 ][ x]
We can read off the sets D_x from this. For example, to find D_5 we look in the table and see that 5 appears
in the position where u = −2 and v = 4, and also in the position where u = 3 and v = −2.
We therefore
have D_5 = {(−2, 4),(3, −2)}. The complete list of sets D_x is as follows:
D_1 = {(4, 3),(5, 4)}
D_−1 = {(3, 4),(4, 5)}
D_2 = {(3, 1),(5, 3)}
D_−2 = {(1, 3),(3, 5)}
D_3 = {(1, −2),(4, 1)}
D_−3 = {(−2, 1),(1, 4)}
D_4 = {(−2, 5),(5, 1)}
D_−4 = {(5, −2),(1, 5)}
D_5 = {(−2, 4),(3, −2)}
D_−5 = {(4, −2),(−2, 3)}
We find that |D_x| = 2 = n in every case, as predicted by the lemma.
THM 14: matching problem in def quadratic residues
The matching problem in Definition 6 is a (4n + 2, 4n + 2, 2n + 1, 2n + 1, n)-block design.
