Prolific Generation of Williamson Type Matrices

Table of contents

1. INTRODUCTION

e recall the following definitions from Craigen and Kharaghani [1].

1.1 Hadamard Matrix [or H-Matrix] : An n x n (+1, -1) matrix H is a Hadamard matrix if HH T = nI n . It is conjectured that an H-matrix exists for every order n = 4t where t is a positive integer. 1 Back circulant bcirc (0 0 .... 0 1) is called back diagonal matrix.

1.5 Matrics used in the construction of H-Matrices : n x n ( +1, -1) matrices A, B, C, D satisfying AA T + BB T + CC T + DD T = 4nI n (1) Are (i) Williamson Matrices if they are symmetric and circulant.

(ii) Goethals Seidel type matrices if they are circulant but not necessarily symmetric. (iii) Williamson type matrices if they are pairwise amicable. vide [1] 1.5 Matrics used in the construction of H-Matrices : n x n ( +1, -1) matrices A, B, C, D satisfying AA T + BB T + CC T + DD T = 4nI n ( 1) are (i) Williamson Matrices if they are symmetric and circulant. (ii) Goethals Seidel type matrices if they are circulant but not necessarily symmetric. (iii) Williamson type matrices if they are pairwise amicable. vide [1] 1.6 Orthogonal Design OD (4t, t, t, t, t): OD (4t, t, t, t, t) is an orthogonal design of order 4t and type (t, t, t, t), t is a +ve integer, which is defined as an 4t x 4t matrix with entries ±A, ±B, ±C, ±D (A,B,C,D are commuting indeterminates) satisfying XX T = t(A 2 +B 2 +C 2 +D 2 )I 4t For details vide Geramita and Seberry [2] II.

2. PREVIOUS WORK

If A,B,C,D are Williamson or Williamson type Matrices then the H-matrix, H can be constructed as

A -B -C -D B A -D C H = C D A ?B D -C B A

Originally Williamson [3] constructed Williamson matrices for m ? 21, m=25, 37, 43. Baumert, Golomb and Hall [4] constructed Williamson matrix for m = 23. Baumert and Hall [5] found all solutions for 3 ? m ? 23 and some solutions for m =25, 27, 37, 43. For details of the solutions vide Hall [6]. Baumert [7] gave one solution for m = 29. Koukouvinos and Kounians [8] made exhaustive search for all Williamson atrices of order 33.

Williamson type martrices have been constructed by Seberry [9], [10] & Whiteman [11].

If A, B, C, D are circulant matrices satisfying equation ( 1) then H-matrix G can be obtained as the Goethals & Seidel array [12] A

?BR ?CR ?DR BR A ?D T R C T R G = CR DR A -BR Where R is a (0,1) -back DR ?CR BR A diagonal matrix.

