New weighing matrices and orthogonal designs constructed using two sequences with zero autocorrelation function – a review
Introduction
An orthogonal design A, of order n, and type (s1,s2,…,su), denoted OD(n;s1,s2,…,su), on the commuting variables is a square matrix of order n with entries where for each occurs sk times in each row and column and such that the distinct rows are pairwise orthogonal.
In other wordswhere In is the identity matrix. It is known that the maximum number of variables in an orthogonal design is ρ(n), the Radon number, defined by ρ(n)=8c+2d, where n=2ab,b odd, and .
A weighing matrix W=W(n,k) is a square matrix with entries 0,±1 having k non-zero entries per row and column and inner product of distinct rows zero. Hence W satisfies WWT=kIn, and W is equivalent to an orthogonal design OD(n;k). The number k is called the weight of W.
Weighing matrices have long been studied because of their use in weighing experiments as first studied by Hotelling (1944) and later by Raghavarao (1971) and others Craigen (1996) and Seberry and Yamada (1992).
Given a set of sequences, the sequences , of length n the non-periodic autocorrelation function NA(s) is defined asIf Aj(z)=aj1+aj2z+⋯+ajnzn−1 is the associated polynomial of the sequence Aj, thenGiven , as above, of length n the periodic autocorrelation function PA(s) is defined, reducing i+s modulo n, as
For the results of this paper generally PAF is sufficient. However NPAF sequences imply PAF sequences exist, the NPAF sequence being padded at the end with sufficient zeros to make longer lengths. Hence NPAF can give more general results. Notation. We use the following notation throughout this paper We use ā to denote −a. means the reverse of the sequence Z, for example [X/Y] means the interleaved sequenceand [0/Y/0m] means the interleaved sequence We will say that two sequences of variables are directed if the sequences have zero autocorrelation function independently of the properties of the variables, i.e. they do not rely on commutativity to ensure zero autocorrelation. For example, {a,b} and {a,−b} are directed sequences while {a,b} and {b,−a} are not directed. X={x1,x2,…,xn} and Y={y1,y2,…,yn} are two disjoint sequences if at least one of each pair xi,yi is non-zero. Two sequences, of length n, will be said to be of type (s,t) if the sequences are composed of two variables, say a and b, and a and −a occur a total of s times and b and −b occur a total of t times. Such sequences will be used as the first rows of two circulant matrices in Theorem 5 to obtain an OD(2n;s,t). The sequences are said to be of type (0,±1) and weight w if they have a total of w non-zero elements and will be used as the first rows of two circulant matrices in Theorem 5 to obtain a W(2n,w).
Section snippets
Necessary conditions and conjectures
In this paper we concentrate on weighing matrices in orders . The first work towards this conjecture appears in Wallis (1972).
We have two theoretical necessary conditions. Theorem 1 If there is an odd, then s1+s2<2n. Also s1,s2 and s1+s2 are each the sum of two squares. Corollary 1 If there is a odd, then k<2n and k is the sum of two squares. Theorem 2 Eades sum-fill theorem An OD(2n;a,b) constructed from two circulants exists only if there is a 2×2 integer matrix P satisfying PPT=diag(a,b).Geramita and Seberry, 1979
The first asymptotic
Preliminary results
As the book of Geramita and Seberry (1979) is out of print, we quote the following theorems and lemmas and totally review the existence of weighing matrices, especially though constructed using two circulant matrices. Lemma 1 Let A and B be circulant matrices of order n and R=(rij) where rij=1 if i+j−1=n and 0 otherwise. Then A(BR)T=(BR)AT.Geramita and Seberry, 1979, Lemmas 4.21 and 4.22
The following theorem is one of the most important for construction of weighing matrices and orthogonal designs. Theorem 5 If there exist two circulant matrices A1,A2 of order n The two circulant construction; Geramita and Seberry, 1979, Theorem 4.46
Sequences with zero autocorrelation
We now consider a few constructions which allow new sequences to be constructed from those that are already known. The last two theorems are extensions of theorems used in Geramita and Seberry (1979). Other results, which are new, are inspired by Gysin and Seberry (1996). Theorem 13 Suppose X and Y are two disjoint sequences of commuting variables of length n and type (s,t) or of type (0,±1) and weight w with zero PAF or NPAF, then there are sequences of length n and type (2s,2t) or (w,w), respectively.
Existence of weighing matrices
We now review and extend the results of Geramita and Seberry (1979) for the existence of . Lemma 8 Suppose k⩽2n−1 and k=a2+b2 where a and b are integers. Then there exists a W(2n,k) for all possible k for n=3,5,7,9,11,13,15,17,19,21. All, except the W(18,9), which cannot be constructed from two circulants and the and W(54,18), which are not known constructed from two circulants, are constructed using two circulant matrices. Proof. We consider the orders individually. n=3: Table 13
Existence of orthogonal designs
Theorem 17 There exist orthogonal designs in order 2n of type: (1,9) constructed using two circulant matrices exists for lengths 9,11,17,27,29,31,33,37,41,43,47 and 51 and their multiples; (1,9) for n⩾6 (except possibly for n=9,11); (4,9) constructed using two circulant matrices exists for lengths 19 and 21 and their multiples; (4,9) for except possibly for n=9,11,13); (1,16) constructed using two circulant matrices exists for lengths 11,13,15,17,19 and 21 and their multiples; an OD(18:1,9), i.e. n=9, does not exist. (1,16)
References (24)
- Arasu, K.T., 1996. Private email communication to J. Seberry, 22...
- et al.
Circulant weighing designs
J. Combin. Des.
(1996) - Craigen, R., 1996. Weighing matrices and conference matrices. In: Colbourn, C.J., Dinitz, J.H. (Eds.), The CRC Handbook...
- Eades, P., 1977. On the existence of orthogonal designs. Ph.D. Thesis, Australian National University,...
- Eades, P., 1979. Circulant (v,k,λ) designs, Combinatorial Mathematics VII. Lecture Notes in Mathematics, vol. 829....
- et al.
On circulant weighing matrices
Ars Combin.
(1976) - Eades, P., Wallis, J.S., 1976. An infinite family of skew-weighing matrices. Combinatorial Mathematics IV. Lecture...
- et al.
Orthogonal designs
Linear Multilinear Algebra
(1975) - Geramita, A.V., Seberry, J., 1979. Orthogonal Designs: Quadratic Forms and Hadamard Matrices. Marcel Dekker, New...
- et al.
Orthogonal designs with zero diagonal
Can. J. Math.
(1976)
Multiplication of ternary complementary pairs
Australasian J. Combin.
Cited by (46)
A class of composite designs for response surface methodology
2014, Computational Statistics and Data Analysis4-regular oriented graphs with optimum skew energies
2014, European Journal of Combinatorics3-Regular digraphs with optimum skew energy
2012, Linear Algebra and Its ApplicationsOn the average complexity for the verification of compatible sequences
2011, Information Processing LettersImproving the lower bounds on inequivalent Hadamard matrices through orthogonal designs and meta-programming techniques
2010, Applied Numerical Mathematics