Namespaces
Variants
Actions

Difference between revisions of "Block design"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (a)
m (typo)
 
(6 intermediate revisions by 2 users not shown)
Line 1: Line 1:
A system of subsets of a finite set which satisfies certain conditions related to the frequency of appearance of pairs of elements of the set in the subsets of the system. The concept of a block design arose in the theory of design (planning) of (statistical) experiments in the 1920s and 1930s, but had been studied as early as the mid-19th century under the name tactical configurations. The concept of a block design is a variation of the concepts of a hypergraph, a net and a complex. As a rule, in a block design several additional limitations are imposed on the family of subsets. A block design may be defined by a pair of sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b0166701.png" /> where
+
{{TEX|done}}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b0166702.png" /></td> </tr></table>
+
A system of subsets of a finite set which satisfies certain conditions related to the frequency of appearance of pairs of elements of the set in the subsets of the system. The concept of a block design arose in the theory of design (planning) of (statistical) experiments in the 1920s and 1930s, but had been studied as early as the mid-19th century under the name tactical configurations. The concept of a block design is a variation of the concepts of a hypergraph, a net and a complex. As a rule, in a block design several additional limitations are imposed on the family of subsets. A block design may be defined by a pair of sets  $  (V,\  B) $
 +
where
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b0166703.png" /></td> </tr></table>
+
$$
 +
V \  = \  \{ a _ {1} \dots a _ {v} \} ,\ \
 +
B \  = \  \{ B _ {1} \dots B _ {b} \} ,
 +
$$
  
The elements of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b0166704.png" /> are called the points (treatments) of the block design, or varieties or elements, while the elements of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b0166705.png" /> are called its blocks. The element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b0166706.png" /> and the block <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b0166707.png" /> are incident if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b0166708.png" />. The number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b0166709.png" /> of elements incident with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667010.png" /> is usually denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667011.png" />, while the number of blocks incident with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667012.png" /> is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667013.png" />. The number
+
$$
 +
B _ {i} \  \subseteq \  V,\ \  i = 1 \dots b.
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667014.png" /></td> </tr></table>
+
The elements of the set  $  V $
 +
are called the points (treatments) of the block design, or varieties or elements, while the elements of the set  $  B $
 +
are called its blocks. The element  $  a _ {i} $
 +
and the block  $  B _ {j} $
 +
are incident if  $  a _ {i} \in B _ {j} $.  
 +
The number  $  | B _ {j} | $
 +
of elements incident with  $  B _ {j} $
 +
is usually denoted by  $  k _ {j} $,
 +
while the number of blocks incident with  $  a _ {i} $
 +
is denoted by  $  r _ {i} $.  
 +
The number
  
is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667015.png" />. The numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667016.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667017.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667018.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667019.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667020.png" />) are said to be the parameters of the block design. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667021.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667022.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667023.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667024.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667025.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667026.png" /> is a balanced incomplete block design  (BIB-design) with parameters <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667027.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667028.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667029.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667030.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667031.png" />. The meaning of the word  "balanced"  is that the frequencies of appearance of all elements and pairs of elements in the blocks are respectively equal, while the word  "incomplete"  indicates that, generally speaking, not all the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667032.png" />-element sets are included in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667033.png" />.
+
$$
 +
| \{ {B _ j} : {a _ {i} \in B _ {j} ,\
 +
a _ {l} \in B _ j} \}
 +
|
 +
$$
  
Let exactly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667034.png" /> different numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667035.png" /> be encountered among the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667036.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667037.png" />, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667038.png" /> symmetric association relations be introduced on the elements of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667039.png" /> so that the following conditions are satisfied:
+
is denoted by  $  \lambda _ {il} $.  
 +
The numbers  $  v,\  b,\  r _ {i} $,
 +
$  k _ {j} $,
 +
$  \lambda _ {il} $(
 +
$  i,\  l = 1 \dots v $;
 +
$  j = 1 \dots b $)
 +
are said to be the parameters of the block design. If  $  r _ {i} = r $
 +
for all  $  i = 1 \dots v $,  
 +
$  k _ {j} = k $
 +
for all  $  j = 1 \dots b $
 +
and $  \lambda _ {il} = \lambda $,
 +
$  (V,\  B) $
 +
is a ''[[balanced incomplete block design]]''  (BIBD) with parameters  $  v $,
 +
