It is known that an automorphism group \(G\) acting on a symmetric, uniform, and balanced incidence structure \({\cal D}\) has the same number of orbits on the set of points and the set of lines of \({\cal D}\). Moreover, a group \(G\) induces a tactical decomposition of \({\cal D}\). These facts are often used to perform efficient constructions of various combinatorial designs and other incidence structures. In this paper, we use a variation of this approach to construct Hadamard 3-balanced incidence structures by employing an automorphism of order 3. We are also able to reach structures with a small automorphism group.
Combinatorial \(t\)-designs are a central topic in discrete mathematics due to their deep connections with group theory, finite geometries, coding theory, and other branches of combinatorics. While \(2\)-designs are relatively well understood and classified for many parameter sets, \(3\)-designs remain significantly more difficult to construct and analyze.
While within 2-designs every two points lie on \(\lambda\) lines, 3-designs are even more regular having every triple of points lying on the \(\lambda\) lines. Obviously, every \(t\)-design, \(t \ge 2\), is also a \(2\)-design. More precisely, every \(t\)-\((v,k,\lambda)\) is a \(s\)-\((v,k,\lambda_s)\) design, \(0 \leq s \leq t\), where
As an example, note that a design with parameters \(3\)-\((14,4,1)\) is also a \(2\)-design with \(\lambda=6\). The four structures with these parameters and having large automorphism group, are found by N. Mendelsohn [12]. There are several infinite series of 3-designs [4, 10]. A common property of these structures is that they have many more blocks than points.. In particular, a class of 3-designs having parameters
is usually called Hadamard 3-designs. If a Hadamard matrix of order \(4n\) exist, then there is also a \(2\)-design with parameters
Conversely, every design with these parameters corresponds to a Hadamard matrix..
The smallest representative of the family (2) has parameters \(3\)-\((8,4,1)\) and up to isomorphism there is only one such structure whose automorphism group has order \(1344\). An elementary construction of this structure by considering cube vertices is well known. To construct such structures for larger parameters, one usually uses methods based on group action [1, 3, 8]. In particular, one can use the method of tactical decomposition [7, 11]. An overview of classification algorithms for combinatorial designs can be found in [6].
In what follows we perform constructions of Hadamard 3-designs admitting an automorphism of order 3. More precisely, we use a variation of the standard tactical decomposition from [9], in order to obtain structures with small automorphism groups.
Previous computational classifications of block designs frequently relied on relatively large automorphism groups in order to reduce the search space. In contrast, we assume only the existence of an automorphism of order 3. Although this leads to significantly larger computational tasks, it allows the construction of designs with very small automorphism groups, including rigid designs with trivial automorphism group.
An incidence structure is a triple \({\cal I}=({\cal P}, {\cal B}, I)\) where
is a set of points,
is a set of lines or blocks and \(I \subseteq {\cal P} \times {\cal B}\) is an incidence relation. If every point \(p \in {\cal P}\) is incident with the same number \(r\) of lines, the structure \({\cal I}\) is called regular with the degree of regularity equal to \(r\), denoted \(d(p)=r\). Similarly, the structure is uniform, with the degree of uniformity equal to \(k\) if \(d(L)=k, \enspace \forall L \in {\cal L}\). Finally, the structure is balanced if every \(t\) points is on the same number \(\lambda\) of lines. These three properties are not independent: uniformity and balanced property imply the regularity. The order \(n\) of a regular incidence structure is defined as the difference \(n:=r-\lambda\). Uniform and balanced incidence structure is uniquely determined by the 4-tuple of parameters \(\displaystyle t-(v,k,\lambda)\) and it is called \(t\)-design or balanced incomplete block design. When lines \(B_i, i=1,\ldots, b\) are consisted of points, \(B_i=\{p_{i_1},\ldots,p_{i_k}\}\), we write \(B_i=\{i_1i_2\cdots i_k\}\), in short.
Thus, the four parameters, \(t, v, k\) and \(\lambda\), uniquely determine a \(t\)-design \({\cal D}\). We let \({\cal D}_{n}\) denote a class of \(t\)-designs \({\cal D}\) of order \(n\). There are several notable series of \(t\)-designs [10]. For example, a wide class of \(t\)-designs are finite geometries, with finite projective planes and biplanes as the best known representatives.
Recall that an isomorphism on a combinatorial design is a map preserving the structure. We let \({\cal D}=({\cal P},{\cal B},I)\) and \({\cal D’}=({\cal P’},{\cal B’},I’)\) be two \(t\)-designs. A bijection \({\phi}:{\cal P} \cup {\cal B} \to {\cal P’} \cup {\cal B’}\) is an isomorphism if
i) \(\phi\) maps points onto points and blocks onto blocks, and
ii) \((p,B)\in I \Leftrightarrow ({\phi}(p),{\phi}(B))\in I’, \enspace \forall p \in {\cal P}, \enspace \forall B \in {\cal B}.\)
Two \(t\)-designs \(\cal D\) and \(\cal D’\) are isomorphic, \(\cal D \approx \cal D’\), if there exists an isomorphism of \(\cal D\) on \(\cal D’\). An isomorphism of \(t\)-design \(\cal D\) is an automorphism of \(\cal D\). It is known that a set of all automorphisms of \(\cal D\) form a group, which is called a a full automorphisms group and it is denoted by \(Aut({\cal D})\). An automorphism group order \(|Aut({\cal D})|\) is the cardinality of a full automorphism group of \(\cal D\).
Naturally, an incidence structure is represented by its incidence matrix, whose entries define the incidence relation \(I\). We let \({\cal D}=({\cal P}, {\cal B}, I)\) be a \(t\)-design where \({\cal P}= \{ {p_1, \dots ,p_v} \}\) and \({\cal B}= \{ {B_1, \dots ,B_b} \}\) are set of points and set of blocks, respectively. An incidence matrix of \({\cal D}\) is a \(v \times b\) binary matrix \(M=[m_{ij}]\) defined by the rule
Throughout this paper we represent considered Hadamard designs by its incidence matrices.
Sometimes, a design \(\cal D\) is represented by five parameters \(t, v, b, r\) and \(k\), denoted
A remarkable property of an uniform and balanced incidence structure is relationship among these parameters,
To see this, we count the elements of set
in two different ways. Firstly, each \(p \in {\cal P}\) is incident with \(r\) blocks. Thus, \(|S| = v \cdot r\). On the other hand, each of \(b\) blocks contain \(k\) points.
In addition to the mentioned approaches on constructions and classification of \(t\)-designs, recall that the method of tactical decomposition were introduced and applied in papers [2, 5]. In this work we use a variation of the method that is precisely described in [9]. Namely, in the second step of the construction procedure we allow combination not only among cyclic matrices but both cyclic and anticyclic matrices. We denote the basic type of construction by “Cyc” and the second type by “ACyc”. It follows from the definition of an incidence matrix \(M\) of a \(t\)-\((v,b,r,k,\lambda)\) design that it satisfies the following properties:
i) every column contains exactly \(k\) “1”s,
ii) every row contains exactly \(r\) “1”s, and
iii) every \(t\)-tuple of rows intersect in exactly \(\lambda\) “1”s.
In order to carry out the final step of our construction procedure, we develop an algorithm which checks these properties to determine whether a “matrix candidate” is a valid incidence matrix.
In all computations, every admissible tactical decomposition matrix was expanded by a custom C program generating all incidence matrix candidates compatible with the prescribed decomposition. Each candidate was tested against the defining conditions of a Hadamard 3-design. To eliminate isomorphic copies, every obtained design was transformed into its incidence graph and processed using the nauty package of McKay [13]. Canonical labeling was employed to partition the generated designs into isomorphism classes, and only one representative of each class was retained.
For the parameter sets \(3\)-\((12,6,2)\), \(3\)-\((16,8,3)\), \(3\)-\((20,10,4)\), and \(3\)-\((28,14,6)\), all incidence matrices arising from the considered tactical decomposition matrices were exhaustively generated and tested. Consequently, the reported numbers of non-isomorphic designs are exact within the class of designs admitting an automorphism of order 3.
For the parameter set \(3\)-\((24,12,5)\), the number of possible completions became prohibitively large and the search was not exhaustive. Therefore, the results reported in Section 3.2 represent only a partial classification and provide lower bounds on the number of non-isomorphic designs obtained.
The second class of designs \({\cal D}\) in the series (2) has parameters
According to basic properties of the \(3\)-designs, these designs \({\cal D}_9\) have \(b=22\) lines and every point is incident with \(r=11\) lines. In the first step of the construction procedure, we assume that an automorphism \(g \in Aut({\cal D}_9)\) of order 3 acts on \({\cal D}_9\). We obtain two candidates for tactical decomposition matrices, \(T_1\) and \(T_2\), one with four fixed blocks and no one fixed point and another one having three fixed points and four fixed blocks, respectively. When attempting to expand these matrices into incidence matrices of a design, only \(T_2\),
produces valid designs, whereas in the first case no admissible combination of cyclic matrices leads to a valid incidence matrix. Matrix \(T_2\) yields two isomorphic incidence matrices. Related automorphism group order is \(|Aut({\cal D}_9) |= 7920\).
To reach designs with smaller automorphism groups, we carry out constructions in which both cyclic and anticyclic matrices of order 3 are permitted. However, for these parameters of designs this approach results only with already constructed design. The facts presented above prove Theorem 3.1.
Theorem 3.1. There is unique design \({\cal D}_{6}\) with parameters \(3\)-\((12,6,2)\) admitting an action of an automorphism of order \(3\), having the order of the full automorphism group \(|Aut({\cal D}_{6})| = 7920\).
In the same manner we were able to partially classify Hadamard 3-design with parameters \(3\)-\((16,8,3)\), \(3\)-\((20,10,4)\) and \(3\)-\((28,14,6)\). More precisely, we construct all structure of these parameters that admits an automorphism of order 3. We describe it in the following subsection 3.1.
Hadamard designs \({\cal D}_{12}\) of order \(12\) are designs with parameters
These designs have \(v=16\) points and \(b=30\) blocks where every point is incident with \(r=15\) blocks. Every \(t=3\) rows of incidence matrix intersect in \(\lambda=3\) points within these designs. These regularities of the structure of designs \({\cal D}_{12}\) suggest huge number of the inner symmetries, as obtained results confirm. Our method of construction results with \(5\) non-isomorphic \(3\)-designs \({\cal D}_{12}\). We constructed duals with the automorphism group orders of \(2688\), and three designs having \(|Aut({\cal D}_{12})|\) equal to \(1536\), \(9216\) and \(322560\). The incidence matrix of the most symmetric design is depicted in Figure 1 (with “+” instead of 1s and “-” instead of 0s).
These designs \({\cal D}_{12}\) are developed from total of 5 tactical decomposition matrices. In two tactical decomposition matrices, automorphism \(g \in Aut({\cal D}_{12})\) of order 3 fixes one point whereas in the rest of three matrices \(g\) fixes 4 points and 6 blocks. Neither within these designs our second type of construction result with any additional design. These facts are summarized in the following Theorem 3.2.
Theorem 3.2. There are exactly \(5\) non-isomorphic designs \({\cal D}_{12}\) with parameters \(3\)-\((16,8,3)\) admitting an action of the automorphism of order \(3\). The orders of the full automorphism group of these designs are \(1536, 2688, 9216\) and \(322560\). There are dual designs having the automorphism group order \(2688\).
The forth class of designs \({\cal D}\) in the series (2) is the class of designs \({\cal D}_{15}\) with parameters
These designs are consisted from \(b=38\) blocks, where every point is incident with \(r=19\) blocks. An incidence matrix of such design is a \(20 \times 38\) matrix having every three rows intersecting in \(\lambda=4\) points. An automorphism of order \(3\) acts on these designs only forming two fixed points and two fixed blocks. There is a tactical decomposition matrix and it gives three non-isomorphic structures. The automorphism group orders of these designs are \(96\), \(144\) and \(171\).
When performing the “ACyc” type of construction, no one additional structure appears. These facts prove Theorem 3.3.
Theorem 3.3. There are exactly \(3\) non-isomorphic designs \({\cal D}_{15}\) with parameters \(3\)-\((20,10,4)\) admitting an action of the automorphism of order \(3\). Automorphism groups of these designs are of orders \(96, 144\) and \(171\).
Hadamard 3-design of order \(21\) is an uniform and balanced incidence structure with parameters
Thus, an incidence matrix of this structure has size \(28 \times 54\) where every three rows meet at 6 points. The automorphism \(g\) of order \(3\) act on this design on three different ways, fixing:
i) \(1\) point and no one block,
ii) \(4\) points and \(6\) blocks,
iii) \(7\) points and \(12\) blocks.
For these cases we get 5, 3 and 1 matrix of tactical decomposition, respectively. All these matrices were in scope for our algorithm only in case of “Cyc” type of construction (while in “ACyc” case we face too large number of possibilities to check). Obtained results are stated in the following Theorem 3.4. Frequencies of appearing automorphism group order are presented in Table 1. Parameter \(niso\) refers to the number of non-isomorphic structures among constructed incidence matrices.
| \(|Aut(D)|\) | \(niso\) |
|---|---|
| \(3\) | \(152\) |
| \(6\) | \(14\) |
| \(9\) | \(2\) |
| \(12\) | \(1\) |
| \(18\) | \(3\) |
| \(27\) | \(1\) |
| \(39\) | \(1\) |
| \(156\) | \(1\) |
| \(1053\) | \(1\) |
Theorem 3.4. There are exactly \(176\) non-isomorphic designs \({\cal D}_{21}\) with parameters \(3\)-\((28,14,6)\) admitting an action of the automorphism of order \(3\). Automorphism groups of these designs are of orders \(3, 6, 9, 12, 18, 27, 39 156\) and \(1053\).
Now we summarize achieved classification results in Table 2.
| \(n\) | \(t-(v,k,\lambda)\) | \(niso\) |
|---|---|---|
| \(2\) | \(3-(8,4,1)\) | \(1\) |
| \(3\) | \(3-(12,6,2)\) | \(1\) |
| \(4\) | \(3-(16,8,3)\) | \(5\) |
| \(5\) | \(3-(20,10,4)\) | \(3\) |
| \(6\) | \(3-(24,12,5)\) | \(\ge 24\) |
| \(7\) | \(3-(28,14,6)\) | \(176\) |
It is noteworthy that for the parameter set 3-(28,14,6), the overwhelming majority of the obtained designs have very small automorphism groups. In particular, 152 out of 176 non-isomorphic designs have automorphism group of order 3. This suggests that highly symmetric examples are relatively rare within the class of designs admitting an automorphism of order 3.
Hadamard designs \({\cal D}_{18}\) with parameters
have \(b=46\) blocks, where every of \(v=24\) points is incident with \(r=23\) blocks. Every three rows of incidence matrix intersect in \(\lambda=5\) points.
The automorphism \(g\) of order \(3\) act on this design on four different ways, fixing:
i) \(4\) blocks and no one points,
ii) \(10\) blocks and no one points,
iii) \(3\) points and \(10\) blocks, and
iv) \(6\) points and \(10\) blocks.
In case when the automorphism \(g\) fixes \(4\) blocks and no one point, we obtain two tactical decomposition matrices while in every other case there are one tactical decomposition matrix. In the second step of the construction procedure we face difficulty with these designs. Namely, the number of combination to check was too large to be done in practical time. So, here we done only partial classification. We found structures with the automorphism group orders:
Finally, the type “ACyc” of construction is fruitful within Hadamard \(3\)-designs \({\cal D}_{18}\) of order \(18\). In addition to already listed orders, here we obtain designs having \(|Aut({\cal D}_{18})|\) equal to:
More precisely, we constructed 3 designs with trivial automorphism group, 11 designs with the order of automorphism group equal to 4, 5 structure is of orders 8 and 16 and 4 structures have the order of automorphism group equal to 32. Figure 2 shows the incidence matrix of a structure having trivial automorphism group (with “+” instead of 1s and “-” instead of 0s). Thus, there are at least \(62\) designs \({\cal D}_{18}\) with parameters \(3\)-\((24,12,5)\) and at least \(24\) out of them admit an action of the automorphism \(g \in Aut({\cal D}_{18})\) of order \(3\). There are at least \(3\) designs with these parameters having the trivial automorphism group.