Construction of Non-Symmetric Balanced Incomplete Block Design through Combination of Symmetric Disjoint Balanced Incomplete Block Designs ()
1. Introduction
A Balanced Incomplete Block Design (BIBD) is an arrangement of v treatments into b blocks each of size k such that each treatment is replicated r times in the design while each pair of treatments occurs together
times in the entire design [1] . The design is said to be symmetric if
and
[1] [2] [3] and non symmetric if
[2] [3] .
The design is mostly applicable in experimental design when designing experiments with huge blocks which are too large to maintain homogeneity of the experimental units or when the cost of setting up a full block design is too high. Under these circumstances, the design aid in reducing the block sizes hence making the maintenance of block homogeneity possible and also reducing the cost of setting up the experimental design by reducing the amount of resources required in setting up the experiment. The design is used in all fields of experiment such as medical, agricultural, and industrial among others [3] [4] .
Despite the importance of BIBDs, the design does not universally exist as it is required that the design parameters must satisfy some necessary conditions for it to possibly exist [5] [6] [7] . First, the total number of plots in the design (bk) is always required to be equivalent to the number of treatments v times the number of replication r. Thus,
(1)
This property originate from the fact that the total number of blocks b in the design is given by the formula
The second, the total number of treatments that occur together with a particular treatment in the design
must always be equal to the number of replications r times the number of plots per block less 1 plot
. Thus,
(2)
This property is also derived from the total number of block b in the design, which can also be given by the formula
But it is known that
. Therefore, it can be shown that
The properties in Equations (1) and (2), are known as the fundamental properties of a BIBD which must always be satisfied for the design to exist. However, over the years, other properties that apply for both symmetric and non-symmetric BIBD have been ascertained as given in Equations (3) and (4). The property in Equation (3), requires that for a BIBD to exist then the number of times each treatment is replicated
must be greater than the number of times the treatment occurs together with other treatments.
(3)
Fisher’s also introduced a property that for a BIBD to exist then,
(4)
The property in Equation (4), is known as Fisher’s Inequality. Past studies have determined that when properties in Equations (1) and (2) are satisfied then automatically the properties in Equations (3) and (4) are also satisfied [3] [8] [9] [10] .
One of the breakthroughs concerning the properties of BIBDs was the establishment of the non-existence properties of symmetric BIBDs. According to the properties, if we consider a v by b incidence matrix T for a BIBD such that
where
Each column of the matrix has a total of k ones and
zeros while in each row, there are r ones and
zeros.
The determinant of the product of the matrix and its transpose is given as
(5)
Therefore, If the incidence matrix T is of a symmetric BIBD, then it follows that
(6)
Given that the determinant of the incidence matrix for symmetric BIBD must be an integer, then the design does not exist when v is even and
is not a perfect square [5] [9] [11] [12] .
Similarly, according to the Bruck-Ryser-Chowla theorem, for a symmetric BIBD with parameters
,
, and
. When the number of treatments v is odd. Then the design does not exist if the equation
(7)
do not have a solution in integers
not all simultaneously zero [1] .
Similar to the properties of BIBDs, much stride has been made in the construction of BIBDs. One of the key contributors to the construction of BIBDs was Bose [13] . The study illustrated the various techniques used in constructing BIBDs, such as projection geometry, Euclidean geometry, and Difference sets. The study lists some BIBDs that could be constructed using these techniques and some BIBDs that couldn’t be constructed using these methods. The study used construction techniques to find solutions to existing BIBD construction problems. The study’s weakness was that it could not find a solution to all the BIBD construction problems as it could not construct all the BIBDs. This gave room to other authors to solve the remaining construction problems by developing new construction techniques for BIBDs.
Alam [14] conducted a study on some methods of constructing BIBDs. The study discussed and illustrated how BIBD design could be constructed from existing designs. The study discussed and illustrated the construction of designs such as derived BIBD, Residual BIBD, Un-reduced BIBD, Complementary BIBD, Construction of BIBD by deleting blocks with specified treatment for
designs, construction of PBIBD using replacement method and Dual BIBDs. The study, however, could not exhaust all techniques of constructing BIBDs using existing designs. The study was also unable to generalize the construction of BIBDs by deleting blocks containing a specified treatment for different values of
.
Hsiao [15] conducted a study on methods of constructing BIBDs. The study discussed the various methods used in constructing BIBDs, such as the construction of BIBDs using difference sets, Latin square, Un-reduced BIBD, and the construction of BIBDs using existing designs.
Yasmin [16] looked into the construction of BIBD using cyclic shifts. The study illustrated how the cyclic shift sets could be used to construct BIBDs and gave illustrative examples of how the technique is used in constructing BIBDs. However, the study could not provide a complete list of possible BIBDs that could be constructed using this technique.
Goud [17] conducted a study on new construction methods of BIBDs. The study used the triangular association scheme and the lattice square design to construct BIBDs. The study, however, failed to give the list of designs that could be constructed using the proposed construction methods and was also not able to show if the designs satisfied the necessary conditions for the existence of BIBDs.
Rayma [18] conducted a study on the construction of BIBDs using mutually orthogonal Latin squares of order six. The study discussed how BIBD could be constructed for several treatments
, which was a non-prime using the MOLS and even gave examples to illustrate how the technique could be used in constructing BIBDs. The study concluded that the same technique could be used to construct BIBDs with a non-prime number of treatments. The study, however, failed to provide a list of BIBDs with a non-prime number of treatments that could be constructed using the method.
Alabi [19] checked on the construction of BIBDs using Lattice Series I and II. The study showed how the design could be constructed using the technique and verified that the technique could only be used for constructing BIBDs when the number of treatments v was a perfect square and the block size k was the square root of the number of treatments.
. The method could also construct a BIBD for prime and non-prime plot sizes k. The shortfall of the study was that it was only restricted to BIBDs that satisfy the set conditions and could not be generalized to other BIBDs that did not satisfy the required conditions.
Lastly, Akral [20] carried out a study on the Finite Euclidean Geometry approach for constructing Balanced Incomplete Block Design. The study provided proof of the necessary conditions for the existence of BIBD as stated in 1 to 3. The study also showed how Euclidean geometry could be used to construct BIBD. The study’s shortcoming was that it could only prove the existing properties in the literature. However, the study could not come up with other new properties for the existence of BIBD, which would bring us closer to sufficient conditions. It was also not able to develop a new construction method for BIBD.
In conclusion, various scholars have done extensive work over the years on the construction of BIBDs. However, the studies have not been able construct all the BIBDs especially non-symmetric BIBDs, given that the non-existence condition for this class of BIBD is still unknown. Therefore, the existence of a number of non-symmetric BIBD is left unknown as there non-existence cannot be established at the moment and also the construction methods cannot construct them [8] [21] .
2. Statement of the Problem
Several construction methods of BIBD have been discovered over the years which include the use of projection geometry, Euclidean geometric, cyclic difference sets, repeated difference sets, Latin square technique, Linear Integer Algorithm, R ibd package, using existing BIBD designs among others. However, the existence of several BIBDs especially non-symmetric is still unknown because the designs satisfy the necessary conditions for the existence of BIBD still cannot be constructed using the existing techniques.
The study aimed at bridging this gap through introduction a new class of BIBDs which are constructed by combining disjoint symmetric BIBDs. The study also aimed at establishing the non-existence property for such designs so that the existence or non-existence of this class of design would be known with certainty.
3. Methods
3.1. Construction of Combined Non-Symmetric BIBD
Consider n symmetric disjoint BIBDs with parameters
that do not share any block in comment. The incidence matrix of each of the n symmetric disjoint BIBD has a equal number of rows v and equal number of columns b. In each column there are a total of k 1s and
0s and in each row there are a total of r 1s and
zeros. Given that the designs are disjoint (do not share any block in common) then for all the n incidence matrices, there is no column that is shared by any of the n incidence matrices. Hence, if the columns of the matrices are combined together then a new incidence matrix with v rows and nb columns is formed. In the new matrix, each columns has a total of k 1s and
0s and in each row there are a total of nr 1s and
zeros. The new incidence matrix is for a BIBD with parameters
,
,
,
,
which is non symmetric because
.
3.2. Non-Existence Property for Combined Non-Symmetric BIBD
The construction of combined non-symmetric BIBD involves the combination of n symmetric disjoint BIBDs. Therefore, in order for the design to exist then it is required that the n symmetric disjoint BIBDs must first exist and be constructed. As a result, when the n symmetric disjoint BIBDs, fail to exist then the combined non-symmetric BIBD seize to exist. Given that the non-existence property for symmetric BIBDs is known and the design parameters of combined non-symmetric BIBD is related to those of symmetric BIBD, the study applied the non-existence property for symmetric BIBDs and relationship between non-symmetric BIBD and combined non-symmetric BIBD to derive the non-existence property for combined non-symmetric BIBD. This aided in determining a number of non-symmetric BIBDs that do not exist.
4. Main Results
4.1. Number of Symmetric Disjoint BIBD in Un-Reduced BIBD
In order to know the optimum size of non-symmetric BIBD which can be obtained through combining disjoint symmetric BIBDs with parameters
. The study first established the number of possible disjoint symmetric BIBDs that can be obtained from the universal un-reduced BIBD design with parameters v and k.
Theorem 1. Let
be un-reduced BIBD and (
) be a symmetric BIBD. Then
such symmetric BIBDs which do not share any block in common (disjoint) can be obtained from un-reduced BIBD.
Proof. The total number of blocks in the un-reduced BIBD
and the number of disjoint treatment replications which are disjoint to a particular treatment in the un-reduced BIBD (
) is given by the formula.
Now we wish to obtain a symmetric BIBD with b blocks from the un-reduced block design, then the fraction of blocks from the unreduced block design f that will be used to construct the symmetric BIBD will be given by;
However, we know that the number of blocks b is given by the formula
therefore, this shows that the fraction of blocks f from the un-reduced block design that is used to create the symmetric BIBD is given by the formula;
However, to create disjoint BIBD, the blocks must be composed of a disjoint set of treatments. Therefore, to know the total number of disjoint symmetric BIBD (n) with blocks of size b that can be constructed from the un-reduced BIBD, we multiply the fractions of symmetric BIBD within the un-reduced BIBD with the number of disjoint replications in the design because each disjoint replication contain a disjoint block set and the fraction of symmetric BIBD within the BIBD give us the fraction of blocks required to create each symmetric BIBD. Therefore, the total number of disjoint symmetric, BIBD that can be obtained from unreduced BIBD is given by the formula:
Now if we add and subtract 1 from the term
, the result is
But
. Therefore
end of proof.¨
The results in Table 1, shows the number of disjoint symmetric BIBDs that can be constructed from un-reduced BIBD.
Table 1. Number of disjoint symmetric BIBDs that can be constructed from un-reduced BIBD.
4.2. Construction of BIBD Using the Combination Method
Theorem 2. Let (
) be parameters of n symmetric BIBDs which do not share any block in common. If the BIBDs are combined then a BIBD with parameters (
,
,
,
,
) is formed.
Proof. When we combine n disjoint symmetric BIBDs of the same parameters, the number of treatments vk and the block size v do not change, however, the number of blocks, replication and
will be increased n times, the issue that arises however, is that, does the newly created design satisfy the conditions for the existence of a BIBD. First, the study looked into the first condition
The first condition is satisfied. Next, we look at the second condition for the existence of a BIBD.
This shows that the second condition is also satisfied, hence the resultant design is a BIBD.¨
Example 1.
Let’s consider two disjoint BIBDs with parameters
as illustrated in Table 2.
Now if we combine the two BIBDs to form a single BIBD with parameters
as shown in the Table 3.
Table 2. Two disjoint sets of balance incomplete block design with
.
Table 3. The resultant combined balance incomplete block design with
Example 2
Let’s consider two disjoint BIBDs with parameters
as illustrated in Table 4.
Now if we combine the two BIBDs to form a single BIBD with parameters
as shown in the Table 5.
Given that, we know the number of disjoint symmetric BIBDs that we can obtain from an Unreduced BIBD. The list of BIBDs shown in Table 6, can be constructed by combining disjoint symmetric BIBDs of the same kind.
4.3. Non-Existence Properties for Combined Non-Symmetric BIBD
Theorem 3. The design of a non-symmetric BIBD with parameters (
,
,
,
,
) formed by combining n symmetric disjoint BIBDs with parameters (
) such that
, where
is not a perfect square does not exist when v is even.
Proof. Consider a symmetric BIBD with parameters (
) and incidence matrix T. Based on the property in Equation (6), the symmetric BIBD is considered to be non-existing if when
is not a perfect square v is even. Following from Equation (6), based on the relation between combined non-symmetric BIBD and symmetric BIBD. The
can be given by
Table 4. Two disjoint sets of balance incomplete block design with
.
Table 5. The resultant combined balance incomplete block design with
.
Given that
is an integer, then this can only be true if either
is a perfect square or v is odd. Thus, when
is not a perfect square then, v must be odd.¨
Based on theorems 3 the combined non-symmetric BIBDs in Table 7, are determined to be non-existing.
Table 6. List of some BIBDs that can be constructed using the combination method.
Table 7. List of some non-existing combined non-symmetric BIBDs.
Theorem 4. Let (
,
,
,
,
) be a non-symmetric BIBD formed by combining n symmetric disjoint BIBDs with parameter (
) such that
. If v is odd, then the equation
has no solution in the integers
not all simultaneously zero for the design not to exist.
Proof. According to Bruck-Ryser-Chowla theorem, for a symmetric BIBD with parameter
which is odd the design is considered non-existing if the Equation 7 does not have a solution in integers
not all simultaneously zero [1] . If we relate the non-symmetric combined BIBD to the symmetric BIBD and apply the condition in Equation (7). This shows that
Now using the relation between symmetric disjoint BIBDs and the combined BIBD, it is evident that
(8)
Therefore, going as per Bruck-Ryser-Chowla theorem, when v is even then the Equation 8 should have solutions in integers
which are not all simultaneously zero.¨
Hence the proof.
Based on theorem 4, the non-symmetric combined BIBDs in Table 8 are determined to be non-existing
5. Conclusion and Suggestion
In conclusion, when n symmetric disjoint BIBDs with parameters
are combined together (
), then a new class of BIBD is formed with parameters
,
,
,
,
. The created design does not exist if when
is not a perfect square v is even and when v is odd then the Equation
should not
Table 8. List of some non-existing combined non-symmetric BIBDs.
have a solution in integers
not all simultaneously zero. For the design to be constructed then the symmetric disjoint BIBDs must first be constructed.