On the existence and generation of non- trivial BIBDs

Abstract

A balanced incomplete block design (BIBD) is an efficient tool to infer parameters of a linear model. With a BIBD $v$ treatments are compared in $b$ blocks of size $k.$ A variety of algebraic methods were developed to determine BIBDs depending on the parameter pair (v,k). Despite the progress in the field, there are many pairs (v,k) without an algebraic solution. For such pairs it is solely known, that a trivial BIBD exists, which is commonly large. In this study we present new results on the existence and generation of BIBDs which are smaller than the trivial ones. Such so-called non- trivial BIBDs exist if a trivial BIBDs is not elementary. With a recursive method of BIBD- generation it is shown that for $v\le 126,$ $3\le k\le v/2,$ and $(v,k)\mathrm{ }\ne (8,\mathrm{ }3),$ there exist non- trivial BIBDs. The same is shown for $v\le 1000$ and $22\le k\le v/2.$ Numerical programs were written for the generation of new non- trivial BIBDs, which delivered smaller BIBDs than the recursive method for $25\le v\le 40.$ Commonly used R-programs like “crossdes” and “ibd” failed to determine such BIBDs.

Keywords:

• Balanced incomplete block design (BIBD)
• Trivial design
• Elementary design
• P versus NP problem

1. Introduction

Balanced incomplete block designs (BIBDs) are well-tried tools in experimental practise. A BIBD can be defined as a $v\times b$ incidence matrix $X,$ where $v$ is the number of treatments and $b$ the number of blocks, see e.g. Colbourn and Dinitz (2006). For $v=7$ and $b=7,$ an incidence matrix of a BIBD is $$X=\left(\begin{array}{ccccccc}1& 1& 1& 0& 0& 0& 0\\ 1& 0& 0& 1& 1& 0& 0\\ 0& 1& 0& 1& 0& 1& 0\\ 1& 0& 0& 0& 0& 1& 1\\ 0& 0& 1& 1& 0& 0& 1\\ 0& 0& 1& 0& 1& 1& 0\\ 0& 1& 0& 0& 1& 0& 1\end{array}\right).$$

The conditions for $X$ to represent a BIBD are: In each row $i,$ there are $r$ unities, i.e. ${\sum }_{j=1}^b{x}_{i,j}=r,$ in each column $j,$ there are $k$ unities, i.e. ${\sum }_{i=1}^v{x}_{i,j}=k,$ and for each pair $i$ and i′ of rows, there are $\lambda$ unities in common, i.e. ${\sum }_{j=1}^b{x}_{i,j}{x}_{i\prime ,j}=\lambda .$ In the following, these conditions will be called $r$-, $k$-, and $\lambda$- conditions. With the example we have $r=3,$ $k=3,$ and $\lambda =1.$ A compressed form of the incidence matrix is $$\left(\begin{array}{ccccccc}1& 1& 1& 2& 2& 3& 4\\ 2& 3& 5& 3& 6& 4& 5\\ 4& 7& 6& 5& 7& 6& 7\end{array}\right),$$ where column j consists of the treatments occurring in block j. For example, the first block consists of treatments (1,2,4).

A BIBD is characterized by the quintuple $\left(v,k,b,r,\lambda \right).$ The well-known necessary conditions for the existence of a BIBD are: (1) $$b\ge v$$(1) (2) $$v r=b k$$(2) (3) $$\lambda \left(v-1\right)=r\left(k-1\right).$$(3)

Parameters $b,r,$ and $\lambda$ fulfilling the necessary conditions for given $v$ and $k$ are called admissible.

It is known, that for each pair $\left(v,k\right)$ the so- called trivial BIBD exists. A BIBD is called trivial if it’s incidence matrix is identical to the set of all $\left(\begin{array}{c}v\\ k\end{array}\right)$ possible v-tuples (column vectors) with $k$ unities and $v-k$ zeros. The appropriate parameters of a trivial BIBD are (4) $$b_t=\left(\begin{array}{c}v\\ k\end{array}\right),\mathrm{ }{r}_t=\left(\begin{array}{c}v-1\\ k-1\end{array}\right)\text{ and }{\lambda }_t=\left(\begin{array}{c}v-2\\ k-2\end{array}\right).$$(4)

A BIBD for a pair (v, k) is called elementary if it cannot be split into at least two BIBDs for this (v, k). For many pairs (v, k) it is known, that the trivial BIBD is not elementary and can be reduced, i.e. there exist smaller BIBDs. Therefore, trivial BIBDs are also known as unreduced BIBDs.

For the example above we have $\left(b_t,r_t,{\lambda }_t\right)=\left(35,15,5\right).$ The blocks of the trivial BIBD are

(1,2,3), (1,2,4), (1,2,5), (1,2,6), (1,2,7), (1,3,4), (1,3,5), (1,3,6), (1,3,7), (1,4,5), (1,4,6), (1,4,7), (1,5,6), (1,5,7), (1,6,7), (2,3,4), (2,3,5), (2,3,6), (2,3,7), (2,4,5), (2,4,6), (2,4,7), (2,5,6), (2,5,7), (2,6,7), (3,4,5), (3,4,6), (3,4,7), (3,5,6), (3,5,7), (3,6,7), (4,5,6), (4,5,7), (4,6,7), and (5,6,7).

This trivial BIBD can be partitioned into three elementary BIBDs, see Rasch and Herrendörfer (1985). The first one (printed with bold digits) was given above. The second one (printed with italic digits) has also parameters $b=7,$ $r=3,$ $\mathrm{\lambda }=1.$ The set of the residual 21 of the 35 blocks is an elementary BIBD with $b=21,$ $r=9,$ $\mathrm{\lambda }=3.$

The first author of Rasch, Teuscher, and Verdooren (2016) observed that there is a trivial BIBD, which cannot be reduced: for (v, k) = (8, 3) there is no BIBD which is smaller than the trivial one. He formulated the conjecture: For $3\le k\le v/2,$ the case (v, k) = (8, 3) is the only one where the trivial BIBD is elementary.

This conjecture is relevant in the given context. If it was wrong, there were other pairs (v, k) for which the BIBD were elementary and attempts to generate a non- trivial BIBD were useless. If the conjecture was true, such attempts were reasonable.

While a proof of the conjecture is certainly difficult, a disproof would be complete, if a pair (v, k) was found, for which the smallest admissible parameters $\left(b,r,\lambda \right)$ are those of the trivial BIBD. With the sections two and three of this study, this possibility is refuted. In section two, results on the smallest admissible parameters are summarized. In section three it is shown that for $3\le k\le v/2$ and (v,k) $\ne$ (8, 3) there are admissible parameters which are smaller than those of the trivial design.

Note, that the restriction $k\le v/2$ has a technical background. If a BIBD for $k\le v/2$ exists, one can generate the complementary BIBD by exchanging zeros and unities in the incidence matrix. This complementary BIBD has parameters $v^{*}=v,$ $k^{*}=v-k,$ $b^{*}=b,$ $r^{*}=b-r,$ and ${\lambda }^{*}=b-2r+\lambda .$ Then, $k^{*}=v-k\ge v-v/2=v/2,$ i.e. complementary BIBDs ensure the existence of BIBDs for $k>v/2.$ In this study, we concentrate without loss of generality on designs for $k\le v/2.$ Therefore, the BIBDs for (v, k) = (8, 3) and (v, k) = (8, 5) are elementary.

It is a demanding algebraic task to construct BIBDs for given $v$ and $k,$ see e.g. Colbourn and Dinitz (2006). (When we write about the construction of BIBDs we mean the construction of non- trivial BIBDs.) The priority aim is to find the smallest BIBDs. Several authors contributed results on the existence, construction, and nonexistence of BIBDs with specific parameters. For a list of literature, we refer to Rasch, Teuscher, and Verdooren (2016). Rasch et al. (2011) collected 21 available methods to construct BIBDs.

There are a lot of pairs $\left(v,k\right),$ for which no construction method is known. For $v\le 50,$ these pairs can be found in Table 1 of Rasch, Teuscher, and Verdooren (2016). The smallest $v$ with an unknown non- trivial BIBD is $v=26.$ For $v\le 25,$ the smallest BIBDs are known, see Rasch et al. (2011). These BIBDs can be generated with the software package CADEMO, see Rasch et al. (1987) and Rasch, Guiard, and Nürnberg (1990). Rasch and Verdooren (2023) made these BIBDs publicly available.

