On an inequivalence criterion for cocyclic Hadamard matrices

On an inequivalence criterion for cocyclic Hadamard matrices José Andrés Armario Abstract Given two Hadamard matrices of the same order, it can be quite difficult to decide whether or not they are equivalent. There are some criteria to determine Hadamard inequivalence. Among them, one of the most commonly used is the 4-profile criterion. In this paper, a reformulation of this criterion in the cocyclic framework is given. The improvements obtained in the computation of the 4-profile of a cocyclic Hadamard matrix are indicated. Keywords Cocyclic Hadamard matrices · Hadamard equivalence · 4-profile criterion 1 Introduction A Hadamard matrix of order n is an n × n matrix with every entry either 1 or −1, which satisfies HHT = nI. It is known that n is necessarily 1, 2 or a multiple of 4, but there is no certainty whether such a Hadamard matrix exists for every size 4t. This is the Hadamard conjecture, which remains unsolved for more than a century. Two Hadamard matrices are called equivalent if one can be obtained from the other by some sequence of row and column permutations and negations. To identify the equivalence of two Hadamard matrices of order n, a complete search compares (2nn!)2 pairs of matrices and is known to be an NP hard problem when n increases [13]. The classification of Hadamard matrices of order n ≥ 32 remains an open and This work has been partially supported by the research projects FQM-296 and P07-FQM-02980 from JJAA and MTM2008-06578 from MICINN (Spain). J. A. Armario (B) Department of Applied Math I, University of Seville, Avda. Reina Mercedes s/n, 41012 Seville, Spain e-mail: [email protected] difficult problem and only partial results are known. What is known is that there is only one equivalence class of Hadamard matrices for each of the orders n=1,2,3,8 and 12. There are five equivalence classes for n=16,3for n=20,60 for n=24 and 487 for n=28 [9]. For updates on the lower bounds for the number of equivalence classes for higher orders, visit this website [10]. The 4-profile criterion is a sufficient (but not necessary) condition for Hadamard inequivalence. Hadamard matrices with unequal 4-profiles are inequivalent. However, Hadamard matrices with equal 4-profiles may or may not be inequivalent. Cooper, Milas and Wallis in [4] suggested the 4-profile criterion to investigate the equivalence of Hadamard matrices. Later Lin, Wallis and Zhu in [11] proposed some modifications of this criterion. Suppose that H=(hij)is a Hadamard matrix of order 4t≥8.Define Pijkl = 4t  x=1 hixhjxhkxhlx. We shall write π(m)for the number of sets {i,j,k,l}of four distinct rows such that Pijkl =m. It is well-known that π(m)=0unless m≥0and m=4nmod8.Wecall π(m)the 4-profile of H. The complexity in terms of time for the computation of this invariant is of orders O(t5). This criterion has been implemented in the Computer Algebra System, MAGMA [3]. In the early 90s, a surprising link between homological algebra and Hadamard matrices [6,7] led to the study of cocyclic Hadamard matrices [8]. Hadamard matrices of many classes are revealed to be (equivalent to) cocyclic matrices [5,9]. Among them, Silvester Hadamard matrices, Williamson-type Hadamard matrices and Paley Hadamard matrices. Furthermore, cocyclic construction is the most uniform construction technique for Hadamard matrices currently known, and cocyclic Hadamard matrices may consequently provide a uniform approach to the famous Hadamard conjecture. The main purpose of this paper is to rewrite the 4-profile criterion in the cocyclic framework. It also shows that the additional internal structure in a matrix, which represents a cocycle, is sufficient to provide a substantial reduction in computational complexity of the problem of calculating this invariant. We will focus on the D8 case. 2 Preliminaries Assume throughtout that G={g1=1,g2,...,g4t}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(1) are called (binary) cocycles (over G)[12]. Acocycleψis naturally displayed as a cocyclic matrix Mψ; that is, the entry in the (i,j)th position of the cocyclic matrix is ψ(gi,gj)),forall1≤i,j≤4t. A cocycle is a coboundary ∂φ if it is derived from a set mapping φ:G→−1 by ∂φ(a,b)=φ(a)φ(b)φ(ab)−1.For instance, the function ∂dwhich is constructed from the characteristic set map δd:G→{−1,1}associated to an element gd∈G, so that ∂d(gi,gj)=δd(gi)δd(gj)δd(gigj)for δd(gi)=−1gd=gi 1gd= gi,(2) is so-called an elementary coboundary. Although the elementary coboundaries generate the set of all coboundaries, they might not be linearly independent (see [2]for details). Acocycleψis normalized if ψ(1,gj)=ψ(gi,1)=1for all gi,gj∈G. The cocyclic matrix coming from a normalized cocycle is called normalized cocylic matrix. Note that M∂dis normalized if d>1. 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 Hadamard if and only if the summation of each row (but the first) is zero [8]. The generalized coboundary matrix M∂jrelated to an elementary coboundary ∂j consists of negating the jth-row of the matrix M∂j. Note that negating a row or a column of a matrix does not change its Hadamard character. As it is pointed out in [1], every generalized coboundary matrix M∂jcontains exactly two negative entries in each row s= 1, which are located at positions (s,i)and (s,e),forge=g−1 sgi. In the following lemma, we study the distribution of −1by columns in the generalized coboundary matrices. Lemma 1 Every column j =linM∂lcontains precisely only one −1which is located in the position (i,j)for gi=glg−1 j. Furthermore, the lth column is formed by −1s, except in the position (1,l). Proof The proof follows from particularizing (2) to the cocycle ∂l. Let us observe that fixed l,thengi=glg−1 jreaches all the values of G= {g1,...,g4t}when gjis taking values from g1until g4t. Hence, for every generalized coboundary matrix M∂lthere exists a 4t×4tpermutation matrix Plsuch that M∂l=APl, where A=⎛ ⎜ ⎜ ⎜ ⎝ ++···+ − − . . .... −− ⎞ ⎟ ⎟ ⎟ ⎠4t×4t. Another relevant property of these generalized coboundary matrices is given in the following lemma. Lemma 2 No two generalized coboundary matrices share a column in the same position. Hence, every column jof A appears in a different position in two generalized coboundary matrices. Proof Given M∂l1and M∂l2where 1≤l1<l2≤4t. Obviously, the l1th column in M∂l1 is different from the l1th column in M∂l2(the same follows for the l2th column). On the other hand, since l1=l2then gl1= gl2and gl1g−1 j= gl2g−1 jfor all 1≤j≤4. If j=l1,l2then the jth column of M∂l1has its only non null entry in the position gl1g−1 jand the jth column of M∂l2has its only non null entry in the position gl2g−1 j. Therefore, both jth columns are different.  3 The 4-profile criterion for cocyclic Hadamard matrices Let Mψbe a cocyclic Hadamard matrix over G. In this section, we deal with the problem of computing the 4-profile for Mψ. To this end, we have to compute the absolute value of the generalized inner product of rows i,j,kand l, Pijkl = 4t  x=1 ψ(gi,gx)ψ(gj,gx)ψ(gk,gx)ψ(gl,gx) for every set {i,j,k,l}of four distinct rows (i.e., four distinct integers of {1,...,4t}). Working in a similar way to [9, Lemma 6.6] and using the identity (1), we get Pijkl = 4t  x=1 ψ(gig−1 j,gx)ψ(gkg−1 l,glg−1 jgx).(3) It seems to be a first reduction in the formula, but it presents a problem because the factor glg−1 jproduces a permutation in the elements of the gkg−1 lth row. To solve this problem, we use the distribution of −1by columns in the generalized coboundary matrices pointed out in Lemma 1 and consider the following permutation matrix P: –The1st column of Phas its unique non null entry in the same position where the jth column of Mδlhas its unique negative entry. – The rest of the columns of Pcan be computed from the first one and the multiplication table of the group. Lemma 3 Fixed y,gjand gl∈G and taking the permutation matrix P described above ψ(y,glg−1 jx)=ψ(y,x)·P,∀x∈G. Proof Let us observe that the jth column of Mδlhas its unique negative entry in the position kwhere gk=glg−1 j. Example 1 If G=D4t=a,b:a2t=b2=(ab)2=1the dihedral group with ordering {1,a,a2,...,a2t−1,b,ab,...,a2t−1b} indexed as {1,...,4t}, and we know that the 1st column of Phas its unique non null entry in position kthen the permutation matrix Phas the form: For 1≤k≤2t, ⎛ ⎜ ⎜ ⎝ Ik−1 I2t−k+1Ik−1 I2t−k+1 ⎞ ⎟ ⎟ ⎠ where Inis the n×nidentity matrix. For 2t+1≤k≤4t, ⎛ ⎜ ⎜ ⎝ ˆ Ik−2tˆ I4t−k ˆ Ik−2tˆ I4t−k ⎞ ⎟ ⎟ ⎠ where ˆ Inis the n×nback diagonal matrix where its non null entries are in positions (i,j)satisfying i+j=n+1and these entries are all 1s. On the other hand, the number of sets {i,j,k,l}of four distinct rows for Mψis 4t 4. Actually, this is mainly responsible for the computational cost in computing for the 4-profile. In the sequel, we will define an equivalence relation for the sets {i,j,k,l}of four distinct rows, and we will be able to compute the 4-profile of Mψ from a representatives element of at most 4t 4/tclasses. Definition 1 Let X={x1,x2,x3,x4}and Y={y1,y2,y3,y4}be subsets of four distinct integers of {1,...,4t}.Xand Yare called equivalent (or G-equivalent)ifthese following identities hold: gx1g−1 x2=gy1g−1 y2,gx3g−1 x4=gy3g−1 y4,and gx4g−1 x2=gy4g−1 y2.(4) Remark 1 For a given group Gof 4telements with a fixed ordering, the relation of G-equivalence is an equivalence relation. Therefore, one can study the equivalence classes and define representative for each class. [{x1,x2,x3,x4}] denotes the class defined by the element {x1,x2,x3,x4}. Definition 2 The size of [{x1,x2,x3,x4}], denoted by [{x1,x2,x3,x4}], is the number of “different” elements Y={y1,y2,y3,y4}equivalent to X={x1,x2,x3,x4}.IfY and α(Y)={yα(1),yα(2),yα(3),yα(4)}are G-equivalent to Xfor a permutation αof the integers {1,2,3,4},thenYand α(Y)are considered to be the same to this end. Lemma 4 Let αbe a permutation of the integers {1,2,3,4}.IfX={x1,x2,x3,x4} and Y ={y1,y2,y3,y4}are G-equivalent. Then α(X)={xα(1),xα(2),xα(3),xα(4)}and α(Y)={yα(1),yα(2),yα(3),yα(4)}are G-equivalent too. Proof Assume 1≤i,j≤4and i= j. We are going to prove that gxig−1 xj=gyig−1 yj. Firstly, for being Xequivalent to Y, we have gx1g−1 x2=gy1g−1 y2,gx3g−1 x4=gy3g−1 y4,and gx4g−1 x2=gy4g−1 y2. Now, we check that the desired identity holds for: gx2g−1 x3=gx2g−1 x4gx4g−1 x3=gx2g−1 x4(gx3g−1 x4)−1=gy2g−1 y4(gy3g−1 y4)−1 =gy2g−1 y4gy4g−1 y3=gy2g−1 y3. gx1g−1 x3=gx1g−1 x2gx2g−1 x3=gy1g−1 y2gy2g−1 y3=gy1g−1 y3. The rest of the identities follow in a similar manner.  Corollary 1 Given two different equivalent classes [X]and [Y]. If Z is equivalent to Xandα(Z)is equivalent to Y for a permutation αof the integers {1,2,3,4},thenthese two classes [α(X)]and [Y]are the same. Definition 3 Aset{[X1],...,[Xn]} of different equivalence classes is not proper if there exists two classes, [Xi]and [Xj], and a permutation αof the integers {1,2,3,4} such that [Xi]=[α(Xj)]. Otherwise, we say that {[X1],...,[Xn]} is a set of proper equivalence classes. Definition 4 We will say that a set ={[X1],...,[Xn]} is a distribution of proper equivalence classes,ifis a set of proper equivalence classes and ∪[Y]is not proper for any equivalent class [Y]. Fixed a group G, we outline a procedure to construct a distribution of proper equivalent classes and to evaluate the size of every class. Algorithm 1 Searching for a distribution of proper G-equivalent classes. Input: a multiplicative group Gof 4telements. Output: a distribution of proper equivalent classes and the size of every class. ←∅ S←all 4t 4subsets of four distinct elements of {1,2,...,4t} while Sis not empty { 1. Choose a set Xin S. 2. S←S\{X}. 3. Check whether either X or a permutation of its components is equivalent to one element of . If no, go to 5; otherwise go to 4. 4. [Y]←[Y]+1where [Y]is the unique element of satisfying that either X or a permutation of its components is equivalent to Y.Goto1. 5. ←∪[X]and [X]←1. } ={[X1],...,[Xn]}and ={[X1],[X2],...,[Xn]} Correctness: Corollary 1 guarantees the uniqueness of [Y]in the Step 4. By construction, is a set of proper equivalence classes and ∪[Z]is not proper for any equivalence class [Z]. Furthermore, gives the size of every class. The following result can be seen as an immediate consequence of the procedure described above. Proposition 1 Assuming that ={[X1],...,[Xn]}is a distribution of proper equivalence classes. We have: – Given a set {i,j,k,l}of four distinct integers of {1,2,...,4t}. There is one and only one class in ,[Xm], such that either {i,j,k,l}or a permutation of its components is equivalent to Xm. – n  i=1 [Xi]=4t 4. Now we study the connection between the 4-profile of Mψand the relation of G-equivalence. Proposition 2 Given two sets {i,j,k,l}and {i,j,k,l}of four distinct rows of Mψ (i.e., sets of four distinct integers of {1,...,4t}). If {i,j,k,l}is equivalent to {i,j,k,l} then Pijkl =Pijkl. Proof It follows from Eqs. 3and 4. We now describe a method to evaluate the 4-profile for a cocyclic Hadamard matrix over G. Let us observe that Step 1 of this method depends only on G. Algorithm 2 Computing the 4-profile of Mψ. Inputs: a multiplicative group Gof 4telements and a cocyclic Hadamard matrix Mψ over G Output: the 4-profile of Mψ Step 1. Calculate and . Step 2. Calculate I={PX1,PX2,...,PXn}. Step 3. For each m∈I,π(m)= [Xi]∈/PXi=m [Xi] In the remaining part of this section, we will tackle the problem of determining the size of every equivalent class. To this end, we fix a set {i,j,k,l}of four distinct rows of Mψ. Any solution {i,j,k,l}of the following equations system ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ gig−1 j=gig−1 j gkg−1 l=gkg−1 l glg−1 j=glg−1 j, (5) is G-equivalent to {i,j,k,l}and vice versa. Therefore, the size of [{i,j,k,l}] is the number of different solutions of Eq. 5. In the following lemma we study the number of different solutions for one equation. Lemma 5 Given a set {i,j}of two distinct rows of Mψ.Ifλdenotes the number of different pairs {i,j}such that gig−1 j=gig−1 j.(6) Then, 2t≤λ≤4t. Proof By Lemma 1, gig−1 jindicates the position of the unique −1entry of the jst column of M∂i. Let cijbe the 4t×1vector of ones except in the position gig−1 jwith entry −1.By Lemma 2, cijappears only one time in every generalized coboundary as a column, but always in a different position. Thus, there is a permutation αof the integers {1,...,4t} such that the first column of M∂α(1)coincides with cij, the second column of M∂α(2) coincides with cijand so on. Therefore, any element of {gα(1)g−1 1,...,gα(4t)g−1 4t}is a solution of Eq. 6and obviously, these are all the solutions. We point out that some of the following identities could hold gα(1)g−1 1=g1g−1 α(1),gα(2)g−1 2=g2g−1 α(2),...,gα(4t)g−1 4t=g4tg−1 α(4t). Since the sets {i,α(i)}and {α(i), i}of two distinct rows are the same, it follows the desired result.  Remark 2 To solve Eq. 6is equivalent to localizing a determinate column in each generalized coboundary matrix. Lemma 6 If κdenotes the number of different sets {i,j,k,l}of four distinct rows which are solutions of Eq. 5. Then, t≤κ≤4t. Proof To solve Eq. 5, we start by taking one solution, gx1g−1 x2, from the third equation. It determines the second and the fourth component for the solution of Eq. 5 {−,x2,−,x1}. Now, we have to look for the solution of the second equation of type gy1g−1 x1. Thus, we have the third component {−,x2,y1,x1}. Finally, we have to look for the solution of the first equation of type gz1g−1 x2. Thus, {z1,x2,y1,x1} is a solution of the system (5). So, every solution of the third equation generates a unique solution of the system. Furthermore, we could have started by taking one solution from either the first or the second equation and, in a similar manner, we would have obtained the unique solution of the system from this input. On the one hand, the most favorable case takes place when every solution gx1g−1 x2 generates one “different” solution {z1,x2,y1,x1}of the system. Since there are 4t solutions for an equation, we have 4tsolutions for the system. On the other hand, the worst scenario takes place when for every solution X= {x1,x2,x3,x4}of the system, the cardinal of the set A={αj:αj(X)is a solution too} is maximum, where αjdenotes a permutation of the integers {1,2,3,4}.Letus observe that if αpand αq∈Asatisfy that αp(i)=αq(i)for some i,thenαp(i)= αq(i), ∀i.Hence, 4 is an upper bound for the cardinal of A, since if the cardinal of A were five or more, then there would exist two permutations αpand αqsatisfying that αp(i)=αq(i)for some i. As a consequence, 4t/4is a lower bound of the number of different solutions for Eq. 5. Remark 3 Let ={[X1],...,[Xn]} be a distribution of proper equivalence classes. On the one hand, using the identification between the size of [X]and κ(the number of different solutions of Eq. 5), we have by Lemma 6 that the size of every equivalent class, [Xi], is greater than or equal to t. On the other hand, by Proposition 1, this identity n i=1[Xi]=4t 4holds. So, the number of elements in a distribution of proper equivalence classes, n, is lesser than or equal to 4t 4/t. Taking into account the step 2 of Algorithm 2, the number of sets of {i,j,k,l}of four distinct rows to be considered for computing the 4-profile of a cocyclic Hadamard matrix over Gis n instead of being 4t 4. 3.1 The D8case In this section, we will solve Eq. 5and will compute a distribution of proper equivalence classes being Gthe dihedral group of 8 elements, D8, with presentation a,b:a4=b2=(ab)2=1, and with ordering {1,a,a2,a3,b,ab,a2b,a3b}, indexed as {1,...,8}.