A Quadruple of Williamson type matrices A,B,C,D has advantage over other Quadruples used to construct H-matrices. The following lemma of Baumert and Hall [vide Colbourn & Dimtz [13] shows that from a quadruple(A,B,C,D) of Williamson type matrices. Several Hadamard matrices can be constructed.

Lemma 1: The existence of orthogonal design OD(4t; t,t,t,t) and four Williamson type matrices of order n implies the existence of H-matrices of order 4nt. Though it is generally conjectured that the above OD exists for all t, the existence is known for t ?73 (vide Colbourn and Dinitz ([14] p295).

3. III. METHODOLOGY

3.1 Some basic facts: We will begin with the following (new) definitions: (we assume that n is an odd positive integer) (i) Input Set A set S k ={n 1 , n 2 , ........n k } of inergers where 0 < n i < n, k is even, will be called an input set. The input set S k will be called symmetric if n i ?? S k ? n -n i ?? S k (ii) Output Vector Let m = (n-1)/2. Let S k be an input set defined above Let S k + j = { n 1+j , n 2+j , .........n k+j }, where + stands for addition mod n. Let r j = S k+j -S k = the order of the set ( S k+j ) -S k ----( 1) and e j = n -4r j , j = 1, 2, 3 .........m ----(2) Binary reprentation of S k : row vector b k =(a 1 , a 2 , . . . ..a n -1 ) will be called binary representation vector ((BR)-vector) of S k if a i = -1 if i ?? S k & a i = +1, otherwise

4. Method of Construction

Step-I Generation of size vector First construct 4-vector (k 1 , k 2 , k 3 ; k 4 ) which consists of feasible sizes of the four input sets as follows Express 4n as 4n = n Step-IV Sum of output vectors corresponding to three symmetric input sets Form the set S = {s=(s 1 , s 2 , s 3 , ........ s m ) : s is the sum of triplets of output vectors corresponding to symmetric input sets S k1 , S k2 , S k3 obtained in Step II (a) Omit all vectors ?? S for which |si| ? n -2. Let S' be the resulting set. Also record the correspondences (S k1 , S k2 , S k3 ) ? s ?? S' .

Step-V Set of output vectors corresponding to S k4

Form the set T of output vectors t = (t 1 , t 2 , t 3 , .. (b) In the multiset M of differences obtained in (a) i appears f i times i = 1, 2, 3, ... m, where f i are numbers defined in (ii) t ? T will be called feasible vector, if the set D 1 defined in (iii) exists. Each feasible t ? T will give Williamson type matrices A, B, C, D which can be obtained as follows Circulant A, B, C can be obtained through the correspondence : feasible t ?s ? {A, B, C} using the correspondence in Step-IV.

...... t m ) of S k4 obtained in Step II (b) Let T'= {-t = (-t 1 , -t 2 , -t 3 , ........ -t m )} Record all correspondences S k4 ? -t Step-VI

The back circulant matrix D can be obtained as follows : [15], [16], [17], [18]). Using the method described above, we have obtained all Williamson type matrices of order 9,11,13,15 & 17 by exhaustive computing search.

(iv) if D 1 = (d 1 ,

IV.

5. RESULTS

Williamson type matrices of order 9

Type -I (4 x 9 = 1 2 + 1 2 + 3 2 + 5 2 ) Subtype -I (Size Vector (4, 2, 6; 4))

Sl.no Input Set Set of Williamson type Matrices Output Vector 1 {3,6} A circ (1 1 1 -1 1 1 -1 1 1) 1 1 5 1 {1,4,5,8} B circ (1 -1 1 1 -1 -1 1 1 -1) -3 -3 1 1 {2,3,4,5,6,7} C circ (1 1 -1 -1 -1 -1 -1 -1 1) 5 1 -3 -3 {3,5,7,8} D circ (1 1 1 -1 1 -1 1 -1 -1) -3 1 -3 1 2 {3,6} A circ (1 1 1 -1 1 1 -1 1 1) 1 1 5 1 {1,2,7,8} B circ (1 -1 -1 1 1 1 1 -1 -1) 1 -3 1 -3 {1,3,4,5,6,8} C circ (1 -1 1 -1 -1 -1 -1 1 -1) -3 5 -3 1 {3,6,7,8} D circ (1 1 1 -1 1 1 -1 -1 -1) 1 -3 -3 1 3 {3,6} A circ (1 1 1 -1 1 1 -1 1 1) 1 1 5 1 {2,4,5,7} B circ (1 1 -1 1 -1 -1 1 -1 1 1) -3 1 1 -3 {1,2,3,6,7,8} C circ (1 -1 -1 -1 1 1 -1 -1 -1) 1 -3 -3 5 {4,6,7,8} D circ (1 1 1 1 -1 1 -1 -1 -1 ) 1 1 -3 -3 Subtype-II (Size Vector (2, 4, 4; 3)) Sl.no Input Set Set of Williamson type Matrices Output Vector 1 {2,7} A circ (1 1 -1 1 1 1 1 -1 1) 1 1 1 5 {1,4,5,8} B circ (1 -1 1 1 -1 -1 1 1 -1) -3 -3 1 1 {3,4,5,6} C circ (1 1 1 -1 -1 -1 -1 1 1) 5 1 -3 -7 {3,6,8} D circ (1 1 1 -1 1 1 -1 1 -1) -3 1 1 1 2 {4,5} A circ (1 1 1 1 -1 -1 1 1 1) 5 1 1 1 {1,3,6,8} B circ (1 -1 1 -1 1 1 -1 1 -1) -7 5 -3 1 {1,2,7,8} C circ (1 -1 -1 1 1 1 1 -1 -1) 1 -3 1 -3 {4,7,8} D circ (1 1 1 1 -1 1 1 -1 -1) 1 -3 1 1 3 {1,8} A circ (1 -1 1 1 1 1 1 1 -1) 1 5 1 1 {2,4,5,7} B circ (1 1 -1 1 -1 -1 1 -1 1) -3 1 1 -3 {2,3,6,7} C circ (1 1 -1 -1 1 1 -1 -1 1) 1 -7 -3 5A circ (1 1 1 -1 1 -1 -1 1 -1 1 1) -1 3 3 -5 -1 {1,2,3,8,9,10} B circ (1 -1 -1 -1 1 1 1 1 -1 -1 -1) 3 -1 -5 -1 -1 {1,2,3,5,6,8,9,10} C circ (1 -1 -1 -1 1 -1 -1 1 -1 -1 -1) -1 -1 3 7 -1 {4,6,9,10} D circ (1 1 1 1 -1 1 -1 1 1 -1 -1) -1 -1 -1 -1 3 2 {2,4,7,9} A circ (1 1 -1 1 -1 1 1 -1 1 -1 1) -5 3 -1 -1 3 {2,3,5,6,8,9} B circ (1 1 -1 -1 1 -1 -1 1 -1 -1 1) -1 -5 3 -1 -1 {2,3,4,5,6,7,8,9} C circ (1 1 -1 -1 -1 -1 -1 -1 -1 -1 1) 7 3 -1 -1 -1 {3,7,9,10} D circ (1 1 1 -1 1 1 1 -1 1 -1 -1) -1 -1 -1 3 -1 3 {3,4,7,8} A circ (1 1 1 -1 -1 1 1 -1 -1 1 1) 3 -5 -1 3 -1 {1,4,5,6,7,10} B circ (1 -1 1 1 -1 -1 -1 -1 1 1 -1) -1 -1 -1 -5 -3 {1,3,4,5,6,7,8,10} C circ (1 -1 1 -1 -1 -1 -1 -1 -1 1 -1) -1 7 -1 3 -1 {4,7,8,10} D circ (1 1 1 1 -1 1 1 -1 -1 1 -1) -1 -1 3 -1 -1 4 {1,2,9,10} A circ (1 -1 -1 1 1 1 1 1 1 -1 -1) 3 -1 3 -1 -5 {1,3,4,7,8,10} B circ (1 -1 1 -1 -1 1 1 -1 -1 1 -1) -5 -1 -1 3 -1 {1,2,3,4,7,8,9,10} C circ (1 -1 -1 -1 -1 1 1 -1 -1 -1 -1) 3 -1 -1 -1 7 {5,7,9,10} D circ (1 1 1 1 1 -1 1 -1 1 -1 -1) -1 3 -1 -1 -1 5 {1,5,6,10} A circ (1 -1 1 1 1 -1 -1 1 1 1 -1) -1 -1 -5 3 3 {2,4,5,6,7,9} B circ (1 1 -1 1 -1 -1 -1 -1 1 -1 1) -1 3 -1 -1 -5 {1,2,4,5,6,7,9,10} C circ (1 -1 -1 1 -1 -1 -1 -1 1 -1 -1) -1 -1 7 -1 3 {5,8,9,10} D circ (1 1 1 1 1 -1 1 1 -1 -1 -1) 3 -1 -1 -1 -1A circ (1 -1 1 1 1 -1 -1 1 1 1 -1) -1 -1 -5 3 3 {4,5,6,7} B circ (1 1 1 1 -1 -1 -1 -1 1 1 1) 7 3 -1 -5 -5 {1,2,3,5,6,8,9,10} C circ (1 -1 -1 -1 1 -1 -1 1 -1 -1 -1) -1 -1 3 7 -1 {2,4,7,9,10} D circ (1 1 -1 1 -1 1 1 -1 1 -1 -1) -5 -1 3 -5 3 2 {2,4,7,9} A circ (1 1 -1 1 -1 1 1 -1 1 -1 1) -5 3 -1 -1 3 {3,4,7,8} B circ (1 1 1 -1 -1 1 1 -1 -1 1 1) 3 -5 -1 3 -1 {2,3,4,5,6,7,8,9} C circ (1 1 -1 -1 -1 -1 -1 -1 -1 -1 1) 7 3 -1 -1 -1 {3,6,8,9,10} D circ (1 1 1 -1 1 1 -1 1 -1 -1 -1) -5 -1 3 -1 -1 3 {2,3,8,9} A circ (1 1 -1 -1 1 1 1 1 -1 -1 1) 3 -5 -5 -1 7 {1,2,9,10} B circ (1 -1 -1 1 1 1 1 1 1 -1 -1) 3 -1 3 -1 -5 {1,3,4,5,6,7,8,10} C circ (1 -1 1 -1 -1 -1 -1 -1 -1 1 -1) -1 7 -1 3 -1 {3,6,8,9,10} D circ (1 1 1 -1 1 1 -1 1 -1 -1 -1) -5 -1 3 -1 -1 4 {1,4,7,10} A circ (1 -1 1 1 -1 1 1 -1 1 1 -1) -5 -1 7 -5 3 {3,4,7,8} B circ (1 1 1 -1 -1 1 1 -1 -1 1 1) 3 -5 -1 3 -1 {2,3,4,5,6,7,8,9} C circ (1 1 -1 -1 -1 -1 -1 -1 -1 -1 1) 7 3 -1 -1 -1 {3,5,7,9,10} D circ (1 1 1 -1 1 -1 1 -1 1 -1 -1) -5 3 -5 3 -1 5 {2,4,7,9} A circ (1 1 -1 1 -1 1 1 -1 1 -1 1) -5 3 -1 -1 3 {4,5,6,7} B circ (1 1 1 1 -1 -1 -1 -1 1 1 1) 7 3 -1 -5 -5 {1,2,3,5,6,8,9,10} C circ (1 -1 -1 -1 1 -1 -1 1 -1 -1 -1) -1 -1 3 7 -1 {3,4,7,9,10} D circ (1 1 1 -1 -1 1 1 -1 1 -1 -1) -1 -5 -1 -1 3A circ (1 1 1 -1 1 -1 -1 1 -1 1 1) -1 3 3 -5 -1 {3,4,7,8} B circ (1 1 1 -1 -1 1 1 -1 -1 1 1) 3 5 -1 3 -1 {1,3,4,5,6,7,8,10} C circ (1 -1 1 -1 -1 -1 -1 -1 -1 1 -1) -1 7 -1 3 -1 {3,4,7,9,10} D circ (1 1 1 -1 -1 1 1 -1 1 -1 -1) -1 -5 -1 -1 3 7 {3,5,6,8} A circ (1 1 1 -1 1 -1 -1 1 -1 1 1) -1 3 3 -5 -1 {2,3,8,9} B circ (1 1 -1 -1 1 1 1 1 -1 -1 1) 3 -5 -5 -1 7 {1,3,4,5,6,7,8,10} C circ (1 -1 1 -1 -1 -1 -1 -1 -1 1 -1) -1 7 -1 3 -1 {3,6,7,9,10} D circ (1 1 1 -1 1 1 -1 -1 1 -1 -1) -1 -5 3 3 -5 8 {1,4,7,10} A circ (1 -1 1 1 -1 1 1 -1 1 1 -1) -5 -1 7 -5 3 {1,5,6,10} B circ (1 -1 1 1 1 -1 -1 1 1 1 -1) -1 -1 -5 3 3 {2,3,4,5,6,7,8,9} C circ (1 1 -1 -1 -1 -1 -1 -1 -1 -1 1) 7 3 -1 -1 -1 {3,6,7,8,10} D circ (1 1 1 -1 1 1 -1 -1 -1 1 -1) -1 -1 -1 3 -5 9 {2,4,7,9} A circ (1 1 -1 1 -1 1 1 -1 1 -1 1) -5 3 -1 -1 3 {1,2,9,10} B circ (1 -1 -1 1 1 1 1 1 1 -1 -1) 3 -1 3 -1 -5 {1,2,3,4,7,8,9,10} C circ (1 -1 -1 -1 -1 1 1 -1 -1 -1 -1) 3 -1 -1 -1 7 {3,6,7,8,10} D circ (1 1 1 -1 1 1 -1 -1 -1 1 -1) -1 -1 -1 3 -5 10 {2,5,6,9} A circ (1 1 -1 1 1 -1 -1 1 1 -1 1) -1 -5 3 7 -5 {3,5,6,8} B circ (1 1 1 -1 1 -1 -1 1 -1 1 1) -1 3 3 -5 -1 {1,2,3,4,7,8,9,10} C circ (1 -1 -1 -1 -1 1 1 -1 -1 -1 -1) 3 -1 -1 -1 7 {4,6,8,9,10} D circ (1 1 1 1 -1 1 -1 1 -1 -1 -1) -1 3 -5 -1 -1 11 {1,5,6,10} A circ (1 -1 1 1 1 -1 -1 1 1 1 -1) -1 -1 -5 3 3 {1,2,9,10} B circ (1 -1 -1 1 1 1 1 1 1 -1 -1) 3 -1 3 -1 -5 {1,2,4,5,6,7,9,10} C circ (1 -1 -1 1 -1 -1 -1 -1 1 -1 -1) -1 -1 7 -1 3 {4,6,8,9,10} D circ (1 1 1 1 -1 1 -1 1 -1 -1 -1) -1 3 -5 -1 -1 12 {1,3,8,10} A circ (1 -1 1 -1 1 1 1 1 -1 1 -1) -5 7 -5 3 -1 {1,2,9,10} B circ (1 -1 -1 1 1 1 1 1 1 1 -1 -1) 3 -1 3 -1 -5 {1,2,4,5,6,7,9,10} C circ (1 -1-1 1 -1 -1 -1 -1 1 -1 -1) -1 -1 7 -1 3 {4,5,8,9,10} D circ (1 1 1 1 -1 -1 1 1 -1 -1 -1) 3 -5 -5 -1 3 13 {1,3,8,10} A circ (1 -1 1 -1 1 1 1 1 -1 1 -1) -5 7 -5 3 -1 {3,4,7,8} B circ (1 1 1 -1 -1 1 1 -1 -1 1 1) 3 -5 -1 3 -1 {1,2,4,5,6,7,9,10} C circ (1 -1 -1 1 -1 -1 -1 -1 1 -1 -1) -1 -1 7 -1 3 {4,7,8,9,10} D circ (1 1 1 1 -1 1 1 -1 -1 -1 -1) 3 -1 -1 -5 -1 14 {1,5,6,10} A circ (1 -1 1 1 1 -1 -1 1 1 1 -1) -1 -1 -5 3 3 {3,5,6,8} B circ (1 1 1 -1 1 -1 -1 1 -1 1 1) -1 3 3 -5 -1 {1,2,3,5,6,8,9,10} C circ (1 -1 -1 -1 1 -1 -1 1 -1 -1 -1) -1 -1 3 7 -1 {4,7,8,9,10} D circ (1 1 1 1 -1 1 1 -1 -1 -1 -1) 3 -1 -1 -5 -1 15 {2,4,7,9} A circ (1 1 -1 1 -1 1 1 -1 1 -1 1) -5 3 -1 -1 3 {2,5,6,9} B circ (1 1 -1 1 1 -1 -1 1 1 -1 1) -1 -5 3 7 -5 {1,2,3,4,7,8,9,10} C circ (1 -1 -1 -1 -1 1 1 -1 -1 -1 -1) 3 -1 -1 -1 7 {5,7,8,9,10} D circ (1 1 1 1 1 -1 1 -1 -1 -1 -1) 3 3 -1 -5 -5

6. Table IV WILLIAMSON TYPE MATRICES OF ORDER 13

Type -I (4 x 13 = 1 2 + 1 2 + 1 2 + 7

A circ (1 -1 -1 1 1 1 -1 -1 1 1 1 -1 -1) 1 -7 -3 1 5 -3 {3,5,6,7,8,10} B circ (1 1 1 -1 1 -1 -1 -1 -1 1 -1 1 1) 1 5 1 -3 -3 -7 {1,2,3,4,5,8,9,10,11,12} C circ (1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1) 5 1 1 1 1 9 {2,5,7,9,11,12} D circ (1 1 -1 1 1 -1 1 -1 1 -1 1 -1 -1) -7 1 1 1 -3 1 Sl.no Input Set Set of Williamson type Matrices Output Vector 1 {1,5,8,12} A circ (1 -1 1 1 1 -1 1 1 -1 1 1 1 -1) -3 1 1 5 -3 5 {5,6,7,8} B circ (1 1 1 1 1 -1 -1 -1 -1 1 1 1 1) 9 5 1 -3 -3 -3 {1,2,6,7,11,12} C circ (1 -1 -1 1 1 1 -1 -1 1 1 1 -1 -1) 1 -7 -3 1 5 -3 {2,4,6,9,11,12} D circ (1 1 -1 1 -1 1 -1 1 1 -1 1 -1 -1) -7 1 1 -3 1 1

Type -III (4 x 13 = 3 2 + 3 2 + 3 2 + 5

A circ(1 -1 1 -1 -1 1 -1 -1 1 -1 -1 1 -1) -7 1 5 -3 1 1 {2,3,4,6,7,9,10,11} B circ(1 1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 1) 1 -3 -3 1 1 1 {2,3,4,6,7,9,10,11} C circ(1 1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 1) 1 -3 -3 1 1 1 (8,10,11,12} D circ(1 1 1 1 1 1 1 1 -1 1 -1 -1 -1) 5 5 1 1 -3 -3A circ (1 -1 -1 1 1 -1 1 1 1 1 -1 1 1 -1 -1) -1 -5 7 3 -5 -1 -1 {2,3,4,6,7,8,9,11,12,13} B circ (1 1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 1) 1 -7 -3 1 5 -3 {1,2,3,4,5,10,11,12,13,14} C circ (1 -1 -1 -1 -1 -1 1 1 1 1 -1 -1 -1 -1 -1) 7 3 -1 -5 -5 3 3 {2,4,6,9,11,13,14} D circ (1 1 -1 1 -1 1 -1 1 1 -1 1 -1 1 -1 -1) -9 3 -1 -1 3 -5 3

Type -II (4 x 15 = 1 2 + 1 2 + 3 2 + 7 4,6,7,8,9,11,12 C circ (1

A circ (1 1 -1 1 -1 1 1 -1 -1 1 1 -1 1 -1 1) -5 -1 -1 3 -1 7 -5 {1,2,6,7,8,9,13,14} B circ (1 -1 -1 1 1 1 -1 -1 -1 -1 1 1 1 -1 -1) 3 -5 -5 -5 -1 -1 7 {3,1 1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 1 1) 3 -1 3 -1 -1 -5 -5 {7,10,12,14} D circ (1 1 1 1 1 1 1 -1 1 1 -1 1 -1 1 -1) -1 7 3 3 3 -1 3

7. WILLIAMSON TYPE MATRICES OF ORDER 17

Type -I (4 x 17 = 1 2 + 3 2 + 3 2 + 7 V.

A circ(1 -1 1 1 1 -1 1 -1 -1 -1 -1 1 -1 1 1 1 -1) -3 5 -3 1 -7 1 -3 1 {1,2,3,6,8,9,11,14,15,16} B circ (1 -1 -1 -1 1 1 -1 1 -1 -1 1 -1 1 1 -1 -1 -1) -3 -3 1 -3 5 -3 1 1 {1,2 ,4,5,6,11,12,13,15,6} C circ(1 -1 -1 1 -1 -1 -1 1 1 1 1 -1 -1 -1 1 -1 -1) 1 -3 1 -3 -3 1 5 -3 {2,6,7,8,11} D circ(1 1 -1 1 1 1 -1 -1 -1 1 1 -1 1 1 1 1 1)5A circ(1 1 -1 1 1 1 -1 1 -1 -1 1 -1 1 1 1 -1 1) -3 1 1 5 -3 1 1 1 {1,3,4,7,8,9,10,13,14,16} B circ (1 -1 1 -1 -1 1 1 -1 -1 -1 -1 1 1 -1 -1 1 -1) -3 -3 -3 1 1 5 1 -3 {1,2,3,6,8,9,11,14,15,16} C circ(1 -1 -1 -1 1 1 -1 1 -1 -1 1 -1 1 1 -1 -1 -1) -3 -3 1 -3 5 -3 1 1 {2,3,4,5,7,8,9,10,11,12,13} D circ(1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 1 1) 9 5 1 -3 -3 -3 -A circ (1 -1 1 1 -1 1 1 1 -1 -1 1 1 1 -1 1 1 -1) -3 -3 1 1 9 -7 1 5 {1,3,8,9,14,16} B circ(1 -1 1 -1 1 1 1 1 -1 -1 1 1 1 1 -1 1 -1) -3 5 -7 1 1 5 1 1 {1,2,3,4,5,12,13,14,15,16} C circ(1 -1 -1 -1 -1 -1 1 1 1 1 1 1 -1 -1 -1 -1 -1) 9 5 1 -3 -7 -3 -3 -3 {2,6,7,10,12,13,16} D circ(1 1 -1 1 1 1 -1 -1 1 1 -1 1 -1 -1 1 1 -1) -3 -7 5 1 -35A circ(1 1 1 -1 1 -1 1 1 -1 -1 1 1 -1 1 -1 1 1) -3 1 1 1 1 5 -3 1 {1,2,3,6,8,9,11,14,15,16} B circ(1 -1 -1 -1 1 1 -1 1 -1 -1 1 -1 1 1 -1 -1 -1) -3 -3 1 -3 5 -3 1 1 {1,5,6,7,8,9,10,11,12,16} C circ(1 -1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 1 -1)5

8. REMARK

Remark-1 In the above tables A, B, C are circulant matrices and D is a back circulant matrix whose 1 st row is shown.

Remark-2 Table 7 shows that there exists a Williamson type matrix corresponding to the expression 4x19 = 1 2 + 5 2 + 5 2 + 5 2 , whereas there is no Williamson matrix to the above expression. This indicates that one can find Williamson type matrices by our method, where Williamson's method fails.

The following Table 8 shows that the number of Williamson type matrices of small order obtained by our method is much greater than that of Williamson matices of the same order.

9. Global Journal of Computer Science and Technology

Volume XI Issue VIII Version I 2011

Figure 1.
Construction of four Williamson type matrices A, B, C, D Corresponding to each vector ? S' ? T' , there is a set of four Williamson type matrices (A, B, C, D) which can be obtained as follows: Find s = -t ? S ? T' ............ (4) Find the corresponding (S k1 , S k2 , S k3 ) & S k4 through the correspondences in Step IV & Step V Next find the binary vectors b k1 , b k2 , b k3 , b k4 corresponding to input sets S k1 , S k2 , S k3 & S k4 obtained in step VI by means of the correspondences in Step-III. Form circulant matrices A, B, C whose 1st rows are b k1 , b k2 , b k3 respectively and back circulant one D whose 1st row is bk4 . Then A, B, C, D are required Williamson type matrics. Step-VII Exhaustive search for A, B, C, D For exhaustive search repeat the preceding process for all possible size vector (k 1 , k 2 , k 3 ; k 4 ). Remark: We can get rid of Step II(b), Step-V and Step-VI by replacing them by the following single step to obtain S k4 . Step Use of Turnpike problem Form the set T consisting of t = (-s 1 , -s 2 . . . -s m ) satisfying (s 1 , s 2 , . . . .s m ) ? S' (constructed in Step IV) Record the correspondences t ? s ? {A, B, C} using the correspondences s ? {A, B, C} For the vector t = (?s 1 , ? s 2 ,.............. ? s m ) ? T (i) Find k 4 = (n -?n ? 2(s 1 + s 2 + .......... + s m )) / 2 (ii) Find fi = ( 4k 4 -n -s i ) / 4 where i = 1, 2, .................... m (iii) Form a set D 1 = {d 1 , d 2 , ...... d k }, di ? {1, 2, .... m} and a multiset M of differences dj -di (mod n) of every pair of distinct elements of D 1 such that (a) Differences are between 0 and m, (if a difference is <-m, then replace it by n -m).
Figure 2.
a 1 a 2 .. a n?1 a n
a n a 1 a 2 ... a n?1
called circulant matrix.
a n?1 a n a 1 ... a n?2
.. .. .. .. ..
a 2 a 3 .. .. a 1
1.4 Back circulant matrix : bcirc(a 1 , a 2 , . . . ..a n )
is the matrix
a 1 a 2 .. a n?1 a n
a 2 a 3 .. a n a 1
called back circulant matrix.
a 3 a 4 .. a 1 a 2
.. .. .. .. ..
a n a 1 .. .. a n-1
Figure 3.
then form a back circulant matrix D where first row
contains -1 at d 1 th , d 2 th , .... d k th place and +1 elsewhere.
Remark : Step-(iii) is equivalent to turnpike or
partial digest problem (vide
Figure 4. Table III
III
Subtype-II (Size Vector (4, 4, 8; 5))
Sl.no Input Set Set of Williamson type Matrices Output Vector
1 {1,5,6,10}
Figure 5. Table V
V
Type -I (4 x 15 = 1 2 + 3 2 + 5 2 + 5 2 )
Subtype-I (Size Vector (6, 10, 10; 7))
Sl.no Input Set Set of Williamson type Matrices Output Vector
1 {1,2,5,10,13,14}
Figure 6. Table VII
VII
Type -I (4 x 19 = 1 2 + 5 2 + 5 2 + 5 2 )
Subtype-I (Size Vector (8, 8, 8; 6))
Sl. Input Set Set of Williamson type Matrices Output Vector
no
2
5
3
8
10

Appendix A

Appendix A.1 May

----------e

where k 4 = k4 if k4 is odd Proof (i) In AA T e j = scalar product of 1 st row R1 of A with (j + 1) th row R j+1 of A . Let S k1 be the input set corresponding to 1 st row R1of A and j+S k1 be that corresponding to (j+1) throw R j+1 of A (where + stands for addition mod n). Let the order of the set ( j + S k1 ) -S k1 be r j . The rows R 1 and R j+1 of A differ at 2r j places. Hence the scalar product R 1 R 2 is (n -2r 2 ) -2r 2 = n -4rj= e j by definition. By the same argument we get expressions for BB T , CC T & D 1 D 1 T . Since from (4) the sum of output vectors for A, B, C, D 1 is 0, it follows that ?AA T = circ (4n, 0, 0, ----------0) A, B, C, D 1 = 4nI n Proof (ii) Consider all k 1 (k 1 -1) differences (mod n) of the set S k1 . Suppose in the multiset of differences j appears g j times j = 1, 2 , -------(n-1).

) Also j + S k1 and S k1 has g j common elements. Hence |(j + S k1 ) ? S k1 |= k 1g j =r j Also e j = n -4r j [ from ( 1

Appendix A.2 FUTURE WORK

Like Williamson's method, the present method requires great computational effort. However using genetic algorithm or some other heuristic method one can find some Williamson type matrices of higer order.

Appendix B

  1. An infinite family of Hadamard matrices of Williamson type. A L Whiteman . J. Combin, Theory ser. A 1973. 14 p. .
  2. Orthogonal Designs: Quadratic forms and Hadamard matrices, A V Geramita , Jennifer Seberry . Marcel Dekker, New York-Basel, 1979, viii. 460.
  3. The CRC Handbook of Combinational Design IV Chapter, C.J.Colbourn & J.H.Dinitz (ed.) 1996. USA: CRC Press.
  4. Handbook of combinatorial designs, C J Colbourn, & J H Dinitz (ed.) 2007. CRC Boea Raton. (Second edition)
  5. , C Koukouvinos , S Kounias Discrete , Mathematics . 1988. North-Holland: Elsevier Science Publisher. 68 p. .
  6. Seidel Orthogonal matrices with zero diagonal canad. J M Goethals , JJ . J. Math 1967. 19 p. .
  7. Construction of Williamson type matrices. J Seberry Wallis . Linear and Multilinear Algebra 1975. 3 p. .
  8. On Hadamard matrices. J Seberry Wallis . J. Combin. Theory Ser. A 1975. 18 p. .
  9. Hadamard's determinant theorem and the sum of four squares. J Williamson . Duke Math. J 1944. 11 p. .
  10. Discovery of an Hadamard matrix of order 92. L D Baumert , S W Golomb , M HallJr . Bull, Amer, Math. Soc 1962. 68 p. .
  11. Hadamard Matrices of the Williamson Type. L D Baumert , M HallJr . Math. Comp 1965. 19 p. .
  12. Hadamard matrices of orders 116 and 232. L D Baumert . Bull. Amer. Math. Soc 1966. 72 p. 237.
  13. M HallJr . Combinatorial Theory, (Blasisdell, Waltham, MA
    ) 1967.
  14. P Pevzner . Computational Molecular Biology: An Algorithmic Approach, 2000. MIT Press.
  15. Hadamard Matrices and Hadamard Design in Handbook of Combinatorial Designs, R Cragen , H Kharaghani . C.J.Colbourn and J.H.Dinitz (ed.) 2006. Boca Raton, London: Chapman & Hall. (2nd Edition)
  16. Global Journal of Computer Science and Technology Volume XI Issue VIII Version I. S Skiena , G Sundaram . Bulletin of Mathematical Biology 1994. 2011. 56 p. . (A Partial Digest Approach to Restriction Site Mapping)
  17. On the Turnpike problem, T Dakie . 2000. Simon Fraser University (PhD thesis)
  18. An Exponential Example for a Partial Digest Mapping Algorithm. Z Zhang . Journal of Computional Biology 1994. 1 (3) p. .
Notes
2.
MayProlific Generation of Williamson Type Matrices ©2011 Global Journals Inc. (US)
5.
MayProlific Generation of Williamson Type Matrices ©2011 Global Journals Inc. (US)
3
©2011 Global Journals Inc. (US)
8.
MayProlific Generation of Williamson Type Matrices ©2011 Global Journals Inc. (US)
10.
May ©2011 Global Journals Inc. (US)This page is intentionally left blank
Home 
Date: 2011-05-04