b $,
 +
$  r $,
 +
$  k $,
 +
$  \lambda $.  
 +
The meaning of the word  "balanced" is that the frequencies of appearance of all elements and pairs of elements in the blocks are respectively equal, while the word  "incomplete" indicates that, generally speaking, not all the $  k $-
 +
element sets are included in  $  B $.
  
1) the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667040.png" /> of all pairs of distinct elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667041.png" /> is subdivided into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667042.png" /> disjoint subsets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667043.png" /> and, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667044.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667045.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667046.png" /> are said to be <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667047.png" />-associated;
+
Let exactly  $  m $
 +
different numbers  $  \lambda _ {1} \dots \lambda _ {m} $
 +
be encountered among the numbers  $  \lambda _ {il} $,
 +
$  i,\  l = 1 \dots v $,  
 +
and let  $  m $
 +
symmetric association relations be introduced on the elements of the set  $  V $
 +
so that the following conditions are satisfied:
  
2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667048.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667049.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667050.png" />;
+
1) the set  $  V  ^ {2} $
 +
of all pairs of distinct elements of  $  V $
 +
is subdivided into  $  m $
 +
disjoint subsets  $  V _ {1}  ^ {2} \dots V _ {m}  ^ {2} $
 +
and, if  $  (a,\  a  ^  \prime  ) \in V _ {j}  ^ {2} $,  
 +
then  $  a $
 +
and  $  a  ^  \prime  $
 +
are said to be  $  j $-
 +
associated;
  
3) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667051.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667052.png" />;
+
2) $  | \{ {B _ j} : {a \in B _ {j} ,\  a  ^  \prime  \in B _ {j} ,\  (a,\  a  ^  \prime  ) \in V _ {i}  ^ {2}} \} | = \lambda _ {i} $,
 +
$  i = 1 \dots m $,
 +
$  j = 1 \dots b $;
  
4) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667053.png" />, and, in view of the symmetry, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667054.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667055.png" />. A block design with the properties 1)–4) is said to be a partial balanced incomplete block design with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667057.png" /> types of relations or PBIB(<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667059.png" />)-design. The rule which specifies the association relation is called the association design. A BIB-design is a PBIB(<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667060.png" />)-design. An example of a PBIB(<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667061.png" />)-design is a block design which may be represented as the table
+
3) $  | \{ {a} : {\exists ^  \prime  \  (a,\  a  ^  \prime  ) \in V _ {i}  ^ {2}} \} | = n _ {i} $,
 +
$  i = 1 \dots m $;
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667062.png" /></td> </tr></table>
+
4)  $  | \{ {a  ^ {\prime\prime}} : {(a  ^ {\prime\prime} ,\  a) \in V _ {j}  ^ {2} ,\  (a  ^ {\prime\prime} ,\  a  ^  \prime  ) \in V _ {k}  ^ {2} ,\  (a,\  a  ^  \prime  ) \in V _ {i}  ^ {2}} \} | = p _ {jk}  ^ {i} $,
 +
and, in view of the symmetry,  $  p _ {jk}  ^ {i} = p _ {kj}  ^ {i} $,
 +
$  i,\  j,\  k = 1 \dots m $.
 +
A block design with the properties 1)–4) is said to be a partial balanced incomplete block design with  $  m $
 +
types of relations or a  PBIB( $  m $)-
 +
design. The rule which specifies the association relation is called the association design. A BIB-design is a PBIB( $  1 $)-
 +
design. An example of a PBIB( $  2 $)-
 +
design is a block design which may be represented as the table
  
where any two numbers in the same column are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667063.png" />-associated, while any two numbers in different columns are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667064.png" />-associated. Here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667065.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667066.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667067.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667068.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667069.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667070.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667071.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667072.png" />.
+
$$
 +
\begin{array}{r}
 +
1 \\
 +
4 \\
 +
7 \\
 +
10
 +
\end{array}
 +
\ \
 +
\begin{array}{r}
 +
1 \\
 +
5 \\
 +
8 \\
 +
11
 +
\end{array}
 +
\ \
 +
\begin{array}{r}
 +
1 \\
 +
6 \\
 +
9 \\
 +
12
 +
\end{array}
 +
\ \
 +
\begin{array}{r}
 +
2 \\
 +
