A brief survey on tactical decomposable families of rectangular designs (RDs) is presented. Rectangular designs have well–known applications in statistics. Here, applications of RDs in cryptography and coding theory are described. Earlier, \((2,\ n) -\)threshold schemes were proposed from tactical decomposable regular group divisible designs. Threshold schemes are proposed here from tactical decomposable RDs. Further, an application of RDs in low–density parity–check (LDPC) codes is also given. Tactical decomposable RDs had not been previously used in the constructions of threshold schemes and LDPC codes.
A brief survey on tactical decomposable rectangular designs (RDs) families is presented and their applications in cryptography and coding theory are also described. Earlier, Saurabh [20] proposed \((2,\ n) -\)threshold schemes from tactical decomposable regular group divisible designs. Threshold schemes are obtained here from tactical decomposable RDs.
Previously low–density parity–check (LDPC) codes from group divisible designs had been studied by Shan and Li [28], Xu et al. [39] and Saurabh and Sinha [24], among others. Here, an application of RDs in low–density parity–check (LDPC) codes is also given. A brief survey on the constructions of LDPC codes based on certain combinatorial structures is available in Saurabh and Sinha [27].
The paper is organized as follows: Section 1 contains introduction and contributions, Section 2 contains some preliminaries on rectangular designs and their applications in statistics, Section 3 contains some previously obtained tactical decomposable RDs families, applications of RDs in threshold schemes and LDPC codes are described in Sections 4 and 5 respectively, whereas discussion and conclusion are given in Section 6.
The theorems related to tactical decomposable RDs families given in Section 3, are taken from earlier sources. Such families of designs are applied here in threshold schemes and LDPC code constructions. Tactical decomposable RDs had not been previously used in the constructions of threshold schemes and LDPC codes.
Notations: \(I_{n}\) is the identity matrix of order \(n\), \(J_{v \times b}\) is the \(v \times b\) matrix all of whose entries are 1 and \(J_{v \times v} = J_{v}\), \(A^{T}\) is the transpose of matrix \(A\), \(A \otimes B\) is the Kronecker product of two matrices \(A\) and \(B\) and \(\alpha = circ\ (0\ 1\ 0\ldots 0)\) is a permutation circulant matrix of order \(q\ \)such that \(\alpha^{q} = I_{q}.\) \(EA\left( p^{n} \right) = C_{p} \times C_{p} \times \cdots \times C_{p}\) (n copies) denotes the elementary abelian group \(EA\ (q)\) of order \(q = p^{n}\) and \(C_{p} = \left\{ 1,\ \alpha,\ \alpha^{2},\ldots,\alpha^{p – 1} \right\}\) is a cyclic group of order \(p\) where \(p\) is a prime.
Some relevant definitions related to the paper are as follows:
Definition 1.1. (Dual design). The dual of a design \(D\ (v,\ b,\ r,\ k)\) is a design \(D^{'}(b,\ v,\ k,\ r)\) whose elements are the blocks of the design \(D\) and whose blocks are the elements of the design \(D\). If \(N\) is the incidence matrix of a design \(D\) then \(N^{T}\) is the incidence matrix of design \(D^{'}\), see Clatworthy [7].
Definition 1.2. (Balanced incomplete block design). A balanced incomplete block (BIB) design/a \(2 – (v,k,\lambda)\) design is an arrangement of \(v\) elements into \(b\) blocks such that
(i) Every block contains \(k( < v)\) distinct elements;
(ii) Every element is replicated \(r\) times and any pair of distinct elements occurs together in exactly \(\lambda\) blocks.
The integers: \(v,b,r,k,\lambda\) are known as parameters of the BIB design and they satisfy the relations:
\[\notag bk = vr,r(k – 1) = \lambda(v – 1),b = \frac{\lambda v(v – 1)}{k(k – 1)}.\]
Definition 1.3. (Skew–Hadamard design). A \((1, – 1) -\)matrix \(H\) of order \(4t\) is called a skew–Hadamard matrix if \(HH^{T} = 4tI_{4t}\) and \(H – I_{4t}\) is a skew–symmetric matrix. A skew–Hadamard matrix is in normalized form if its first row as well as first column contains entirely 1’s. For details, we refer to Wallis et al. [37] and Koukouvinos and Stylianou [14].
The matrix of order \(4t – 1\) obtained by deleting 1st row and 1st column of a normalized skew–Hadamard matrix \(H\) is called the core \(C\) of \(H\). Then \(N = \frac{(C + J_{4t – 1})}{2}\) is the incidence matrix of a skew–Hadamard \((4t – 1,2t – 1,t – 1) -\)design and \(N\) satisfies the following relations:
(i) \(N + N^{T} = (J – I)_{4t – 1},NN^{T} = N^{T}N = (2t – 1)I_{4t – 1} + (t – 1)(J – I)_{4t – 1};\)
(ii)\(N^{2} + N = \left( N^{T} \right)^{2}{+ N}^{T} = t(J – I)_{4t – 1},\ N^{2} + \left( N^{T} \right)^{2} = (2t – 1)(J – I)_{4t – 1}.\)
Example 1.4. \(N = circ.\ (0\ 1\ 1\ 0\ 1\ 0\ 0)\) is the incidence matrix of a skew–Hadamard \((7,\ 3,\ 1) -\)design.
Definition 1.5. (Generalized Hadamard matrix). Let \(G\) be a multiplicative group of order \(g\). Then a generalized Hadamard matrix \(GH(\lambda g;G)\) is a \(\lambda g \times \lambda g\) array with entries from \(G\) such that
(i) Each row and column contain exactly \(\lambda g\) group elements (repeated or non–repeated) as entries;
(ii) For each pair of distinct rows (columns): \((x_{1},\ x_{2},\ \ldots,\ x_{b})\) and \((y_{1},\ y_{2},\ \ldots,\ y_{b})\), the multi–set \(\{ x_{i}y_{i}^{- 1}:i = 1,\ 2,\ \ldots,\ b( = \lambda g)\}\) contains each group element exactly \(\lambda\) times.
A \(GH(\lambda g;G)\) is in normalized form if its first row and column contain only identity element of \(G\).
Example 1.6. \(GH\left( 6;\ C_{3} \right) = \ \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & \alpha & \alpha^{2} & \alpha & \alpha^{2} & 1 \\ 1 & \alpha^{2} & \alpha & \alpha & 1 & \alpha^{2} \\ 1 & \alpha^{2} & \alpha^{2} & 1 & \alpha & \alpha \\ 1 & 1 & \alpha & \alpha^{2} & \alpha^{2} & \alpha \\ 1 & \alpha & 1 & \alpha^{2} & \alpha & \alpha^{2} \end{pmatrix}\) over a cyclic group \(C_{3} = \left\{ 1,\ \alpha,\ \alpha^{2} \right\}.\)
Let \(v = mn\) elements be arranged in an \(m \times n\) array \(A\). A rectangular design (RD), introduced by Vartak [36], is an arrangement of the \(v = mn\) elements in \(b\) blocks each of size \(k\) such that
1. Every element occurs at most once in a block;
2. Every element occurs in exactly \(r\) blocks;
3. Every pair of elements, which are in the same row of the array \(A\) occur together in \(\lambda_{1}\) blocks; which are in same column occur together in \(\lambda_{2}\) blocks; while every other pair of elements occur together in \(\lambda_{3}\) blocks. The elements in the same row are first associates, the elements in the same column are second associates and the elements not in the same row or column are third associates.
The non–negative integers \(v = mn,r,k,b,\lambda_{1},\lambda_{2},\lambda_{3},m,n\) are known as parameters of the RD and they satisfy the relations: \(bk = vr;(n – 1)\lambda_{1} + (m – 1)\lambda_{2} + (n – 1){(m – 1)\lambda}_{3} = r(k – 1).\)
The \(m \times n\) array \(A\) is given as:
\[\begin{matrix} 1 & 2 & 3 & \cdots & n \\ n + 1 & n + 2 & n + 3 & \cdots & 2n \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ (m – 1)n + 1 & (m – 1)n + 2 & (m – 1)n + 3 & \cdots & mn \end{matrix}.\]
Further, let \(N\) be \(v \times b\) \((0,\ 1) -\)incidence matrix of a block design which satisfies the following conditions:
(i) \(J_{v}N = kJ_{v \times b},\) which confirms that each column sum of \(N\) is \(k\);
(ii) \(NN^{T} = \begin{pmatrix} P & Q & \cdots & Q \\ Q & P & \cdots & Q \\ \vdots & \vdots & \vdots & \vdots \\ Q & Q & \cdots & P \end{pmatrix}\), where \(P = \left( r – \lambda_{1} \right)I_{n} + \lambda_{1}J_{n}\) and \(Q = \left( \lambda_{2} – \lambda_{3} \right)I_{n} + \lambda_{3}J_{n}= r\left( I_{m} \otimes I_{n} \right) + \lambda_{1}\left( I_{m} \otimes I_{n}^{c} \right) + \lambda_{2}\left( I_{m}^{c} \otimes I_{n} \right) + \lambda_{3}\left( I_{m}^{c} \otimes I_{n}^{c} \right);\) \(I_{n}^{c} = (J – I)_{n}.\)
Alternatively, let \(R_{i}\ \)and \(R_{j}\) be any two rows of blocks of \(N\). Then the inner product of rows is
\[R_{i}R_{j}^{T} = \left\{ \begin{array}{r} rI_{n} + \lambda_{1}(J – I)_{n};i = j \\ \lambda_{2}I_{n} + \lambda_{3}(J – I)_{n};i \neq j \end{array} \right.\ = \left\{ \begin{array}{r} (r – \lambda_{1})I_{n} + \lambda_{1}J_{n};i = j ,\\ (\lambda_{2} – \lambda_{3})I_{n} + \lambda_{3}J_{n};i \neq j. \end{array} \right. \tag{1}\]
Then \(N\) represents an RD with parameters: \(v = mn,r,k,b,\lambda_{1},\lambda_{2},\lambda_{3},m,n\). The RD will be called STD\((n)\) with orthogonal rows if its incidence matrix satisfies the condition (1). Clearly a STD\((n)\) RD with \(v = mn\) elements has \(\frac{m(m – 1)}{2}\) pairs of orthogonal rows. Group divisible designs and \(L_{2}\ \)designs are special cases of RDs [30].
Further, let \(N\) be the incidence matrix of an RD with parameters: \(v, r, k, b, \lambda_{1}, \lambda_{2},\lambda_{3}, m, n\). Then four distinct eigenvalues of \(NN^{T}\) are given as:
\({\theta_{0} = rk,\theta}_{1} = r – \lambda_{1} + (m – 1)\left( \lambda_{2} – \lambda_{3} \right),\theta_{2} = r – \lambda_{2} + (n – 1)(\lambda_{1} – \lambda_{3})\),\(\theta_{3} = r – \lambda_{1} – \lambda_{2} + \lambda_{3}\) with respective multiplicities: \(1,n – 1,m – 1,\ (m – 1)(n – 1)\).
A classification of RDs based on the eigenvalues of \(NN^{T}\) is given in Singh and Saurabh [30]. The complementary design of an RD with parameters: \(v = mn, r, k, b, \lambda_{1}, \lambda_{2}, \lambda_{3}, m, n\) is again an RD with parameters: \(v^{*} = mn, r^{*} = b – r, k^{*} = v – k, b^{*} = b, {\lambda_{1}}^{*} = b – 2r + \lambda_{1}, {\lambda_{2}}^{*} = b – 2r + \lambda_{2},{\lambda_{3}}^{*} = b – 2r + \lambda_{3}, m, n.\)
A recent survey on RDs are available in Singh and Saurabh [30]. Some series of cyclic RDs are obtained by Sinha et al. [31] and Saurabh [21], among others. RDs are useful as factorial experiments, having balance as well as orthogonality, see Gupta and Mukerjee [11]. In addition, RDs having \(\lambda_{3} > \lambda_{1},\lambda_{2}\) when used as the \(m \times n\) complete confounded experiments, the loss of information on the main effects is small, see Suen [34]. An application of RD in cluster sampling is described in Raghavarao and Singh [17]. RDs are also applicable in agricultural field trials.
Let a (0, 1) – matrix \(N\) have a decomposition \(N = \left\lbrack N_{ij} \right\rbrack_{\begin{array}{r} i = 1,2,\ldots,s \\ j = 1,2,\ldots,t \end{array}}\) where \(N_{ij}\) are submatrices of \(N\) of suitable sizes. The decomposition is called row tactical if row sum of \(N_{ij}\) is \(r_{ij}\) and column tactical if the column sum of \(N_{ij}\) is \(k_{ij}\) and tactical if it is row as well as column tactical. If \(N\) is the incidence matrix of a block design \(D\), \(D\) is called row (column) tactical decomposable. \(D\) is called uniform row (column) tactical decomposable if \(r_{ij} = \alpha\left( k_{ij} = \beta \right)\forall i,j.\) If each \(N_{ij}\) is an \(n \times n\) matrix, \(D\) is called square tactical decomposable design, STD \((n)\).
Several methods of constructions of tactical decomposable rectangular, group divisible and \(L_{2}\) designs are available in Bekar et al. [4], Singh and Saurabh [30], Saurabh and Sinha [23, 25] and Saurabh [18, 20, 19], among others. Recently, STD \((n)\) RDs have been extensively studied by Singh and Saurabh [30]. Here, some series are given to illustrate their applications in threshold schemes and LDPC codes constructions. Theorems (1\(-\)5) are taken from Singh and Saurabh [30].
Theorem 3.1. The existence of symmetric \(2 – (n,k_{i},\lambda_{i})\) designs \((i = 1,2)\), whose incidence matrices \(N_{i},i = 1,2\) satisfy the relation: \(N_{1}N_{2}^{'} + N_{2}N_{1}^{'} = \mu_{1}I_{n} + \mu_{2}(J – I)_{n}\), implies the existence of a STD \((n)\) RD with parameters:
\[\left.\begin{aligned} v &= b = mn,r = k = k_{1} + (m – 1)k_{2},\lambda_{1}^{'} = \lambda_{1} + (m – 1)\lambda_{2},\\ \lambda_{2}^{'} &= (m – 2)k_{2} + \mu_{1},\lambda_{3}^{'} = (m – 2)\lambda_{2} + \mu_{2},m,n. \end{aligned}\right\} \tag{2}\]
Proof. Consider a block matrix: \(N = I_{m} \otimes N_{1} + I_{m}^{c} \otimes N_{2}\), where \(I_{m}^{c} = (J – I)_{m},\) \(N_{1}\) and \(N_{2}\) are same as defined above. Then we have
(i) \(J_{mn}N = \left\{ k_{1} + (m – 1)k_{2} \right\} J_{mn};\)
(ii) \(NN^{T} = r\left( I_{m} \otimes I_{n} \right) + \lambda_{1}^{'}\left( I_{m} \otimes I_{n}^{c} \right) + \lambda_{2}^{'}\left( I_{m}^{c} \otimes I_{n} \right) + \lambda_{3}^{'}\left( I_{m}^{c} \otimes I_{n}^{c} \right)\), where \[\notag r = k_{1} + (m – 1)k_{2},\ \lambda_{1}^{'} = \lambda_{1} + (m – 1)\lambda_{2},\lambda_{2}^{'} = (m – 2)k_{2} + \mu_{1},\lambda_{3}^{'} = (m – 2)\lambda_{2} + \mu_{2}.\]
Hence, \(N\) represents an RD with above mentioned parameters (2). \(\square\)
For Corollaries 3.2–3.4 of RDs obtained from Theorem 3.1, \(N_{4t – 1}\) denotes the incidence matrix of a Skew–Hadamard \((4t – 1,2t – 1,t – 1) -\)design.
Corollary 3.2. For \(N_{1} = N_{4t – 1},N_{2} = I_{4t – 1},\) we get a series of STD \((4t – 1)\) RDs with parameters:
\[\tag{3} v = b = m(4t – 1),r = k = m + 2t – 2,\lambda_{1} = t – 1,\lambda_{2} = m – 2,\lambda_{3} = 1,m,n = 4t – 1.\]
Proof. For \(N_{1} = N_{4t – 1},N_{2} = I_{4t – 1},\) we have \(N_{1}N_{2}^{T} + N_{2}N_{1}^{T} = I_{4t – 1}^{c}.\) Hence, \(N = I_{m} \otimes N_{1} + I_{m}^{c} \otimes N_{2}\) represents an RD with above mentioned parameters (3). \(\square\)
Example 3.3. For \(t = 2,\) we have \(N_{1} = circ.\ (0\ 1\ 1\ 0\ 1\ 0\ 0),N_{2} = I_{7}.\) Consider the block matrix \[\notag N = \begin{pmatrix} N_{1} & I_{7} & I_{7} & I_{7} \\ I_{7} & N_{1} & I_{7} & I_{7} \\ I_{7} & I_{7} & N_{1} & I_{7} \\ I_{7} & I_{7} & I_{7} & N_{1} \end{pmatrix}.\]
Then \(N\) represents a STD \((7)\) RD with parameters: \(v = b = 28,r = k = 6,\lambda_{1} = 1,\lambda_{2} = 2,\lambda_{3} = 1,m = 4,n = 7,\) which reduces to a group divisible design.
Corollary 3.4. For \(N_{1} = I_{4t – 1} + N_{4t – 1},N_{2} = I_{4t – 1},\) we get a series of STD \((4t – 1)\) RDs with parameters:
\[\tag{4} v = b = m(4t – 1),r = k = m + 2t – 1,\lambda_{1} = t,\lambda_{2} = m,\lambda_{3} = 1,m,n = 4t – 1.\]
Proof. For \(N_{1} = I_{4t – 1} + N_{4t – 1},N_{2} = I_{4t – 1},\) we have \(N_{1}N_{2}^{T} + N_{2}N_{1}^{T} = 2I_{4t – 1} + I_{4t – 1}^{c}.\) Hence, \(N = I_{m} \otimes N_{1} + I_{m}^{c} \otimes N_{2}\) represents an RD with above mentioned parameters (4). \(\square\)
Example 3.5. For \(t = 2,\) we have \(N_{1} = circ.\ (0\ 1\ 1\ 0\ 1\ 0\ 0),N_{2} = I_{7}.\) Consider the block matrix
\[\notag N = \begin{pmatrix} {I_{7} + N}_{1} & I_{7} & I_{7} \\ I_{7} & {I_{7} + N}_{1} & I_{7} \\ I_{7} & I_{7} & {I_{7} + N}_{1} \end{pmatrix}.\]
Then \(N\) represents a STD \((7)\) RD with parameters: \(v = b = 21,r = k = 6,\lambda_{1} = 2,\lambda_{2} = 3,\lambda_{3} = 1,m = 3,n = 7.\)
The proof of following Theorem 3.6 using mutually orthogonal Latin squares (MOLSs) are described in Singh and Saurabh [30]:
Theorem 3.6. Let \(q\) be a prime or prime power. Then there exist STD \((q)\) RDs with parameters:
\[\left.\begin{aligned} v &= b = q^{2} – q,r = k = (q – 1)^{2},\lambda_{1} = \lambda_{2} = (q – 1)(q – 2),\\ \lambda_{3} &= (q – 1)(q – 2) + 1,m = q – 1,n = q. \end{aligned}\right\} \tag{5}\]
Theorem 3.7. Let \(q\) be a prime or prime power. Then there exists a STD\(\ (q)\) RD with parameters:
\[\tag{6} v = q^{2},b = q(q – 1),r = q – 1,k = q,\lambda_{1} = 0,\lambda_{2} = 0,\lambda_{3} = 1,m = n = q.\]
Proof. It is well known that a \(GH\left( q,\ EA\ (q) \right)\) always exists, where \(EA\ (q)\) is an elementary abelian group of order \(q\), see Launey [8]. We obtain a \(q \times (q – 1)\) matrix \(M\) obtained by deleting first column of \(GH\left( q,\ EA\ (q) \right)\) in the normalized form.
Further, let \(N\) be a \(q^{2} \times q(q – 1)\) matrix obtained from replacing the group elements of \(M\) by corresponding permutation matrices. Then using properties of permutation matrices, we have
(i) \(J_{q^{2}}N = qJ_{q^{2} \times q(q – 1)};\)
(ii) \(NN^{T} = (q – 1)\left( I_{q} \otimes I_{q} \right) + \left( I_{q}^{c} \otimes I_{q}^{c} \right)\), where \(I_{q}^{c} = (J – I)_{q}.\)
Hence, \(N\) represents an RD with above mentioned parameters (6). \(\square\)
Further, removing any \(t( > 1)\) rows of blocks of the incidence matrix of RD with parameters (6), we obtain:
Corollary 3.8. Let \(q\) be a prime or prime power. Then there exists a STD\(\ (q)\) RD with parameters:
\[v = q(q – t),b = q(q – 1),r = q – 1,k = q – t,\lambda_{1} = 0,\lambda_{2} = 0,\lambda_{3} = 1,m = q – t,n = q. \tag{7}\]
Proof. Let \(N = \left\lbrack N_{ij} \right\rbrack_{\begin{array}{r} 1 \leq i \leq q \\ 1 \leq j \leq (q – 1) \end{array}}\) be the incidence matrix of the RD with parameters (6), where each \(N_{ij}\) is a permutation matrix of size \('q'\). Let\(\ M\) be a matrix obtained by removing \('t'\) rows of blocks of \(N\). Since each column sum of \(N_{ij}\) is one, each column sum of the block matrix \(M\) is \(q – t\) i. e. \[\notag J_{q^{2} – qt}M = (q – t)J_{{(q}^{2} – qt) \times q(q – 1)}.\]
Clearly \(M\) also satisfies the condition (ii) as the same condition is preserved even after removing \('t'\) rows of blocks of \(N\). Then we have
\(MM^{T} = (q – 1)\left( I_{q – t} \otimes I_{q} \right) + \left( I_{q – t}^{c} \otimes I_{q}^{c} \right)\), where \(I_{q}^{c} = (J – I)_{q}.\)
Hence, \(M\) represents an RD with above mentioned parameters (7). \(\square\)
Remark 3.9. If \(q\) is a prime then the incidence matrix \('N'\) of the STD\(\ (q)\) RD of Theorem 3.7 is given as: \[\notag N = \begin{pmatrix} I_{q} & I_{q} & \cdots & I_{q} \\ \alpha & \alpha^{2} & \cdots & \alpha^{q – 1} \\ \alpha^{2} & \left( \alpha^{2} \right)^{2} & \cdots & \left( \alpha^{q – 1} \right)^{2} \\ \vdots & \vdots & \ddots & \vdots \\ \alpha^{q – 1} & \left( \alpha^{2} \right)^{q – 1} & \cdots & \left( \alpha^{q – 1} \right)^{q – 1} \end{pmatrix},\] where \(\alpha = circ\ (0\ 1\ldots 0)\ such\ that\ \alpha^{q} = I_{q}\ and\ \alpha^{i} = circ\ (0\ 0\ldots 0\ 1\ 0\ldots 0)\) is a permutation circulant matrix of order \(q\ \)with 1 situated at \((i + 1) – th\) position.
Example 3.10. For \(q = 5.\) the following block matrix represents an RD with parameters: \(v = 25,b = 20,r = 4,k = 5,\lambda_{1} = \lambda_{2} = 0,\lambda_{3} = 1,m = n = 5,\) where \(\alpha = circ\ (0\ 1\ 0\ 0\ 0)\) is a permutation circulant matrix of order 5. \[\notag N = \begin{pmatrix} I_{5} & I_{5} & I_{5} & I_{5} \\ \alpha & \alpha^{2} & \alpha^{3} & \alpha^{4} \\ \alpha^{2} & \alpha^{4} & \alpha & \alpha^{3} \\ \alpha^{3} & \alpha & \alpha^{4} & \alpha^{2} \\ \alpha^{4} & \alpha^{3} & \alpha^{2} & \alpha \end{pmatrix}.\]
Further, removing any row of blocks of \(N\), we obtain an RD with parameters: \(v = b = 20,r = k = 4,\lambda_{1} = \lambda_{2} = 0,\lambda_{3} = 1,m = 4,\ n = 5.\)
Theorem 3.11. There exists a STD \((4t – 1)\) RD with parameters:
\[v = b = 5(4t – 1),r = k = 8t – 3,\lambda_{1} = 4(t – 1),\lambda_{2} = 2t – 1,\lambda_{3} = 3t – 1,m = 5,n = 4t – 1. \tag{8}\]
Proof. Let \(N\) be the incidence matrix of a skew\(-\)Hadamard \((4t – 1,\ 2t – 1,\ t – 1) -\)design. Consider a block matrix: \[\notag M = \begin{pmatrix} I_{4t – 1} & N & N & N^{T} & N^{T} \\ N & I_{4t – 1} & N^{T} & N^{T} & N \\ N & N^{T} & I_{4t – 1} & N & N^{T} \\ N^{T} & N^{T} & N & I_{4t – 1} & N \\ N^{T} & N & N^{T} & N & I_{4t – 1} \end{pmatrix}.\]
Then we have
(i) \(J_{5(4t – 1)}M = (8t – 1)J_{5(4t – 1)};\)
(ii) \(NN^{T} = r\left( I_{m} \otimes I_{n} \right) + \lambda_{1}\left( I_{m} \otimes I_{n}^{c} \right) + \lambda_{2}\left( I_{m}^{c} \otimes I_{n} \right) + \lambda_{3}\left( I_{m}^{c} \otimes I_{n}^{c} \right)\), where \[\notag I_{m}^{c} = (J – I)_{m},r = 8t – 3,\ \lambda_{1} = 4(t – 1),\lambda_{2} = 2t – 1,\lambda_{3} = 3t – 1.\]
Hence, \(N\) represents an RD with above mentioned parameters (8). \(\square\)
Example 3.12. For \(t = 3\), \(N = circ\ (\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0)\) represents a skew\(-\)Hadamard \((11,\ 5,\ 2) -\) design. Hence, we obtain a STD \((11)\) RD with parameters: \(v = b = 55,r = k = 21,\lambda_{1} = 8,\lambda_{2} = 5,\lambda_{3} = 8,m = 5,n = 11.\)
Corollary 3.13. The complement of \(M:\) \(M^{c} = J_{5(4t – 1)} – M\) represents a STD \((4t – 1)\) RD with parameters \(v = 5(4t – 1),k = 2(6t – 1),\lambda_{1} = 8t – 3,\lambda_{2} = 6t,\lambda_{3} = 7t,m = 5,n = 4t – 1.\)
Theorem 3.14. Let \(q\) be a prime or prime power. Then there exists a STD \((q)\) RD with parameters:
\[\tag{9} v = q^{2} – q,k = 2(q – 1),\lambda_{1} = {2,\lambda}_{2} = q – 1,\lambda_{3} = 3,m = q – 1,n = q.\]
The proof of Theorem 3.14 is based on MOLSs. Some series of tactical decomposable RD families in which all internal block matrices are not square are given below:
Theorem 3.15. [Sinha et al. [31], Th. 2.5] The existence of a BIB design with parameters: \(v^{'},b^{'},r^{'},k^{'},\lambda^{'}\) implies the existence of an RD with parameters:
\[\tag{10}\left\{ \begin{aligned} v &= 2v^{'},b = 2\left( b^{'} – r^{'} \right),r = b^{'} – r^{'},k = v^{'},\lambda_{1} = 0,\\ \lambda_{2} &= b^{'} – 2r^{'} + \lambda^{'},\lambda_{3} = r^{'} – \lambda^{'},m = v^{'},n = 2. \end{aligned}\right.\]
Proof. Let \(N\) be the \(v^{'} \times b^{'}\) incidence matrix of a BIB design with parameters: \(v^{'},b^{'},r^{'},k^{'},\lambda^{'}\).
Consider the following block matrix: \[\notag M = \begin{pmatrix} N & J_{v^{'} \times \left( b^{'} – 2r^{'} \right)} \\ J_{v^{'} \times b^{'}} – N & O_{v^{'} \times \left( b^{'} – 2r^{'} \right)} \end{pmatrix},\] where \(O_{v^{'} \times \left( b^{'} – 2r^{'} \right)}\) is a null matrix of order \(v^{'} \times \left( b^{'} – 2r^{'} \right).\) Then we have
(i) \(J_{2v^{'}}N = v^{'}J_{2v^{'} \times 2\left( b^{'} – r^{'} \right)};\)
(ii) \(NN^{T} = (b^{'} – r^{'})\ \left( I_{v^{'}} \otimes I_{2} \right) + (b^{'} – 2r^{'} + \lambda^{'})\left( I_{v^{'}}^{c} \otimes I_{2} \right) + (r^{'} – \lambda^{'})\left( I_{v^{'}}^{c} \otimes I_{2}^{c} \right)\); \(I_{m}^{c} = (J – I)_{m}.\)
Hence, \(M\) represents an RD with above mentioned parameters (10). \(\square\)
Theorem 3.16. [Sinha and Kageyama [13], Th. 2.3] The existence of a BIB design with parameters: \(v^{'} = m,b^{'},r^{'},k^{'},\lambda^{'}\) implies the existence of an RD with parameters:
\[\tag{11} \left\{\begin{aligned} v &= mn,b = nb^{'},r = (n – 1)r^{'} + b^{'},k = (n – 1)k^{'} + v^{'},\\ \lambda_{1} &= nr^{'},\lambda_{2} = (n – 1)\lambda^{'} + b^{'},\lambda_{3} = (n – 2)\lambda^{'} + 2r^{'}. \end{aligned}\right.\]
Proof. Let \(N\) be the \(m \times b^{'}\) incidence matrix of a BIB design with parameters: \(v^{'} = m,b^{'},r^{'},k^{'},\lambda^{'}\). Consider the following block matrix: \(M = {(J – I)}_{n} \otimes N + I_{n} \otimes J_{m \times b^{'}}.\)
Then we have
(i) \(J_{mn}N = \{(n – 1)k^{'} + v^{'}\} J_{mn \times nb^{'}};\)
(ii) \(NN^{T} = \{(n – 1)r^{'} + b^{'})\}\left( I_{m} \otimes I_{n} \right) + \lambda_{1}\left( I_{m} \otimes I_{n}^{c} \right) + \lambda_{2}\left( I_{m}^{c} \otimes I_{n} \right) + \lambda_{3}\left( I_{m}^{c} \otimes I_{n}^{c} \right)\); \(I_{m}^{c} = (J – I)_{m}\), where \(\lambda_{1} = nr^{'},\lambda_{2} = (n – 1)\lambda^{'} + b^{'},\lambda_{3} = (n – 2)\lambda^{'} + 2r^{'}.\)
Hence, \(M\) represents an RD with above mentioned parameters (11). \(\square\)
Theorem 3.17. [Sinha and Kageyama [13], Th. 2.4] The existence of a BIB design with parameters: \(v^{'} = m,b^{'},r^{'},k^{'},\lambda^{'}\) implies the existence of an RD with parameters:
\[\tag{12}\left\{ \begin{aligned} v &= mn,b = nb^{'},r = (n – 2)r^{'} + b^{'},k = (n – 2)k^{'} + v^{'},\\ \lambda_{1} &= (n – 2)r^{'},\lambda_{2} = b^{'} – 2r^{'} + n\lambda^{'},\lambda_{3} = (n – 4)\lambda^{'} + 2r^{'}. \end{aligned}\right.\]
Proof. Let \(N\) be the \(m \times b^{'}\) incidence matrix of a BIB design with parameters: \(v^{'} = m,b^{'},r^{'},k^{'},\lambda^{'}\). Consider the following block matrix: \(M = {(J – I)}_{n} \otimes N + I_{n} \otimes (J_{m \times b^{'}} – N).\)
Then we have
(i) \(J_{mn}N = \{(n – 1)k^{'} + v^{'}\} J_{mn \times nb^{'}};\)
(ii) \(NN^{T} = \{(n – 2)r^{'} + b^{'})\}\left( I_{m} \otimes I_{n} \right) + \lambda_{1}\left( I_{m} \otimes I_{n}^{c} \right) + \lambda_{2}\left( I_{m}^{c} \otimes I_{n} \right) + \lambda_{3}\left( I_{m}^{c} \otimes I_{n}^{c} \right)\); \(I_{m}^{c} = (J – I)_{m}\), where \(\lambda_{1} = (n – 2)r^{'},\lambda_{2} = b^{'} – 2r^{'} + n\lambda^{'},\lambda_{3} = (n – 4)\lambda^{'} + 2r^{'}.\)
Hence, \(M\) represents an RD with above mentioned parameters (12). \(\square\)
Let \(\mathcal{K}\) be a finite key space and \(P\) be a finite set of participants. In a secret sharing scheme, a special participant \(D \notin P\), called the dealer, secretly chooses a key \(K \in \mathcal{K}\) and distributes one share or shadow from the share set \(S\) to each participant in a secure manner, so that no participant knows the shares given to other participants. A \((t,\ n) -\)threshold scheme is a secret sharing scheme in which if any \(t( \leq n)\) or more participants pool their shares, where \(n = |P|\), then they can reconstruct the secret key \(K \in \mathcal{K}\), but any \(t – 1\) or fewer participants can gain no information about it.
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 \(n = 3\), \(t = 2\), op. cit. Stinson and Vanstone [33], Stinson [32].
Pieprzyk and Zhang [16] obtained ideal (t, w) \(-\)threshold schemes from \(b^{t} \times (n + 1)\) orthogonal array \(OA\ (b^{t},\ n + 1,\ b,\ t)\) by considering \(OA\ (i,j)\) as the shares of participants \(P_{j}\ (1 \leq j \leq n)\) and \(OA\ (i,0)\) as a secret key \((1 \leq i \leq b^{t})\) where \(OA\ (i,j)\) denotes the entry in the \(i^{th}\) row and \(j^{th}\) column of \(OA\ (b^{t},\ n + 1,\ b,\ t)\). Stinson and Vanstone [33] obtained perfect threshold schemes from Steiner system \(S(t,\ w,\ v)\). Adachi and Lu [1] constructed \((3,\ 3) -\)threshold schemes from magic cubes by considering magic cube as a secret key and the corresponding three cubes as the shadows.
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 [22, 26]. A recent survey on threshold schemes from combinatorial designs may be found in Bose [6]. Recently Saurabh [20] obtained \((2,\ n) -\)threshold schemes from tactical decomposable regular GD designs. The schemes used here are presented below:
Scheme 1. Consider a STD \((n)\) matrix \(N\) whose each submatrix is of size \(n\). Then there are \(m\) rows of blocks and \(\frac{m(m – 1)}{2}\) pairs of rows in \(N\). The dealer provides arbitrary pair \((R_{i},R_{j})(1 \leq i \neq j \leq \frac{m(m – 1)}{2})\) of rows to any two participants as their shares. Two participants can reveal the secret if their shares \(R_{i}\) and \(R_{j}\) are any arbitrary pair of orthogonal rows of the STD \((n)\) RD design i. e.
\[\notag R_{i}R_{j}^{T} = \left\{ \begin{array}{r} rI_{n} + \lambda_{1}(J – I)_{n};i = j \\ \lambda_{2}I_{n} + \lambda_{3}(J – I)_{n};i \neq j \end{array} \right.\ = \left\{ \begin{array}{r} (r – \lambda_{1})I_{n} + \lambda_{1}J_{n};i = j, \\ (\lambda_{2} – \lambda_{3})I_{n} + \lambda_{3}J_{n};i \neq j. \end{array} \right.\ \]
Hence, corresponding to a STD \((n)\) RD, we obtain a \(\left( 2,\ \frac{m(m – 1)}{2} \right) -\)threshold scheme. Proceeding similarly, a \(\left( 2,\ \frac{n(n – 1)}{2} \right) -\)threshold scheme can also be obtained from STD \((n)\) \(L_{2}\) designs based on \(n\) elements. Some recent constructions of STD \((n)\) \(L_{2}\) designs are available in Saurabh and Sinha [23] and Saurabh [19]. Clearly, the tactical decomposable RDs families given in Section 3 correspond to \(\left( 2,\ \frac{m(m – 1)}{2} \right) -\)threshold schemes.
Example 4.1. For \(q = 27\) in Theorem 3.7 (see Section 3), we obtain a STD \((27)\) RD with parameters: \(v = b = 702,r = k = 676,\lambda_{1} = \lambda_{2} = 650,\lambda_{3} = 651,m = 26,n = 27\).
Then the incidence matrix of STD \((27)\) RD with above mentioned parameters contains 26 orthogonal rows of blocks which can be used to obtain a \((2,\ 325) -\)threshold scheme.
Scheme 2. Consider an uniform column STD \((n)\) matrix \(N\) whose each submatrix is of size \(n\). Then there are \(m\) rows of blocks and \(_{t}^{m}C = \frac{m!}{t!(m – t)!}\) ‘\(t -\)combinations’ of rows in \(N.\)
Then \(N\) may be decomposed as: \(N = \left\lbrack N_{ij} \right\rbrack_{1 \leq i,j \leq m}\), where each \(N_{ij}\) is of size \(n\). Let each \(N_{ij}\) has constant column sum, say \(s\) i. e. \(J_{n}N_{ij} = sJ_{n}.\)
The dealer provides \(t -\)combinations of rows \(R_{i}(1 \leq i \leq \frac{m!}{t!(m – t)!})\) of blocks of \(N\) to \('t'\) participants as their shares. Then \(t( \leq m)\) participants can reveal the secret if their shares are arbitrarily chosen \('t'\) orthogonal rows of the uniform column STD \((n)\) RD design and each column sum of shares of the participants is \(ts\) (constant) i. e. \(\sum\limits_{i = 1}^{t}N_{ij} = ts\ (1 \leq j \leq m)\). Hence, we obtain a \(\left( t,\ \frac{m!}{t!(m – t)!} \right) -\)threshold scheme.
Example 4.2. For \(q = 11\) in Theorem 3.7 (see Section 3), we obtain an uniform column STD \((11)\) RD with parameters: \(v = 121,b = 110,r = 10,k = 11,\lambda_{1} = 0,\lambda_{2} = 0,\lambda_{3} = 1,m = n = 11\). This design can be used to obtain a \((5,\ 462) -\)threshold scheme for \(t = s = 5\), where \(_{5}^{11}C = 462.\)
A binary \((m,n,\ \rho,\mu) -\)regular low–density parity–check (LDPC) code is the null space of an \(m \times n\) \((m < n)\) sparse \((0,\ 1)\) parity–check matrix \(H\) over a Galois field GF (2) of order 2 such that each row has \(\mu\) nonzero elements and each column has \(\rho\) nonzero elements where \(\mu \ll n\) and \(\rho \ll m\), where \(m\) and \(n\) are the number of parity–check equations and code length respectively. LDPC codes are the codes specified by a matrix containing mostly 0’s and relatively few 1’s.
The minimum distance of a code is equal to the minimum number of nonzero columns in the parity–check matrix such that a nontrivial linear combination of these columns sums to zero over GF (2), see Wicker [38, p. 84] and Johnson and Weller [12, p. 1416]. The code rate is given as \(\frac{(n – rank(H))}{n}\) and the code dimension is \(n – rank(H)\), where \(rank(H)\) is calculated over GF (2). Further, for a given a parity–check matrix: \(H = \left( h_{ij} \right)_{\begin{array}{r} 1 \leq i \leq m \\ 1 \leq j \leq n \end{array}}\), an \(n -\)tuple \(v = \left( v_{1},\ v_{2},v_{3}\ldots,v_{n} \right)\) is a code word if and only if the value of the expression \(T = \sum\limits_{j = 1}^{n}{\lbrack h_{ij}v_{j}\mod2\rbrack},\) where \(1 \leq i \leq m,\) is the zero vector.
The LDPC code may also be represented by a Tanner bipartite graph. A cycle in a graph is a sequence of connected vertices with same initial and terminal vertex and no other vertex appears more than once. The number of edges is the length of the cycle and length of the smallest cycle is girth of a graph. Since the Tanner graph is bipartite, the length of a cycle must be even and at least four.
An LDPC code performs well with iterative decoding if the corresponding Tanner graph is free of short cycles, mainly four cycles. These short cycles limit the performance of iterative decoding. The iterative decoding becomes correlated after two iterations for these cycles. Hence, the four length cycles should be avoided in code construction, see Bonello et al. [5], Mostari and Ahmed [15], Alinejad and Khashyarmanesh [2] and Gholami and Nassaj [10].
A binary regular LDPC code is free of 4–cycles provided the inner product of any two distinct rows (or two distinct columns) of its parity–check matrix \(H\) is at most one which is known as a row–column (RC) constraint on \(H\), see Diao et al. [9], Saurabh and Sinha [27]. This constraint confirms that the girth of the LDPC codes is at least six.
The following result is an extension of Lemma 5.1 of Saurabh and Sinha [24]:
Lemma 5.1. The incidence matrix \('N'\) of an RD with parameters: \(v = mn,b,r,k,\lambda_{1} = 0,\lambda_{2} = 0,\lambda_{3} = 1,m,n\) satisfies RC–constraint and the corresponding LDPC code is free of 4 – cycles.
Proof. Consider an RD design with parameters:
\[v = mn,b,r,k,\lambda_{1} = \lambda_{2} = 0,\lambda_{3} = 1. \tag{13}\]
Let \(B_{i}\) and \(B_{j}\) be any two distinct blocks of the RD with parameters (13). The condition \(\lambda_{1} = \lambda_{2} = 0,\lambda_{3} = 1\) confirms that any two elements occur in either one block or no block, we have \(\left| B_{i} \cap B_{j} \right| \leq 1\). Hence any two distinct columns of the incidence matrix \(N\) have at most one nonzero element common.
Further since for an RD with parameters (13), every pair of elements is contained in at most one block, any two distinct rows of \(N\) have at most one nonzero element common. Thus \(N\) satisfies the RC– constraint. If we consider \(N\) as parity – check matrix then the corresponding LDPC code (or Tanner graph) is free of 4 –cycles. Also since \(N\) is the incidence matrix, its each column sum is \(k\) and each row sum is \(r\). Hence the \((v,\ b,\ k,\ r) -\)LDPC code is regular. \(\square\)
Remark 5.2. Applying same logic to the dual of RD with parameters (13), it can be easily verified that \(N^{T}\ \)also satisfies RC–constraint.
Further, it should be noted that the number of columns in a parity–check matrix should be greater than the number of rows for positive code rate. Let \(N\) be same as defined in Lemma 5.1. Then \(N\) is the parity–check matrix of a \((v,\ b,\ k,\ r) -\)LDPC code (\(v < b\) ) with code rate \(\frac{(b – rank(N))}{n}\) and the code dimension: \(b – rank(N)\), where \(rank(N)\) is calculated over GF (2).
Also \(N^{T}\ \)is the parity–check matrix of a \((b,v,\ r,\ k) -\)LDPC code with (\(b < v\)) with code rate \(\frac{(v – rank\left( N^{T} \right))}{n}\) and the code dimension: \(v – rank\left( N^{T} \right)\), where \(rank\left( N^{T} \right)\) is calculated over GF (2).
Result. In view of Lemma 5.1 and Remark 5.2, we have following results:
The dual of RD with parameters: \(v = q^{2},b = q(q – 1),r = q – 1,k = q,\lambda_{1} = 0,\lambda_{2} = 0,\lambda_{3} = 1,m = n = q\) yields an LDPC code free of 4–cycles with length \(q^{2}\), column weight \(q – 1,\) row weight \(q\), rank over field of order 2\(\ = q^{2} – 2q + 2\) and code rate: \(R = \frac{2(q – 1)}{q^{2}}.\)
The RD design with parameters: \(v = q(q – t),b = q(q – 1),r = q – 1,k = q – t,\lambda_{1} = 0,\lambda_{2} = 0,\lambda_{3} = 1,m = q – t,n = q\) \((t \geq 2)\) yields an LDPC code free of 4–cycles with length \(q(q – 1),\) column weight \(q – t,\) row weight \(q – 1\), rank over field of order 2\(\ = \left( q^{2} – 2q + 2 \right) – (t – 1)(q – 1)\) and code rate:
\[\notag R = \frac{\lbrack(q – 1)(q + t – 1) – \left( q^{2} – 2q + 2 \right)\rbrack}{q(q – 1)}.\]
The ranks in results 1 and 2 are determined using polyfit() function of MATLAB.
Example 5.3. For \(q = 7\) in Result 1 above, we obtain an RD with parameters: \(v = 49,b = 42,r = 6,k = 7,\lambda_{1} = 0,\lambda_{2} = 0,\lambda_{3} = 1,m = n = 7\). The dual of this design yields an LDPC code free of 4–cycles with length 49, column weight 6, row weight 7, rank 37 and rate \(R = 0.24.\)
Example 5.4. For \(q = 31,\ t = 2\) in Result 2 above, we obtain an RD with parameters: \(v = 899,b = 930,r = 30,k = 29,\lambda_{1} = 0,\lambda_{2} = 0,\lambda_{3} = 1,m = 29,n = 31\). Then the design yields an LDPC code free of 4–cycles with length 930, column weight 29, row weight 30, rank 871 and rate \(R = 0.06.\)
Here, a brief survey on tactical decomposable RD families is presented. RDs already have wide applications in statistics and agricultural field experiments. Some applications of RDs in cryptography and coding theory are described here. Tactical decomposable RDs had not been previously used in the constructions of threshold schemes and LDPC codes. RDs provide candidate incidence structures for threshold scheme and LDPC\(-\)code constructions, subject to the additional reconstruction, privacy, rank, and performance analyses.
A binary \(\left( m,n,\rho,\{\mu – 1,\mu\} \right) -\)near regular (NR) LDPC code \(\complement\) of block length \(n\) is the null space of a \(m \times n\) sparse parity–check matrix \(H\) over a Galois field GF (2) such that each row has varying weights \(\mu – 1\) or \(\mu\) and each column has constant weight \(\rho\) where \(\mu,\mu – 1 \ll n\) and \(\rho \ll m\). RDs may also have possible applications in the constructions of NRLDPC codes.
The following aspects of RDs can be investigated further:
(i) Although several series of doubly resolvable group divisible designs are available in the literature, no such series is available for RDs. It would be interesting to obtain some series of doubly resolvable RDs. Doubly resolvable designs are also applicable in coding theory, see Topalova and Zhelezova [35].
(ii) Recently Singh [29] introduced doubly near affine doubly \((\mu,\ \nu) -\)resolvable designs. Interested workers in design theory can obtain some series of such RDs.
(iii) An association scheme (AS) on triples on a set \(\Omega\ \)is a partition of \(\Omega \times \Omega \times \Omega\) satisfying certain regularity properties, see Balmaceda et al. [3]. Some series of RDs based on this AS can be obtained and their applications in statistics, cryptography and coding theory can also be explored.
(iv) Some series of tactical decomposable RD families, in which all internal block matrices are not square, are provided in Section 3 (Theorems: 3.15, 3.16 and 3.17). Such series of designs can also be used in the constructions of threshold schemes.
The author has no financial or non–financial conflict of interest to declare for the research work conducted in this article.
The author is grateful to anonymous reviewers and Dr. M. K. Singh and for their valuable suggestions in improving the content and presentation of the paper. The author is also obliged to Dr. S. N. Topno for determining the rank of some block matrices.
This research received no external funding.
This study is theoretical and does not involve the generation or analysis of datasets.