Some methods of decomposing
A balanced incomplete block (BIB) design or a 2 − (v, k, λ) design is an arrangement of v elements into b = λ(v² − v)/(k² − k) blocks, each of size k (k < v) such that every element occurs in exactly r blocks and any two distinct elements occur together in λ blocks. Further, a BIB design is symmetric if v = b and is self-complementary if v = 2k.
Let a (0, 1) – matrix N have a decomposition N = [Nij]i=1,…,s; j=1,…,t where Nij are submatrices of N of suitable sizes. The decomposition is called row tactical if row sum of Nij is rij and column tactical if the column sum of Nij is kij and tactical if it is row as well as column tactical. If N is the incidence matrix of a block design D(v, b, r, k), D is called row (column) tactical decomposable. D is called uniform row (column) tactical decomposable if rij = α (kij = β) ∀i, j. If each Nij is an m × m matrix, D is called square tactical decomposable design, STD(m).
Several methods of constructions of tactical decomposable rectangular, group divisible and L2–type designs may be found in Bekar et al. [2], Singh and Saurabh [19], Saurabh and Sinha [16], [17] and Saurabh [14], among others.
Let v = mn elements be arranged in an m × n array. A regular group divisible (RGD) design is an arrangement of the v = mn elements in b blocks each of size k such that:
Further let N be a v × b incidence matrix of a block design such that JvN = kJv×b and satisfies the following conditions (1) or (2).
(i)Let
Then (2)
Then N represents a GD design with parameters: v = mn, r, k, b, λ1, λ2, m, n. For GD schemes, we refer to Saurabh [14]. A GD design will be called STD(n) or STD(m) with orthogonal rows if its incidence matrix satisfies the conditions (1) or (2) respectively.
Let the incidence matrix N of a block design D(v, r, k, b) may be decomposed into submatrices as N = (N1 | N2 | … | Nt) such that each row sum of Ni (1 ≤ i ≤ t) is μi. Then the design is (μ1, μ2, …, μt)–resolvable [see Kageyama [8], Saurabh [13]]. If μ1 = μ2 = … = μt = μ then the design is μ–resolvable. Such designs are also denoted as A–resolvable designs in combinatorial design theory [see Ge and Miao [7]]. A practical application of (μ1, μ2, …, μt)–resolvable designs may be found in Kageyama [8]. These designs may also have potential applications in coding theory and cryptography.
A block design D(v, b, r, k) is cyclic if its solution may be obtained by adding the elements of a cyclic group Zv = {0, 1, 2, …, v} mod v to the initial blocks of the design, whereas a design is partial cyclic if its solution may be obtained by developing the initial blocks under a partial cycle: 1 ↔ q, q + 1 ↔ 2q, …, [q(p − 1) + 1] ↔ v = pq of length q where (1 ↔ q) ⇐⇒ 1 → 2, 2 → 3, …, (q − 1) → q, q → 1 [see Saurabh [12]].
Some constructions of partial cyclic GD designs can be found in Dey and Nigam [6], Mukerjee et al. [10], Dey and Balasubramanian [5], Midha and Dey [9], among others.
Example 1.1. A partial cyclic solution to the GD design R80: v = 14, r = 9, k = 3, b = 42, λ1 = 6, λ2 = 1, m = 7, n = 2 may be obtained by developing the initial blocks: (1, 2, 8); (1, 8, 9); (1, 3, 8); (1, 8, 10); (1, 4, 8); (1, 8, 11) under a partial cycle 1 ↔ 7, 8 ↔ 14 of length 7 [see Clatworthy [4]].
Notation 1.2. In is the identity matrix of order n, Jv×b is the v × b matrix all of whose entries are 1 and Jv×v = Jv, A′ is the transpose of matrix A, A ⊗ B is the Kronecker product of two matrices A and B, 0n is a zero matrix of order n × n and a (0,1)–matrix: α = circ(0 1 0 … 0) is a permutation circulant matrix of order m such that αm = Im. RX numbers are from Clatworthy [4].
Proof. Let N be the incidence matrix of a RGD design D having partial cyclic solution of length m. Then the number of initial blocks is t = b/m. Our aim is to decompose N as N = [Nij]i=1,…,n; j=1,…,t where each Nij is a square matrix of order m. Then corresponding to each initial block Bi (1 ≤ i ≤ t) of D, we obtain the ith–column of blocks of N as follows:
Step I: Break the interval [1, mn] into n subintervals as: [1, m], [m + 1, 2m], …, [m(n − 1) + 1, mn] such that each subinterval contains m elements which is the length of partial cycle.
Step II: Let α = circ(0 1 0 … 0) be a permutation circulant matrix of order m. Then corresponding to initial block whose elements belong to above subintervals, we obtain the following m × m block matrices:
Hence we obtain a STD(m) RGD design corresponding to its partial cyclic solution. ∎
Theorem 2.2.
The existence of a self–complementary BIB design with parameters:
Proof. Let
Since the BIB design is self–complementary, we obtain
Example 2.3. Consider a selfcomplementary BIB design with parameters: v = 4, r = 3, k = 2, b = 6, λ = 1 whose incidence matrix is:
Then replacing in
Further since each row sum of
Here, some RGD designs of Clatworthy [4]
are identified as STD
1)
Initial blocks are [(1, 2, 8), (1, 8, 9), (1, 3, 8), (1, 8, 10), (1,
4, 8), (1, 8, 11)] under the partial cycles
Then
The initial blocks of the remaining RGD designs listed below may be found in Clatworthy .
2)
Since each row sum of
3)
Since each row sum of
4)
Since each row sum of
5)
Since each row sum of
6)
Since each row sum of
7)
Since each row sum of
8)
Since each row sum of
9)
10)
11)
Let
According to Time Magazine (May 4, 1992, p. 13), control of
nuclear weapons in Russia in early 1990s depended upon
“two–out–of–three” access mechanism. The three parties involved were the
President, the Defense–minister and the Defense Ministry. This would
correspond to a threshold scheme with
Pieprzyk and Zhang [11] obtained ideal
(t, w)
Some recent constructions of perfect secret sharing schemes from doubly resolvable GD designs and orthogonal resolutions of certain combinatorial designs can be found in Saurabh and Sinha [15,18]. A recent survey on threshold schemes from combinatorial designs may be found in Bose [3].
Present scheme: Consider a STD
Hence corresponding to a STD
Further using Theorem 2.1 and 2.2, we obtain:
Scheme: The tactical decomposable RGD designs in Theorem 2.1 correspond to
Example 4.1. The STD (4) RGD design R200 given in Section 3 can be used to obtain a
1970-2025 CP (Manitoba, Canada) unless otherwise stated.