4 \\
 +
9 \\
 +
11
 +
\end{array}
 +
\ \
 +
\begin{array}{r}
 +
2 \\
 +
5 \\
 +
7 \\
 +
12
 +
\end{array}
 +
\ \
 +
\begin{array}{r}
 +
2 \\
 +
6 \\
 +
8 \\
 +
10
 +
\end{array}
 +
\ \
 +
\begin{array}{r}
 +
3 \\
 +
4 \\
 +
8 \\
 +
12
 +
\end{array}
 +
\ \
 +
\begin{array}{r}
 +
3 \\
 +
5 \\
 +
9 \\
 +
10
 +
\end{array}
 +
\ \
 +
\begin{array}{r}
 +
3 \\
 +
6 \\
 +
7 \\
 +
11
 +
\end{array}
 +
,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667073.png" /></td> </tr></table>
+
where any two numbers in the same column are  $  1 $-
 +
associated, while any two numbers in different columns are  $  2 $-
 +
associated. Here  $  v = 12 $,
 +
$  b = 9 $,
 +
$  r = 3 $,
 +
$  k = 4 $,
 +
$  \lambda _ {1} = 1 $,
 +
$  \lambda _ {2} = 0 $,
 +
$  n _ {1} = 9 $,
 +
$  n _ {2} = 2 $.
  
To each block design with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667074.png" /> elements and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667075.png" /> blocks corresponds an incidence matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667076.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667077.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667078.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667079.png" /> otherwise, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667080.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667081.png" />. The theory of block designs considers problems on the existence and classification as well as problems involved in the construction of a block design with given parameters. The parameters of a block design are related in a certain manner. The following equations are valid for BIB-designs:
+
$$
 +
P  ^ {1} \  = \  \| p _ {jk}  ^ {1} \| \  = \
 +
\left \|
 +
{6 \atop 2} \
 +
{2 \atop 0} \
 +
\right \| ,\ \
 +
P  ^ {2} \  = \  \| p _ {jk}  ^ {2} \| \  = \
 +
\left \|
 +
{9 \atop 0} \
 +
{0 \atop 1} \
 +
\right \| .
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667082.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
To each block design with  $  v $
 +
elements and  $  b $
 +
blocks corresponds an [[incidence matrix]]  $  A = \| c _ {ij} \| $,
 +
where  $  c _ {ij} = 1 $
 +
if  $  a _ {i} \in B _ {j} $
 +
and  $  c _ {ij} = 0 $
 +
otherwise,  $  i = 1 \dots v $;  
 +
$  j = 1 \dots b $.  
 +
The theory of block designs considers problems on the existence and classification as well as problems involved in the construction of a block design with given parameters. The parameters of a block design are related in a certain manner. The following equations are valid for BIB-designs:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667083.png" /></td> </tr></table>
+
$$ \tag{1}
 +
vr \  = \  kb,
 +
$$
 +
 
 +
$$
 +
\lambda (v-1) \  = \  r (k-1).
 +
$$
  
 
Equation (1) and the relationships
 
Equation (1) and the relationships
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667084.png" /></td> </tr></table>
+
$$
 +
\sum _ { i=1 } ^ m
 +
n _ {i} \  = \  v - 1,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667085.png" /></td> </tr></table>
+
$$
 +
\sum _ {i = 1} ^ m
 +
\lambda _ {i} n _ {i} \  = \
 +
r (k - 1),
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667086.png" /></td> </tr></table>
+
$$
 +
\sum _ {k = 1} ^ m
 +
p _ {jk}  ^ {i} \  = \
 +
