New weighing matrices and orthogonal designs constructed using two sequences with zero autocorrelation function – a review

Abstract

The book, Orthogonal Designs: Quadratic Forms and Hadamard Matrices, Marcel Dekker, New York-Basel, 1979, by A.V. Geramita and Jennifer Seberry, has now been out of print for almost two decades. Many of the results on weighing matrices presented therein have been greatly improved. Here we review the theory, restate some results which are no longer available and expand on the existence of many new weighing matrices and orthogonal designs of order 2n where n is odd. We give a number of new constructions for orthogonal designs. Then using number theory, linear algebra and computer searches we find new weighing matrices and orthogonal designs. We have reviewed completely the weighing matrix conjecture for orders $\text{2n,}\text{n⩽35,}\text{n}$ odd. The previously known results for weighing matrices for n⩽21 are summarized here, and new results given, leaving three unresolved cases. The results for weighing matrices for n⩾23 are presented here for the first time. For orders $\text{n,}\text{23⩽n⩽25,}\text{3}$ remain unsolved as do a further 106 cases for orders 27⩽n⩽49. We also review completely the orthogonal design conjecture for two variables in orders $\text{≡2}\text{(}\text{mod}\text{4)}$. The results for orders $\text{2n,}\text{n}$ odd, 15⩽n⩽33 being given here for the first time.

Introduction

An orthogonal design A, of order n, and type (s₁,s₂,…,s_u), denoted OD(n;s₁,s₂,…,s_u), on the commuting variables $\text{(±}\text{x}{}_1\text{,±}\text{x}{}_2\text{,…,±}\text{x}{}_{\mathrm{u}}\text{,0)}$ is a square matrix of order n with entries $\text{±}\text{x}{}_{\mathrm{k}}$ where for each $\text{k,}\text{x}{}_{\mathrm{k}}$ occurs s_k times in each row and column and such that the distinct rows are pairwise orthogonal.

In other words

$$\text{AA}{}^{\mathrm{<mtext>T</mtext>}}\text{=(s}{}_1\text{x}{}_1{}^2\text{+⋯+s}{}_{\mathrm{u}}\text{x}{}_{\mathrm{u}}{}^2\text{)I}{}_{\mathrm{n}}\text{,}$$

where I_n 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+2^d, where n=2^ab,b odd, and $\text{a=4c+d,}\text{0⩽d<4}$.

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 WW^T=kI_n, 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 $\text{l}$ sequences, the sequences $\text{A}{}_{\mathrm{j}}\text{={a}{}_{\mathrm{j1}}\text{,a}{}_{\mathrm{j2}}\text{,…,a}{}_{\mathrm{jn}}\text{},}\text{j=1,…,}\text{l}$, of length n the non-periodic autocorrelation function N_A(s) is defined as

$$\text{N}{}_{\mathrm{A}}\text{(s)=}\text{∑}\text{j=1}\text{l}\text{∑}\text{i=1}\text{n−s}\text{a}{}_{\mathrm{ji}}\text{a}{}_{\mathrm{j,i+s}}\text{,}\text{s=0,1,…,n−1.}$$

If A_j(z)=a_j1+a_j2z+⋯+a_jnzⁿ⁻¹ is the associated polynomial of the sequence A_j, then

$$\text{A(z)A(z}{}^{\mathrm{-1}}\text{)=}\text{∑}\text{j=1}\text{l}\text{∑}\text{i=1}\text{n}\text{∑}\text{k=1}\text{n}\text{a}{}_{\mathrm{ji}}\text{a}{}_{\mathrm{jk}}\text{z}{}^{\mathrm{i-k}}\text{=N}{}_{\mathrm{A}}\text{(0)+}\text{∑}\text{j=1}\text{l}\text{∑}\text{s=1}\text{n−1}\text{N}{}_{\mathrm{A}}\text{(s)(z}{}^{\mathrm{s}}\text{+z}{}^{\mathrm{-s}}\text{).}$$

Given $\text{A}{}_{\mathrm{<mtext>l</mtext>}}$, as above, of length n the periodic autocorrelation function P_A(s) is defined, reducing i+s modulo n, as

$$\text{P}{}_{\mathrm{A}}\text{(s)=}\text{∑}\text{j=1}\text{l}\text{∑}\text{i=1}\text{n}\text{a}{}_{\mathrm{ji}}\text{a}{}_{\mathrm{j,i+s}}\text{,}\text{s=0,1,…,n−1.}$$

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.

• $\text{Z}{}^{\mathrm{\ast }}$ means the reverse of the sequence Z, for example

  $$\text{Z={z}{}_1\text{,z}{}_2\text{,…,z}{}_{\mathrm{n}}\text{}}\text{and}\text{Z}{}^{\mathrm{\ast }}\text{={z}{}_{\mathrm{n}}\text{,z}{}_{\mathrm{n-1}}\text{,…,z}{}_2\text{,z}{}_1\text{}.}$$

• [X/Y] means the interleaved sequence

  $$\text{x}{}_1\text{,y}{}_1\text{,x}{}_2\text{,y}{}_2\text{,…,x}{}_{\mathrm{n}}\text{,y}{}_{\mathrm{n}}$$

  and [0/Y/0_m] means the interleaved sequence

  $$\text{0,y}{}_1\text{,0}{}_{\mathrm{m}}\text{,0,y}{}_2\text{,0}{}_{\mathrm{m}}\text{,…,0,y}{}_{\mathrm{n}}\text{,0}{}_{\mathrm{m}}\text{.}$$

• 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={x₁,x₂,…,x_n} and Y={y₁,y₂,…,y_n} are two disjoint sequences if at least one of each pair x_i,y_i 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).