Generating binary partial Hadamard matrices

Generating binary partial Hadamard matrices V. Álvarez a, J.A. Armario a, R.M. Falcón a, M.D. Frau a, F. Gudiel a, M.B. Güemes b, A. Osuna a a Dpto. Matemática Aplicada I, Universidad de Sevilla, Spain b Dpto. Álgebra, Universidad de Sevilla, Spain Keywords: Partial Hadamard matrix Hadamard graph Clique Constraint satisfaction problem a b s t r a c t This paper deals with partial binary Hadamard matrices. Although there is a fast simple way to generate about a half (which is the best asymptotic bound known so far, see de Launey (2000) and de Launey and Gordon (2001)) of a full Hadamard matrix, it cannot provide larger partial Hadamard matrices beyond this bound. In order to overcome such a limitation, we introduce a particular subgraph Gtof Ito’s Hadamard Graph ∆(4t) (Ito, 1985), and study some of its properties, which facilitates that a procedure may be designed for constructing large partial Hadamard matrices. The key idea is translating the problem of extending a given clique in Gtinto a Constraint Satisfaction Problem, to be solved by Minion (Gent et al., 2006). Actually, iteration of this process ends with large partial Hadamard matrices, usually beyond the bound of half a full Hadamard matrix, at least as our computation capabilities have led us thus far. 1. Introduction Binary Hadamard matrices consist in {1,−1}-square n×nmatrices Hsuch that HHT=nIn. It may be straightforwardly checked that such a matrix Hmust be of size 1, 2 or a multiple of 4, as soon as three rows are assumed to be mutually orthogonal. Actually, it seems that Hadamard matrices might exist for every order multiple of 4, as the Hadamard Conjecture claims, although this fact remains still open for more than a century (see [10] for further details). From a practical point of view, taking into account possible applications, sometimes there is no need to consider a full Hadamard matrix. In fact, it suffices to meet a large amount of pairwise orthogonal rows. This has originated the interest in constructing binary partial Hadamard matrices, that is, m×4t(1,−1)-matrices PH satisfying PH ·PHT=4tIm, for m≤4t. We call mthe depth of PH. For instance, existence of large partial Hadamard matrices implies large lower bounds on the size of several interesting combinatorial objects, as pointed out in [5]. Unfortunately it seems that their explicit construction is equally hard as well. De Launey proved in [4] that partial Hadamard matrices of size about a third of a full 4t×4tHadamard matrix exist for large t. The proof gives a polynomial time algorithm in tfor constructing such a matrix. Furthermore, De Launey and Gordon proved in [5] that about a half of a Hadamard matrix 4t×4texists for large t, assuming that the Riemann hypothesis is true. The idea was decomposing 2t−ias the sum of iodd prime numbers pi, 2 ≤i≤3, so that the juxtaposition of the corresponding Paley conference matrices provides a partial Hadamard matrix of depth 2 min{pi} + 2. From a theoretical point of view, one could proceed even in a simpler way, avoiding this assumption concerning the Riemann hypothesis, which is just used in order to provide an explicit constructive algorithm working in polynomial time. Actually, given any positive integer t, consider the set PHtof pairs of integers (t1,t2) such that t1≤ ⌊ t 2⌋ ≤ t2,t1+t2=t and some full Hadamard matrices H4t1and H4t2exist of orders 4t1and 4t2, respectively. Let m=max(t1,t2)∈PHtt1. Then a partial Hadamard matrix PH of order 4m×4tmay be straightforwardly constructed, as soon as any full Hadamard matrix of order 4mand a collection of whatever 4mrows of any full Hadamard matrix of order 4(t−m) are juxtaposed. Notice that, as defined, 4mis necessarily close to 2t, since it may rarely occur that systematically no full Hadamard matrices exist of orders 4t1and 4t2, for t1≤t2,t1∼t2,t1+t2=2t, no matter the Hadamard Conjecture has not been proved yet. As a matter of fact, a look at the updated list of integers t<500 for which no Hadamard matrices of order 4tare known (namely, 167,179,223,283,311,347,359,419,443,479,487,491 [7]), supports this idea. Unfortunately, none of these methods can provide a partial Hadamard matrix of depth greater than half of a full Hadamard matrix. The aim of this work is to describe an alternative procedure providing large partial Hadamard matrices as well, hopefully beyond this bound. Actually, this will be the case for the examples we have worked out. The work may be summarized as follows. Partial Hadamard matrices will be naturally identified as cliques of a suitable subgraph of Ito’s Hadamard Graph [11]. This subgraph and its properties will be analyzed in Section 2. From this information, in Section 3the problem of adding a new vertex to a given clique in Gtwill be described as a Constraint Satisfaction Problem, to be solved by means of Minion [8]. Some examples will be provided. Last section will be devoted to conclusions and comments about further work. A brief sketch of the work has been recently exposed in [1], as a result of a substantial progress on a previous work of some of the authors [2]. 2. The graph Gt Hadamard Graphs were introduced by Ito in [11]. Originally they referred to the graph ∆(4t) whose vertices are the (1,−1)-vectors of length 4tconsisting of an even number of 1s. The adjacency relation consists in orthogonality. We call Hadamard graph to the subgraph Gtof ∆(4t) induced by the (1,−1)-vectors simultaneously orthogonal to the three first rows of a normalized Hadamard matrix, ⎛ ⎜ ⎝ 1. . . 1 1 . . . 1 1 . . . 1 1 . . . 1 1. . . 1 1 . . . 1−1. . . −1−1. . . −1 1. . . 1−1. . . −1 1 . . . 1−1. . . −1 . . . . . . . . . . . . ⎞ ⎟ ⎠. These orthogonality conditions characterize straightforwardly the form of the vertices in Gt, as follows. Lemma 1. The vertices of Gtconsist of (1,−1)-vectors of length 4t where the 2t negative entries are distributed so that exactly k, t −k, t −k and k negative entries occur respectively among the ranges [1, . . . , t],[t+1, . . . , 2t],[2t+1, . . . , 3t]and [3t+1, . . . , 4t], for some 0≤k≤t. We may then classify the set of vertices in Gtattending to the number kof negative entries which appear in positions 1 to t. In what follows, a k-vertex (or k-vector) in Gtrefers to a vertex with precisely knegative entries among positions 1 to t. Actually, for the remainder of the paper, it can be assumed that 0 ≤k≤ ⌊ t 2⌋, since any vector vand its negated −vshare a common set of adjacent vertices. It is readily checked that the size of Gt(both in vertices and edges) grows exponentially on t. Lemma 2. In particular, the number of vertices in Gtis |Gt| = t ∑ k=0(t k)4 . Hereafter, for brevity, we will adopt the additive notation for representing Hadamard matrices, so that the 1s turn to 0s and the −1s turn to 1s. This way, k-vectors in Gtare now described as (0,1)-vectors of length 4tconsisting of precisely 2t ones (and hence 2tzeros), which are distributed in the following way: there are exactly kones in positions 1 to t, other t−k ones in positions t+1 to 2t, another t−kones in positions 2t+1 to 3t, the last kones being located in positions 3t+1 to 4t. Each of these k-vectors may be straightforwardly codified as an integer, assuming that the k-vector is the binary representation of a decimal number. Therefore, cliques are codified as lists of integers, each of them being the decimal representation of a binary number consisting of 2tones and length less or equal to 4t. Since cliques of size min Gttranslate to partial Hadamard matrices (m+3)×4t, we would like to search for large cliques in Gt. Since the largest clique in ∆(4t) is at most of size 4t, the largest clique in Gtis at most of size 4t−3. Cliques meeting this upper bound would correspond, in turn, to full 4t×4tHadamard matrices. Amaximum clique is a clique with the maximum cardinality (which is called the maximum clique number). This notion is different from that of maximal clique, which refers to a clique which is not a proper subset of any other clique. Thus, maximal cliques do not need to be maximum ones, though the converse is always true. Concerning cliques in Gt, this means that a partial Hadamard matrix does not need to be a submatrix of a full Hadamard matrix. Given a graph, the maximum clique problem consists in finding a maximum clique, and it is NP-complete [3]. Furthermore, itisknown thatthereis nopolynomial-timealgorithm forapproximatingthe maximum cliquewithin a factorofn1−ϵunless P =NP [9], where nis the number of the vertices of the graph. Moreover, there is no polynomial-time algorithm approximating the clique number within a factor of n (log n)1−ϵunless NP =ZPP [12]. Fortunately, the aim of the paper is not to describe a general purpose algorithm for solving the maximum clique problem. The aspiration is to design an ad hoc algorithm for constructing sufficiently large cliques in Gt. To this end, we need to study the properties of Gtin a more detailed way. Firstly, we describe a procedure for determining a set δvof generators for the adjacency list related to a fixed k-vector v, that is, for those s-vectors wsharing exactly 2tentries with v. Lemma 3. At the first and fourth (resp., the second and third) quarters the number i of coincidences in 1s (resp., in 0s) runs in the range i ∈ [0,min(k,s)]. Lemma 4. At each quarter, the number αiof total coincidences (both in 1s and 0s) satisfies αi=t−s−k+2i, and runs in the range αi∈ [t−s−k,t− |s−k|]. Corollary 1. αi+1=αi+2. Let n=min(k,s). In the conditions above, the set of total coincidences is given by t−s−k=α0<· · · < αn=t−|s−k|. We may now describe the set of s-vectors adjacent to a given k-vector. Proposition 1. The set of vectors that are orthogonal to a given k-vector corresponds to the full set of distributions of vectors satisfying tuples of total coincidences (αi1, αi2, αi3, αi4)such that αi1+αi2+αi3+αi4=2t. Proposition 2. The set of tuples (αi1, αi2, αi3, αi4)which give rise to orthogonal s-vectors are characterized as the solutions of the following system of diophantine equations {x0α0+. . . +xnαn=2t x0+. . . +xn=4 xi∈Z:0≤xi≤4 (2.1) Here, n =min(k,s)and xiindicates how many coincidences of the type αimust occur among the four quarters. We now give a constructive way to solve the system above. Proposition 3. There exists a solution for the system (2.1) if and only if 4α0≤2t≤4αn. Corollary 2. Fixed t and 0≤k,s≤ ⌊ t 2⌋, the set sol of solutions to the system (2.1) may be constructed in the following way: sol ← ∅ α0←t−k−s αn←t− |k−s| for i1from max{α1,2t−3αn}to min{αn,⌊2t 4⌋} with step 2 do for i2from max{i1,2t−i1−2αn}to min{αn,⌊2t−i1 3⌋} with step 2 do for i3from max{i2,2t−i1−i2−αn}to min{αn,⌊2t−i1−i2 2⌋} with step 2 do sol ←sol ∪ {{i1,i2,i3,2t−i1−i2−i3}} od od od Given a tuple (αi1, αi2, αi3, αi4) solution to (2.1), construct the four matrices Nkwhose rows are those vectors satisfying αiktotal coincidences with the corresponding quarter of v. By construction, the juxtaposition of any of the rows of these matrices gives a vector orthogonal to v. Proposition 4. A set δvof generators for the adjacency list of vmay be straightforwardly constructed in terms of matrices of the type above. Proposition 5. Fixed a k-vector v, there exist s-vectors orthogonal to vif and only if s ∈ [⌈ t 2⌉ − k,⌊t 2⌋]. Furthermore, we may straightforwardly precise the number of s-vectors orthogonal to a given k-vector, for some fixed s∈ [⌈ t 2⌉ − k,⌊t 2⌋]. Table 2.1 Rows in Hadamard matrices are s-rows, for s∈ {⌊ t 2⌋ − 1,⌊t 2⌋}. t3 4 5 6 7 8 9 row4 6 5 4 5 4 4 #{s= ⌊ t 2⌋} 8 8 15 11 21 12 26 #{s= ⌊ t 2⌋ − 1}0 4 1 9 3 16 6 Lemma 5. Fixed a valid distribution (i1,i2,i3,i4), the number of s-vectors orthogonal to a given k-vector is given by the expression: (k i1)( t−k s−i1)( k i2)( t−k s−i2)( k i3)( t−k s−i3)( k i4)( t−k s−i4) In particular, this might suggest that large cliques in Gtshould more likely consist of k-vectors, for large values of k, close to ⌊t 2⌋. This seems to be the case in practice, as the following calculations suggest. For each 3 ≤t≤9, we choose at random a Hadamard matrix of order 4tfrom Sloane’s online library [14], say had.12, had16.4,had20.hall.n,had24.pal,had28.pal2,had32.pal,had36.pal2. We now normalize these matrices, by means of the following algorithm. Notice that since just negation and permutation of columns are used, the Hadamard character of the matrix is preserved. Algorithm 1. Hadamard normalization •Negate those columns consisting of a first negative entry. •Now, locate those columns i, 1 ≤i≤2t, consisting of a second negative entry. Similarly, locate those columns j, 2t+1≤j≤4t, consisting of a second positive entry. Interchange them. •Proceed as the step before, now by quarters. As a result, you will obtain a normalized Hadamard matrix. Fixed a ⌊t 2⌋-vector among the rows of these matrices (as indicated in Table 2.1), one may have a look on the range in which the values srun, for the s-vectors defining the remaining rows. Table 2.1 suggests that one should focus on s-vectors for s∈ {⌊ t 2⌋ − 1,⌊t 2⌋}. We take advantage of this fact for speeding the algorithm extending cliques in Gt, as described in the following section. 3. A CSP for extending cliques in Gt As we commented before, finding the maximum clique of a graph is a NP-Hard problem, and consequently exact algorithms for this purpose are infeasible even in case of moderately large problem instances. Therefore most of the efforts to give practical solutions to the maximum clique problem are based on heuristic approaches. The authors themselves tried out some of them in a preliminary work [2]. Unfortunately, no matter the choice of the heuristic is, all of them require to explicitly construct the adjacency lists of the vertices which are considered along the computation. And it is apparent from the precedent section that such a task is intractable for the case of the graph Gt, as soon as tincreases. We describe here a novel and completely different approach. The idea is translating the problem of extending a given clique in Gt, into a Constraint Satisfaction Problem [6] (CSP in brief, hereafter). The constraint satisfaction paradigm pursues solving a problem as the set of simultaneous solutions to a series of constraints completely characterizing the former. As noticed in [6], ‘‘constraints identify the impossible and reduce the realm of possibilities to effectively focus on the possible, allowing for a natural declarative formulation of what must be satisfied, without expressing how’’. Any model characterizing a CSP consists of a finite set of variables, their finite domains and the constraints to be satisfied. As usual, it often occurs that the same problem may be modeled in different ways, each of them involving possibly different complexities. A careful study of the particular circumstances of the problem should permit discriminating between them. A solution to an instance of CSP is an assignment to each variable, such that all constraints are simultaneously satisfied. Solvers typically find all (or optionally just one) solutions, if any does exist. In our case, an explicit formulation of the CSP relays on the knowledge of the properties of Gtdescribed in the previous section. More specifically, given a clique Cin Gt, we look for an s-vector (condition (C2) below) x=(x1,...,x4t), for the two most promising values of s(condition (C1) below), which is simultaneously orthogonal to every vertex already in the clique (condition (C3) below). Therefore, a model for the CSP consists in the following constraints: (C1) ⌊t 2⌋ − 1≤s≤ ⌊ t 2⌋. (C2) The number of −1s in the ranges (x1, . . . , xt), (xt+1, . . . , x2t), (x2t+1, . . . , x3t) and (x3t+1, . . . , x4t) are s,t−s,t−sand s, respectively. (C3) The number of coincidences of vwith each of the vertices already in Cis 2t. Once a model is fixed, the following step consists in carrying it into a solver. A translation of the constraints defining the model into the syntaxis of the solver is needed. In this paper we make use of Minion [8], one of the fastest and most scalable constraint solvers using the ‘‘model and run’’ methodology. Actually, this solver is based on the common technique of alternating between splitting and propagation. The key point here is that splitting is minimized in practice by effective propagation, since the former inherits an exponential-time solution method. Nevertheless, unlike most other constraint solvers, Minion does not break up constraints into smaller pieces, neither introduce new variables nor simplify or manipulate constraints. Typically, a depth-first chronological backtracking is performed by default. But few further information is available about the internals of Minion’s performance. In essence, it is a black box from the user point of view, deliberately providing few options, but guaranteeing raw speed in return. Minion expects to be provided with the name of an input file .min as an argument. This file contains a specification of the CSP to be solved (in terms of variables and constraints, to be declared in separated sections) as well as settings that the search process should use (a number of switches are supported to augment default behavior). The constraints section consists of any number of constraint declarations on separate lines, constructed from the limited range of elementary constraints which are available. Four different variable types may be declared. Sorted by speed of performance, boolean (BOOL) variables operate faster, followed by discrete (DISCRETE), delimited domains (BOUND), and arbitrary ranges of integers (SPARSEBOUND). If no variable ordering is explicitly stated, then one is generated based on the order the variables are declared. Obviously, depending on the choice of the ordering, the time required for finding a solution may vary in a significant way. The interested reader is referred to [8,13] for more information concerning Minion. We now describe the way in which the CSP for extending a given clique Cin Gthas been formalized into Minion syntax. Three variables are considered. The desired vertex x=(x1, . . . , x4t) which might potentially extend the clique Cis codified as a boolean matrix xof 4×tunknowns, the row irelated to the range of coordinates x(i−1)t+1, . . . , xit, for 1 ≤i≤4. Assuming the advantages commented in the precedent section, a discrete variable s DISCRETE s {⌊t 2⌋ − 1..⌊t 2⌋} provides straightforwardly a simple way to fulfill the constraint (C1). Conditions (C2) are codified in terms of the constraint occurrence(vec,elem,count), which ensures that there are count occurrences of the value elem in the vector vec. This way, the set of constraints ocurrence([x[0,_]],1,s) ocurrence([x[1,_]],0,s) ocurrence([x[2,_]],0,s) ocurrence([x[3,_]],1,s) characterizes that the vertex xwhich we are looking for defines an s-vector. Finally, translating the relations (C3) requires a more sophisticated elaboration, which combines the use of the constraint element(vec,i,e) and the constraint reify(cons,r). The former specifies that, in any solution, vec[i] = e. The latter ensures that the boolean variable ris set to 1 if and only if the constraint cons is satisfied. Consider a boolean matrix coin[|C|,4t], whose ith-row will keep trace of the entrywise coincidences of xand the ith vertex of C, so that coin[i−1,j−1] = 1 if and only if x[⌊j−1 t⌋,(j−1) mod t] = C(i,j). As soon as the ith-row of coin consists of exactly 2tones, then the vertex xwill be orthogonal to the vertex iin C. Therefore, the relations (C3) are codified as |C|blocks of 4t+1 constraints of the type: reify(element(x[0,_],0,C(i,1)),coin[i−1,0]) . . . reify(element(x[0,_],t−1,C(i,t)),coin[i−1,t−1]) . . . reify(element(x[3,_],4t−1,C(i,4t)),coin[i−1,4t−1]) ocurrence([coin[i−1,_]],1,2t) Obviously, it is far from being operative that all these constraints are introduced by hand, step by step. Nevertheless, it is preferable to make use of some programming language and design a small executable file which, provided Cas input data, straightforwardly generates the full code of the Minion file .min to be executed in turn. We have performed 10 searches for each tin the range 3 ≤t≤11. In all cases, starting from a vertex randomly generated, the procedure has consisted in iteratively trying to add a new vertex to the structure already constructed, until the CSP fails to provide a new vertex. Table 3.2 resumes the average time (Av.T.) for each of these calculations, as well as the smallest (Sm.) and largest (Lg.) sizes of the cliques found so far. Notice that for small tfull or almost full Hadamard matrices have been found, and for large tcliques have been found around the bound 2t. 4. Conclusions and further work In this paper a new way of generating (possibly large) partial Hadamard matrices m×4thas been described. Two are the main novelties of the approach. On one hand, the problem has been translated to the context of Graph Theory, involving the construction of cliques in certain subgraph Gtof Ito’s Hadamard Graph ∆(4t). Secondly, the problem itself of extending a clique has been described as a Constraint Satisfaction Problem. Table 3.2 A summary of the results, involving about 1500 runs of the procedure. tAv.T. Sm. Lg. 3 1′′ 9 9 4 1′′ 12 13 5 1′′ 9 17 6 2′′ 9 21 7 8′′ 10 17 8 39′′ 12 21 9 7′50′′ 14 16 10 1h32′10′′ 15 17 11 8h38′9′′ 14 17 Although the size of the graph Gtcertainly makes the problem untractable even for not so large values of t, in comparison to the work in [2], this approach facilitates extending cliques for larger values of t. Furthermore, for common values of t, it improves either the size of the output clique, or the required time for execution, or even both. As a matter of fact, it is worth noting that the approach itself might be used to extend those cliques described in the introduction, rounding the bound of 2tvertices, obtained by the juxtaposition of most of the rows of two full Hadamard matrices of appropriated sizes t1+t2=t. For instance, progressing from the juxtaposition of two Hadamard matrices of order 16, iteration of the procedure ends providing a full Hadamard matrix of order 32. It takes barely 8 s to add a vertex in each step. Unfortunately, the sizes of the objects which might be of real interest (those related to orders for which no full Hadamard matrices are known) are out of the scope of the actual capabilities for which the community has access to, for the moment. However, as a secondary benefit, the procedure itself as defined might shed light on a new practical way to afford hard problems on Graph Theory, in terms of Constraint Satisfaction Problems accurately designed ad hoc, far beyond the traditional and didactical use of the graph coloring problem for illustrating the typical performance of a CSP. The door is open to many other interesting and potential applications. References [1] V. Álvarez, J.A. Armario, R.M. Falcón, M.D. Frau, F. Gudiel, M.B. Güemes, A. Osuna, Generating partial Hadamard matrices as solutions to a constraint satisfaction problem characterizing cliques. in: Proceedings of X Encuentro Andaluz de Matemática Discreta, pp. 17–20 ISBN: 978-84-697-4743-8, (La Línea, Cádiz, July 10–11 2017). [2] V. Álvarez, J.A. Armario, M.D. Frau, F. Gudiel, M.B. Güemes, E. Martín, A. Osuna, Searching for partial Hadamard matrices, 2012, arXiv:1201.4021 [math.CO]. [3] I.M. Bomze, M. Budinich, P.M. Paradalos, M. Pelillo, in: D.Z. Du, P.M. Paradalos (Eds.), The maximum clique problem, in: Handbook of Combinatorial Optimization, vol. 4, Kluwer, Norwell, MA, 1999. [4] W. de Launey, On the assymptotic existence of partial complex hadamard matrices and related combinatorial objects, Discrete Appl. Math. 102 (2000) 37–45. [5] W. de Launey, D.M. Gordon, A comment on the hadamard conjecture, J. Combin. Theory Ser. A 95 (1) (2001) 180–184. [6] R. Dechter, Constraint Processing, Morgan Kaufmann, 2003. [7] D.v. Ðokovic, O. Golubitsky, I.S. Kotsireas, Some new orders of hadamard and skew-hadamard matrices, J. Combin. Des. 22 (6) (2014) 270–277. [8] I.P.Gent,C.Jefferson,I.Miguel,MINION:afastscalableconstraintsolver,in:G.Brewka,S.Coradeschi,A.Perini,P.Traverso(Eds.),ECAI,IOS,Amsterdam, 2006, pp. 98–102. [9] J. Hastad, Clique is hard to approximate within n1−ϵ, in: Proc. 37th Annu. Symp. Found. Comput. Sci. Burlington, 1996, pp. 627–636. [10] K.J. Horadam, Hadamard Matrices and their Applications, Princeton University Press, 2007. [11] N. Ito, Hadamard graphs i, Graphs Combin. 1 (1) (1985) 57–64. [12] S. Khot, Improved inapproximability results for maxclique, chromatic number and approximate graph coloring, in: Proceedings of 42nd Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2001, pp. 600–609. [13] MINION official site, 2017, https://constraintmodelling.org/minion/. [14] N.J.A. Sloane, The on-line encyclopedia of integer sequences, 2017, http://www2.research.att.com/~njas/hadamard.