\left \{ \
 +
{
 +
n _ {j}\qquad \textrm{ if }i \neq j ,\qquad\qquad \atop n _ {j} - 1 \ \  \textrm{ if } \  i = j,\  i,\  j = 1 \dots m,}
 +
\quad \textrm { with }\quad
 +
n _ {i} p _ {jk}  ^ {i} \  = \
 +
n _ {j} p _ {ik}  ^ {j} \  = \
 +
n _ {k} p _ {ij}  ^ {k} ,\ \
 +
i,\  j,\  k = 1 \dots m,
 +
\right .$$
  
are valid for the parameters of PBIB(<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667087.png" />)-designs. The incidence matrix of a BIB-design satisfies the fundamental matrix relation
+
are valid for the parameters of PBIB( $  m $)-
 +
designs. The incidence matrix of a BIB-design satisfies the fundamental matrix relation
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667088.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
$$ \tag{2}
 +
A A  ^ {T} \  = \
 +
(r - \lambda )
 +
E + \lambda J ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667089.png" /> is the unit matrix of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667090.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667091.png" /> is the matrix of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667092.png" /> consisting exclusively of ones. The existence of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667093.png" />-matrix which satisfies condition (2) is a sufficient condition for the existence of a BIB-design with the given parameters. The inequality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667094.png" /> follows from (2). A BIB-design for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667095.png" /> (i.e. also <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667096.png" />) is said to be a symmetric block design or a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667098.png" />-configuration. The following theorem applies to symmetric BIB-designs: If there exists a symmetric BIB-design with parameters <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667099.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670100.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670101.png" />, then: 1) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670102.png" /> is even, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670103.png" /> is a perfect square; 2) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670104.png" /> is odd, the equation
+
where $  E $
 +
is the unit matrix of order $  v $
 +
and $  J $
 +
is the matrix of order $  v $
 +
consisting exclusively of ones. The existence of a $  (0,\  1) $-
 +
matrix which satisfies condition (2) is a sufficient condition for the existence of a BIB-design with the given parameters. The [[Fisher inequality]]  $  b \geq v $
 +
follows from (2). A BIB-design for which $  b = v $(
 +
i.e. also $  r = k $)  
 +
is said to be a [[symmetric design]] or a $  (v,\  k,\  \lambda ) $-
 +
configuration. The following theorem applies to symmetric BIB-designs: If there exists a symmetric BIB-design with parameters $  v $,  
 +
$  k $,  
 +
$  \lambda $,  
 +
then: 1) if $  v $
 +
is even, $  k - \lambda $
 +
is a perfect square; 2) if $  v $
 +
is odd, the equation
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670105.png" /></td> </tr></table>
+
$$
 +
z  ^ {2} \  = \  (k - \lambda ) x  ^ {2} + (-1)  ^ {(v-1)/2} \lambda y  ^ {2}
 +
$$
  
has a solution in integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670106.png" />, not all of which are zero. The conditions of this theorem are sufficient for the existence of a rational matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670107.png" /> satisfying equation (2).
+
has a solution in integers $  x,\  y,\  z $,  
 +
not all of which are zero. The conditions of this theorem are sufficient for the existence of a rational matrix $  A $
 +
satisfying equation (2).
  
A special range of problems involving the existence of BIB-designs arises in the context of the following problem: Given <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670108.png" /> blocks, find the conditions necessary for the completion of these blocks to form a BIB-design. In their most general form these conditions are expressed as the requirement of positive definiteness of some quadratic form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670109.png" />, as well as the possibility of representing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670110.png" /> as a sum of squares of linear forms with non-negative coefficients.
+
A special range of problems involving the existence of BIB-designs arises in the context of the following problem: Given b $
 +
blocks, find the conditions necessary for the completion of these blocks to form a BIB-design. In their most general form these conditions are expressed as the requirement of positive definiteness of some quadratic form $  Q $,  
 +
as well as the possibility of representing $  Q $
 +
as a sum of squares of linear forms with non-negative coefficients.
  
The following subclasses of BIB-designs have been most extensively studied: Steiner systems (BIB-designs with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670111.png" />), in particular Steiner triple systems (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670112.png" />); Hadamard configurations (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670113.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670114.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670115.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670116.png" />), the incidence matrix of which is obtained from a [[Hadamard matrix|Hadamard matrix]]; affine finite geometries and projective finite geometries [[#References|[1]]]. In the class of PBIB-designs those most extensively studied are PBIB(<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670117.png" />)-designs, which may be subdivided according to their association design into group-divisible block designs, triangular block designs, Latin square block designs, cyclic block designs, etc. [[#References|[3]]].
+
The following subclasses of BIB-designs have been most extensively studied: Steiner systems (BIB-designs with $  \lambda = 1 $),  
 +
in particular [[Steiner triple system]]s ( $  k = 3 $);  
 +
Hadamard configurations ( $  v = b = 4t - 1 $,  
 +
$  r = k = 2t - 1 $,  
 +
$  \lambda = t - 1 $,  
 +
$  t\geq 2 $),  
 +
the incidence matrix of which is obtained from a [[Hadamard matrix|Hadamard matrix]]; affine finite geometries and projective finite geometries [[#References|[1]]]. In the class of PBIB-designs those most extensively studied are PBIB( $  2 $)-
 +
designs, which may be subdivided according to their association design into group-divisible block designs, triangular block designs, Latin square block designs, cyclic block designs, etc. [[#References|[3]]].
  
 
The methods for constructing block designs are usually classified as direct and recursive. The latter methods make it possible to use designs with smaller parameter values to construct designs with larger parameter values. The direct methods mostly utilize the properties of finite fields or some geometric properties.
 
The methods for constructing block designs are usually classified as direct and recursive. The latter methods make it possible to use designs with smaller parameter values to construct designs with larger parameter values. The direct methods mostly utilize the properties of finite fields or some geometric properties.
Line 61: Line 273:
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  H.J. Ryser,  "Combinatorial mathematics" , Wiley  (1963)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  M. Hall,  "Combinatorial theory" , Blaisdell  (1967)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  S.A. Shirokova,  "Block designs"  ''Russian Math. Surveys'' , '''23''' :  5  (1968)  pp. 47–94  ''Uspekhi Mat. Nauk'' , '''23''' :  5  (1968)  pp. 51–98</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  H.J. Ryser,  "Combinatorial mathematics" , Wiley  (1963)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  M. Hall,  "Combinatorial theory" , Blaisdell  (1967)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  S.A. Shirokova,  "Block designs"  ''Russian Math. Surveys'' , '''23''' :  5  (1968)  pp. 47–94  ''Uspekhi Mat. Nauk'' , '''23''' :  5  (1968)  pp. 51–98</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====
The theorem giving conditions on the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670118.png" /> in order that a symmetric BIB-design with these numbers as parameters exists, is called the Bruck–Ryser–Chowla theorem.
+
The theorem giving conditions on the numbers $  v,\  k,\  \lambda $
 +
in order that a symmetric BIB-design with these numbers as parameters exists, is called the Bruck–Ryser–Chowla theorem.
  
 
[[Category:Combinatorics]]
 
[[Category:Combinatorics]]

Latest revision as of 16:08, 6 February 2020


A system of subsets of a finite set which satisfies certain conditions related to the frequency of appearance of pairs of elements of the set in the subsets of the system. The concept of a block design arose in the theory of design (planning) of (statistical) experiments in the 1920s and 1930s, but had been studied as early as the mid-19th century under the name tactical configurations. The concept of a block design is a variation of the concepts of a hypergraph, a net and a complex. As a rule, in a block design several additional limitations are imposed on the family of subsets. A block design may be defined by a pair of sets $ (V,\ B) $ where

$$ V \ = \ \{ a _ {1} \dots a _ {v} \} ,\ \ B \ = \ \{ B _ {1} \dots B _ {b} \} , $$

$$ B _ {i} \ \subseteq \ V,\ \ i = 1 \dots b. $$

The elements of the set $ V $ are called the points (treatments) of the block design, or varieties or elements, while the elements of the set $ B $ are called its blocks. The element $ a _ {i} $ and the block $ B _ {j} $ are incident if $ a _ {i} \in B _ {j} $. The number $ | B _ {j} | $ of elements incident with $ B _ {j} $ is usually denoted by $ k _ {j} $, while the number of blocks incident with $ a _ {i} $ is denoted by $ r _ {i} $. The number

$$ | \{ {B _ j} : {a _ {i} \in B _ {j} ,\ a _ {l} \in B _ j} \} | $$

is denoted by $ \lambda _ {il} $. The numbers $ v,\ b,\ r _ {i} $, $ k _ {j} $, $ \lambda _ {il} $( $ i,\ l = 1 \dots v $; $ j = 1 \dots b $) are said to be the parameters of the block design. If $ r _ {i} = r $ for all $ i = 1 \dots v $, $ k _ {j} = k $ for all $ j = 1 \dots b $ and $ \lambda _ {il} = \lambda $, $ (V,\ B) $ is a balanced incomplete block design (BIBD) with parameters $ v $, $ b $, $ r $, $ k $, $ \lambda $. The meaning of the word "balanced" is that the frequencies of appearance of all elements and pairs of elements in the blocks are respectively equal, while the word "incomplete" indicates that, generally speaking, not all the $ k $- element sets are included in $ B $.

Let exactly $ m $ different numbers $ \lambda _ {1} \dots \lambda _ {m} $ be encountered among the numbers $ \lambda _ {il} $, $ i,\ l = 1 \dots v $, and let $ m $ symmetric association relations be introduced on the elements of the set $ V $ so that the following conditions are satisfied:

1) the set $ V ^ {2} $ of all pairs of distinct elements of $ V $ is subdivided into $ m $ disjoint subsets $ V _ {1} ^ {2} \dots V _ {m} ^ {2} $ and, if $ (a,\ a ^ \prime ) \in V _ {j} ^ {2} $, then $ a $ and $ a ^ \prime $ are said to be $ j $- associated;

2) $ | \{ {B _ j} : {a \in B _ {j} ,\ a ^ \prime \in B _ {j} ,\ (a,\ a ^ \prime ) \in V _ {i} ^ {2}} \} | = \lambda _ {i} $, $ i = 1 \dots m $, $ j = 1 \dots b $;

3) $ | \{ {a} : {\exists a ^ \prime \ (a,\ a ^ \prime ) \in V _ {i} ^ {2}} \} | = n _ {i} $, $ i = 1 \dots m $;

4) $ | \{ {a ^ {\prime\prime}} : {(a ^ {\prime\prime} ,\ a) \in V _ {j} ^ {2} ,\ (a ^ {\prime\prime} ,\ a ^ \prime ) \in V _ {k} ^ {2} ,\ (a,\ a ^ \prime ) \in V _ {i} ^ {2}} \} | = p _ {jk} ^ {i} $, and, in view of the symmetry, $ p _ {jk} ^ {i} = p _ {kj} ^ {i} $, $ i,\ j,\ k = 1 \dots m $. A block design with the properties 1)–4) is said to be a partial balanced incomplete block design with $ m $ types of relations or a PBIB( $ m $)- design. The rule which specifies the association relation is called the association design. A BIB-design is a PBIB( $ 1 $)- design. An example of a PBIB( $ 2 $)- design is a block design which may be represented as the table

$$ \begin{array}{r} 1 \\ 4 \\ 7 \\ 10 \end{array} \ \ \begin{array}{r} 1 \\ 5 \\ 8 \\ 11 \end{array} \ \ \begin{array}{r} 1 \\ 6 \\ 9 \\ 12 \end{array} \ \ \begin{array}{r} 2 \\ 4 \\ 9 \\ 11 \end{array} \ \ \begin{array}{r} 2 \\ 5 \\ 7 \\ 12 \end{array} \ \ \begin{array}{r} 2 \\ 6 \\ 8 \\ 10 \end{array} \ \ \begin{array}{r} 3 \\ 4 \\ 8 \\ 12 \end{array} \ \ \begin{array}{r} 3 \\ 5 \\ 9 \\ 10 \end{array} \ \ \begin{array}{r} 3 \\ 6 \\ 7 \\ 11 \end{array} , $$

where any two numbers in the same column are $ 1 $- associated, while any two numbers in different columns are $ 2 $- associated. Here $ v = 12 $, $ b = 9 $, $ r = 3 $, $ k = 4 $, $ \lambda _ {1} = 1 $, $ \lambda _ {2} = 0 $, $ n _ {1} = 9 $, $ n _ {2} = 2 $.

$$ P ^ {1} \ = \ \| p _ {jk} ^ {1} \| \ = \ \left \| {6 \atop 2} \ {2 \atop 0} \ \right \| ,\ \ P ^ {2} \ = \ \| p _ {jk} ^ {2} \| \ = \ \left \| {9 \atop 0} \ {0 \atop 1} \ \right \| . $$

To each block design with $ v $ elements and $ b $ blocks corresponds an incidence matrix $ A = \| c _ {ij} \| $, where $ c _ {ij} = 1 $ if $ a _ {i} \in B _ {j} $ and $ c _ {ij} = 0 $ otherwise, $ i = 1 \dots v $; $ j = 1 \dots b $. The theory of block designs considers problems on the existence and classification as well as problems involved in the construction of a block design with given parameters. The parameters of a block design are related in a certain manner. The following equations are valid for BIB-designs:

$$ \tag{1} vr \ = \ kb, $$

$$ \lambda (v-1) \ = \ r (k-1). $$

Equation (1) and the relationships

$$ \sum _ { i=1 } ^ m n _ {i} \ = \ v - 1, $$

$$ \sum _ {i = 1} ^ m \lambda _ {i} n _ {i} \ = \ r (k - 1), $$

$$ \sum _ {k = 1} ^ m p _ {jk} ^ {i} \ = \ \left \{ \ { n _ {j}\qquad \textrm{ if }i \neq j ,\qquad\qquad \atop n _ {j} - 1 \ \ \textrm{ if } \ i = j,\ i,\ j = 1 \dots m,} \quad \textrm { with }\quad n _ {i} p _ {jk} ^ {i} \ = \ n _ {j} p _ {ik} ^ {j} \ = \ n _ {k} p _ {ij} ^ {k} ,\ \ i,\ j,\ k = 1 \dots m, \right .$$

are valid for the parameters of PBIB( $ m $)- designs. The incidence matrix of a BIB-design satisfies the fundamental matrix relation

$$ \tag{2} A A ^ {T} \ = \ (r - \lambda ) E + \lambda J , $$

where $ E $ is the unit matrix of order $ v $ and $ J $ is the matrix of order $ v $ consisting exclusively of ones. The existence of a $ (0,\ 1) $- matrix which satisfies condition (2) is a sufficient condition for the existence of a BIB-design with the given parameters. The Fisher inequality $ b \geq v $ follows from (2). A BIB-design for which $ b = v $( i.e. also $ r = k $) is said to be a symmetric design or a $ (v,\ k,\ \lambda ) $- configuration. The following theorem applies to symmetric BIB-designs: If there exists a symmetric BIB-design with parameters $ v $, $ k $, $ \lambda $, then: 1) if $ v $ is even, $ k - \lambda $ is a perfect square; 2) if $ v $ is odd, the equation