When for a pair $\left(v,k\right)$ no specific construction methods are known, one is legitimated to try numerical search procedures. Numerical local search programs were developed. Most popular are the R- procedures “crossdes” (https://CRAN.R-project.org/package=crossdes) by Sailer (2005) and “ibd” (https://CRAN.R-project.org/package=ibd), basing on the work of Mandal, Gupta, and Parsad (2014a, 2014b) and Mandal (2015). Prestwich (2003) and Rueda, Cotta, and Fernandez (2009) have investigated other general numeric algorithms. The data of Prestwich (2003), ranging up to $v=31,$ were taken by the later authors as reference data to evaluate the efficiency of the new methods. As their authors reported, the programs and algorithms do not always produce valid BIBDs, insofar that the generated designs do not always hold the conditions on $r,$ $k,$ and $\lambda .$ Particularly, several BIBDs for $v\le 25$ cannot be found, although they exist. Furthermore, the convergence of “crossdes” and “ibd” is problematic for $vb>1000,$ i.e. for $v\ge 32.$

Due to these restrictions, “crossdes” and “ibd” are not useful to generate new BIBDs. For unknown BIBDs with $26\le v\le 31,$ $vb\ge 3380$ is valid and the programs do not converge. Therefore, for the generation of new BIBDs new concepts are needed.

In Appendix A, the recursive generation of BIBDs is introduced. It is shown, how to construct a BIBD for the pair $\left(v,k\right)$ from the BIBDs for the pairs $\left(v-1,k\right)$ and $\left(v-1,k-1\right).$ With the recursive method, relevant propositions about the existence of non- trivial BIBDs are found.

In Appendix B, a general search procedure is presented, which ensures the generation of valid BIBDs. The usefulness of the methods is summarized in section four.

2. The smallest admissible parameters

In this section, we present essential facts on the smallest admissible parameters for parameters $\left(v,k\right).$ In the literature, we did not find these results, although they are partly known, see the programs of Mandal (2015).

Theorem 1.

With $\left(b^{*},r^{*},{\lambda }^{*}\right)=\frac{\left(b,r,\lambda \right)}{\mathrm{GCD}\left(b,r,\lambda \right)},$ where $\left(b,r,\lambda \right)$ is an admissible triple for $\left(v,k\right),$ the smallest admissible triple is (5) $$\left(b\mathrm{’},\mathrm{ }r\mathrm{’},\mathrm{ }\lambda ’\right)=\mu \mathrm{ }\left(b^{\mathrm{*}},r^{\mathrm{*}},{\lambda }^{\mathrm{*}}\right),$$(5) where $\mu$ is the smallest integer with ${\mu b}^{*}\ge v.$ (GCD = Greatest Common Divisor; the division and multiplication have to be carried out element-wise.)

Proof

: From (2)(2) $$v r=b k$$(2) and (3)(3) $$\lambda \left(v-1\right)=r\left(k-1\right).$$(3) it follows (6) $$\frac{b}{r}=\frac{v}{k},\mathrm{ }\frac{r}{\lambda }=\frac{v-1}{k-1},\text{ and }\frac{b}{\lambda }=\frac{v\left(v-1\right)}{k\left(k-1\right)},$$(6) i.e. the ratios between the parameters b, r, $\lambda$ depend on v and k only. Let there be another set of admissible parameters $b^{*},$ $r^{*},$ and ${\lambda }^{*}.$ Then,

$\frac{b^{\mathrm{*}}}{r^{\mathrm{*}}}=\frac{b}{r},$ $\frac{r^{\mathrm{*}}}{{\lambda }^{\mathrm{*}}}=\frac{r}{\lambda }$ and $\frac{b^{\mathrm{*}}}{{\lambda }^{\mathrm{*}}}=\frac{b}{\lambda }$ or

$\frac{b^{\mathrm{*}}}{b}=\frac{r^{\mathrm{*}}}{r},\mathrm{ }\frac{r^{\mathrm{*}}}{r}=\frac{{\lambda }^{\mathrm{*}}}{\lambda }\mathrm{ }$$\mathrm{and} \frac{b^{\mathrm{*}}}{b}=\frac{{\lambda }^{\mathrm{*}}}{\lambda },$ i.e. (7) $$\frac{b^{\mathrm{*}}}{b}=\frac{r^{\mathrm{*}}}{r}=\frac{{\lambda }^{\mathrm{*}}}{\lambda }=c$$(7)

holds for some rational number $c=m/n$ with natural numbers m and n. Hence, $$b^{\mathrm{*}}=\frac{m}{n}\mathrm{ }b,\mathrm{ }\mathrm{ }{r}^{\mathrm{*}}=\frac{m}{n}\mathrm{ }r,\text{ and }{\lambda }^{\mathrm{*}}=\frac{m}{n}\mathrm{ }\lambda .$$

The smallest triple of natural numbers ($b^{*}, r^{*}, {\lambda }^{*}$) is obtained for $n=\mathrm{GCD}\left(b,r,\lambda \right)$ and $m=1.$ In case $b^{*}<v,$ the parameters do not satisfy condition (1)(1) $$b\ge v$$(1) . Therefore, they have to be multiplied with $\mu ,$ the smallest integer with ${\mu b}^{*}\ge v.$ □

Equation (5)(5) $$\left(b\mathrm{’},\mathrm{ }r\mathrm{’},\mathrm{ }\lambda ’\right)=\mu \mathrm{ }\left(b^{\mathrm{*}},r^{\mathrm{*}},{\lambda }^{\mathrm{*}}\right),$$(5) shows how to obtain the smallest admissible parameters from admissible ones. The parameters of the trivial BIBD, mentioned in the introduction, are admissible. Hence, they could be used as a starting point. It is however well known that there are smaller admissible parameters:

Eliminating $r$ of equation (2)(2) $$v r=b k$$(2) gives $r=\frac{bk}{v}.$ Eliminating $\lambda$ of equation (3)(3) $$\lambda \left(v-1\right)=r\left(k-1\right).$$(3) gives $\lambda =\frac{r(k-1)}{v-1}$ and substitution of $r$ results in $\lambda =\frac{bk(k-1)}{v\left(v-1\right)}.$ The parameters b, r, and $\lambda$ are admissible if b, r, and $\lambda$ are integers for arbitrary $v$ and $k$ and if $b\ge v$ holds. This clearly is guaranteed with $b=(v-1)v.$ Therefore, (8) $$b=(v-1)v,\mathrm{ }\mathrm{ }r=(v-1)k,\text{ and }\lambda =(k-1)k$$(8) are admissible parameters. The smallest admissible parameters are determined by equation (5)(5) $$\left(b\mathrm{’},\mathrm{ }r\mathrm{’},\mathrm{ }\lambda ’\right)=\mu \mathrm{ }\left(b^{\mathrm{*}},r^{\mathrm{*}},{\lambda }^{\mathrm{*}}\right),$$(5) .

Often, no BIBD exists for the smallest admissible parameters $\left(b’,\mathrm{ }r’,\mathrm{ }\lambda ’\right),$ e.g. for $\left(v,k\right)=\left(15, 5\right)$ and $\left(22, 7\right).$ One could think that the next admissible parameters would be $n\left(b’,\mathrm{ }r’,\mathrm{ }\lambda ’\right)$ with $n=2,3,\dots$ However, thinking so could hide the smallest BIBD. For example, for $\left(v,k\right)=\left(34, 12\right)$ we have via (8)(8) $$b=(v-1)v,\mathrm{ }\mathrm{ }r=(v-1)k,\text{ and }\lambda =(k-1)k$$(8) admissible parameters $\left(b,r,\lambda \right)=\left(33\times 34, 33\times 12, 11\times 12\right)$ and $\mathrm{GCD}\left(b,r,\lambda \right)=33\times 2.$ Hence, from theorem 1, we obtain $\left(b^{*},r^{*},{\lambda }^{*}\right)=\left(17, 6, 2\right)$ and because of $17<v=34,$ $\mu =2$ and $\left(b’,\mathrm{ }r’,\mathrm{ }\lambda ’\right)=\left(34, 12, 4\right).$ It is known that for these parameters no BIBD exists. The former idea would lead to the next potentially admissible parameters $2\left(34, 12, 4\right)=\left(68, 24, 8\right).$ However, with $\mu =3$ we obtain $\mu \left(b^{*},r^{*},{\lambda }^{*}\right)=\left(52, 18, 6\right).$ Theory shows, that for these parameters, a BIBD exists.

Theorem 2:

With $\left(b,r,\lambda \right)=\left(v\left(v-1\right),\left(v-1\right)k,\left(k-1\right)k\right)$ and $\left(b^{*},r^{*},{\lambda }^{*}\right)=\frac{\left(b,r,\lambda \right)}{\mathrm{GCD}\left(b,r,\lambda \right)},$ the ordered set of admissible parameters $v$ and $k$ is given by $\left(\mu +n\right) \frac{\left(b,r,\lambda \right)}{\mathrm{GCD}\left(b,r,\lambda \right)}$ with $n=0, 1, 2, \dots ,$ were $\mu$ is the smallest integer with ${\mu b}^{*}\ge v.$

3. For which v and k are the smallest admissible parameters identical with those of the trivial BIBD?

Theorem 3:

For all $3\le k\le v/2,$ with exception of $\left(v,k\right)=(8,3),$ an admissible triple $\left(b,r,\lambda \right)$ exists which is smaller than that of the trivial BIBD $\left(b_t,r_t,{\lambda }_t\right).$

Proof:

We investigate $b_t⋚b,$ where $b=(v-1)v$ belongs via (8)(8) $$b=(v-1)v,\mathrm{ }\mathrm{ }r=(v-1)k,\text{ and }\lambda =(k-1)k$$(8) to an admissible parameter triple. If $b_t>b$ holds, the admissible parameters are smaller than the trivial ones. If $b_t\le b$ holds, we check via theorem 1, whether there are admissible parameters smaller than $b_t$ and $b.$ If there are none, the trivial BIBD is elementary.

The relation $b_t/b=1$ is equivalent to (9) $$\frac{\left(k+1\right)\left(k+2\right)\cdots \left(v-2\right)}{\left(v-k\right)!}=1.$$(9)

In the numerator, we have v$-k-$2 factors. In the denominator, we have v$-k-$1 factors larger than one. Hence, with $m=v-k-2$ and $a=k+1,$ we are looking for all solutions of (10) $$\frac{{\prod }_{i=0}^{m-1}\left(a+i\right)}{\left(m+2\right)!}=1.$$(10)

For $m=1$ we get $a/6=1,$ i.e. $a=6$ and following (8)(8) $$b=(v-1)v,\mathrm{ }\mathrm{ }r=(v-1)k,\text{ and }\lambda =(k-1)k$$(8) we receive $k+1=v-2=6,$ i.e. $k=5$ and $v=8.$

For $m=2$ we get $a\left(a+1\right)/4!=1,$ which has no integer solution.

For $m=3$ we consider $a\left(a+1\right)\left(a+2\right)/5!,$ which is a monotone function in $a.$ For $a=3$ it is $a\left(a+1\right)\left(a+2\right)/5!=1/2.$ For $a=4$ it is one. For $a=5$ it is $7/4.$ Thus $a=4$ is the only solution with $k+1=a$ and $v-2=a+2,$ i.e. $k=3$ and $v=8.$

For $m>3$ and $a=3$ we obtain $\frac{3\times 4\times \cdots \times \left(m+2\right)}{\left(m+2\right)!}=\frac{1}{2}.$ For $m>3$ and $a=4$ we obtain $\frac{4\times 5\times \cdots \times \left(m+3\right)}{\left(m+2\right)!}=\frac{m+3}{6}.$ Since $m>3,$ this expression is larger than one. Due to monotonicity with respect to $a,$ there is no solution of equ. (9)(9) $$\frac{\left(k+1\right)\left(k+2\right)\cdots \left(v-2\right)}{\left(v-k\right)!}=1.$$(9) for $m>3.$

With the same technique it can be shown that for the designs with $\left(v,k\right)=$ (6, 3) and (7, 3), there are solutions with $b_t<v\left(v-1\right).$ However, it is known that existing BIBDs are smaller than the trivial designs. For $v=6$ and $k=3$ ($b_t=20,$ $r_t=10,$ ${\lambda }_t=4)$ the BIBD with $b=10,$ $r=5$ and $\lambda =2$ exists and for $v=7$ and $k=3$ ($b_t=35,$ $r_t=15,$ ${\lambda }_t=5),$ the BIBD with $b=7,$ $r=3$ and $\lambda =1$ exists. □

3.1. Conclusion

The equation (11) $$\mathrm{GCD}\left(b_t,r_t,{\lambda }_t\right)=\mathrm{GCD}\left(\left(\begin{array}{c}v\\ k\end{array}\right),\left(\begin{array}{c}v-1\\ k-1\end{array}\right),\left(\begin{array}{c}v-2\\ k-2\end{array}\right)\right)=1$$(11)

can hold only for $\left(v,k\right)=\left(8,3\right)$ and $\left(v,k\right)=\left(8,5\right).$

4. The generation of new BIBDs

For $v\le 25,$ the smallest BIBDs are known and reported by Rasch et al. (2011). For $v>25,$ there are many (v, k) pairs for which it is not known if non-trivial BIBDs exist, see, e.g. Table 1 of Rasch, Teuscher, and Verdooren (2016). Numerical programs like “crossdes” or “ibd” do not allow the generation of missing BIBDs for two reasons. The first one is that the algorithms often do not terminate for $v b>1000.$ The second reason is that they often do not generate valid BIBDs. To overcome the problems, two new approaches were used.

Table 1. Generated BIBDs. The parameter pairs $\left(v,k\right)$ comprise those pairs with $v\le 40$ and $k\le v/2,$ for which non- trivial BIBDs were not known. The lengths of the trivial BIBDs are denoted with $b_t.$ The smallest length satisfying the necessary conditions (1)(1) $$b\ge v$$(1) , (2)(2) $$v r=b k$$(2) , and (3)(3) $$\lambda \left(v-1\right)=r\left(k-1\right).$$(3) is denoted with $b\prime .$ The lengths of the BIBDs generated with two methods are denoted with $b.$ The factor $f$ in parentheses says that $b$ is the $f$- fold of $b\prime .$

$\mathit{v}$	$\mathit{k}$	$\mathit{b}$t	$\mathit{b}$' Smallest admissible	$\mathit{b}$ Recursive method		$\mathit{b}$ Numerical method
26	11	7726160	130	1040	(8)	520	(4)*
26	12	9657700	325	650	(2)	650	(2)*
28	11	21474180	756	19656	(26)	1512	(2)*
28	13	37442160	252	19656	(78)	1008	(4)*
30	11	54627300	870	24360	(28)	3480	(4)*
30	12	86493225	145	4060	(28)	290	(2)*
30	13	119759850	870	24360	(28)	1740	(2)*
30	14	145422675	435	12180	(28)	870	(2)*
33	10	92561040	528	32736	(62)	2112	(4)*
33	13	573166440	264	32736	(124)	1056	(4)*
33	14	818809200	528	32736	(62)	2112	(4)*
33	15	1037158320	176	10912	(62)	704	(4)*
34	10	131128140	187	46376	(248)	1496	(8)*
34	13	927983760	374	371008	(992)	2992	(8)*
34	14	1391975640	561	556512	(992)	4488	(8)*
34	15	1855967520	374	371008	(992)	2992	(8)*
34	16	2203961430	187	185504	(992)	2992	(16)
35	11	417225900	595	147560	(248)	4760	(8)
35	12	834451800	595	590240	(992)	2380	(4)
35	13	1476337800	595	590240	(992)	4760	(8)
35	15	3247943160	119	1298528	(10912)	1904	(16)
35	16	4059928950	595	6492640	(10912)	4760	(8)
36	11	600805296	252	1062432	(4216)	2016	(8)
36	13	2310789600	1260	21248640	(16864)	5040	(4)*
36	17	8597496600	1260	13749120	(10912)	10080	(8)*
38	10	472733756	703	12654	(18)	5624	(8)
38	11	1203322288	1406	50616	(36)	5624	(4)*
38	12	2707475148	703	25308	(36)	5624	(8)
38	13	5414950296	1406	50616	(36)	5624	(4)*
38	14	9669554100	703	25308	(36)	5624	(8)
38	15	15471286560	1406	50616	(36)	11248	(8)*
38	16	22239974430	703	25608	(36)	11248	(16)
38	17	28781143380	1406	50616	(36)	11248	(8)*
39	10	635745396	741	493506	(666)	5928	(8)
39	11	1676056044	741	493506	(666)	5928	(8)
39	12	3910797436	247	329004	(1332)	3952	(16)
39	14	15084504396	741	987012	(1332)	11856	(16)
39	15	25140840660	247	329004	(1332)	7904	(32)
39	16	37711260990	741	987012	(1332)	11856	(16)
39	17	51021117810	741	987012	(1332)	11856	(16)
39	18	62359143990	247	329004	(1332)	7904	(32)
40	11	2311801440	1560	19740240	(12654)	6240	(4)
40	17	88732378800	1560	39480480	(25308)	12480	(8)
40	18	113380261800	260	6580080	(25308)	8320	(32)
40	19	131282408400	520	692640	(1332)	8320	(16)

*Here, BIBDs for the smallest admissible parameters $b\prime$ were generated with the advanced numerical methods. Thus, $b=b\prime$ and $f=1$ was achieved.

The first one is a recursive method, which generates a BIBD for $\left(v,k\right)$ from the BIBDs for $\left(v-1,k\right)$ and $\left(v-1,k-1\right).$ The method is described in Appendix A. When a preceding BIBD is not known, it has to be generated from its predecessors. This may go back to the BIBDs for $v^{*},$ where $v^{*}$ is a prime power, i.e. a prime number or a power of a prime number. For such a $v^{*},$ the smallest BIBDs can be generated (at least theoretically; for large $v^{*},$ there might be practical numerical problems).

With the recursive method, BIBDs for parameter pairs $\left(v,k\right)$ with $26\le v\le 1000$ and $10\le k\le v/2$ were generated. From 243994 generated BIBDs, only 282 were trivial. This appeared particularly, when the distance between $v$ and $v^{*},$ the largest prime power smaller than $v,$ was large. The generation of a BIBD for $v=v^{*}+1,$ i.e. $v$ is the successor of a prime power, never led to a trivial BIBD. The same is true up to $v=v^{*}+6,$ i.e. trivial BIBD appeared for $v\ge v^{*}+7.$

The results are summarized by the following theorem.

Theorem 4:

For $26\le v\le 126,$ there exists a non- trivial BIBD for each pair $\left(v,k\right).$ For all pairs $\left(v,k\right)$ with $26\le v\le 1000$ and $k\ge 22,$ non- trivial BIBDs exist.

For $26\le v\le 40,$ the sizes of the BIBDs generated with the recursive method are presented in Table 1. The table documents those pairs $\left(v,k\right),$ for which the existence of non-trivial BIBDs was not known.

Table 1 shows that the BIBDs generated with the recursive method are considerable smaller than the trivial BIBDs, but mostly much larger than the smallest admissible designs.

In Appendix B, basic and advanced numerical methods are introduced. They were intended to reach three goals. The first goal was the generation of approximate BIBDs for parameters $v,$ $k,$ and the smallest admissible $b\prime .$ The generation is guaranteed not only for parameters with $vb\prime <1000,$ but for parameters with $vb\prime <100000.$ The second goal was to generate valid BIBDs with elementary methods. The third goal was the improvement of BIBDs with advanced methods, i.e. the generation of BIBDs smaller than those generated with the basic methods.

With the basic numerical methods, BIBDs were generated for the pairs $\left(v,k\right)$ presented in Table 1. With the exception for $\left(v,k\right)=\left(26,12\right),$ these BIBDs were smaller than those generated with the recursive method, partly drastically.

The application of the advanced numerical methods to the pairs $\left(v,k\right)$ of Table 1 is not completed yet. So far, for twenty two pairs it succeeded to generate BIBDs with $f=1$ and $b=b\prime ,$ i.e. the smallest possible ones (marked by an asterisk in the last column of the table). We are optimistic to find BIBDs with a maximum factor $f=2$ for the remaining pairs $\left(v,k\right)$ of Table 1. For example, the intermediate result for the pair $\left(v,k\right)=\left(39,15\right)$ is $f=4,$ while it was $f=32$ with the basic methods. With an enlarged effort, a further improvement is expected. Hence, the potential of the advanced methods is large but the needed running time is large as well.

5. Discussion

The new methods allowed a considerable progress in generating BIBDs. With the recursive method, non-trivial BIBDs were generated for $v\le 126.$ Since the generated BIBDs were often large, the recursive method is more of theoretical than of practical importance.

The basic numerical methods were applied to produce BIBDs for $26\le v\le 40$ whose existence was unknown so far. For several pairs $\left(v,k\right),$ the advanced numerical methods were applied. The generated BIBDs were smaller than those generated with the recursive method. For twenty two pairs $\left(v,k\right),$ a fully satisfying result was obtained: the generation of a BIBD for the smallest admissible parameters $\left(f=1, b=b\prime \right).$ For the other pairs, further improvements demand longwinded calculations.

As a starting point of our procedures, approximate BIBDs were generated for given $\left(v,k\right)$ and the smallest admissible number of blocks b′ “Approximate” means that the deviations of the actual ${\lambda }_{i,j}$ from the nominal $\lambda$ are minimized, while the $r$- and $k$- conditions are satisfied. As a rule, the obtained differences between ${\lambda }_{i,j}$ and $\lambda$ are −1, 0, or 1. Sometimes, the generated design is a valid BIBD, i.e. all obtained ${\lambda }_{i,j}$ are identical with $\lambda .$

With the basic tool 1, approximate BIBDs can be calculated also for inadmissible numbers of blocks $b.$ An example is given, that the results can compete with those of the program “ibd”. For $\left(v,k\right)=\left(8,4\right)$ and $b=8$ (with the smallest admissible parameter $b^{\prime }=14$) we obtained the incidence matrix $X$ and the concurrence matrix $C=XX\prime :$ $$X=\left[\begin{array}{cccccccc}1& 1& 0& 0& 0& 0& 1& 1\\ 1& 1& 0& 1& 1& 0& 0& 0\\ 0& 1& 1& 0& 1& 0& 1& 0\\ 1& 0& 1& 0& 1& 1& 0& 0\\ 0& 0& 0& 0& 1& 1& 1& 1\\ 0& 0& 1& 1& 0& 1& 1& 0\\ 0& 1& 0& 1& 0& 1& 0& 1\\ 1& 0& 1& 1& 0& 0& 0& 1\end{array}\right],\mathrm{ }\mathrm{ }C\left(X\right)=\left[\begin{array}{cccccccc}4& 2& 2& 1& 2& 1& 2& 2\\ 2& 4& 2& 2& 1& 1& 2& 2\\ 2& 2& 4& 2& 2& 2& 1& 1\\ 1& 2& 2& 4& 2& 2& 1& 2\\ 2& 1& 2& 2& 4& 2& 2& 1\\ 1& 1& 2& 2& 2& 4& 2& 2\\ 2& 2& 1& 1& 2& 2& 4& 2\\ 2& 2& 1& 2& 1& 2& 2& 4\end{array}\right].$$

The design is balanced with respect to $k$ and $r.$ The pairwise parameters ${\lambda }_{i,j}$ vary between one and two (with mean $\overline{\lambda }=12/7$). The A- and D- efficiency parameters were 0.991 and 0.996, respectively. The concurrence matrix obtained with “ibd” contained pairwise parameters ${\lambda }_{i,j}$ between zero and four. The parameters of A- and D-efficiency were 0.933 and 0.971, respectively. Hence, our result is clearly more balanced.

Ignoring the problem of large running times, there was a simple method to generate a BIBD for admissible parameters $\left(v,k,b,r,\lambda \right):$ One could generate all incidence matrices of dimension $v\times b$ with $r$ unities and $b-r$ zeros in each row and check each matrix, whether the $k$- and $\lambda$- conditions for a BIBD are fulfilled. (Without loss of generality, the first two rows and the first column could be fixed in advance: $x_{1,1}=\cdots =x_{1,r}=1,$ $x_{2,1}=\cdots =x_{2,\lambda }=1,$ $x_{2,r+1}=\cdots =x_{2,2r-\lambda }=1,$ $x_{1,3}=\cdots =x_{1,k}=1.$ The other entries were zero. The entries of the $v$-th row can be calculated by $x_{v,j}=k-{\sum }_{n=1}^{v-1}\mathrm{ }{x}_{n,j}.$) When an admissible matrix is found, it is the incidence matrix of a BIBD. Otherwise, applying theorem 2, the next larger admissible parameters could be attempted. However, this method is so time demanding, that it is not realizable even for small designs.

When there is no practicable strategy to solve the problem as a whole, sequential strategies are needed. With our methods, and with the programs “crossdes” and “ibd”, the strategy is the subsequent increasement of admissible rows of the incidence matrix. Often, the concrete problem aroused that at a certain stage, it was not possible to generate the next admissible row. Hopefully, theoretical results on this problem are obtainable.

One could call this problem the inverse BIBD problem: We consider row vectors of length $\beta$ with $\varrho$ unities and $\beta -\varrho$ zeros. How many such row vectors can be built, so that each pair of them has $\lambda$ unities in common (there are $\lambda$ columns with unities for both row vectors)?

Those parameters $\beta ,$ $\varrho ,$ and $\lambda$ are of interest which coincide with the smallest admissible parameters $b\prime ,$ $r\prime ,$ and $\lambda \prime$ for a BIBD with $\left(v,k\right).$ If a BIBD exists for these parameters, the answer on the formulated question would be: $v.$ If theoretical results (accompanied by a construction method) on the inverse BIBD problem would, for example, deliver $v-2,$ $v-3,$ or $v-4$ admissible row vectors, a doubling of the design and the use of our methods would probably lead to a BIBD. With our methods it even happened that with a doubling of a design, seven new admissible rows were generated.

Of particular interest is the inverse problem for $b=v\left(v-1\right),$ $r=k\left(v-1\right),$ and $\lambda =k\left(k-1\right).$ Often, these parameters are the smallest admissible ones (ten cases in Table 1). If for them BIBDs would exist, we had another case were the necessary conditions (1)(1) $$b\ge v$$(1) are sufficient. Furthermore, the conjecture of Rasch, Teuscher, and Verdooren (2016) could be proofed via theorem 3.

Generally, the numerical search for BIBDs is a very expensive procedure. On the other hand, a suggested design can be checked for being a valid BIBD by some matrix operations. This discrepancy reminds of the “P versus NP” problem, see Clapham and Nicholson (2014). Since the effort of optimization procedures with integer variables increases exponentially with the number of variables, the numerical generation of BIBDs is an excellent candidate for solving the “P versus NP” problem. A closer look of specialists is emphasized.

Generated BIBDs and the programs for the generation of approximate designs and BIBDs will be sent to interested readers.

Acknowledgement

The authors are indebted to the reviewers for valuable hints.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Appendix A.

The construction of a BIBD for (v, k) from the BIBDs with (v-1, k) and (v-1, k-1)

Let $X$ be the $v\times b$ incidence matrix, consisting of zeros and unities, of a BIBD with parameters $\left(v,k,b,r,\lambda \right).$ We order the columns of this matrix so that the first row starts with zeros and ends with unities: $$X=\left[\begin{array}{cc}0\mathrm{ }0\mathrm{ }0\mathrm{ }\dots \mathrm{ }0\mathrm{ }0\mathrm{ }0& 1\mathrm{ }1\mathrm{ }1\mathrm{ }\dots \mathrm{ }1\mathrm{ }1\mathrm{ }1\\ X_1& X_2\end{array}\right],$$ where $X_1$ and $X_2$ are certain zero- one matrices. Since the number of unities in the first row is r and the number of zeros is therefore $b-r,$ $X_1$ has dimension $\left(v-1\right)\times \left(b-r\right)$ and $X_2$ has dimension $\left(v-1\right)\times r.$

We now assume, that $X_1$ and $X_2$ are BIBDs. Since the sum of column elements in $X$ is k, the sum of column elements in $X_1$ is also k, while it is $k-1$ in $X_2.$ Hence, $X_1$ and $X_2$ have parameters $\left(v-1,k,b_1=b-r,r_1,{\lambda }_1\right)$ and $\left(v-1,k-1,b_2=r,r_2,{\lambda }_2\right),$ respectively.

Then, the parameters of the BIBDs are related by the following conditions: $$b=b_1+b_2$$ (A1) $$r=r_1+r_2 \mathrm{and}$$(A1) $$\lambda ={\lambda }_1+{\lambda }_2.$$

Example A1

: Consider the smallest BIBD for v = 8 and k = 4. Following Rasch et al. (2011), it has parameters $\left(8,4,14,7,3\right).$ An ordered (with respect to the first row) incidence matrix is, e.g. $$X=\left[\begin{array}{cccccccccccccc}0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1\\ 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0& 1& 1& 1\\ 1& 1& 0& 0& 1& 1& 0& 0& 0& 1& 1& 0& 0& 1\\ 1& 0& 1& 0& 1& 0& 1& 0& 1& 0& 1& 0& 1& 0\\ 1& 0& 0& 1& 0& 1& 1& 0& 1& 1& 0& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 0& 1& 1& 0& 0& 0& 0& 1\\ 0& 1& 0& 1& 1& 0& 1& 1& 0& 1& 0& 0& 1& 0\\ 0& 1& 1& 0& 0& 1& 1& 1& 0& 0& 1& 1& 0& 0\end{array}\right].$$

Ignoring the first row, the matrix X can be partitioned into matrices X₁ and X₂. The matrices $$X_1=\left[\begin{array}{ccccccc}1& 1& 1& 1& 0& 0& 0\\ 1& 1& 0& 0& 1& 1& 0\\ 1& 0& 1& 0& 1& 0& 1\\ 1& 0& 0& 1& 0& 1& 1\\ 0& 0& 1& 1& 1& 1& 0\\ 0& 1& 0& 1& 1& 0& 1\\ 0& 1& 1& 0& 0& 1& 1\end{array}\right]\text{ and }{X}_2=\left[\begin{array}{ccccccc}0& 0& 0& 0& 1& 1& 1\\ 0& 0& 1& 1& 0& 0& 1\\ 0& 1& 0& 1& 0& 1& 0\\ 0& 1& 1& 0& 1& 0& 0\\ 1& 1& 0& 0& 0& 0& 1\\ 1& 0& 1& 0& 0& 1& 0\\ 1& 0& 0& 1& 1& 0& 0\end{array}\right]$$ are BIBDs with parameters $\left(7,4,7,4,2\right)$ and $\left(7,3,7,3,1\right),$ respectively (the sum of row elements is $r_i,$ the sum of column elements is $k_i,$ and each pair of rows has ${\lambda }_i$ unities in common). Particularly, $X_1$ is the complementary design to $X_2$ (zeros and unities are interchanged).

Now, we change the viewpoint. With given BIBDs $X_1$ with $\left(v-1,k,b_1,r_1,{\lambda }_1\right)$ and $X_2$ with $\left(v-1,k-1,b_2,r_2,{\lambda }_2\right)$ (not necessarily the smallest ones) we construct a BIBD $X$ with $\left(v,k,b,r,\lambda \right)$ in the following manner: $$X=\left[\begin{array}{cc}0\mathrm{ }0\mathrm{ }0\mathrm{ }\dots \mathrm{ }0\mathrm{ }0\mathrm{ }0& 1\mathrm{ }1\mathrm{ }1\mathrm{ }\dots \mathrm{ }1\mathrm{ }1\mathrm{ }1\\ X_1\cdots X_1& X_2\cdots X_2\end{array}\right],$$ where the design $X_1$ appears $n_1$ times and the design $X_2$ appears $n_2$ times. The parameters of $X$ result according to $$b=n_1\mathrm{ }{b}_1+n_2\mathrm{ }{b}_2,$$ (A2) $$r=n_1\mathrm{ }{r}_1+{n_2\mathrm{ }r}_2,$$(A2) $$\lambda =n_1\mathrm{ }{\lambda }_1+n_2\mathrm{ }{\lambda }_2.$$

From the first row, we obtain the condition $r={n_2 b}_2,$ since there are ${n_2 b}_2$ unities. Furthermore, the first row has unities in common with other rows only on the right-hand side, namely ${n_2 r}_2,$ i.e. $\lambda ={n_2 r}_2.$ Hence there are to solve two equations: ${n_2 b}_2=n_1 r_1+{n_2 r}_2$ and ${n_2 r}_2=n_1 {\lambda }_1+n_2 {\lambda }_2.$ Setting $q=n_1/n_2,$ this gives (A3) $$b_2-r_2=q\mathrm{ }{r}_1\mathrm{ }\mathrm{and}$$(A3) $$r_2-{\lambda }_2=q\mathrm{ }{\lambda }_1.$$

From (A1)(A1) $$r=r_1+r_2 \mathrm{and}$$(A1) , (2)(2) $$v r=b k$$(2) , $v_1=v_2=v-1,$ and $k=k_1=k_2+1$ we get (A4) $$q=\frac{b_2-r_2}{r_1}=\frac{b_2-\frac{b_2{k}_2}{v_2}}{\frac{b_1{k}_1}{v_1}}=\frac{b_2\left(v-1\right)-b_2{k}_2}{b_1{k}_1}=\frac{b_2\left(v-1-k+1\right)}{b_{1}k}=\frac{b_2\left(v-k\right)}{b_1\mathrm{ }k}.$$(A4)

Having canceled out common factors of the numerator and denominator of q, we obtain $n_1=\mathrm{numerator}\left(q\right)$ and $n_2=\mathrm{denominator}\left(q\right).$

Example A2

: Consider BIBDs for $v=26.$ From Table 1 of Rasch, Teuscher, and Verdooren (2016), the existence of non-trivial BIBD is unknown for $k=11$ and $k=12.$ Available software like “crossdes” and “ibd” fail to generate BIBDs for these parameters. Since the smallest BIBDs for $v=25$ are known (Table 6.1 of Rasch et al. (2011)), the recursive method can be applied. Afterwards it can be checked, whether the resulting BIBDs are trivial or shorter.

For the construction of the BIBD for $v=26$ and $k=11$ we use the BIBDs $\left(25,11,300,132,55\right)$ and $\left(25,10,40,16,6\right),$ i.e. $b_1=300$ and $b_2=40.$ Following (A6) we obtain $q=2/11$ and $b=1040,$ shown within Table A1.

Table A1. The construction of BIBDs for $v=26$ and $k=11$ and $12.$ The length of the smallest admissible design is $b\prime .$

k	$b_1$	$b_2$	q	$n_1$	$n_2$	$b$	$b\prime$
11	300	40	$\frac{40\times 15}{300\times 11}=\frac{2}{11}$	2	11	$2\times 300+11\times 40=1040$	$130$
12	50	300	$\frac{300\times 14}{50\times 12}=\frac{7}{1}$	7	1	$7\times 50+1\times 300=650$	$325$

For the construction of the BIBD for $v=26$ and $k=12$ we use the BIBDs $\left(25,12,50,24,11\right)$ and $\left(25,11,300,132,55\right),$ i.e. $b_1=50$ and $b_2=300.$ Following (A6) we obtain $q=7/1$ and $b=650.$

The constructed designs have parameters $\left(26,11,1040,440,176\right)$ and $\left(26,12,650,300,132\right).$ The first one is the eight-fold of the smallest admissible design (with length b’) and the second one is the two-fold of the smallest admissible design. Both are much shorter than the trivial BIBDs.

The described construction of a BIBD for given $v$ and $k$ assumes the availability of BIBDs for $\left(v-1,k\right)$ and $\left(v-1,k-1\right).$ If this assumption is not fulfilled, the method is not directly applicable. Then, BIBDs for $v-2$ are required, i.e. the method has to be used recursively. Fortunately, we have not to go backwards too much, since we may start with $v^{*},$ a prime number or a power of a prime number. With such a $v=v^{*},$ BIBDs can always be constructed, e.g. via method 6 of Rasch et al. (2011). The lengths $b$ of such BIBDs are at most $b=v\left(v-1\right).$ This length was used in the recursive procedure. Beside the BIBDs for a prime power $v^{*},$ the BIBDs for $k=7, 8,$ and 9 are taken as known, following the theory of Abel and Greig (1998), Abel, Bluskov, and Greig (2001), and Abel, Bluskov, and Greig (2004).

Appendix B:

Basic and advanced numerical methods

Advanced methods are introduced, which allow the generation of shorter BIBDs than generated with the basic program.

The basic numerical method

We describe the numerical method to generate a BIBD by means of an example: $\left(v,k\right)=\left(15,5\right).$ We start with an incidence matrix $X$ for the smallest admissible design, which has parameters $\left(v,k,b,r,\lambda \right)=\left(15,5,21,7,2\right).$ $X$ has to satisfies the $r-$ and $k-$condition. Such a matrix is simply constructed: (B1) $$X=\left(\begin{array}{ccccccccccccccccccccc}1& 1& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 1& 1& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 1& 1& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 1& 1& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 1& 1& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1\end{array}\right)$$(B1)

As it can be seen, the sums of row elements are seven and the sums of column elements are five. The $\lambda$- condition was not in the focus at this stage.

Definition B1

: Let $b$ and $r$ be admissible parameters for given $\left(v,k\right).$ Then, a $v\times b$ incidence matrix $X$ (consisting of zeros and unities) is called a design, when the sum of row elements is $r$ for each row and when the sum of column elements is $k$ for each column.

The appropriateness of design $X$ is measured by the concurrence matrix $C:$ (B2) $$C\left(X\right)=XX\prime -\lambda \mathrm{ }\mathbf{1}.$$(B2)

If $X$ were a BIBD, we had (B3) $$XX\prime =\left(\begin{array}{ccccc}r& \lambda & \cdots & \lambda & \lambda \\ \lambda & r& & ⋮& ⋮\\ \lambda & \lambda & \ddots & \lambda & \lambda \\ ⋮& ⋮& & r& \lambda \\ \lambda & \lambda & \cdots & \lambda & r\end{array}\right)\text{ and }C\left(X\right)=\left(\begin{array}{ccccc}r-\lambda & \mathrm{0}& \cdots & 0& \mathrm{0}\\ \mathrm{0}& r-\lambda & & ⋮& ⋮\\ 0& \mathrm{0}& \ddots & 0& \mathrm{0}\\ ⋮& ⋮& & r-\lambda & \mathrm{0}\\ 0& \mathrm{0}& \cdots & \mathrm{0}& r-\lambda \end{array}\right).$$(B3)

For the design (B1)(B1) $$X=\left(\begin{array}{ccccccccccccccccccccc}1& 1& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 1& 1& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 1& 1& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 1& 1& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 1& 1& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1\end{array}\right)$$(B1) , the concurrence matrix is (B4) $$C\left(X\right)=\left(\begin{array}{ccccccccccccccc}5& 5& 5& 5& 5& -2& -2& -2& -2& -2& -2& -2& -2& -2& -2\\ 5& 5& 5& 5& 5& -2& -2& -2& -2& -2& -2& -2& -2& -2& -2\\ 5& 5& 5& 5& 5& -2& -2& -2& -2& -2& -2& -2& -2& -2& -2\\ 5& 5& 5& 5& 5& -2& -2& -2& -2& -2& -2& -2& -2& -2& -2\\ 5& 5& 5& 5& 5& -2& -2& -2& -2& -2& -2& -2& -2& -2& -2\\ -2& -2& -2& -2& -2& 5& 5& 5& 5& 5& -2& -2& -2& -2& -2\\ -2& -2& -2& -2& -2& 5& 5& 5& 5& 5& -2& -2& -2& -2& -2\\ -2& -2& -2& -2& -2& 5& 5& 5& 5& 5& -2& -2& -2& -2& -2\\ -2& -2& -2& -2& -2& 5& 5& 5& 5& 5& -2& -2& -2& -2& -2\\ -2& -2& -2& -2& -2& 5& 5& 5& 5& 5& -2& -2& -2& -2& -2\\ -2& -2& -2& -2& -2& -2& -2& -2& -2& -2& 5& 5& 5& 5& 5\\ -2& -2& -2& -2& -2& -2& -2& -2& -2& -2& 5& 5& 5& 5& 5\\ -2& -2& -2& -2& -2& -2& -2& -2& -2& -2& 5& 5& 5& 5& 5\\ -2& -2& -2& -2& -2& -2& -2& -2& -2& -2& 5& 5& 5& 5& 5\\ -2& -2& -2& -2& -2& -2& -2& -2& -2& -2& 5& 5& 5& 5& 5\end{array}\right)$$(B4) with elements $c_{i,j}.$ The diagonal elements are admissibly $c_{i,i}=r-\lambda =5.$ The non- diagonal elements are all different from zero. Since $c_{i,j}^2$ is a measure of the deviation from zero, the appropriateness of a design $X$ can be quantified by the sum of squared deviations (B5) $$P\left(C\left(X\right)\right)={\sum }_{i=2}^v{\sum }_{j=1}^{i-1}{c}_{i,j}^2,$$(B5)

which is the penalty function. The general aim of an algorithm is to suggest changes within $X$ and to check whether a change decreases the penalty function.

Note that due to the symmetry of $C\left(X\right),$ only elements below the diagonal found entrance into $P\left(C\left(X\right)\right).$ Hence, there is no need to change row one of $X.$ It is therefore called admissible.

Definition B2

: Row $\mathit{i}\ge \mathbf{2}$ of design $X$ is called to be admissible, if $c_{i,1}=c_{i,2}=\cdots =c_{i,N_a-1}=0$ holds, where $N_a$ is the number of admissible rows$, 1\le N_a\le v.$

For the initial design (B1)(B1) $$X=\left(\begin{array}{ccccccccccccccccccccc}1& 1& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 1& 1& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 1& 1& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 1& 1& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 1& 1& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1\end{array}\right)$$(B1) , we have $N_a=1.$ The aim is to increase $N_a.$

The change of one entry, say $x_{i,j},$ of $X$ (substitution of a “1” by a “0”, or vice versa) would lead to a violation of the $r-$ and $k-$ conditions. We allow only changes, which do not violate these conditions. Therefore, a second row, $i\prime ,$ and a second column, $j\prime ,$ have to be taken into account.

We are ready now to define the first basic algorithm. Often, it has to be applied several times. Then, the parameters will differ (with exception of $v$ and $k$). When the algorithm is applied the first time, we have $b=b\prime ,$ $r=r^{\prime },$ $\lambda =\lambda \prime ,$ and $N_a=1.$

Basic tool 1

For a pair $\left(i,i\prime \right)$ of rows of design $X,$ $N_a<i<i\prime \le v,$ determine the set $M_1$ of the column numbers $j,$ for which $x_{i,j}=1$ and $x_{i\prime ,j}=0$ hold. Then, determine the set $M_2$ of the column numbers $j\prime ,$ for which $x_{i,j\prime }=0$ and $x_{i\prime ,j\prime }=1$ hold. (The number of elements of $M_1$ and $M_2$ is $r-c_{i,i\prime }-\lambda .$) Then, with $\tilde{X}=X,$ put ${\tilde{x}}_{i,j}=0,$ ${\tilde{x}}_{i,j\prime }=1,$ ${\tilde{x}}_{i\prime ,j}=1,$ and ${\tilde{x}}_{i\prime ,j\prime }=0$ for a pair $\left(j,j\prime \right),$ $j\in M_1$ and $j\prime \in M_2.$ With such $\tilde{X},$ determine $C\left(\tilde{X}\right)=\tilde{X}\tilde{X}\prime -\lambda 1$ and calculate the penalty parameter $P,$ (B6) $$P\left(C\left(\tilde{X}\right)\right)={\sum }_{i=N_a+1}^v{\sum }_{j=1}^{i-1}\left[\begin{array}{c}1000\text{ if }i=N_a+1\\ \mathrm{ }1\text{ if }i\ne N_a+1\mathrm{ }\end{array}\right]c_{i,j}^2.$$(B6)

If $P\left(C\left(\tilde{X}\right)\right)$ is smaller than $P\left(C\left(X\right)\right),$ set $X=\tilde{X}.$ In case $c_{N_a+1,1}=c_{N_a+1,2}=\cdots =c_{N_a+1,N_a}=0,$ $N_a$ is increased by one. The algorithm is applied to all pairs $\left(i,i\prime \right)$ and $\left(j,j\prime \right).$ The algorithm terminates, when no further reduction of the penalty $P$ can be obtained. □

Ideally, the basic tool 1 terminates with penalty zero. Then, a BIBD was obtained. If the basic tool 1 did not terminate with penalty zero, it is finalized it by another run with penalty (B5)(B5) $$P\left(C\left(X\right)\right)={\sum }_{i=2}^v{\sum }_{j=1}^{i-1}{c}_{i,j}^2,$$(B5) . The resulting design $X$ can be taken as an approximation of a BIBD. If one wants to come near to C- or D- optimality of the design, one can use appropriate penalty terms.

However, the aim is to generate a BIBD. When the basic tool 1 was not successful, we have to enlarge the dimensions of the task by setting $\left(b,r,\lambda \right):=2\left(b\prime ,r\prime ,\lambda \prime \right).$ With our example, the concurrence matrix with the lowest penalty was (B7) $$C\left(X\right)=\left(\begin{array}{ccccccccccccccc}5& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& -1\\ 0& 5& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 5& 0& 0& 0& 0& 0& 0& 0& 0& 0& -1& 1& 0\\ 0& 0& 0& 5& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 5& 0& 0& 0& 0& 0& 0& 0& 0& -1& 1\\ 0& 0& 0& 0& 0& 5& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 5& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 5& 0& 0& 0& 0& 0& -1& 1\\ 0& 0& 0& 0& 0& 0& 0& 0& 5& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 5& 0& 0& 1& -1& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 5& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 5& 0& 1& -1\\ 0& 0& -1& 0& 0& 0& 0& 0& 0& 1& 0& 0& 5& 0& 0\\ 1& 0& 1& 0& -1& 0& 0& -1& 0& -1& 0& 1& 0& 5& 0\\ -1& 0& 0& 0& 1& 0& 0& 1& 0& 0& 0& -1& 0& 0& 5\end{array}\right)$$(B7)

We compose a new design $X\prime$ by taking the design $X$ and hang on another design $X_2$ of length $b\prime ,$ i.e. the row vectors of $X$ are prolonged by the row vectors of $X_2.$ We abbreviate this merging with $X^{\prime }=\left[X,X_2\right].$ The resulting concurrence matrix is $C\left(X\prime \right)=C\left(X\right)+C\left(X_2\right),$ since the scalar products are additive.

Then the question is, how to choose $X_2.$ Taking $X_2=X$ has the advantage, that a zero in $C\left(X\right)$ becomes also a zero in $C\left(X\prime \right),$ i.e. rows 1 to $N_a$ of $X\prime$ are admissible. The disadvantage is that a non-zero in $C\left(X\right)$ becomes twice the non- zero in $C\left(X\prime \right).$ In example (B7)(B7) $$C\left(X\right)=\left(\begin{array}{ccccccccccccccc}5& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& -1\\ 0& 5& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 5& 0& 0& 0& 0& 0& 0& 0& 0& 0& -1& 1& 0\\ 0& 0& 0& 5& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 5& 0& 0& 0& 0& 0& 0& 0& 0& -1& 1\\ 0& 0& 0& 0& 0& 5& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 5& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 5& 0& 0& 0& 0& 0& -1& 1\\ 0& 0& 0& 0& 0& 0& 0& 0& 5& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 5& 0& 0& 1& -1& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 5& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 5& 0& 1& -1\\ 0& 0& -1& 0& 0& 0& 0& 0& 0& 1& 0& 0& 5& 0& 0\\ 1& 0& 1& 0& -1& 0& 0& -1& 0& -1& 0& 1& 0& 5& 0\\ -1& 0& 0& 0& 1& 0& 0& 1& 0& 0& 0& -1& 0& 0& 5\end{array}\right)$$(B7) we have $c_{13,3}\left(X\right)=-1.$ To obtain a zero in $C\left(X\prime \right),$ i.e. $c_{13,3}\left(X\prime \right)=0,$ we need a modification of $X_2$ so that $c_{13,3}\left(X_2\right)=1.$ Furthermore, we have $c_{13,10}\left(X\right)=1.$ To obtain $c_{13,10}\left(X\prime \right)=0,$ we need $c_{13,10}\left(X_2\right)=-1.$ This modification is reached when $X_2$ is taken as $X,$ but with exchanged rows 3 and 10. Then, $C\left(X_2\right)$ results from $C\left(X\right)$ by exchanging rows 3 and 10 and as well columns 3 and 10. The concurrence matrix of $X\prime$ is then (B8) $$C\left(X\prime \right)=\left(\begin{array}{ccccccccccccccc}10& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 2& -2\\ 0& 10& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 10& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 10& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 10& 0& 0& 0& 0& 0& 0& 0& 0& -2& 2\\ 0& 0& 0& 0& 0& 10& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 10& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 10& 0& 0& 0& 0& 0& -2& 2\\ 0& 0& 0& 0& 0& 0& 0& 0& 10& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 10& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 10& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 10& 0& 2& -2\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 10& 0& 0\\ 2& 0& 0& 0& -2& 0& 0& -2& 0& 0& 0& 2& 0& 10& 0\\ -2& 0& 0& 0& 2& 0& 0& 2& 0& 0& 0& -2& 0& 0& 10\end{array}\right)$$(B8)

Incidentally, by the exchange of rows 3 and 10 in $X_2,$ two more zeros in $C\left(X\prime \right)$ were generated: $c_{14,3}\left(X\prime \right)=0$ and $c_{14,10}\left(X\prime \right)=0.$ This resulted from $c_{14,3}\left(X\right)=-c_{14,10}\left(X\right).$

Visiting the concurrence matrix (B8)(B8) $$C\left(X\prime \right)=\left(\begin{array}{ccccccccccccccc}10& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 2& -2\\ 0& 10& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 10& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 10& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 10& 0& 0& 0& 0& 0& 0& 0& 0& -2& 2\\ 0& 0& 0& 0& 0& 10& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 10& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 10& 0& 0& 0& 0& 0& -2& 2\\ 0& 0& 0& 0& 0& 0& 0& 0& 10& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 10& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 10& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 10& 0& 2& -2\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 10& 0& 0\\ 2& 0& 0& 0& -2& 0& 0& -2& 0& 0& 0& 2& 0& 10& 0\\ -2& 0& 0& 0& 2& 0& 0& 2& 0& 0& 0& -2& 0& 0& 10\end{array}\right)$$(B8) , one can see, that additionally exchanging rows 1 and 5 of $X_2$ will lead to $c_{14,1}\left(X\prime \right)=0,$ $c_{15,1}\left(X\prime \right)=0,$ $c_{14,5}\left(X\prime \right)=0,$ and $c_{15,5}\left(X\prime \right)=0.$ When we still exchange rows 8 and 12 of $X_2,$ we obtained a BIBD $X$ by defining $X=\left[X,X_2\right].$

Basic tool 2

With the doubling of the design, as much as possible new admissible rows are generated.

Unfortunately, basic tool 1 does not often terminate with a comfortable situation given with the example (B7)(B7) $$C\left(X\right)=\left(\begin{array}{ccccccccccccccc}5& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& -1\\ 0& 5& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 5& 0& 0& 0& 0& 0& 0& 0& 0& 0& -1& 1& 0\\ 0& 0& 0& 5& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 5& 0& 0& 0& 0& 0& 0& 0& 0& -1& 1\\ 0& 0& 0& 0& 0& 5& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 5& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 5& 0& 0& 0& 0& 0& -1& 1\\ 0& 0& 0& 0& 0& 0& 0& 0& 5& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 5& 0& 0& 1& -1& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 5& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 5& 0& 1& -1\\ 0& 0& -1& 0& 0& 0& 0& 0& 0& 1& 0& 0& 5& 0& 0\\ 1& 0& 1& 0& -1& 0& 0& -1& 0& -1& 0& 1& 0& 5& 0\\ -1& 0& 0& 0& 1& 0& 0& 1& 0& 0& 0& -1& 0& 0& 5\end{array}\right)$$(B7) . Such uncomfortable situation is given, when ${\sum }_{j=1}^{N_a}{c}_{N_a+1,j}\ne 0.$ Then, with the basic tool 1 but with an appropriate penalty term, row $N_a+1$ of $X$ must be brought into a shape, that pairs $\left(j,j\prime \right)$ ensure $c_{N_a+1,j}\left(X\right)=-c_{N_a+1,j\prime }\left(X\right).$ The following two theorems are useful in this context.

Theorem B1

: Let $X$ be a design. Then, the sum of all non- diagonal elements of each row and each column of $C\left(X\right)$ is zero.

Proof:

Without loss of generality, we consider row one (for row $i\in \left\{2,\dots ,v\right\},$ rows $i$ and one are interchanged). The assertion is then ${\sum }_{j=2}^v{c}_{1,j}=0.$ By construction we have $${\sum }_{j=2}^v{c}_{1,j}={\sum }_{j=2}^v\left({\sum }_{l=1}^b{x}_{1,l}{x}_{j,l}-\lambda \right)={\sum }_{j=2}^v{\sum }_{l=1}^b{x}_{1,l}{x}_{j,l}-\left(v-1\right)\lambda =$$ $$={\sum }_{l=1}^b{\sum }_{\mathrm{j}=2}^v{x}_{1,l}{x}_{j,l}-\left(v-1\right)\lambda ={\sum }_{l=1}^b{x}_{1,l}{\sum }_{j=2}^v{x}_{j,l}-\left(v-1\right)\lambda =$$ $$=\sum _{l:x_{1,l}=0}{x}_{1,l}{\sum }_{j=2}^v{x}_{j,l}+\sum _{l:x_{1,l}=1}{x}_{1,l}{\sum }_{j=2}^v{x}_{j,l}-\left(v-1\right)\lambda$$

The sums ${\sum }_{j=1}^v{x}_{j,l}$ of the column elements equal $k.$ Therefore, the sum ${\sum }_{j=2}^v{x}_{j,l}$ is $k,$ if $x_{1,l}=0$ and $k-1,$ if $x_{1,l}=1.$ There are $r$ columns with $x_{1,l}=1.$ Thus, ${\sum }_{j=2}^v{c}_{1,j}=r\left(k-1\right)-\left(v-1\right)\lambda$ holds. Since $r\left(k-1\right)=\left(v-1\right)\lambda$ is a necessary condition for the existence of a BIBD and we apply only admissible parameters, the assertion is proofed. Due to symmetry of $C,$ the result applies also to the columns.□

Theorem B2

: If solely the two last rows of $X$ are not admissible (i.e. $N_a=v-2$) and if $c_{v-1,j}\in \left\{-1, 0, 1\right\}$ holds for $j=1,\dots ,N_a,$ then one can immediately define a design $X_2$ so that $X^{\prime }=\left[X,X_2\right]$ is a BIBD.

Proof:

Following theorem B1 applied to columns $j=1,\dots ,v-2,$ $c_{v-1,j}=-c_{v,j}$ holds. Thus, the last two rows of the concurrence matrix $C$ have the following form: (B9) $$\begin{array}{ccccccc}\text{Row}& & & & \text{Column}& & \\ & 1& 2& \dots & v-2& v-1& v\\ v-1& c_{v-1,1}& c_{v-1,2}& \dots & c_{v-1,v-2}& r-\lambda & c_{v-1,v}\\ v& -c_{v-1,1}& -c_{v-1,2}& \dots & -c_{v-1,v-2}& c_{v,v-1}& r-\lambda \end{array}$$(B9)

From theorem B1 we have ${\sum }_{j=1}^{v-2}{c}_{v-1,j}+c_{v-1,v}=0$ for row $v-1$ and ${\sum }_{j=1}^{v-2}\left(-c_{v-1,j}\right)+c_{v,v-1}=0$ for row $v.$ Adding both equalities and regarding symmetry of $C$ we get $2c_{v-1,v}=0,$ i.e. $c_{v-1,v}=0.$

Assume furthermore, that $c_{v-1,j}\in \left\{-1,\mathrm{ }0,\mathrm{ }1\right\}$ holds. Then, $0={\sum }_{j=1}^{v-2}{c}_{v-1,j}=\sum _{j:c_{v-1,j}=-1}{c}_{v-1,j}+\sum _{j:c_{v-1,j}=1}{c}_{v-1,j}=-\#\left(j:\mathrm{ }{c}_{v-1,j}=-1\right)+\#\left(j:\mathrm{ }{c}_{v-1,j}=1\right).$ This means, that in rows $v-1$ and $v,$ there is the same number, say $n,$ of “-1” and “1”. Therefore, we may create $n$ pairs $\left(j,\mathrm{ }j\prime \right)$ of columns, so that $c_{v-1,j}=1$ and $c_{v-1,j\prime }=-1.$ The design $X_2$ is generated from design $X$ by exchanging all pairs $\left(j,\mathrm{ }j\prime \right)$ of rows. □

Conclusion B1

If $N_a=v-1$ rows of the design $X$ are admissible, the $v$-th row is also admissible.

When the basic tool 2 ends with $N_a=v$ admissible rows, a BIBD was generated. If not, the basic tool 1 is started again with $b:=2b,$ $r:=2r,$ $\lambda :=2\lambda ,$ and the actual $N_a.$

Advanced numerical methods

The basic numerical program often does not generate the smallest possible BIBDs. To obtain smaller BIBDs advanced methods are necessary. The improvements of the basic tools were caused by the exchange of four entries of a design $X,$ which were the points of intersection of two rows and two columns. Advanced methods have to offer more than four changes. A straightforward approach would be to try, e.g. two rows and four columns. We experienced that the gain of such approaches was not substantial enough to compensate the increase of running time. Therefore, other approaches were used.

A view on the concurrence matrix (B7)(B7) $$C\left(X\right)=\left(\begin{array}{ccccccccccccccc}5& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& -1\\ 0& 5& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 5& 0& 0& 0& 0& 0& 0& 0& 0& 0& -1& 1& 0\\ 0& 0& 0& 5& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 5& 0& 0& 0& 0& 0& 0& 0& 0& -1& 1\\ 0& 0& 0& 0& 0& 5& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 5& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 5& 0& 0& 0& 0& 0& -1& 1\\ 0& 0& 0& 0& 0& 0& 0& 0& 5& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 5& 0& 0& 1& -1& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 5& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 5& 0& 1& -1\\ 0& 0& -1& 0& 0& 0& 0& 0& 0& 1& 0& 0& 5& 0& 0\\ 1& 0& 1& 0& -1& 0& 0& -1& 0& -1& 0& 1& 0& 5& 0\\ -1& 0& 0& 0& 1& 0& 0& 1& 0& 0& 0& -1& 0& 0& 5\end{array}\right)$$(B7) shows, that the non- diagonal elements of columns 2, 4, 6, 7, 9, and 11 are zero. We call them admissible columns, although they are caused by those rows of design $X$ which satisfy the $\lambda$- condition with respect to all other rows. We reorder the rows of $X,$ so that rows 2, 4, 6, 7, 9, and 11 are the first six rows of $X$ afterwards.

Definition

$N_c, 0\le N_c\le N_a\le v,$ is called the number of admissible columns of the concurrence matrix $C\left(X\right),$ if $c_{N_a+1,i}=c_{N_a+2,i}=\cdots =c_{v,i}=0$ holds for $1\le i\le N_c.$

Generally, the number of admissible columns $N_c$ can be increased by another run of the basic tool 1 with the penalty (B10) $$P\left(C\left(\tilde{X}\right)\right)={\sum }_{i=N_a+1}^v{\sum }_{j=1}^{i-1}\left[\begin{array}{c}{10}^6\text{ if }j<N_c+1\\ {10}^3\text{ if }j=N_c+1\\ \mathrm{ }1\text{ if }j>N_c+1\end{array}\right]c_{i,j}^2.$$(B10)

In case there was no admissible column, $N_c=0$ has to be taken.

We may now modify the basic tool 1 to improve the design $X$ under the constraints that the first $N_c$ columns of $C\left(X\right)$ remain admissible. Analogously to the basic tool 1 we determine the sets $M_1$ and $M_2$ for rows $i$ and $i\prime$ of $X.$ The number of elements of $M=M_1\cup M_2$ is $N_M=2\left(r-c_{i,i^{\prime }}-\lambda \right).$ We reorder the columns of design $X,$ so that the columns with $x_{i,j}=1$ and $x_{i\prime ,j}=0,$ i.e. $j\in M_1,$ are then the columns 1, 3, 5, etc… Analogously, the columns with $x_{i,j}=0$ and $x_{i\prime ,j}=1,$ i.e. $j\in M_2,$ are then the columns 2, 4, 6, etc… Rows $i$ and $i\prime$ of design $X$ (which is now the reordered design) have the following principal shape then: (B11) $$\begin{array}{ccccccccc}\text{Row}& & & & & \text{Column}& & & \\ & 1& 2& \dots & N_M-1& N_M& N_M+1& \dots & b\\ i& 1& 0& \dots & 1& 0& 0& \dots & 1\\ i\prime & 0& 1& \dots & 0& 1& 0& \dots & 1\end{array}$$(B11)

We now want to create a new design $\tilde{X}$ with few changes compared to design $X$ which is potentially better. The first $N_c$ columns of $C\left(\tilde{X}\right)$ should remain admissible, i.e. $c_{i,j}=0$ and $c_{i\prime ,j}=0$ must hold for $j=1, \dots ,N_c.$ (Note however, that the latter equations $c_{i\prime ,j}=0$ automatically hold due to theorem B1.) Furthermore, we demand ${\sum }_{j=1}^{b\prime }{x}_{i,j}=r\prime .$ Hence, we have $N_c+1$ equations to hold. To exploit these equations, we have to introduce variables $y_1,$ $y_2,$…, $y_{N_c+1}.$ For example, this can be done by putting $x_{i,j}=y_j$ and $x_{i\prime ,j}=1-y_j$ with $j=1,\dots ,N_c+1.$ Generally, the set of columns, assigned to the variables, is $M_y=\left\{j_1,j_2,\dots ,j_{N_c+1}\right\},$ where $M_y$ is a set of size $N_c+1$ with $M_y\subset M.$ (B12) $$\begin{array}{ccccccccc}\text{Row}& & & & & \text{Column}& & & \\ & 1& 2& \dots & N_c+1& N_c+2& N_c+3& \dots & N_M\\ i& y_1& y_2& \dots & y_{N_c+1}& 0& 1& \dots & 0\\ i\prime & 1-y_1& 1-y_2& \dots & 1-y_{N_c+1}& 1& 0& \dots & 1\end{array}$$(B12)

We have $N_c+1$ equations and $N_c+1$ variables. (We assume here, that the system of linear equations is of full rank. This is not always true. Then, the number of variables has to be reduced in an efficient way.)

Now, the system of equations can be solved. However, the solutions are $y_j=x_{i,j},$ i.e. we obtain the former entries of $X.$ The reason is, that the design $X$ satisfied the equations and that we did not really change the design $X.$ Hence, we have to change some entries $x_{i,j}$ and $x_{i\prime ,j}$ with $j\in M\backslash M_y.$ The most elementary case is to change just one column and to put ${{\tilde{x}}_{i,j\prime }=1-x}_{i,j\prime }$ and ${{\tilde{x}}_{i\prime ,j\prime }=1-x}_{i\prime ,j\prime }.$ Such change was successful when the solutions $y_j$ are zeros or unities and when the penalty $P\left(C\left(\tilde{X}\right)\right)$ is smaller than $P\left(C\left(X\right)\right).$ For the exchange index $j^{\prime },$ all elements of $M\backslash M_y$ were applied.

A penalty to increase the number of admissible rows or admissible columns is (B13) $$P\left(C\left(\tilde{X}\right)\right)={\sum }_{i=N_a+1}^v{\sum }_{j=N_c+1}^{i-1}\left[\begin{array}{c}1000\text{ if }i=N_a+1\\ \mathrm{ }1\text{ if }i\ge N_a+1\mathrm{ }\end{array}\right]\times \left[\begin{array}{c}1000\text{ if }j=N_c+1\\ \mathrm{ }1\text{ if }j>N_c+1\mathrm{ }\end{array}\right]\times c_{i,j}^2$$(B13)

From running time reasons, it is not realistic to apply all subsets $M_y\subset M.$ We applied a grid by first taking $M_y=\left\{1, 2,\dots ,N_c+1\right\},$ then $M_y=\left\{1+\Delta , 2+\Delta ,\dots ,N_c+1+\Delta \right\},$ then $M_y=\left\{1+2\Delta , 2+2\Delta ,\dots ,N_c+1+2\Delta \right\},$ etc., where $\Delta$ is a natural number with $N_c+1\le \Delta <N_M.$

The next modification is to suggest not only one changed column, but to suggest $L>1$ changed columns. This is done by generating vectors of zeros and unities of length $L.$ With $L=20,$ the generation of these vectors takes seconds. For $L=40,$ the generation of these vectors takes more than a week on a normal computer. The potential of this modification is large, but may demand enormous running time.

The chance to find an admissible new row depends on the goodness of row $N_a+1.$ Ideally, there is only one non- zero entry $c_{N_a+1,j}$ with $j\le N_a.$ In that case, one can try to improve row $j,$ although row $j$ is admissible. If there are more non- zero entries $c_{N_a+1,j},$ $j\in J,$ one can try to find sequentially new admissible rows $j\in J.$ Thus, an admissible row needs not to be fixed for all times.

It may happen, that the introduced methods fail to increase $N_a.$ For $\left(v,k\right)=\left(45,22\right)$ with $\left(b^{\prime },r^{\prime },\lambda \prime \right)=\left(90,44,21\right),$ this appeared for $N_a=25$ and $N_c=24.$ The number of equations was $N_c+1=25.$ However, the maximum number for $L$ is limited by $N_c+1+L\le \mathrm{ }{N}_M.$ In that case, the average number of $N_M$ was $2\left(r-\lambda \right)=46.$ Often, we could not generate vectors longer than $L=21.$ In such cases it is not appropriate to handle pairs of rows, but solely row $N_{a+1}.$ In the described case we can add the equation $c_{26,25}=0.$ Then we may generate vectors longer than $L=21.$ For each generated vector it must be checked, if the solution of the equations consists of zeros and unities.

If an admissible new row was found we have $N_a:=N_a+1.$ Since we treated only one row, the resulting incidence matrix is no longer an admissible design (some $k-$ conditions are violated). Therefore, rows $N_a+1$ to $v$ must be renewed. This is done by a modified version of the initial generation of a design $X.$ Then, the procedure is continued with a new run of the basic tool 1.

The optimization procedures of the software package “Mathematica” (Wolfram 1999) are known to be efficient (see Zeidler 2004). The optimization procedures NMaximize and NMinimize allow a variety of constraints, among them the restriction of the variables to be integers. Objective functions of different kind may be applied. Particularly, linear objective functions were treated effectively. In the given context, the objective functions are of quadratic or of forth degree. Because of $x_{i,j}\in \left\{0,1\right\},$ we have $x_{i,j}=x_{i,j}^2=x_{i,j}^3=x_{i,j}^4$ and the objective functions can be transformed into quasilinear ones. We checked whether the procedure NMinimize runs faster than our advanced methods. But this was not the case. This was also the case with the recently implemented Mathematica- method “Couenne”. Then the question arose, how to apply NMinimize with a strictly linear objective function.

We start with an incidence matrix obtained with the basic tool 1 and the advanced methods of moderate effort ($L=20$). Experience shows, that the first inadmissible row $N_a+1$ of the incidence matrix has then entries $c_{N_a+1,j}\in \left\{-1,0,1\right\}$ for $j\le N_a$ in the concurrence matrix, Instead of minimizing ${\sum }_{j=1}^{N_a}{c}_{N_a+1,j}^2,$ we demand $c_{N_a+1,j}=0$ for $j\le N_a$ now. We introduce variables $y_i,$ $i=1,\dots ,N_a+1+L,$ in row $N_a+1$ like described above. Then we use the procedure Solve to solve $N_a+1$ linear equations ($c_{N_a+1,j}=0,$ $j=1,\dots ,N_a,$ and ${\sum }_{j=1}^b{x}_{N_a+1,j}=r$) with respect to $y_{L+1},\dots ,y_{L+N_a+1}.$ Denoting the solutions (depending on $y_1,\dots ,y_L$) with $z_1,\dots ,z_{N_a+1},$ the side conditions are formulated as $0\le y_j\le 1$ and $y_j\in \mathrm{Integers},$ $j=1,\dots ,L$ and $0\le z_j\le 1,$ $j=1,\dots ,N_a$+1. (It is useful to program the inequalities in matrix form.)

In a strong sense, this is not an optimization problem, since it would be sufficient if the problem has a solution. Hence, to apply NMinimize, an auxiliary linear objective function was used: $y_1.$ This means that we are looking for the minimum of a free variable (although we are not really interested whether it is zero or one). Applied in this way, NMinimize works much more effective than the earlier described advanced methods.

The application of NMinimize to solve a system of conditions was also much more effective than the direct use of the Mathematica- procedures NSolve or FindInstance.

As expected, the effectiveness of the NMinimize- method turned out to be best when there was only one non-zero entry $c_{N_a+1,j}$ for $j\le N_a$ and became worse with an increasing number of non-zero entries. Therefore, a modification is applied for $N_u>1$ non-zero entries. We reorder the rows of the incidence matrix, so that $c_{N_a+1,j}\ne 0$ for $j\in \left\{N_a-N_u+1, N_a-N_u+2,\dots ,N_a\right\}.$ Then, rows $N_a$ and $N_a+1$ are exchanged. Thus, $c_{N_a+1,N_a}$ is the only non-zero entry in row $N_a+1$ (while there are $N_u-1$ non-zero entries in row $N_a$). Now we apply the described method (to row $N_a+1$). Having determined a solution rows $N_a$ and $N_a+1$ are exchanged again. Thus, the number of non-zero entries in row $N_a+1$ was reduced to $N_u-1.$ This technique is repeated until $N_u=1$ is reached. Then, the original technique can be used.

When this procedure succeeded, we generated a new admissible row. Checking the concurrence matrix of the obtained incidence matrix, we generally observe a deterioration of the fit of the remaining inadmissible rows. Furthermore, some $k$- conditions are violated (changes in a row were not compensated by changes in another row). Hence, we cannot start immediately with the treatment of the next inadmissible row. First we have to modify the inadmissible rows of the incidence matrix so that the $r$- and $k$- conditions are satisfied. This causes another deterioration of the fit of the remaining inadmissible rows.

Since the application of the NMinimize- technique is particularly effective when there are many zero entries in row $N_a+1$ of the concurrence matrix and only a few $1$ and $-1$ entries, the improvement of the actual incidence matrix is necessary. This can be realized by the application of the basic tool 1 and the earlier introduced advanced methods. (These methods are suited to improve the whole concurrence matrix as well as parts of it, while the NMinimize- technique is suited to improve certain cells of the concurrence matrix.)