Embedding cocylic D-optimal designs in cocylic Hadamard matrices

Electronic Journal of Linear Algebra Volume 24 ELA Volume 24 (2012/2013) Article 7 2012 Embedding cocylic D-optimal designs in cocylic Hadamard matrices Victor Alvarez Jose Andres Armario [email protected] Maria Dolores Frau Felix Guidiel Follow this and additional works at: http://repository.uwyo.edu/ela This Article is brought to you for free and open access by Wyoming Scholars Repository. It has been accepted for inclusion in Electronic Journal of Linear Algebra by an authorized editor of Wyoming Scholars Repository. For more information, please contact [email protected]. Recommended Citation Alvarez, Victor; Armario, Jose Andres; Frau, Maria Dolores; and Guidiel, Felix. (2012), "Embedding cocylic D-optimal designs in cocylic Hadamard matrices", Electronic Journal of Linear Algebra, Volume 24. DOI: https://doi.org/10.13001/1081-3810.1580 ELA EMBEDDING COCYCLIC D-OPTIMAL DESIGNS IN COCYCLIC HADAMARD MATRICES∗ V´ ICTOR ´ ALVAREZ†, JOS´ E ANDR´ ES ARMARIO†, MAR´ IA DOLORES FRAU†,AND F´ ELIX GUDIEL† Abstract. A method for embedding cocyclic submatrices with “large” determinants of orders 2tin certain cocyclic Hadamard matrices of orders 4tis described (tan odd integer). If these determinants attain the largest possible value, we are embedding D-optimal designs. Applications to the pivot values that appear when Gaussian elimination with complete pivoting is performed on these cocyclic Hadamard matrices are studied. Key words. D-optimal Designs, Cocyclic Hadamard matrices, Embedded matrices, Gaussian elimination pivots. AMS subject classifications. 05B20, 15A15, 65F40, 65F05. 1. Introduction. AHadamard matrix Hof order nis an n×nmatrix with elements ±1 and HHT=nI. A Hadamard matrix is said to be normalized if it has its first row and column all ones. We can always normalize a Hadamard matrix by multiplying rows and columns by −1. These matrices must have order 1, 2 or a multiple of 4. It is conjectured 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). Two Hadamard matrices H1and H2are called equivalent (or Hadamard equivalent, or H-equivalent) if one can be obtained from the other by a sequence of row and/or column interchanges and row and/or column negations. The question of classifying Hadamard matrices of order n > 28 remains unanswered and only partial results are known [6, 20]. Problems involving Hadamard matrices sound very easy, but they are notoriously difficult to solve. One interesting open problem, among others, is the question of the largest pivot encountered during the process of Gaussian elimination (GE) with complete pivoting for an n×nHadamard matrix H(the so called “growth factor” for H). Traditionally, backward error analysis for Gaussian elimination (GE), see e.g. ∗Received by the editors on November 23, 2011. Accepted for publication on March 24, 2012 Handling Editor: Oskar Maria Baksalary. †Department of Applied Math I, University of Seville, Avda. Reina Mercedes s/n, 41012 Seville, Spain ({valvarez,armario,mdfrau,gudiel}@us.es). 66 Electronic Journal of Linear Algebra ISSN 1081-3810 A publication of the International Linear Algebra Society Volume 24, pp. 66-82, June 2012 http://math.technion.ac.il/iic/ela ELA Embedding cocyclic D-optimal designs in cocyclic Hadamard matrices 67 [8], on a matrix A=ha(1) ij iis expressed in terms of the growth factor g(n, A) = maxi,j,k |a(k) ij | maxi,j |a(1) ij | which involves all the elements a(k) ij , k = 1,2,...,n, that occur during the elimination for a choice of pivoting strategy given. Matrices with the property where no row and column exchanges are needed during GE with complete pivoting are called completely pivoted (CP) or feasible. In other words, at each step of the elimination the element of largest magnitude (the “pivot”, denoted by pk) is located at the top left position of every appearing submatrix during the process. If A(k) denotes the absolute value of k×kprincipal minor of A, then mathematically Abeing CP means (or is equivalent to) that for each k, we have that A(k) is greater than or equal to the absolute value of any other k×kdeterminant that includes the first k−1 rows and columns. This is not necessarily the maximum k×kminor of A, but only the maximum k×kminor of Awhen its first k−1 rows and columns are fixed. For a CP matrix Awe have g(n, A) = max{p1, p2,...,pn} |a(1) 11 |. If a matrix is not initially CP, by applying row and column operations with complete pivoting we can always bring it to CP form. The following lemma gives a useful relation between pivots and minors. Lemma 1.1. [7] Let Abe a CP matrix. The magnitude of the pivots which appear after application of GE operations to Ais given by pj=A(j) A(j−1), j = 1,2, . . . , n, A(0) = 1. In 1969, Cryer [7] conjectured that if Ais a real n×nmatrix such that |ai,j | ≤ 1, then g(n, A)≤n, with equality if and only if Ais a Hadamard matrix. In 1991 Gould [15] proved that the first part of the conjecture is not true. He found matrices with growth bigger than their orders. Thus, the following remains open: Conjecture(Cryer) The growth of a Hadamard matrix is its order. This conjecture has been proven only for n= 4,8,12 and 16 (see [7, 10, 23]). Great difficulty arises in the study of this problem because H-equivalence operations do not preserve pivots, i.e. the H-equivalent matrices do not necessarily have the same Electronic Journal of Linear Algebra ISSN 1081-3810 A publication of the International Linear Algebra Society Volume 24, pp. 66-82, June 2012 http://math.technion.ac.il/iic/ela ELA 68 V. ´ Alvarez, J.A. Armario, M.D. Frau, and F. Gudiel pivot pattern. For instance, for n= 16 there are 34 pivot patterns although there are only 5 equivalence classes of Hadamard matrices for this order. Furthermore, many pivot patterns can be observed by permuting the rows and columns of any 20 by 20 Hadamard matrix and there are just 3 inequivalent matrices. However, the existence of D-optimal designs (and other specific submatrices with concrete determinants) that exist embedded in a Hadamard matrix have provided some clues on the pivot patterns (see [27, 25]). AD-optimal design of order nis an n×n(1,−1)-matrix having maximal determinant. Here and throughout this paper, for convenience, whenever a determinant or minor is mentioned, we mean its absolute value. 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 [16] that for every (−1,1)-matrix M, det(M)≤nn 2.(1.1) We recall that the original interest in Hadamard matrices stemmed from the fact that these matrices are the only ones that satisfy equality in (1.1). This has led to further study and tighter bounds for the maximal determinant for all (−1,1)-matrices of order n6= 0 (mod 4) have been found (see [5, 11, 12, 29, 21]). For instance, when n≡2 (mod 4), Ehlich in [11] and independently Wojtas in [29] proved that det(M)≤(2n−2)(n−2)n−2 2.(1.2) 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. Here, as usual, In denotes the identity matrix of order n, and Jndenotes the n×nmatrix all of whose entries are equal to one. In these circumstances, it may be proven 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, [14]). In the early 90s, a surprising link between homological algebra and Hadamard matrices [17] led to the study of cocyclic Hadamard matrices [18]. Hadamard matrices of many types are revealed to be (equivalent to) cocyclic matrices [9, 19]. Among them, Sylvester Hadamard matrices, Williamson Hadamard matrices, Ito Hadamard matrices and Paley Hadamard matrices. Furthermore, the 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. Electronic Journal of Linear Algebra ISSN 1081-3810 A publication of the International Linear Algebra Society Volume 24, pp. 66-82, June 2012 http://math.technion.ac.il/iic/ela ELA Embedding cocyclic D-optimal designs in cocyclic Hadamard matrices 69 The main advantages of the cocyclic framework concerning 4tby 4tHadamard matrices may be summarized 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 s generators), instead of the whole set of 216t2matrices of order 4twith entries in {−1,1}. It was shown in [1] that the cocyclic technique can certainly be extended to handle the maximal determinant problem at least when n≡2 (mod 4). More concretely, the study focused on cocyclic matrices over the dihedral group of 2telements with t odd. Based on exhaustive and heuristic searches, three algorithms for constructing cocyclic matrices with large determinants were provided. In this paper we are interested in embedding (cocyclic) submatrices of orders 2twith large determinants in certain cocyclic Hadamard matrices of orders 4t. If these determinants attain the largest possible value, we are embedding D-optimal designs. Also, we discuss the relation between the existence of these submatrices and the growth factor for these Hadamard matrices. In Section 2, an algebraic formalism (in terms of cocycles) to describe two combinatorial operations on a matrix (eliminate and add certain rows and columns) is provided. As a consequence of this formalism a method arises for embedding (cocyclic) submatrices of orders 2twith large determinants in certain cocyclic Hadamard matrices of orders 4t. In Section 3, we connect the existence of specific matrices embedded in cocyclic Hadamard matrices of order 20 with the values of the pivots that appear when we perform Gaussian elimination with complete pivoting on them. The last section is devoted to conclusions and future work. Notation. Throughout this paper we use −for −1 and 1 for +1. We write Hfor a Hadamard matrix and Djfor a D-optimal design of order j. The notation Dj∈H means Djis embedded in H. 2. Cocyclic D-optimal designs embedded in Cocyclic Hadamard matrices. Assume throughout that G={g1= 1, g2,...,gn}is a multiplicative group, not necessarily abelian. Functions ψ:G×G→ h−1i∼ =Z2which satisfy ψ(gi, gj)ψ(gigj, gk) = ψ(gj, gk)ψ(gi, gjgk),∀gi, gj, gk∈G(2.1) are called (binary) cocycles (over G) [22]. A cocycle is a coboundary ∂φ if it is derived from a set mapping φ:G→ h−1iby ∂φ(a, b) = φ(a)φ(b)φ(ab)−1. A cocycle ψis naturally displayed as a cocyclic matrix (or G-matrix) Mψ; that is, Electronic Journal of Linear Algebra ISSN 1081-3810 A publication of the International Linear Algebra Society Volume 24, pp. 66-82, June 2012 http://math.technion.ac.il/iic/ela ELA 70 V. ´ Alvarez, J.A. Armario, M.D. Frau, and F. Gudiel the entry in the (i, j)th position of the cocyclic matrix is ψ(gi, gj), for all 1 ≤i, j ≤n. A cocycle ψis normalized if ψ(1, gj) = ψ(gi,1) = 1 for all gi, 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). A basis Bfor 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, 1gd6=gi. Remark 2.1. ([2, Lemma 1]) In particular, for d6= 1, every row s /∈ {1, d}in M∂dcontains precisely two −1s, which are located at the positions (s, d)and (s, e), for ge=g−1 sgd. Furthermore, the first row is always formed by 1s, while the d-th row is formed all by −1s, except in 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). 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 2.2. ([19, lemma 6.6]) Let Mψbe a cocyclic matrix, [Gr(Mψ)]ij =ψ(gig−1 j, gj)X g∈G ψ(gig−1 j, g),(2.2) [Gc(Mψ)]ij =ψ(gi, g−1 igj)X g∈G ψ(g, g−1 igj).(2.3) Electronic Journal of Linear Algebra ISSN 1081-3810 A publication of the International Linear Algebra Society Volume 24, pp. 66-82, June 2012 http://math.technion.ac.il/iic/ela ELA Embedding cocyclic D-optimal designs in cocyclic Hadamard matrices 71 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 every row sum (apart from the first) is zero [18]. In fact, this is a straightforward consequence of Proposition 2.2. Analyzing this relation from a new perspective, one could think of normalized cocyclic matrices meeting the bound (1.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 proved in [1] 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 X i=2  n X 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.1) if and only if RE(M) is minimum. This condition may be generalized to the case n≡2 (mod 4). For the remainder of the paper tdenotes an odd positive integer. Proposition 2.3. [1] Let Mbe a normalized cocyclic matrix over Gof order n= 2t. Then RE(M)≥2t−2. 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 (1.2). Proposition 2.4. [1] If a cocyclic matrix Mof order n= 2tmeets the bound (1.2), then RE(M) = 2t−2. Unfortunately, although having minimum absolute row excess is a necessary and sufficient condition for meeting the bound (1.1), it is just a necessary (but not sufficient, in general, see [1, Table 5] ) condition for meeting the bound (1.2). But there is some empirical evidence that matrices having minimum absolute row excess correspond with matrices having large determinants, see Table 2.1., page 11. From now on, we fix G=D2mas the dihedral group with presentation ha, b:am= b2= (ab)2= 1i, with ordering {1, a, . . . , am−1, b, ab, . . . , am−1b}and indexed as Electronic Journal of Linear Algebra ISSN 1081-3810 A publication of the International Linear Algebra Society Volume 24, pp. 66-82, June 2012 http://math.technion.ac.il/iic/ela ELA 72 V. ´ Alvarez, J.A. Armario, M.D. Frau, and F. Gudiel {1,...,2m}. A basis for cocycles over D2mconsists in (see [1, 2]): •Let mbe an odd positive integer. B={∂2,...,∂2m−1, β2}. •Let mbe an even positive integer. B={∂2,...,∂2m−2, β1, β2, γ}. Here ∂idenotes the coboundary associated with the ith-element of the dihedral group D2m, that is ai−1 (mod m)b⌊i−1 m⌋. And β1, β2and γare the representative cocycles in cohomology, i.e. the cocyclic matrices coming from inflation are Mβ1=Jm⊗ 1 1 1−and Mβ2=1 1 1−⊗Jm. We use A⊗Bfor denoting the usual Kronecker product of matrices, that is, the block matrix whose blocks are aij B. The transgression cocyclic matrix Mγis Mγ=AmAm BmBmfor the m×m matrices Am= (aij) and Bm= (bij) where aij =−1i+j > m + 1 1 otherwise, and bij =−1i < j 1 otherwise. It has been observed that cocyclic Hadamard matrices over the dihedral group mostly use Mβ2◦Mγand do not use Mβ1(see [3, 13]). In the sequel, we consider only cocyclic Hadamard matrices of this form M∂i1◦ · · · ◦ M∂iw◦Mβ2◦Mγ. In what follows, the goal is to provide an algebraic formalism (in terms of cocycles) to describe two combinatorial operations on a matrix: the first consisting in eliminating and the second in adding certain rows and columns. Remark 2.5. D2tis trivially embedded as a subgroup of D4t, the dihedral group of 4telements. Concretely, if D4t=ha, b:a2t=b2= (ab)2= 1ithen D2t∼ =ha2, bi ⊂ D4t. Proposition 2.6. Let Mψbe a cocyclic matrix over D4t, then the 2tby 2tmatrix obtained by eliminating from Mψthe rows and columns indexed with an even number is a cocyclic matrix over D2tand we denote it as ˜ Mψ. Proof. On the one hand, taking into account the ordering fixed above, D4t= {1, a, . . ., a2t−1, b, ab, . . . , a2t−1b}, the rows and columns in Mψindexed with an odd number correspond with {1, a2,...,a2t−2, b, a2b, . . . , a2t−2b}=ha2, bi. On the other hand, if ψ|ha2,bidenotes the restriction of ψto the subgroup ha2, bi, then ψ|ha2,bisatisfies (2.1) for G=ha2, bi∼ =D2tsince ψsatisfies (2.1) for G=D4t. Electronic Journal of Linear Algebra ISSN 1081-3810 A publication of the International Linear Algebra Society Volume 24, pp. 66-82, June 2012 http://math.technion.ac.il/iic/ela ELA Embedding cocyclic D-optimal designs in cocyclic Hadamard matrices 73 In other words, ψ|ha2,biis a cocycle for G=ha2, biand ˜ Mψ=Mψ|ha2,bi. Lemma 2.7. Let Mψ1and Mψ2be cocyclic matrices over D4tthen ˜ Mψ1·ψ2=˜ Mψ1◦˜ Mψ2, where Mψ1·ψ2=Mψ1◦Mψ2. Proof. It is a straightforward consequence of the pointwise multiplication. From now on, B={∂2,...,∂4t−2, β1, β2, γ}and ˜ B={˜ ∂2,...,˜ ∂2t−1,˜ β2}denote a basis of cocycles for D4tand D2t, respectively. Lemma 2.8. The following identities hold: ˜ M∂i=(J2tieven M˜ ∂i+1 2 iodd ,˜ Mβi=(J2ti= 1 M˜ ∂β2i= 2 and ˜ Mγ= t−1 2 Y i=1 M˜ ∂2i◦M˜ ∂2t−2i+1 . Proof. The identities above follow by direct inspection. Given MψaD4t-matrix. The following result describes, in terms of cocycles, the unique D2t-matrix obtained by eliminating from Mψthe rows and columns indexed with an even number. Theorem 2.9. Given a D4t-matrix Mψ=Mα2 ∂2◦ · · · ◦ Mα4t−2 ∂4t−2◦Mk1 β1◦Mk2 β2◦Mk3 γ where (α2,...,α4t−2, k1, k2, k3)denotes a concrete 4t-uple with entries 0 or 1. Then ˜ Mψ=˜ Mα2 ∂2◦ · · · ◦ ˜ Mα4t−2 ∂4t−2◦˜ Mk1 β1◦˜ Mk2 β2◦˜ Mk3 γ = 2t−2 Y j=1 Mα2j+1 ˜ ∂j+1 ◦Mk2 ˜ β2◦  t−1 2 Y i=1 M˜ ∂2i◦M˜ ∂2t−2i+1   k3 . Proof. It follows from Lemmas 2.7 and 2.8. The whole set of D4t-matrices constructed by adding certain rows and columns to a D2t-matrix M˜ ψis provided in the next theorem. Theorem 2.10. Given a D2t-matrix M˜ ψ=M˜ ∂i1◦ · · · ◦ M˜ ∂iw◦M˜ β2. Electronic Journal of Linear Algebra ISSN 1081-3810 A publication of the International Linear Algebra Society Volume 24, pp. 66-82, June 2012 http://math.technion.ac.il/iic/ela ELA 80 V. ´ Alvarez, J.A. Armario, M.D. Frau, and F. Gudiel 8×8 matrices, we have that it is always lesser than or equal to D10(7) = 2560. Therefore, D10(8) = H′(8). •Taking into account that D9/∈D10, then the maximum 9 ×9 minor of D10 is lesser than or equal to 12288 (the second greatest, see the spectrum of the determinant function [26]). Due to D10(9) = 12288 then D10(9) = H′(9). Now, taking H′as the CP extension of ˆ H, the proof follows. Corollary 3.4. The pivot pattern (1,2,2,4,3,10/3,16/5,5,24/5,6) for the first ten pivots appears in the three classes for Hadamard matrices of orden 20. In a recent search that we have performed, we have found this result: •There is a CP matrix Hequivalent to the following D20-Hadamard matrix Mψ=M∂2◦M∂4◦M∂8◦M∂10 ◦M∂13 ◦M∂14 ◦Mβ2◦Mγsuch that H(10) = 125·29. Although we didn’t find any result in the literature asserting that if the existence of a submatrix with large determinant is proven for a matrix A, then we can indeed assume that it always appears in the upper left corner for some CP matrix A′ equivalent to A. It seems to be true at least when this submatrix reaches the largest determinant (see [25, p.1763]). Also, the above result confirms this for other large determinant (the second largest in Table 2.1). 4. Conclusions and further work. In this paper we have described a method for embedding a D2t-matrix in the rows and columns indexed with an odd number of aD4t-Hadamard matrix whenever it is possible. If this D2t-matrix has a determinant attaining the largest possible value, we get a D-optimal design. This method relies on two combinatorial operations on a cocyclic matrix: eliminate and add certain rows and columns. The idea behind this approach has been to translate these two combinatorial operations into a pure algebraic framework (concretely, in terms of cocycles). Finally, our study has provided some information about the pivot values when Gaussian elimination with complete pivoting is performed on D20-Hadamard matrices. Our next goals are: •Study the relationship between the RE and the values of the determinant for D2t-matrices. •Design heuristic searches based on RE for Algorithm 2.12. •Study if ˜ Mψsatisfies that det( ˜ Mψ) (4t−2)(2t−2)t−1≥0.85 implies that a CP matrix M equivalent to Mψexists such that M(2t) = det( ˜ Mψ). •Study the pivot structure of D4t-Hadamard matrices. •Design an “efficient” method to construct D4t-Hadamard matrices from D2tmatrices. Electronic Journal of Linear Algebra ISSN 1081-3810 A publication of the International Linear Algebra Society Volume 24, pp. 66-82, June 2012 http://math.technion.ac.il/iic/ela ELA Embedding cocyclic D-optimal designs in cocyclic Hadamard matrices 81 Acknowledgment. This work has been partially supported by the research projects FQM-016 and P07-FQM-02980 from JJAA and MTM2008-06578 from MICINN (Spain) and FEDER (European Union). The authors would also like to thank Kristeen Cheng for her reading of this article. REFERENCES [1] V. ´ Alvarez, J.A. Armario, M.D. Frau and F. Gudiel. The maximal determinant of cocyclic (−1,1)-matrices over D2t.Linear Algebra Appl., 436:858–873, 2011. [2] V. ´ Alvarez, J.A. Armario, M.D. Frau and P. Real. A system of equations for describing cocyclic Hadamard matrices. J. Comb. Des., 16:276–290, 2008. [3] V. ´ Alvarez, J.A. Armario, M.D. Frau and P. Real. The homological reduction method for computing cocyclic Hadamard matrices. J. Symb. Comput., 44:558-570, 2009. [4] J.A. Armario. On an inequivalence criterion for cocyclic Hadamard matrices. Cryptogr. Commun., 2:247–259, 2010. [5] G. Barba. Intorno al teorema di Hadamard sui determinanti a volre massimo. Giornale di Matematiche di Battaglini, 71:70–86, 1933. [6] R. Craigen and H. Kharaghani. Hadamard matrices and Hadamard designs. In: Handbook of Combinatorial Designs, 2nd edn., Chapman and Hall/CRC press, Boca Raton, 273–280, 2006. [7] C. W. Cryer. Pivot size in Gaussian elimination. Numer. Math., 12:335–345, 1968. [8] J. Day and B. Peterson. Growth in Gaussian elimination. Amer. Math. Monthly, 95:489–513, 1988. [9] W. de Launey and K.J. Horadam. A weak difference set construction for higher dimensional designs. Des. Codes Cryptogr. 3:75–87, 1993. [10] A. Edelman and W. Mascarenhas. On the complete pivoting conjecture for a Hadamard matrix of order 12. Linear and Multilinear Algebra, 38:181–187, 1995. [11] H. Ehlich. Determiantenabsch¨atzungen f¨ur bin¨are Matrizen. Math. Z., 83:123–132, 1964. [12] H. Ehlich. Determiantenabsch¨atzung f¨ur bin¨are Matrizen mit n≡3 (mod 4). Math. Z., 84:438–447, 1964. [13] D. L. Flannery. Cocyclic Hadamard matrices and Hadamard groups are equivalent. J. Algebra, 192:749–779, 1997. [14] R. J. Fletcher, C. Koukouvinos and J. Seberry. New skew-Hadamard matrices of order 4 ·59 and new D-optimal designs of order 2 ·59. Discrete Math., 286:252–253, 2004. [15] N. Gould. On growth in Gaussian elimination with pivoting. SIAM J. Matrix Anal. Appl., 12:354–361, 1991. [16] J. Hadamard. R´esolution d’une question relative aux d´eterminants. Bull. des Sciences Math., (2) 17:240–246, 1893. [17] K.J. Horadam and W. de Launey. Cocyclic development of designs. J. Algebraic Combin., 2:267–290, 1993; Erratum: J. Algebraic Combin., 3:129, 1994. [18] K.J. Horadam and W. de Launey. Generation of Cocyclic Hadamard matrices. In: Computational algebra and number theory. Math. Appl., Kluwer Acad. Publ, Dordrecht, 279–290, 1995. [19] K.J. Horadam. Hadamard Matrices and Their Applications. Princeton University Press, Princeton, NJ, 2007. [20] H. Kharaghani and B. Tayfeh-Rezaie. On the classification of Hadamard matrices of order 32. J. Comb. Des., 18:328-336, 2010. [21] C. Koukouvinos, M. Mitroulli and J. Seberry. Bounds on the Maximum Determinant for (−1,1) Matrices. Bulletin of the ICA, 29:39–48, 2000. Electronic Journal of Linear Algebra ISSN 1081-3810 A publication of the International Linear Algebra Society Volume 24, pp. 66-82, June 2012 http://math.technion.ac.il/iic/ela ELA 82 V. ´ Alvarez, J.A. Armario, M.D. Frau, and F. Gudiel [22] S. MacLane. Homology. Classics in Mathematics Springer-Verlang, Berlin, 1995, Reprint of the 1975 edition. [23] K. Kravvaritis and M. Mitrouli. The growth factor of a Hadamard matrix of order 16 is 16. Numer. Linear Algebra Appl., 16:715–743, 2009. [24] H. Kharaghani and W. Orrick. D-optimal matrices. In: Handbook of Combinatorial Designs, 2nd edn., Chapman and Hall/CRC press, Boca Raton, 317–321, 2006. [25] M. Mitrouli. D-optimal designs embedded in Hadamard matrices and their effect on the pivot patterns. Linear Algebra Appl., 434:1761–1772, 2011. [26] W. Orrick and B. Solomon. The Hadamard Maximal Determinant Problem. (website), http://www.indiana.edu/∼maxdet/. [27] J. Seberry and M. Mitrouli. Some Remarks on Hadamard matrices. Cryptogr. Commun., 2:293–306, 2010. [28] J. Seberry, T. Xia, C. Koukouvinos and M. Mitrouli. The maximal determinant and subdeterminants of ±1 matrices. Linear Algebra Appl., 373:297–310, 2003. [29] W. Wojtas. On Hadamard’s inequallity for the determinants of order non-divisible by 4. Colloq. Math., 12:73–83, 1964. Electronic Journal of Linear Algebra ISSN 1081-3810 A publication of the International Linear Algebra Society Volume 24, pp. 66-82, June 2012 http://math.technion.ac.il/iic/ela