The maximal determinant of cocyclic (−1, 1)-matrices over D2t

The maximal determinant of cocyclic (−1, 1)-Matrices over D2t V. Álvarez , J.A. Armario ∗ ,M.D.Frau,F. Gudiel Department of Applied Math I, University of Seville, Avda. Reina Mercedes s/n, 41012 Seville, Spain ABSTRACT AMS classification: 05B20 05B30 15A15 Keywords: Cocyclic matrices Maximal determinants D-optimal designs Gram matrices Cocyclic construction has been successfully used for Hadamard matrices of order n.These (−1, 1)-matrices satisfy that HHT = HT H = nI and give the solution to the maximal determinant problem whenn = 1, 2oramultipleof4.Inthispaper,weapproachthemaximal determinant problem using cocyclic matrices when n ≡ 2 (mod 4). More concretely, we give a reformulation of the criterion to decide whetherornot the2t × 2t determinant with entries ±1 attains the Ehlich–Wojtas’boundintheD2t - cocyclicframework.Wealsoprovide some algorithms for constructing D2t -cocyclic matrices with large determinants and some explicit calculations up to t=19. 1. Motivation of the problem – introduction AD-optimal design of order n is a n×n(1,−1)-matrix having maximal determinant. Here and throughout this paper, for convenience, when we say determinant of a matrix we mean the absolute value of the determinant. The question of finding the determinant of a D-optimal design of order nis an old one which remains unanswered in general. In 1893 Hadamard proved in [15] that for every (−1,1)-matrix M, det(M)⩽nn 2.(1) Furthermore, Hadamardprovedthatequalityholdsifandonly if MMT=nI. Matrices satisfying this condition are termed Hadamard matrices, and must have order 1, 2 or a multiple of 4. It is conjectured ∗Corresponding author. E-mail addresses: valvar[email protected] (V. Álvarez), [email protected] (J.A. Armario), [email protected] (M.D. Frau), [email protected] (F. Gudiel). that Hadamard matrices exist for every n≡0(mod 4). Although no proof of this fact is known, there is much evidence about its validity (see [19] and the references there cited). Tighter bounds for the maximal determinant for all (−1,1)-matrices of order n= 0(mod 4)are known (see [5,11,12,35,23], for instance). For n≡1(mod 4),Ehlichprovedin[11] that det(M)⩽(2n−1)1 2(n−1)n−1 2.(2) Moreover, equality holds if and only if there exists a (−1,1)-matrix Mof order nsuch that MMT= (n−1)In+Jn(see [5]). Here, as usual, Indenotes the identity matrix of order n, and Jndenotes the n×nmatrix all of whose entries entries are equal to one. If equality holds, 2n−1isaperfectsquare (2k+1)2(or equivalently, nis the summation of two consecutive squares, n=k2+(k+1)2). It has been conjectured that a matrix attaining the bound exists whenever this is the case. However, order 85 =62+72is the smallest for which this has not been proven. For n≡2(mod 4),Ehlichin[11] and independently Wojtas in [35] proved that det(M)⩽(2n−2)(n−2)n−2 2.(3) In order for equality to hold, it is required that there exists a (−1,1)-matrix Mof order nsuch that MMT=⎛ ⎝ L0 0L⎞ ⎠, where L=(n−2)In 2+2Jn 2. In these circumstances, it may be proved that, in addition, 2n−2 is the sum of two squares, a condition which is believed to be sufficient (order 138 is the lowest for which the question has not been settled yet [13]). To be more precise, Ehlich proved in [11] that 2n−2=(n 2−2r)2+(n 2−2s)2, where r(resp. s) is the number of rows in Mfrom 1 to n 2(resp. n 2+1ton) for which the first entry is positive. Alternatively, Cohn proved in [7] that Mcan be chosen of the type M=⎛ ⎝ XY ZW ⎞ ⎠,so that L=XXT+YYT=ZZT+WWT=XTX+ZTZ=YTY+WTW, 0=XZT+YWT=XTY+ZTW, and 2n−2=x2+y2,forx⩾y⩾0, where every row sum and column sum of each of Xand Wis x, each row sum and each column sum of Yis yand each row sum and column sum of Zis −y. The case n≡3(mod 4)appears to be the most difficult one. In spite of the fact that the bound (2) also holds for these matrices, Ehlich derived a tighter one in [12], (n−3)n−s 2(n−3+4r)u 2(n+1+4r)v 21−ur n−3+4r−v(r+1) n+1+4r,(4) where s=3forn=3, s=5forn=7, s=5or6forn=11, s=6forn=15,19,...,59, and s=7 for n⩾63, r= n s,n=rs +vand u=s−v.Cohnshowedin[9] that this number is an integer only when n=112t2±28t+7 for some integer t. Nevertheless, many orders allowed by Cohn’s criterion are ruled out by the Hasse–Minkowski theorem on rational equivalence of quadratic forms (see [34]). In particular, Ehlich’s bound is not achievable for order 91. The smallest order for which it is potencially attainable is 511. It is well known that the Hadamard bound (1) is attained infinitely often, and has to be considered sharpinthissense.In[23]thisquestionwasstudiedfortheremainingbounds,(2),(3)and(4),andsome lower bounds were described which were attained infinitely often. Today we know that the bounds (1), (2) and (3) are sharp, in the above sense. Nevertheless, it is not known whether the bound (4)is sharp in the same sense, or even if it is achievable beyond n=3. It is conceivable that it is not sharp. Whena n×ndeterminantisfound thatattains therelevantoneofthe above bounds,it isimmediate that the maximal determinant for that order is just the bound itself. Nevertheless when the upper bound is not attained, finding the maximal n×ndeterminant can be exceedingly difficult. For n⩽30, orders 19, 22, 23, 27 and 29 are unresolved. The interested reader is addressed to [20] and the website [30] for further information on what is known about maximal determinants. Table 1 Proportion of inequivalent Hadamard matrices (cocyclic/general framework). n4812162024 28 32 36 #[CH]111 5 3 16 6 100 35 #[H]111 5 3 60 487 ⩾13.7 ×106⩾3·106 #[CH] #[H]111 1 1 2.67·10−11.23 ·10−2⩽7.29 ·10−6⩽1.16 ·10−5 Traditionally, matrices meeting the bound (1) are classified attending to Hadamard equivalence, so that two Hadamard matrices are equivalent if and only if one can be converted into the other by a sequence of permutations of rows and columns, and negations of rows and columns. This classification problemtranslatesnaturallytothecaseoftheremainingbounds.Theclassificationof(−1,1)-matrices achieving the maximal determinant remains as an unanswered question in general. What is known (see [19,29,21] for details), is that there is only one equivalence class of D-optimal designs for each of theordersupton=15, except for n=11. And there are 3 equivalence classes for n=11, 5 for n=16, 3forn=17,18,20, 7 for n=21, 60 for n=24, 78 for n=25 and 487 for n=28. For updates on the lower bounds for the number of equivalence classes for other orders, visit these websites [22,30]. In the early 90s, a surprising link between homological algebra and Hadamard matrices [17]ledto the study of cocyclic Hadamard matrices [18]. As was introduced before, a Hadamard matrix of order 4tis a (−1,1)square 4t×4tmatrix such that its distinct row (resp. column) vectors are pairwise orthogonal. A Hadamard matrix is said to be normalized if it has its first row and column all of 1’s (see [19] for more details and constructions methods). Hadamard matrices of many types are revealed to be (equivalent to) cocyclic matrices [10,19]. Among them, Sylvester Hadamard matrices, Williamson Hadamard matrices, Ito Hadamard matrices andPaleyHadamardmatrices.Furthermore,thecocyclicconstructionisthemostuniformconstruction techniqueforHadamardmatricescurrentlyknown,andcocyclicHadamardmatricesmayconsequently provide a uniform approach to the famous Hadamard conjecture. ThemainadvantagesofthecocyclicframeworkconcerningHadamardmatricesmaybesummarized in the following facts: •The test to decide whether a cocyclic matrix is Hadamard runs in O(t2)time, better than the O(t3) algorithm for usual (not necessarily cocyclic) matrices. •The search space is reduced to the set of cocyclic matrices over a given group (that is, 2smatrices, provided that a basis for cocycles over Gconsists of sgenerators), instead of the whole set of 216t2 matrices of order 4twith entries in {−1,1}. Now an interesting question arises, is it better to look for Hadamard matrices in the general framework or in the cocyclic context instead? A recent work of Ó Catháin and Röder (see [27] for details) has permitted the calculation of the exact number #[CH]of inequivalent cocyclic Hadamard matrices, for orders less than 40. This way, a comparison in terms of the total number #[H]of inequivalent Hadamard matrices is feasible, up to order 36 (see Table 1). Here we have taken into account the work of Kharaghani and Tayfeh-Rezaie in [21], about the number of equivalence classes of Hadamard matrices of order 32. Notice that a cocyclic Hadamard matrix may be Hadamard equivalent to a matrix which is not cocyclic at all. The cocyclic character is not preserved by Hadamard equivalence, in general. From Table 1, it seems that whereas tincreases the quotient #[CH] #[H]between the number of inequivalent cocyclic Hadamard matrices and the number of inequivalent Hadamard matrices decreases drastically. Nevertheless, this comparison is somehow biassed, since the set of Hadamard matrices is not uniformly distributed among the equivalence classes. If we attend to the summation of the number of Hadamard matrices equivalent to a matrix of [H]and [CH]in Table 1, denoted by #Hand #CH respectively (the required information may be extracted from [27] and [32]),weobtainTable2. Notice that the number #Hof Hadamard matrices of a given order, and the number #[H]of equivalence classes in which theydistribute, are linked by the notion of mass. The mass of Hadamard matrices of a given order is defined to be the sum of the reciprocals of the sizes of the automorphism groups over Table 2 Proportion of Hadamard matrices belonging to equivalence classes [CH]and [H]. n4 8 12 16 20 24 28 #CH 192 21,504 190,080 10,838,016 16,440 790,224 64,488 #H192 21,504 190,080 10,838,016 16,440 823,616 74,306 #CH #H1 1 1 1 1 0.9594 0.8678 Table 3 Density of D4t-Hadamard matrices versus that of usual Hadamard matrices. n4 8 12 16 20 24 28 %H(D4t)3.75 ·10−11.25 ·10−11.76 ·10−21.17 ·10−22.1·10−34.46 ·10−44.23 ·10−5 %H2.99 ·10−31.17 ·10−15 8.52 ·10−39 9.36 ·10−71 6.37 ·10−117 3.33 ·10−168 7.30 ·10−232 the equivalence classes of Hadamard matrices of this order. This gives another measure of how many distinct Hadamard matrices there are, without regard to equivalence. See [33, A048615,A048616] for details. In fact, searching for Hadamard matrices, no matter the context (cocyclic or general), is computationally a very hard task, as difficult as looking for a needle in a haystack. Nevertheless, one should compare the sizes of the needle and the haystack to get an objective impression about the difficulty of finding such a needle in such a haystack. Thus what can be said about the proportion of Hadamard matrices in the general framework and in the cocyclic context? Unfortunately, we have no information about the total number of cocyclic matrices, even for small values of t.Theworkin[27] could shed light on this problem. Anyway, we can compare the framework of the usual Hadamard matrices with a concrete family of cocyclic matrices. Among them, the most prolific case seems to be dihedral groups D4t(see [19,3]for instance). Since a basis for normalized cocycles over D4tconsists of 4tcocycles (see [3], for instance), then a full basis for cocycles over D4tconsistsof4t+1 elements, and hence the size of the search space for D4t-cocyclic Hadamard matrices is 24t+1. The search space for the usual Hadamard matrices is the complete set of (−1,1)-matrices square matrices of order 4t, which consists of 216t2matrices. The number of D4t-cocyclic Hadamard matrices for small values of tmay be calculated progressing from the work in [2]. Now we can compare the density %H(D4t)of D4t-Hadamard matrices among D4t- cocyclic matrices, and the density %Hof usual Hadamard matrices among the set of (−1,1)-matrices of order 4t. Undoubtedly, the information in Table 3 is once again biassed, since we should be comparing with the full set of cocyclic matrices of order 4t. Anyway, there is some evidence that searching for cocyclic Hadamard matrices, and in particular for D4t-cocyclic Hadamard matrices, makes sense. Despite the fact that cocyclic construction provides a successful approach for Hadamard matrices, and hence for (−1,1)-matrices meeting the bound (1), as far as the authors know this technique has not yet been used to tackle the maximal determinant problem when n= 0(mod 4). The main purpose of this paper is to show that the cocyclic technique can certainly be extended to handle the maximal determinant problem at least when n≡2(mod 4). More concretely, we will focus on cocyclic matrices over the dihedral group D2t,withtodd, so that we give: •A reformulation of the criterion to decide whether or not a D2t-cocyclic matrix has a determinant attaining Ehlich–Wojtas’ bound. •Some algorithms for constructing D2t-cocyclic matrices with large determinants, based on exhaustive and heuristic searches. Unfortunately, although the largest determinants obtained by these methods so far (up to n=2t=38) meet the optimal bound (3) when n−1isthesumoftwo squares, no D2t-cocyclic matrix has been found neither meeting nor improving the already known lower bounds when n=22,34. Apartfromthisintroductorysection,weorganizethepaperasfollows.Thesecondsectionisdevoted to explain the theoretical results about how to determine D2t-matrices meeting Ehlich and Wojtas’ bound (3). The algorithms and some executions are described in the third section. The last section is devoted to conclusions and future work. 2. Main results From now on, we assume that n≡2(mod 4). When necessary, we will use n=2t, for some odd integer t⩾1. Our goal in this section is to characterize the form of D2t-cocyclic matrices which might meet Ehlich andWojtas’bound (3).Thefirstpart ofthe sectionis devotedtointroducesome notationsandtechnical results. Afterwards, the main statements of the paper are described and proved. As introduced in Section 1, equality in (3) holds if and only if there exists a (1,−1)-matrix Bof order n, such that BBT=BTB=⎛ ⎝ L0 0L⎞ ⎠,(5) with Lt=(n−2)It+2Jt. Moreover, in these circumstances n−1 is necessarily the sum of two squares. Condition (5) implies some combinatorial properties, regarding the number of positive entries of the rows (resp. columns) of B. The rows of any (−1,1)-matrix of size ncan be classified as of even or odd type, depending on the parity of the number of 1s that they contain. It is apparent that the inner product of two rows of the same type is congruent to 2 modulo 4, while the inner product of two rows of opposite type is congruent to 0 modulo 4. In these circumstances, the block structure of the matrix in (5) implies that rows from 1 to tof Bshare a common type, whereas rows from t+1to2tshare the opposite type. The same argument translates to the columns of B. This is a main difference with usual Hadamard matrices of order a multiple of 4, in which rows of different type cannot occur. Notice that this balanced structure of even and odd type rows does not need to be attained anymore when n−1 is not the sum of two squares. In particular, record-determinant matrices are known in sizes 22, 34, 70 and 106 for which the number of even type rows is greater than the number of odd type rows (see [30] for details). How do these conditions translate to the cocyclic framework? In order to answer this question properly, it seems reasonable to give in advance a brief introduction to cocyclic matrices. Assume throughout that G={g1=1,g2,...,gn}is a multiplicative group, not necessarily abelian. Functions ψ:G×G→−1∼ =Z2which satisfy ψ(gi,gj)ψ(gigj,gk)=ψ(gj,gk)ψ(gi,gjgk), ∀gi,gj,gk∈G(6) are called (binary) cocycles (over G)[24]. A cocycle is a coboundary ∂φ if it is derived from a set mapping φ:G→−1by ∂φ(a,b)=φ(a)φ(b)φ(ab)−1. A cocycle ψis naturally displayed as a cocyclic matrix (or G-matrix) Mψ; that is, the entry in the (i,j)th position of the cocyclic matrix is ψ(gi,gj),forall1⩽i,j⩽n. A cocycle ψis normalized if ψ(1,gj)=ψ(gi,1)=1forallgi,gj∈G. The cocyclic matrix coming from a normalized cocycle is called normalized as well. Each unnormalized cocycle ψdetermines a normalized one −ψ, and vice versa. Therefore, we may reduce, without loss of generality, to the case of normalized cocycles. The set of cocycles forms an abelian group Z(G)under pointwise multiplication, and the coboundaries form a subgroup B(G).AbasisBfor cocycles over Gconsists of some elementary coboundaries ∂iand some representative cocycles, so that every cocyclic matrix admits a unique representation as a Hadamard (pointwise) product M=M∂i1◦···◦M∂iw◦R, in terms of some coboundary matrices M∂ijand a matrix Rformed from representative cocycles. Recall that every elementary coboundary ∂dis constructed from the characteristic set map δd:G→ {−1,1}associated with an element gd∈G, so that ∂d(gi,gj)=δd(gi)δd(gj)δd(gigj)for δd(gi)=⎧ ⎨ ⎩ −1gd=gi, 1gd= gi. Remark 1 [2, Lemma 1].In particular, for d= 1, every row s/∈{1,d}in M∂dcontains precisely two −1s, which are located at the positions (s,d)and (s,e),forge=g−1 sgd. Furthermore, the first row is always formed by 1s, while the dth row is formed all by −1s, excepting the positions (d,1)and (d,d). Although the elementary coboundaries generate the set of all coboundaries, they might not be linearly independent (see [3] for details). At this point, it is worthwhile to notice that every row (resp. column) in M∂dconsists of an even number of 1s (see Remark 1). Consequently, for a cocyclic matrix M=M∂i1◦···◦M∂iw◦Rto be a candidate Bfor meeting (5), a necessary (in general, not sufficient) condition is that half the rows (resp. columns) of Rare of even type, whereas the remaining trows (resp. columns) are of odd type. Let Gr(M)(resp. Gc(M)) be the Gram matrix of the rows (resp. columns) of M, Gr(M)=MMT(resp. Gc(M)=MTM). The Gram matrices of a cocyclic matrix can be calculated as follows. Proposition 1. [19, lemma 6.6] Let Mψbe a cocyclic matrix, [Gr(Mψ)]ij =ψ(gig−1 j,gj) g∈G ψ(gig−1 j,g), (7) [Gc(Mψ)]ij =ψ(gi,g−1 igj) g∈G ψ(g,g−1 igj). (8) If a cocyclic matrix Mψis Hadamard, we say that the cocycle involved, ψ, is orthogonal and Mψis a cocyclic Hadamard matrix. The cocyclic Hadamard test asserts that a normalized cocyclic matrix is Hadamardif andonlyifevery row sum(apart fromthe first)is zero[18].In fact, thisis a straightforward consequence of Proposition 1. Analyzing this relation from a new perspective, one could think of normalized cocyclic matrices meeting the bound (1) as normalized cocyclic matrices for which every row sum is zero. Could it be possible that such a relation translates somehow to the case n≡2(mod 4)? We now prove that, in fact, the answer to this question is affirmative. A natural way to measure if the rows of a normalized cocyclic matrix M=[mij]are close to sum zero, is to define an absolute row excess function RE, such that RE(M)= n  i=2 n  j=1 mij . This is a natural extension of the usual notion of excess of a Hadamard matrix, E(H), which consists in the summation of the entries of H. With this definition at hand, it is evident that a cocyclic matrix Mis Hadamard if and only if RE(M)=0. That is, a cocyclic matrix Mmeets (1) if and only if RE(M)is minimum. This condition may be generalized to the case n≡2(mod 4). Proposition 2. Let M be a normalized cocyclic matrix over G. Then RE(M)⩾2t−2. Proof. Let Mbe a cocyclic matrix over G.LetMhave erows of even type (precisely, those whose summations are congruent to 2 modulo 4), and consequently 2t−erows of odd type (those whose summationsarecongruentto0modulo4)Inthesecircumstances,inordertoprovethatRE(M)⩾2t−2 it suffices to prove that e⩾t(notice that the first row of Mis always of even type). As we commented before, since n≡2(mod 4), the inner product of two rows of the same type is congruent to 2 modulo 4, while the inner product of two rows of opposite type is congruent to 0 modulo 4. This way, the number of inner products ≡0(mod 4)is 2e(2t−e),thetotalnumberof ordered pairs of rows of different type. An upper bound of this value is 2e(2t−e)⩽2t2, and equality holds if and only if e=tsince 2e(2t−e)⩽2t2⇔2t2−4et +2e2⩾0⇔2(t−e)2⩾0. Since each of the 2t−egroup elements grcorresponding to rows of odd type can be represented as gsg−1 j, where gj=g−1 rgs, Proposition 1implies that row sof the Gram matrix Gr(M)=MMTcontains 2t−eelements ≡0(mod 4)for each 1 ⩽s⩽2t, and therefore that the Gram matrix Grcontains 2t(2t−e)elements ≡0(mod 4).Hence2t(2t−e)⩽2t2⇔2t−e⩽t⇔e⩾t. But we may go even further. Having the minimum possible value 2t−2 is a necessary condition for a cocyclic matrix Mto meet the bound (3). Proposition 3. If a cocyclic matrix M meets the bound (3), then RE(M)=2t−2. Proof. Let Mbe a cocyclic matrix meeting (3). By means of rows and columns permutations and row negations (no column negations are needed), Mcan be transformed in a Hadamard equivalent matrix Bsatisfying (5). From (5), it is evident that RE(B)=2t−2. Since no column negations have been used, RE(M)=RE(B). Unfortunately, although having minimum absolute row excess is a necessary and sufficient conditionfor meetingthebound(1), itis justa necessary (butnotsufficient, ingeneral,seeTable5) condition for meeting the bound (3). From now on, we fix G=D2t, the dihedral group with presentation a,b:at=b2=(ab)2=1, with ordering {1,a,...,at−1,b,ab,...,at−1b}and indexed as {1,...,2t}where tis an odd positive integer. From the results in [2] and [1], it may be proved that a basis for cocycles over D2tconsists in 2t−1 generators, B={∂2,...,∂ 2t−1,β}.Here∂idenotes the coboundary associated with the ith-element of the dihedral group D2t, that is ai−1(mod t)bi−1 t.Andβis the representative cocycle in cohomology, i.e. Mβ=⎛ ⎝ JtJt Jt−Jt⎞ ⎠. Remark 2. Since half the rows of Mβare of even type (those from 1st to 2tth), it is apparent that a cocyclic matrix Mover D2tcan attain the bound (3)onlyifMdecomposes as a combination of the form M∂i1◦···◦M∂iw◦Mβ. If, on the contrary, Mβis not used, then all the rows of the cocyclic matrix would be of even type, and the condition (5) could not be satisfied. Notice that for every D2t-cocyclic matrix of the form M∂i1◦···◦M∂iw◦Mβ, rows (resp. columns) from 1st to 2tth are of even type, whereas the remaining rows (resp. columns) are of odd type. The following technical result will be used throughout the paper. Lemma 4. Let M be a cocyclic matrix over D2t. •MMThas the form ⎛ ⎝ X0 0Y⎞ ⎠,for some symmetric square matrices X and Y of order t, if and only if it admits a decomposition of the form M =M∂i1◦···◦M∂iw◦Mβ. •If it is the case, in addition, then MMT=MTM. Proof. The argument described in [2, Proposition 11] may be adapted to the case of dihedral groups D2t, so that the summation of any row s,t+1⩽s⩽2t,is0. Actually, consider a matrix N=M∂i1◦···◦M∂iw. Attending to the presentation of D2t,itmaybe readily checked that (akb)−1=akb. In these circumstances, Remark 1implies that the (necessarily even) number 2fsof −1s located at row s,t+1⩽s⩽2t, are distributed in such a way that precisely fsof them occur through columns 1 to t, whereas the remaining fsoccur through columns t+1to2t. Furthermore, fixed a row s,t+1⩽s⩽2t, any twocoboundary matrices M∂iand M∂jeithersharetheir two −1s entries at row s, or do not share any of them at row s. Consequently, attending to the form of Mβ, the summation of row s,t+1⩽s⩽2t, of any cocyclic matrix M∂i1◦···◦M∂iw◦Mβis zero. Now the first part of the Lemma becomes apparent, from Proposition 1and Remark 2. The proof of the second part of this lemma follows from the study of the distribution of −1byrows and by columns in the elementary coboundary (see [2,4]). This study leads to the notion of called (row) n-paths in [2], analogously the notion for columns can be defined. The distribution of −1byrowsand columns in M=[mi,j]can be found by means of n-path. As a consequence, we have the following properties of M: 1. If t+1⩽j⩽2t,thenjth column sum is zero and mj,j=1. 2. Assume 1 ⩽i⩽t. Then, any sequence of coboundaries making up a i-path for rows, also makes upai-pathforcolumns.(Unfortunately,thissituationdoesnotholdwhent+1⩽i⩽2t.)Hence: •The ith row sum is equal to the ith column sum. •If 1 ⩽j⩽tthen the inner product of rows ith and jth is equal to the inner product of columns ith and jth. Let us distinguish three cases: 1. If 1 ⩽i⩽tand t+1⩽j⩽2t(or vice versa) then by (8), we have: [MTM]i,j=± 2t  l=1 ml,k with t+1⩽k⩽2t. Using the properties above, we have that this column sum is zero. 2. Assuming 1 ⩽i,j,⩽t, and taking into account the last property stated above. It follows that [MTM]i,j=[MMT]i,j. 3. Let us show that [MTM]i,j=[MMT]i,jwhen t+1⩽i,j⩽2t. Firstly, let us observe that i=jthe result is trivial. For the remaindering of the proof, we suppose that i= j.Using(7) and (8), we have: [MMT]i,j=mk,j 2t  l=1 mk,l, and [MTM]i,j=mi,k 2t  l=1 ml,k. where 2 ⩽k⩽tsince g−1 i=giand gig−1 j=g−1 igj=gk. In this situation, the kth row sum is equal to the kth column sum. Now, using that the entries of Msatisfying (6) and mi,i=1, it follows that mk,j=mi,k, and this concludes the proof.  In this paper, not only do we pursue a characterization of the D2t-cocyclic matrices whose determinant is equal to (4t−2)(2t−2)t−1, but we will also develop some methods for finding them. If Mis a D2t-cocyclic matrix whose determinant is equal to (4t−2)(2t−2)t−1then Gr(M)is equivalent to C=⎛ ⎝ L0 0L⎞ ⎠, with L=(2t−2)It+2Jt. Starting from Cone may construct Sthe full set of equivalent matrices UTCUT, such that UTis the negation of the diagonal entries with indices in T⊂{1,...,2t}=Qof the identity matrix I2t. S={UTCUT:T⊂Q}.(9) This list has cardinality 22t−1since UTCUT=UQ\TCUQ\T. It is a remarkable fact that Sconstitutes the complete list of candidate Gram matrices (i.e., symmetric, have diagonal elements equal to 2tand positive definite and determinant equal to (4t−2)2(2t−2)2t−2in our cocyclic context. In the general framework, simultaneous permutation of rows and the corresponding columns in the candidate Gram matrices is also allowed. Because of the assumed ordering of the group elements, and the relation of elements of the form ajbwith rows of odd type, arbitrary permutation is not allowed in our context. Given a candidate Gram matrix, not only would we like to determine whether it admits a decomposition UTCUT=MMT,Mbeing a D2t-cocyclic matrix, but we also aim to compute such decomposition whenever possible. The next result will play an essential role in the design of the algorithm solving this problem. Theorem 5. Let M be a normalized cocyclic matrix over D2tand Gr(M)=⎛ ⎝ X0 0Y⎞ ⎠be the Gram matrix of M. If X and Y are square matrices of order t, then the entries of M =[mi,j]are given by the formulas: 1. 1 ⩽i,j⩽2t m1,j=1=mi,1(M normalized) 2. 2 ⩽i⩽t 2.1. 2 ⩽j⩽t mi,j=x[j+i−1],j xi,1 ,where [n]=1+(n−1)mod t 2.2. t+1⩽j⩽2t mi,j=y[j+i−1−t],j−t xi,1 3. i=t+1(By lemma 4,MM T=MTM. Hence we have uniqueness of the entries and these are the values given below.) 3.1. 2 ⩽j⩽t mt+1,j=y1,t+2−j x1,j 3.2. j=t+1 mt+1,t+1=− t  j=1 mt+1,j⎛ ⎝1+ 2t  j=t+2 mj−t,t+1mt+1,j−tm2t+2−j,t+1⎞ ⎠. 3.3. t+2⩽j⩽2t mt+1,j=mj−t,t+1mt+1,j−tm2t+2−j,t+1mt+1,t+1 4. t+2⩽i⩽2t 4.1. 2 ⩽j⩽t mi,j=mi−t,2t−j+2mi−t,t+1mt+1,j [6] T. Chadjipantelis, S. Kounias, C. Moyssiadis, The maximum determinant of 21 ×21 (1,−1)-matrices and D-optimal designs, J. Stat. Plann. Inference 16 (1987) 167–178. [7] J.H.E. Cohn, On determinants with elements ±1, II, Bull. London Math. Soc. 21 (1989) 36–42. [8] J.H.E. Cohn, On the number of D-optimal designs, J. Combin. Theory Ser. A 66 (1994) 214–225. [9] J.H.E. Cohn, Almost D-optimal designs, Util. Math. 57 (2000) 121–128. [10] W. de Launey, K.J. Horadam, A weak difference set construction for higher dimensional designs, Des. Codes Cryptogr. 3 (1993) 75–87. [11] H. Ehlich, Determiantenabschätzungen für binäre Matrizen, Math. Z. 83 (1964) 123–132. [12] H. Ehlich, Determiantenabschätzung für binäre Matrizen mit n≡3mod4), Math. Z. 84 (1964) 438–447. [13] R.J. Fletcher, C. Koukouvinos, J. Seberry, New skew-Hadamard matrices of order 4 ·59 and new D-optimal designs of order 2·59, Discrete Matehmatics 286 (2004) 252–253. [14] Z. Galil, J. Kiefer, D-optimum weighing designs, Ann. Stat. 8 (1980) 1293–1306. [15] J. Hadamard, Résolution d’une question relative aux déterminants, Bull. Sci. Math. 2 (17) (1893) 240–246. [16] J.H. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, 1975. [17] K.J. Horadam, W. de Launey, Cocyclic development of designs, J. Algebraic Combin. 2 (3) (1993) 267–290 (Erratum: J. Algebraic Combin.3(1)(1994)129). [18] K.J. Horadam, W. de Launey, Generation of Cocyclic Hadamard matrices, Computational Algebra and Number Theory, Math. Appl., Kluwer Acad. Publ., Dordrecht, 1995, pp. 279–290. [19] K.J. Horadam, Hadamard Matrices and Their Applications, Princeton University Press, Princeton, NJ, 2007. [20] H. Kharaghani, W.P. Orrick, D-optimal designs, in: C. Colbourn, J. Dinitz (Eds.), The CRC Handbook of Combinatorial Designs, Taylor and Francis, Boca Raton, 2006 [21] H. Kharaghani, B. Tayfeh-Rezaie, On the classification of Hadamard matrices of order 32, J. Comb. Des. 18 (2010) 328–336. [22] C. Koukouvinos, <http://math.ntua.gr/ ckoukouv/>. [23] C. Koukouvinos,M. Mitroulli, J. Seberry, Bounds on the maximum determinant for (−1,1)matrices, Bull. ICA 29 (2000) 39–48. [24] S. MacLane, Homology, Classics in Mathematics, Springer-Verlang, Berlin, 1995.. (Reprint of the 1975 edition). [25] Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs, Springer-Verlag, 1992. [26] C. Moyssiadis, S. Kounias, The exact D-optimal first order saturated design with 17 observations, J. Statist. Plann. Inference 7 (1982) 13–27. [27] P. Ó Catháin, M. Röder, The Cocyclic Hadamard matrices of order less than 40, Des. Codes Cryptogr. 58 (1) (2011) 73–88. [28] W.P. Orrick, The maximal {−1,1}-determinant of order 15, Metrika 62 (2005) 195–219. [29] W.P. Orrick, On the enumeration of some D-optimal designs, J. Statist. Plann. Inference 138 (2008) 286–293. [30] W. Orrick, B. Solomon, The Hadamard Maximal Determinant Problem (website), <http://www.indiana.edu/maxdet/>. [31] J. Seberry, T. Xia, C. Koukouvinos, M. Mitrouli, The maximal determinant and subdeterminants of ±1 matrices, Linear Algebra Appl. 373 (2003) 297–310. [32] N.J.A. Sloane, A Library of Hadamard Matrices (website), <http://www2.research.att.com/ njas/hadamard/>. [33] N.J.A. Sloane, The On-line Encyclopedia of Integer Sequences (website), <http://oeis.org/>. [34] H. Tamura, D-optimal designs and group divisible designs, J. Comb. Des. 14 (2006) 451–462. [35] W. Wojtas, On Hadamard’s inequallity for the determinants of order non-divisible by 4, Colloq. Math. 12 (1964) 73–83.