View source for Partially balanced incomplete block design

''PBIBD''

A (symmetric) association scheme with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p1200801.png" /> classes on the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p1200802.png" /> symbols <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p1200803.png" /> satisfies:

Two distinct symbols <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p1200804.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p1200805.png" /> are termed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p1200806.png" />th associates for exactly one <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p1200807.png" />;

each symbol has exactly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p1200808.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p1200809.png" />th associates; and

when two distinct symbols <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008010.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008011.png" /> are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008012.png" />th associates, the number of other symbols that are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008013.png" />th associates of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008014.png" /> and also <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008015.png" />th associates of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008016.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008017.png" />, independent of the choice of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008018.png" />th associates <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008019.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008020.png" />. The matrices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008021.png" /> of an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008022.png" />-class association scheme are defined as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008023.png" />, and for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008024.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008025.png" /> is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008026.png" />-matrix whose entry <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008027.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008028.png" /> exactly when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008029.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008030.png" /> are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008031.png" />th associates.

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008032.png" /> be a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008033.png" />-set with a symmetric <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008034.png" />-class association scheme defined on it. A partially balanced incomplete block design with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008035.png" /> associate classes (or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008036.png" />) is a [[Block design|block design]] based on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008037.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008038.png" /> sets (the blocks), each of size <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008039.png" />, and with each symbol appearing in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008040.png" /> blocks. Any two symbols that are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008041.png" />th associates appear together in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008042.png" /> blocks of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008043.png" />. The numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008044.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008045.png" />) are the parameters of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008046.png" />. The notation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008047.png" /> is also used. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008048.png" /> is used for the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008049.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008050.png" /> incidence matrix of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008051.png" />.

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008052.png" /> be the matrices of an association scheme corresponding to a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008053.png" />. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008054.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008055.png" />. Conversely, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008056.png" /> is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008057.png" />-matrix which satisfies these conditions and the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008058.png" /> are the matrices of an association scheme, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008059.png" /> is the incidence matrix of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008060.png" />.

It is easily verified that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008061.png" />, that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008062.png" />, and that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008063.png" />. A <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008064.png" /> is a balanced incomplete block design (a BIBD; cf. [[Block design|Block design]]); also, a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008065.png" /> in which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008066.png" /> is a BIBD.

There are six types of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008067.png" />s, [[#References|[a3]]], based on the underlying types of association schemes:

1) group divisible;

2) triangular;

3) Latin-square-type;

4) cyclic;

5) partial-geometry-type; and

6) miscellaneous.

Partition the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008068.png" />-set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008069.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008070.png" /> groups each of size <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008071.png" />. In a group-divisible association scheme the first associates are the symbols in the same group and the second associates are all the other symbols. The eigenvalues of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008072.png" /> are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008073.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008074.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008075.png" />, with multiplicities <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008076.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008077.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008078.png" />, respectively. A group-divisible partially balanced incomplete block design is singular if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008079.png" />; semi-regular if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008080.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008081.png" />; and regular if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008082.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008083.png" />.

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008084.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008085.png" />, and arrange the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008086.png" /> elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008087.png" /> in a symmetrical <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008088.png" />-array with the diagonal entries blank. In the triangular association scheme, the first associates of a symbol are those in the same row or column of the array; all other symbols are second associates. The duals of triangular <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008089.png" />s are the residual designs of symmetric BIBDs with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008090.png" />. Triangular schemes and generalized triangular schemes are also known as Johnson schemes.

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008091.png" /> and arrange the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008092.png" /> symbols in an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008093.png" /> array. Superimpose on this array a set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008094.png" /> mutually orthogonal Latin squares (see [[#References|[a1]]] and also [[Latin square|Latin square]]) of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008095.png" />. Let the first associates of any symbol be those in the same row or column of the array or be associated with the same symbols in one of the Latin squares. This is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008097.png" />-type association scheme. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008098.png" />, then the scheme is group divisible; if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p12008099.png" />, then all the symbols are first associates of each other.

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p120080100.png" />. A non-group divisible association scheme defined on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p120080101.png" /> is cyclic if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p120080102.png" /> and if the set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p120080103.png" /> differences of distinct elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p120080104.png" /> has each element of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p120080105.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p120080106.png" /> times and each element of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p120080107.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p120080108.png" /> times. The first associates of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p120080109.png" /> are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120080/p120080110.png" />.

In a partial-geometry-type association scheme, two symbols are first associates if they are incident with a line of the geometry and second associates if they are not incident with a line of the geometry.

See [[#References|[a2]]], [[#References|[a4]]], [[#References|[a5]]] for further information.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  R.J.R. Abel,   A.E. Brouwer,   C.J. Colbourn,   J.H. Dinitz,   "Mutually orthogonal latin squares"  C.J. Colbourn (ed.)  J.H. Dinitz (ed.) , ''CRC Handbook of Combinatorial Designs'' , CRC  (1996)  pp. 111–141</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  R.A. Bailey,   "Partially balanced designs"  N.L. Johnson (ed.)  S. Kotz (ed.)  C. Read (ed.) , ''Encycl. Stat. Sci.'' , '''6''' , Wiley  (1985)  pp. 593–610</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  W.H. Clatworthy,   "Tables of two-associate-class partially balanced designs" , ''Applied Math. Ser.'' , '''63''' , Nat. Bureau of Standards (US)  (1973)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  D. Raghavarao,   "Constructions and combinatorial problems in design of experiments" , Wiley  (1971)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  D.J. Street,   A.P. Street,   "Partially balanced incomplete block designs"  C.J. Colbourn (ed.)  J.H. Dinitz (ed.) , ''CRC Handbook of Combinatorial Designs'' , CRC  (1996)  pp. 419–423</TD></TR></table>