# 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.


# 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).


# 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


# 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.


# 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

# 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

# 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

# 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.


# Global Journal of Computer Science and Technology

Volume XI Issue VIII Version I 2011
![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).](image-2.png "")
a 1 a 2.. a n?1 a na n a 1a 2 ...a n?1called circulant matrix.a n?1 a na 1 ...a n?2..........a 2a 3....a 11.4 Back circulant matrix : bcirc(a 1 , a 2 , . . . ..a n )is the matrixa 1a 2.. a n?1a na 2a 3..a na 1called back circulant matrix.a 3a 4..a 1a 2..........a na 1....a n-1
then form a back circulant matrix D where first rowcontains -1 at d 1th , d 2th , .... d k th place and +1 elsewhere.Remark : Step-(iii) is equivalent to turnpike orpartial digest problem (vide
IIISubtype-II (Size Vector (4, 4, 8; 5))Sl.noInput SetSet of Williamson type MatricesOutput Vector1{1,5,6,10}
VType -I (4 x 15 = 1 2 + 3 2 + 5 2 + 5 2 )Subtype-I (Size Vector (6, 10, 10; 7))Sl.no Input SetSet of Williamson type MatricesOutput Vector1{1,2,5,10,13,14}
VIIType -I (4 x 19 = 1 2 + 5 2 + 5 2 + 5 2 )Subtype-I (Size Vector (8, 8, 8; 6))Sl.Input SetSet of Williamson type MatricesOutput Vectorno
			MayProlific Generation of Williamson Type Matrices ©2011 Global Journals Inc. (US)
			MayProlific Generation of Williamson Type Matrices ©2011 Global Journals Inc. (US)
			©2011 Global Journals Inc. (US)
			MayProlific Generation of Williamson Type Matrices ©2011 Global Journals Inc. (US)
			May ©2011 Global Journals Inc. (US)This page is intentionally left blank
		
		
			

## 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 


## 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.
			
			

				


* 
	
		Hadamard Matrices and Hadamard Design in Handbook of Combinatorial Designs
		
			RCragen
		
		
			HKharaghani
		
		C.J.Colbourn and J.H.Dinitz
		
			2006
			Chapman & Hall
			Boca Raton, London
		
	
	2nd Edition




* 
	
		Orthogonal Designs: Quadratic forms and Hadamard matrices
		
			AVGeramita
		
		
			JenniferSeberry
		
		
			460
			Marcel Dekker, New York-Basel, 1979, viii
		
	




* 
	
		Hadamard's determinant theorem and the sum of four squares
		
			JWilliamson
		
	
	
		Duke Math. J
		
			11
			
			1944
		
	




* 
	
		Discovery of an Hadamard matrix of order 92
		
			LDBaumert
		
		
			SWGolomb
		
		
			MHallJr
		
	
	
		Bull, Amer, Math. Soc
		
			68
			
			1962
		
	




* 
	
		Hadamard Matrices of the Williamson Type
		
			LDBaumert
		
		
			MHallJr
		
	
	
		Math. Comp
		
			19
			
			1965
		
	




* 
	
		
			MHallJr
		
		Combinatorial Theory
				Blasisdell, Waltham, MA
		
			1967
		
	




* 
	
		Hadamard matrices of orders 116 and 232
		
			LDBaumert
		
	
	
		Bull. Amer. Math. Soc
		
			72
			237
			1966
		
	




* 
	
		
		
			CKoukouvinos
		
		
			SKounias Discrete
		
		
			Mathematics
		
		
			1988
			Elsevier Science Publisher
			68
			
			North-Holland
		
	




* 
	
		Construction of Williamson type matrices
		
			JSeberryWallis
		
	
	
		Linear and Multilinear Algebra
		
			3
			
			1975
		
	




* 
	
		On Hadamard matrices
		
			JSeberryWallis
		
	
	
		J. Combin. Theory Ser. A
		
			18
			
			1975
		
	




* 
	
		An infinite family of Hadamard matrices of Williamson type
		
			ALWhiteman
		
	
	
		J. Combin, Theory ser. A
		
			14
			
			1973
		
	




* 
	
		Seidel Orthogonal matrices with zero diagonal canad
		
			JMGoethals
		
		
			JJ
		
	
	
		J. Math
		
			19
			
			1967
		
	




* 
	
		Handbook of combinatorial designs
				
			CJColbourn
			& JHDinitz
		
		
			CRC Boea Raton
			2007
		
	
	Second edition




* 
	
		The CRC Handbook of Combinational Design IV Chapter
		C.J.Colbourn & J.H.Dinitz
		
			1996
			CRC Press
			USA
		
	




* 
	
		On the Turnpike problem
		
			TDakie
		
		
			2000
		
		
			Simon Fraser University
		
	
	PhD thesis




* 
	
		
			PPevzner
		
		Computational Molecular Biology: An Algorithmic Approach
				
			MIT Press
			2000
		
	




* 
	
		An Exponential Example for a Partial Digest Mapping Algorithm
		
			ZZhang
		
	
	
		Journal of Computional Biology
		
			1
			3
			
			1994
		
	




* 
	
		Global Journal of Computer Science and Technology Volume XI Issue VIII Version I
		
			SSkiena
		
		
			GSundaram
		
	
	
		Bulletin of Mathematical Biology
		
			56
			
			1994. 2011
		
	
	A Partial Digest Approach to Restriction Site Mapping