$$ z ^ {2} \ = \ (k - \lambda ) x ^ {2} + (-1) ^ {(v-1)/2} \lambda y ^ {2} $$

has a solution in integers $ x,\ y,\ z $, not all of which are zero. The conditions of this theorem are sufficient for the existence of a rational matrix $ A $ satisfying equation (2).

A special range of problems involving the existence of BIB-designs arises in the context of the following problem: Given $ b $ blocks, find the conditions necessary for the completion of these blocks to form a BIB-design. In their most general form these conditions are expressed as the requirement of positive definiteness of some quadratic form $ Q $, as well as the possibility of representing $ Q $ as a sum of squares of linear forms with non-negative coefficients.

The following subclasses of BIB-designs have been most extensively studied: Steiner systems (BIB-designs with $ \lambda = 1 $), in particular Steiner triple systems ( $ k = 3 $); Hadamard configurations ( $ v = b = 4t - 1 $, $ r = k = 2t - 1 $, $ \lambda = t - 1 $, $ t\geq 2 $), the incidence matrix of which is obtained from a Hadamard matrix; affine finite geometries and projective finite geometries [1]. In the class of PBIB-designs those most extensively studied are PBIB( $ 2 $)- designs, which may be subdivided according to their association design into group-divisible block designs, triangular block designs, Latin square block designs, cyclic block designs, etc. [3].

The methods for constructing block designs are usually classified as direct and recursive. The latter methods make it possible to use designs with smaller parameter values to construct designs with larger parameter values. The direct methods mostly utilize the properties of finite fields or some geometric properties.

Block designs are used in the design of experiments, the theory of games, graph theory and in the construction of error-correcting codes.

References

[1] H.J. Ryser, "Combinatorial mathematics" , Wiley (1963)
[2] M. Hall, "Combinatorial theory" , Blaisdell (1967)
[3] S.A. Shirokova, "Block designs" Russian Math. Surveys , 23 : 5 (1968) pp. 47–94 Uspekhi Mat. Nauk , 23 : 5 (1968) pp. 51–98

Comments

The theorem giving conditions on the numbers $ v,\ k,\ \lambda $ in order that a symmetric BIB-design with these numbers as parameters exists, is called the Bruck–Ryser–Chowla theorem.

How to Cite This Entry:
Block design. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Block_design&oldid=34450
This article was adapted from an original article by V.E. Tarakanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article