Searching for partial Hadamard matrices

´ A Searching for partial Hadamard matrices V´ıctor ´Alvarez · Jos´e Andr´es Armario · Mar´ıa Dolores Frau · F´elix Gudiel · Mar´ıa Bel´en G¨uemes · Elena Mart´ın · Amparo Osuna In honour of Kathy Horadam. In Memoriam: This paper is dedicated to the late Warwick Richard de Launey (Oct. 1, 1958 to Nov. 8, 2010), for his outstanding contributions in Design Theory and related topics. Abstract Three algorithms looking for pretty large partial Hadamard matrices are described. Here “large” means that hopefully about a third of a Hadamard matrix (which is the best asymptotic result known so far, [8]) is achieved. The first one performs some kind of local exhaustive search, and consequently is expensive from the time consuming point of view. The second one comes from the adaptation of the best genetic algorithm known so far searching for cliques in a graph, due to Singh and Gupta [21]. The last one consists in another heuristic search, which prioritizes the required processing time better than the final size of the partial Hadamard matrix to be obtained. In all cases, the key idea is characterizing the adjacency properties of vertices in a particular subgraph Gt of Ito’s Hadamard Graph ∆(4t) [18], since cliques of order m in Gt can be seen as (m + 3) × 4t partial Hadamard matrices. Keywords Hadamard matrix · clique · Hadamard Graph V. lvarez, J.A. Armario, M.D. Frau, F. Gudiel, E. Mart´ın, A. Osuna Dept. Matema´tica Aplicada 1, ETSII, Avda. Reina Mercedes s/n, 41012, Sevilla, Spain Tel.: +34-95455-2797, -4386, -4389, -6225, -2798, -2798 Fax: +34-954557878 E-mail: {valvarez,armario,mdfrau,gudiel,emartin,aosuna}@us.es M.B. Gu¨emes Dept. Algebra, Fac. Matema´ticas, Avda. Reina Mercedes s/n, 41012, Sevilla, Spain Tel.: +34-954556969 Fax: +34-954556938 E-mail: [email protected] 1 Introduction Hadamard matrices consist in {1,−1}-square matrices whose rows are pairwise orthogonal. This nice property makes Hadamard matrices being objects for multiple applications (see [13] and [14] for instance). It may be straightforwardly checked that such a matrix must be of size 1, 2 or a multiple of 4. The Hadamard Conjecture claims that a matrix of this type exists for every size multiple of 4. Many attempts have been devoted to prove this conjecture (both from a constructive way [14] and also from a theoretical point of view in terms of asymptotic results of existence [9,11]), but it remains unsolved so far. From the 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 [2]. This has originated the interest in constructing partial Hadamard matrices P H, that is, m×n(1,−1)-matrices P H satisfying P H ·P HT=nIm, for m≤n. We call mthe depth of P H. From the orthogonality law, it is readily checked that the number nof columns must be 1, 2 or a multiple of 4. Notice that a partial Hadamard matrix does not need to be a submatrix of a proper Hadamard matrix (for instance, cliques listed in Table 3 for 7 ≤t≤10 are maximal but not maximum; in the sense that although no larger cliques exist containing them, there exist larger cliques, for example, those related to full Hadamard matrices). Although partial Hadamard matrices are as useful as Hadamard matrices themselves with regards to practical purposes, unfortunately it seems that their explicit construction is equally hard as well. De Launey proved in [8] that partial Hadamard matrices of size about a third of a 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 [10] that about a half of a Hadamard matrix 4t×4texists for large t, assuming that the Riemann hypothesis is true. The idea is 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. Unfortunately, none of these methods can provide a partial Hadamard matrix of depth greater than half of a full Hadamard matrix. In this paper, we present three new algorithms for constructing partial Hadamard matrices of size m×4t. The first one performs some kind of local exhaustive search, and consequently is expensive from the time consuming point of view. The second one comes from the adaptation of the best genetic algorithm known so far searching for cliques in a graph, due to Singh and Gupta [21]. The third one consists in another heuristic search, which prioritizes the required processing time better than the final size of the partial Hadamard matrix obtained so far. The idea is looking for large cliques (i.e. subgraphs whose vertices are pairwise adjacent) in a subgraph Gtof Ito’s Hadamard Graph ∆(4t) [18]. Although the results showed in [8] and [10] are impressive and meaningfully better than any obtained from the algorithms described in this paper, it is a remarkable fact that our algorithms may provide partial Hadamard matrices of depth greater than half of a full Hadamard matrix. Furthermore, it is possible (and desirable) to run our algorithms taking as input data partial Hadamard matrices obtained by the procedures in [8,10], so that deeper partial Hadamard matrices are constructed (see Table 4.2). The paper is organized as follows. The graph Gtand its properties are described in Section 2. Section 3 is devoted to the description of the local exhaustive algorithm looking for cliques in Gt. In Section 4, the two heuristics searching for cliques in Gtare described. Last section is devoted to conclusions. 2 The graph Gt In what follows, for clarity in the exposition, we will simply use + and − instead of 1 and −1. Hadamard Graphs were introduced by Ito in [18]. 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,     +. . . + + . . . + + . . . + + . . . + +...+ + . . . +−. . . − − . . . − +...+−. . . −+. . . +−. . . − . . . . . . . . . . . .     These orthogonality conditions straightforwardly characterize the form of the vertices in Gt. Lemma 1 The vertices of Gtconsist of (1,−1)-vectors of length 4twhere the 2tnegative entries are distributed following this pattern, t k t t-k t t kt-k so that exactly k,t−k,t−kand knegative entries occur among every t positions, 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 through t. In what follows, ak-vertex in Gtrefers to a vertex with precisely knegative entries among positions 1 to t. Lemma 2 In particular, the number of vertices in Gtis |Gt|= t X k=0 t k4 . The tables below give the number of k-vertices (n.v.) and their degree δ (number of adjacent vertices), for 1 ≤t≤7 and 0 ≤k≤t. The column total refers to the number of vertices and edges in Gt(notice that the number of edges is half the summation of the degree of every vertex). It is evident that for a fixed value of k, every k-vertex has the same degree (since permuting some columns does not affect to the orthogonality relation). Table 1 Vertices and edges in Gt. t1 k0 1 total n.v. 1 1 2 δ0 0 0 t2 k0 1 2 total n.v. 1 16 1 18 δ16 8 16 80 t3 k0 1 2 3 total n.v. 1 81 81 1 164 δ0 64 64 0 5184 t4 k0 1 2 3 4 total n.v. 1 256 1296 256 1 1810 δ1296 648 648 648 1296 587088 t5 k0 1 2 3 4 5 total n.v. 1 625 10000 10000 625 1 21252 δ0 6912 6912 6912 6912 0 73440000 t6 k0123456 total n.v. 1 1296 50625 160000 50625 1296 1 263844 δ160000 80000 79808 79712 79808 80000 160000 10521080000 t7 k0 1 2 3 4 5 6 7 total n.v. 1 2401 194481 1500625 1500625 194481 2401 1 3395016 δ0 960000 960000 960000 960000 960000 960000 0 1629606720000 It is readily checked that the size of Gtgrows exponentially on t. 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(see [17] for details), the largest clique in Gtis at most of size 4t−3. Cliques meeting the upper bound would correspond to full Hadamard matrices. Example 1 For instance, consider the graph G2, obtained from t= 2. The picture below shows a clique of size 5, so that adding the three normalized rows we obtain a full Hadamard matrix of size 8 ×8. (−−++++−−) = 1 (−+−+−+−+) = 2 (−+−+−+ +−) = 3 (−+−+ + − −+) = 4 (−+−+ + −+−) = 5 (−+ + − − +−+) = 6 (−+ + − − + +−) = 7 (−+ + −+− −+) = 8 (−+ + −+−+−) = 9 (+ − − +−+−+) = 10 (+ − − +−+ +−) = 11 (+ − − + + − −+) = 12 (+ − − + + −+−) = 13 (+ −+− − +−+) = 14 (+ −+− − + +−) = 15 (+ −+−+− −+) = 16 (+ −+−+−+−) = 17 (+ + −−−−++) = 18 1 18 2 3 4 5 6 7 8 9 10 1112 13 14 15 16 17  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 need not be maximum ones (as we had already noticed in the introduction), though the converse is always true. Given a graph, the maximum clique problem (MCP) is to find a maximum clique, and it is NP-complete [6]. Unfortunately, there is no polynomial-time algorithm for approximating the maximum clique within a factor of n1−ǫunless P=NP [12], 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 [19]. Anyway, our purpose here is to design an algorithm for constructing sufficiently large cliques in Gt, at least of depth greater than a third of a full Hadamard matrix. To this end, we need to study the properties of Gtin a more detailed way. In what follows, 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 4t consisting of precisely 2tones (and hence 2tzeros), which are distributed in the following way: there are exactly kones in positions 1 through t, other t−k ones in positions t+1 through 2t, another t−kones in positions 2t+1 through 3t, the last kones being located in positions 3t+ 1 through 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 deci- mal representation of a binary number consisting of 2tones and length less or equal to 4t. Lemma 3 Actually, it can be assumed that 0≤k≤ ⌊ t 2⌋. Proof This is a straightforward consequence of the fact that the negation of a row does not affect to the set of its orthogonal vectors. That being so, the full set of vertices adjacent to a given k-vertex vmay be obtained by calculating those s-vectors worthogonal to v, for 0 ≤s≤ ⌊ t 2⌋, and then adding their complements. Notice that with the additive notation at hand, a k-vector vand a s-vector ware orthogonal if and only if they share exactly 2tbits. We now describe a procedure for determining a set δvof generators for the adjacency list related to a fixed k-vector v, that is, generating those s-vectors worthogonal to v. In order to compute the total amount of coincidences between vand w, one may split the vectors by quarters, and count the amount iof 1-bits (for the first and last quarters) and 0-bits (for the second and third quarters) that these vectors share in each of these basic quarters. Lemma 4 At the first and fourth (resp., the second and third) quarters the number iof coincidences in 1s (resp, in 0s) runs in the range [max(0, s +k− t),min(k, s)]. Actually, assuming the conditions in Lemma 3, i∈[0,min(k, s)]. Lemma 5 At each quarter, the number αiof total coincidences (both in 1s and 0s) satisfies αi=t−s−k+2i, and runs in the range [|t−k−s|, t−|s−k|]. Actually, assuming the conditions in Lemma 3, αi∈[t−s−k, t − |s−k|]. Proof Assume that at a given quarter the vectors vand wshare exactly i 1-bits. Then whas k−i0-bits in those positions where the remaining 1-bits of vare located. Analogously, vhas s−i0-bits in those positions where the remaining 1-bits of ware located. Thus vand wshare exactly t−i−(k− i)−(s−i) = t−k−s+i0-bits. Since vand wshare i1-bits and t−k−s+i 0-bits, the total number of coincidences is αi=t−k−s+ 2i. Corollary 1 αi+1 =αi+ 2. Let denote 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 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 (1) Here, n= min(k, s)and xiindicates how many coincidences of the type αi must 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 (1) iff 4α0≤2t≤4αn. Proof From Corollary 1, we know that the difference between two consecutive αijis 2. Since 4α0, 2tand 4αnare even and taking into account Corollary 1, we conclude that every even number in the range [4α0,4αn] may be (not uniquely, in general) written as a combination αi1+αi2+αi3+αi4for some values α0≤αi1≤αi2≤αi3≤αi4≤αn. The condition above may be straightforwardly generalized for the case of solutions related to tuples of the type (αi1, αi2, αi3, αi4), αi1≤αi2≤αi3≤ αi4. Corollary 2 Fixed tand 0≤k, s ≤ ⌊ t 2⌋, the set sol of solutions to the system (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 (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. In spite of the fact that the size (both in edges and vertices) of Gtgrows exponentially in t, the procedure described in Proposition 4 is a cheaper way (in terms of both time and space) of saving this information. We will illustrate now how the proposition above works by means of an example. In order to simplify the reading, in what follows we will use a vertical line |to separate the different quarters of a k-vector. Example 2 Let us consider the case t= 5, k= 2 and v= 684646 (its binary representation gives the 2-vector v= (10100|11100|10011|00110)). We are going to calculate the full set of s-vectors orthogonal to v, for 0 ≤s≤2 = ⌊5 2⌋ (recall that the remaining orthogonal vectors are obtained by simply interchanging the 0-bits and 1-bits, since they are the negation of the vectors just calculated). 1. Case s= 0. From Lemma 4, we know that there is just one value for the number iof coincidences in 1-bits, namely i= 0. Consequently, there is just one value αi, namely α0= 3. Since 4α0= 12 6= 10 = 2 ·5, the system (1) has no solutions, so there is no 0-vector orthogonal to v. This was evident from the very beginning, since there is only one 0-vector, w= 32736 (i.e. w= (00000|11111|11111|00000)), and it is not orthogonal to v. 2. Case s= 1. From Lemma 4, we know that i∈ {0,1}, and hence αi∈ {2,4}. The set of different ways in which four αimay be orderless chosen to sum 10 is described by the system (1), 2x0+ 4x1= 10 x0+x1= 4 Since 4α0= 8 ≤10 ≤4α1= 16, there exist solutions for the system. In fact, there is just one solution, (x0, x1) = (3,1), which corresponds to the following distribution of total coincidences (up to reordering): (2,2,2,4). In order to explicitly construct those 1-vectors wmeeting the distribution (2,2,2,4), we have to find those 1-vectors with 0 coincidences with vin 1-bits in the first quarter, 0 coincidences in 0-bits in the second and third quarters, and 1 coincidence in 1-bits in the fourth quarter. Since vis a 2-vector, in the first quarter there are 5−2 1choices for placing the 1-bit of wamong the 0-bits of v. Analogously, there are 5−2 1 choices for placing the 0-bit of wamong the 1-bits of vin the second and third quarters. And there are 2 1choices for placing the 1-bit of wamong the 1-bits of v. In conclusion, the set of 1-vectors meeting the distribution of total coincidences (2,2,2,4) is generated by the juxtaposition of any of the rows of the following matrices   0 1 0 0 0 0 0 0 1 0 0 0 0 0 1  ×  0 1 1 1 1 1 0 1 1 1 1 1 0 1 1  ×  01111 11101 11110  ×0 0 1 0 0 0 0 0 1 0 Similar schemes are achieved with the remaining orderings of the valid distribution of total coincidences, (2,2,4,2), (2,4,2,2) and (4,2,2,2). In fact, they may be obtained by simply permuting and/or negating some suitable columns of the distribution above. 3. Case s= 2. From Lemma 4, we know that i∈ {0,1,2}, and hence αi∈ {1,3,5}. The set of different ways in which four αimay be orderless chosen to sum 10 is described by the system (1), x0+ 3x1+ 5x2= 10 x0+x1+x2= 4 Since 4α0= 4 ≤10 ≤4α2= 20, there exist solutions for the system. In fact, there are just two solutions, (x0, x1, x2)∈ {(2,1,1),(1,3,0)}, which correspond to the following distribution of total coincidences (up to reordering): (1,1,3,5) and (1,3,3,3). In order to explicitly construct those 2-vectors wmeeting the distribution (1,1,3,5), we have to find those 2-vectors with 0 coincidences with vin 1-bits in the first quarter, 0 coincidences in 0-bits in the second quarter, 1 coincidence in 0-bits in the third quarter, and 2 coincidences in 1-bits in the fourth quarter. Since vis a 2-vector, in the first quarter there are 5−2 2choices for placing the 1-bits of wamong the 0-bits of v. Analogously, there are 5−2 2 choices for placing the 0-bits of wamong the 1-bits of vin the second quarter. Analogously, in the third quarter, there are 2 1choices for placing one 0-bit of wamong the 0-bits of v, and for each of them, there are 5−2 1choices for placing the second 0-bit of wamong the 1-bits of v. Finally, there are 2 2choices (just one!) for placing the 1-bits of wamong the 1-bits of v. In conclusion, the set of 2-vectors meeting the distribution of total coincidences (1,1,3,5) is generated by the juxtaposition of any of the rows of (αi1, αi2, αi3, αi4)), in terms of distributions (i1, i2, i3, i4) of coincidences in 1s (for the first and last quarters) and 0s (for the second and third quarters). Proposition 5 The set of s-vectors orthogonal to a given k-vector corresponds to the full set of distributions of s-vectors satisfying tuples of coincidences in 1s (first and fourth quarters) and 0s (second and third quarters) (i1, i2, i3, i4)such that i1+i2+i3+i4= 2s+ 2k−t. Furthermore, this is possible iff 2s+ 2k−t≥0. Proof From Proposition 1, we know that the set of s-vectors orthogonal to a given k-vector is characterized by those distributions of total coincidences (αi1, αi2, αi3, αi4) such that αi1+αi2+αi3+αi4= 2t. Since αi=t−s−k+ 2ifrom Lemma 5, the relation above comes to be 4t−4k−4s+ 2i1+ 2i2+ 2i3+ 2i4= 2t⇔i1+i2+i3+i4= 2s+ 2k−t. Now, on one hand, since 0 ≤ij≤min(k, s), the value i1+i2+i3+i4runs over the range 0 ≤i1+i2+i3+i4≤4 min(k, s). On the other hand, since 0 ≤s, k ≤ ⌊ t 2⌋, it is clear that 2s+ 2k−t≤ 2 min(k, s). Thus, provided 2s+ 2k−t≥0, this value is in the range valid for i1+ i2+i3+i4, and therefore there exists a distribution of coincidences in 1s (at first and fourth quarters, i1and i4respectively) and 0s (at second and third quarters, i2and i3respectively), such that i1+i2+i3+i4= 2s+ 2k−t. Now it is apparent that not all possible values sin the range 0 ≤s≤ ⌊ t 2⌋ do provide s-vectors orthogonal to a given k-vector. Proposition 6 Fixed a k-vector v, there exist s-vectors orthogonal to viff s∈[⌈t 2⌉ − k, ⌊t 2⌋]. Proof The upper bound is given in Lemma 3. On the other hand, from Proposition 5, there exist s-vectors orthogonal to a given k-vector iff 0 ≤2s+ 2k−t. Consequently, s≥t 2−k, that is, s≥ ⌈ t 2⌉ − k. 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⌋]. Lemma 6 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 Table 6 Distribution of s-vectors orthogonal to a k-vector. t= 3 k= 0 k= 1 s= 0 0 0 s= 1 0 32 t= 4 t= 5 k= 0 k= 1 k= 2 k= 0 k= 1 k= 2 s= 0 0 0 1 0 0 0 s= 1 0 81 96 0 0 216 s= 2 1296 486 454 0 3456 3240 t= 6 t= 7 k= 0 k= 1 k= 2 k= 3 k= 0 k= 1 k= 2 k= 3 s= 0 0 0 0 1 0 0 0 0 s= 1 0 0 256 486 0 0 0 768 s= 2 0 10000 14688 15795 0 0 40000 57024 s= 3 160000 60000 49920 47148 0 480000 440000 422208 t= 8 k= 0 k= 1 k= 2 k= 3 k= 4 s= 0 0 0 0 0 1 s= 1 0 0 0 625 1536 s= 2 0 0 50625 147000 183904 s= 3 0 1500625 2352000 2601000 2655744 s= 4 24010000 9003750 7183750 6483750 6297030 t= 9 k= 0 k= 1 k= 2 k= 3 k= 4 s= 0 0 0 0 0 0 s= 1 0 0 0 0 2000 s= 2 0 0 0 243000 464000 s= 3 0 0 7203000 11210000 12912000 s= 4 0 76832000 69629000 65367000 63430000 t= 10 k= 0 k= 1 k= 2 k= 3 k= 4 k= 5 s= 0 0 0 0 0 0 1 s= 1 0 0 0 0 1296 3750 s= 2 0 0 0 194481 858600 1200625 s= 3 0 0 9834496 32773650 48326400 53560000 s= 4 0 252047376 407209600 453248775 468312600 472003750 s= 5 4032758016 1512284256 1180754176 1041640236 978746976 960098756 The following tables show the number of s-vectors orthogonal to a given k-vector, for 3 ≤t≤10, 0 ≤k≤ ⌊ t 2⌋, and 0 ≤s≤ ⌊ t 2⌋. In particular, these results suggest that large cliques in Gtshould consist of k-vectors, for large values of k, close to ⌊t 2⌋. This seems to be so, as the calculations below suggest. For each 3 ≤t≤9, we choose at random a Hadamard matrix of order 4tfrom Sloane’s online library [22], 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 3 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. 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. Now we randomly fix a ⌊t 2⌋-vector among the rows of these matrices (for instance, the first such occurrence). The table below shows the distribution of the values s, for the s-vectors of the remaining rows. In addition, we also include the distribution of (not ordered!) total coincidences (αi1, . . . , αi4). Table 7 Rows in Hadamard matrices are k-rows, for k∈ {⌊ t 2⌋ − 1,⌊t 2⌋}. trow s=⌊t 2⌋s=⌊t 2⌋ − 1 #{total coincidences} 3 4 8 0 (1,1,1,3) →8 4 6 8 4 (2,2,2,2) →4 (0,2,2,4) →4 (1,1,3,3) →4 5 5 15 1 (1,3,3,3) →12 (1,1,3,5) →3 (2,2,2,4) →1 6 4 11 9 (2,2,4,4) →9 (2,2,2,6) →1 (0,4,4,4) →1 (1,3,3,5) →6 (3,3,3,3) →3 7 5 21 3 (3,3,3,5) →16 (1,3,5,5) →3 (1,3,3,7) →2 (2,2,4,6) →2 (2,4,4,4) →1 8 4 12 16 (2,4,4,6) →12 (3,3,5,5) →12 (1,5,5,5) →2 (3,3,3,7) →2 9 4 26 6 (3,5,5,5) →20 (1,5,5,7) →6 (2,4,6,6) →6 The table above suggests that one should focus on k-vectors for k∈ {⌊ t 2⌋− 1,⌊t 2⌋}. Furthermore, the vector of total coincidences per quarter uses to be homogeneously distributed. With these ideas at hand, we next design a fast heuristic searching for (or eventually extending) cliques in Gt. Algorithm 4 Fast heuristic for extending cliques in Gt. Input: a clique C in Gt Output: a clique C′ in Gt containing C C′=C for kfrom ⌊t 2⌋to ⌊t 2⌋ − 1step −1do iter = 0 while iter < t do {bool,v}=buildgrapas(C′, k) If bool then iter = 0;C′=C′∪ {v}else iter =iter + 1 od od C′ The function buildgrapas tries to construct an s-vector quarter by quarter (in a random ordering), attending to the following aspects: –Select a number of total coincidences for the quarter, according to the range valid at this step (i.e. such that equation (1) can be satisfied), and with probability proportional to the number of its appearances in the set of solutions described in Corollary 2. –Once the desired number of total coincidences has been fixed, a genetic procedure is performed, for constructing a valid quarter (i.e. such that (1) can be satisfied). This heuristic consists of populations of 4tindividuals. If no valid quarter is found after 4tgenerations, the search ends with a failure. In this case, the last quarter constructed so far is deleted, and the process goes on from this point. This situation is limited to occur at most ttimes. –This search is performed at most 10 times. If no valid vector is constructed after these 10 attempts, the search stops and a False boolean is returned. The table below shows, for every 2 ≤t≤10, the number of essays which have been executed looking for cliques in Gt, the average time required in these calculations, the average size of these cliques, the largest size found so far, the time required in this calculation and one instance among the largest cliques already found. Table 8 Results obtained from Algorithm 4. tEssays Av.Time Av.Size Lar.S. Time Clique 2 10 1.4′′ 5 5 1.4′′ 86,101,149,89,60 3 10 0.565′′ 9 9 0.5′′ 1452,2396,1393,874,756,2482,921, 1242,2281 4 10 19.603′′ 11 12 17.28′′ 25542,15462,13769,39626,50538, 22099,38294,22188,22876,52421, 22947,27802 tEssays Av.Time Av.Size Lar.S. Time Clique 5 10 27.369′′ 9 17 76.924′′ 193425,586090,808611,420073 350674,408358,222834,109987, 315192,341833,604856,662897, 171722,308468,121445,218540, 552900 6 10 51.38′′ 7.6 10 56.87′′ 13215089,13015273,10053835,12875531, 12954262,6768979,3454163,9730420, 3324617,6759253,5685752,8874722, 999010,906181 7 10 1′23′′ 8 9 1′46′′ 159860692,161016643,73886147, 142481171,173143250,170760901, 21953176,43986594,203259148 8 10 2′11′′ 7.6 9 2′53′′ 866473426,1497876124,1273533381, 1697995341,1439971764,3784746441, 2345981979,2309832360,242628440 9 10 3′02′′ 7.8 9 3′05′′ 56095030680,38163367817, 41103334725,54854789721, 22744355553,45279148512, 4785499937,52133944916, 60209197830 Although the size of the cliques obtained so far are smaller than those constructed by the precedent procedures, it is a remarkable fact that this algorithm is substantially faster. In fact, this procedure should be considered as an extension function for cliques better than a procedure itself for constructing cliques starting from the empty graph. This idea is supported by the calculations showed in the table below, where cliques Cof size |C| ≤ 2tin Gtconstructed by the procedures described in [8, 10] (after normalization by Algorithm 3) are extended to larger cliques C′(of size |C′| ≥ 2t, more than a half of a full Hadamard matrix!) with Algorithm 4. Table 9 Algorithm 4 applied to P Hm×4tin [10] produces P H(m+n)×4t, with m+n≥2t. t|C| |C′|time added vertices 4 5 12 17.97′′ 21930,50745,25500,13107, 37740,42330,51510 5 5 7 19.38′′ 118659,341714 6 9 15 1′07′′ 3099915,9123660,8841105, 10606050,4844385,4692870 7 9 9 1′03′′ 8 13 17 2′51′′ 1923517785,3032697660, 1695521520,2956808130 Notice that for t= 7, the input clique has not been extended to a larger one. We suspect that the input clique is maximal, and therefore a larger clique containing it could not exist. 5 Conclusions In this paper we have described three algorithms looking for pretty large partial Hadamard matrices (i.e. about a third of a full Hadamard matrix), in terms of cliques of the Hadamard Graph Gt. The first one (Algorithm 1) performed some kind of local exhaustive search, and consequently is expensive from the time consuming point of view. So we decided to design some heuristic for constructing partial Hadamard matrices. Our first approach (Algorithm 2) consisted in an adaptation of Singh and Gupta’s genetic algorithm for the Maximum Clique Problem. Unfortunately, it did not work properly, since it used Algorithm 1 for extending cliques, and consequently was very expensive in time as well. Algorithm 4 prioritizes the required processing time better than the final size of the partial Hadamard matrix to be obtained. Experimental results show that this algorithm may output pretty large partial Hadamard matrices (larger than half a full Hadamard matrix!), provided a suitable initial clique is given as input data. All the algorithms that we have presented here are based on the properties of the Hadamard Graph Gtwhich have been described in Section 2. It would be an interesting question whether different techniques and methods could be considered for designing alternative algorithms searching for large partial Hadamard matrices. For instance, one could ask about the techniques and methods which have been shown to be useful when manipulating full Hadamard matrices. Unfortunately, this will not be the case, in general. For instance, consider the case of the cocyclic approach. More concretely, the cocyclic framework has arised as a promising way to construct (cocyclic) Hadamard matrices [14,1,3,4]. One could ask whether the cocyclic framework is also a good place to look for partial Hadamard matrices. Actually, this is not the case. Proposition 7 The depth of any partial Hadamard matrix which is a submatrix of a cocyclic matrix Mfis at most a half of the size of Mf. Proof Attending to the proof of the cocyclic Hadamard test in [16] (see Lemma 1.4 on p. 281), fixed a multiplicative group G={g1= 1, . . . , gn}and a cocyclic matrix Mf= (f(gi, gj)) over G, rows gi6=gkin Mfare orthogonal if and only if the summation of the row gig−1 k(6=g1) is zero (and consequently, the summation of the row gkg−1 ias well). If a row gk6=g1in Mffails to sum zero, then, for each 1 ≤i≤n, the pair of rows {gi, g−1 kgi}(and also {gi, gkgi}) fails to be orthogonal. By partitioning the rows of Mfinto pairs of the type {gi, g−1 kgi}, it turns out that such a pair contributes at most one row to a partial Hadamard matrix included in Mf. Consequently, the depth of any partial Hadamard matrix which is a submatrix of Mfis at most n 2, as claimed. It would be interesting to think about the way in which k-vertices in Gt could be combined in order to get larger cliques. Nevertheless, it would be also interesting to investigate whether improved versions of the algorithms described in this paper could be designed, attending to other considerations. Acknowledgements All authors are partially supported by the research projects FQM– 016 and P07-FQM-02980 from Junta de Andaluc´ıa and MTM2008-06578 from Ministerio de Ciencia e Innovaci´on (Spain). References 1. V. ´ Alvarez, J.A. Armario, M.D. Frau, P. Real. A genetic algorithm for cocyclic Hadamard matrices. AAECC16, LNCS 3857, 144–153. Springer, Heidelberg, (2006). 2. V. ´ Alvarez, J.A. Armario, M.D. Frau, E. Mart´ın, A. Osuna. Error Correcting Codes from Quasi-Hadamard Matrices. WAIFI07, LNCS 4547, 294–302. Springer, Heidelberg, (2007). 3. V. ´ Alvarez, J.A. Armario, M.D. Frau, P. Real. A system of equations for describing cocyclic Hadamard matrices. Journal of Comb. Des., 16 (4), 276–290, (2008). 4. V. ´ Alvarez, J.A. Armario, M.D. Frau, P. Real. The homological reduction method for computing cocyclic Hadamard matrices. J. Symb. Comput., 44, 558–570, (2009). 5. V. ´ Alvarez, M.D. Frau, A. Osuna: A genetic algorithm with guided reproduction for constructing cocyclic Hadamard matrices. ICANNGA09, LNCS 5495, 150–160. Springer, Heidelberg, (2009). 6. I.M. Bomze, M. Budinich, P.M. Paradalos and M. Pelillo. The maximum clique problem. Handbook of Combinatorial Optimization, D.Z. Du and P.M. Paradalos Eds. Norwell, MA: Kluwer, vol. 4 (1999). 7. R. Carraghan, P.M. Pardalos. An exact algorithm for the maximum clique problem. Oper. Res. Lett., 9, 375–382, (1990). 8. W. de Launey. On the assymptotic existence of partial complex Hadamard matrices and related combinatorial objects. Discrete Applied Mathematics 102, 37–45, (2000). 9. W. de Launey. On the assymptotic existence of Hadamard matrices. Journal of Combinatorial Theory, Series A 116, 1002–1008, (2009). 10. W. de Launey and D.M. Gordon. A comment on the Hadamard conjecture. Journal of Combinatorial Theory, Series A 95 (1), 180–184, (2001). 11. W. de Launey and H. Kharaghani. On the assymptotic existence of cocyclic Hadamard matrices. Journal of Combinatorial Theory, Series A 116, 1140–1153, (2009). 12. J. Hastad. Clique is hard to approximate within n1−ǫ.Proc. 37th Annu. Symp. Found. Comput. Sci., Burlington, 627-636, (1996). 13. A. Hedayat and W.D. Wallis. Hadamard Matrices and Their Applications. Ann. Stat. 6, 1184–1238, (1978). 14. K.J. Horadam. Hadamard matrices and their applications. Princeton University Press, Princeton (2007). 15. K.J. Horadam and W. de Launey. Cocyclic development of designs. J. Algebraic Combin.,2(3), 267–290, (1993). Erratum: J. Algebraic Combin., (1), pp. 129, (1994). 16. K.J. Horadam and W. de Launey. Generation of cocyclic Hadamard matrices. Computational algebra and number theory (Sydney, 1992), volume 325 of Math. Appl., 279–290. Kluwer Acad. Publ., Dordrecht, (1995). 17. N. Ito. On a family of conjugacy classes graphs. Mem. Konan Univ. 31, 105–112, (1984). 18. N. Ito. Hadamard Graphs I. Graphs Combin. 1(1), 57–64, (1985). 19. S. Khot. Improved inapproximability results for maxclique, chromatic number and approximate graph coloring. Proceedings of 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 600-609 (2001). 20. E. Marchiori. Genetic, Iterated and Multistart Local Search for the Maximum Clique Problem. EvoWorkshop 2002, LNCS 2279, 112–121. Springer-Verlag, Berlin Heidelberg, (2002). 21. A. Singh and A.K. Gupta. A hybrid heuristic for the maximum clique problem. J. Heuristics, 15, 5-22 (2006). 22. N.J.A. Sloane. http://www2.research.att.com/˜njas/hadamard